概览

C++标准模板库（STL）提供了多种容器，主要有以下几类：

一、序列容器

1. std::vector：

   • 动态数组，支持快速随机访问。可以在尾部高效地添加和删除元素，但在中间插入和删除元素可能比较耗时，因为可能需要移动大量元素。

2. std::deque：

   • 双端队列，支持在两端高效地添加和删除元素，也支持随机访问，但随机访问的性能通常不如vector。

3. std::list：

   • 双向链表，在任意位置插入和删除元素都非常高效，但不支持随机访问。

4. std::forward_list：

   • 单向链表，相比std::list更节省空间，只支持单向遍历，在一些特定场景下性能更好。

5. std::array

   静态数组

二、关联容器

1. std::set和std::multiset：

   • 基于红黑树实现的集合，元素是有序的，不允许重复元素（std::set）或允许重复元素（std::multiset）。

   • 查找、插入和删除操作的时间复杂度为对数时间。

2. std::map和std::multimap：

   • 基于红黑树实现的关联数组，元素是键值对，键是唯一的（std::map）或可以重复（std::multimap）。

   • 查找、插入和删除操作的时间复杂度为对数时间。

3. std::unordered_set和std::unordered_multiset：

   • 基于哈希表实现的集合，元素是无序的，不允许重复元素（std::unordered_set）或允许重复元素（std::unordered_multiset）。

   • 平均情况下查找、插入和删除操作的时间复杂度为常数时间，但在最坏情况下可能退化为线性时间。

4. std::unordered_map和std::unordered_multimap：

   • 基于哈希表实现的关联数组，元素是键值对，键是唯一的（std::unordered_map）或可以重复（std::unordered_multimap）。

   • 平均情况下查找、插入和删除操作的时间复杂度为常数时间，但在最坏情况下可能退化为线性时间。

三、容器适配器

1. std::stack：

   • 栈，后进先出（LIFO）的数据结构。

2. std::queue：

   • 队列，先进先出（FIFO）的数据结构。

3. std::priority_queue：

   • 优先队列，元素按照优先级排序，优先级高的元素先出队。