31、map deque list的实现原理【中高频】

list：双向链表，适用于频繁在中间 插入和删除操作。在链表中，每个元素都有 指向前后元素的指针，所以 在任何位置进行插入和删除都非常高效。

• 高效插入和删除：在链表中的插入和删除时间复杂度为 (O(1))，不需要像 vector 一样移动其他元素。

• 访问效率低：由于链表没有连续存储，不能通过索引直接访问某个元素。所以 必须从头或尾遍历，因此访问的效率低。

  

deque：双端队列，可以在头部和尾部 快速插入和删除，适合 在头尾 都需要频繁增删数据的场景

• 高效双端操作：无论是头部还是尾部插入/删除，时间复杂度均为 (O(1))。

• 支持随机访问：deque 支持通过索引 直接访问元素，但它的底层存储结构并非一个连续的内存块，而是一个存储指针的数组，里面的每个元素都是指针，指向了内存中的小块连续的内存空间。这个指针数组从中间位置开始存储指针，留下首尾两端，从而便于扩容。
  

  

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {1, 2, 3};
    dq.push_front(0);  // 在头部添加元素 0
    dq.push_back(4);   // 在尾部添加元素 4

    // 遍历并输出元素
    for (int val : dq) {
        std::cout << val << " ";
    } // 输出 0 1 2 3 4
    return 0;
}

map：键值对容器，类似于字典，它也是通过红黑树实现的，因此也是有序存储。适合需要快速查找键值对的场景，比如存储用户信息或用于配置文件读取等

• 有序存储：键值对按照键的顺序存储（所以map不能修改key的值，但可以修改value的值）

• 键唯一：每个键都是唯一的（如果想保存多个相同的键，可以用multimap）

• 查找高效：map 的查找、插入和删除操作的时间复杂度为 O(log n)。

  

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
    m[3] = "three";  // 插入键值对 (3, "three")

    // 遍历并输出键值对
    for (auto& [key, value] : m) {
        std::cout << key << ": " << value << std::endl;
    }
    return 0;
}