浅谈：C++STL容器

C++STL容器分为序列式容器、关联式容器、无序关联式容器，依次介绍如下：

1、序列式容器

（1）vector（动态数组）

特点：在内存中存储空间连续，因此支持时间复杂度为O(1)的随机访问，但插入删除操作复杂度为O(n);

常用操作：push_back()、pop_back()

（2）list（双向链表）

特点：插入删除复杂度为O(1)，支持头插和尾插，不支持随机访问；

常用操作：insert()、erase()

forward_list：单向链表，不常用；

（3）deque（双端队列）

特点：结合数组与链表优势，底层实现由多个分段连续的内存空间组成，近似随机访问，同时支持高效的头尾插入删除操作，

中间插入删除操作仍然效率较低；

常用操作：push_back()、pop_back()、push_front()、pop_front()

2、关联式容器（有序）

（1）set（集合）

特点：存储唯一元素的容器，自动排序，基于红黑树实现，查找、插入、删除复杂度为O(logn)；

multiset：多重集合，允许元素重复；

常用操作：insert()、erase()；迭代器：find()；

（2）map（映射/字典）

特点：存储键值对，按键排序，键唯一，基于红黑树实现，查找、插入、删除复杂度为O(logn)；

multimap：多重映射，允许键重复；

常用操作：map_name["key"] = value;

3、无序关联式容器

unordered_set（无序集合）、unordered_map（无序映射）

特点：基于哈希表实现，元素无序，查找、插入、删除操作复杂度最好O(1)，最坏O(n)，哈希函数计算完入桶，

桶中数据结构通常为来链表或红黑树；