C++中std::map、std::list和std::deque的底层实现是怎样的？

1.std::map

·它的底层是红黑树，即一颗自平衡的二叉搜索树；

·容器内部不允许有重复的键值；

·容器内的键值排序是有序的，默认是按照键值从小到大排序；

·它删除、插入和查找操作的时间复杂度都是O(log n)；

·迭代器是有序的。

2.std::list

·它的底层是双向链表，提供高校的插入和删除操作。每一个节点都维护上一个和下一个节点的指针；

·不支持访问随机元素，只能顺序访问；

·插入和删除操作的时间复杂度是O(1)，但访问随机元素的时间复杂度可能是O(n)；

·虽然容器中元素的存储空间是不连续的，但其迭代器依然有顺序。

3.std::deque

·它的底层是动态数组，支持在头部和尾部高效的插入或删除元素，以及访问随机元素；

·访问随机元素的时间复杂度是O(1)，在容器中间插入或删除元素的时间复杂度是O(n)。