STL

STL	类型	名称	底层实现	特性
vector	顺序型容器	变长数组	数组	O(1)查找O(n)插入
list	顺序型容器	链表	双向链表	O(n)查找O(1)插入
deque	顺序型容器	双端队列	类似二维数组	由若干段大小相等的连续内存组成，不同段之间可能不连续，数组中每个节点都指向一段内存
map	有序关联型容器	映射	红黑树	按照key值排序，key不重复
mutimap	有序关联型容器	多重映射	红黑树	按照key值排序，key可重复
set	有序关联型容器	集合	红黑树	按照key值排序，key不重复
mutiset	有序关联型容器	多重集合	红黑树	按照key值排序，key可重复
unordered_map	无序关联型容器	无序映射	哈希表	不排序，用链表法解决哈希冲突（哈希桶）
stack	容器适配器	栈	deque	先进后出
queue	容器适配器	队列	deque	先进先出

• 容器支持迭代器，容器适配器不支持迭代器。

• map中的基本元素就是对组pair。

• pair是用一个结构体实现的，结构体主要的两个成员变量first和second，分别存储两个数据。

• map中的pair第一个元素为key(键值)，起索引作用，就相当于数组下标，第二个元素为value(实值)。map所有元素会根据键值大小自动排序