STL容器分类概览

序列容器：

• vector：动态数组
• deque：双端队列
• list：双向链表
• forward_list：单向链表
• array：固定大小数组
• string：动态字符数组

关联容器：基于键值或排序存储，快速查找。

• set/multiset：有序集合
• map/multimap：有序键值对
• unordered_set/unordered_multiset：无序集合
• unordered_map/unordered_multimap：无序键值对

容器适配器：基于其他容器实现的特定接口。

• stack：栈（LIFO）
• queue：队列（FIFO）
• priority_queue：优先队列

新手面临的挑战

对于新手而言，要记住这么多的容器类型已经是难事，而别说挑选合适的类型去使用了。

STL容器全面总结

今天我就来给你总结一下STL中的这些容器。

vector —— 最常用的序列容器

在这些容器中vector一定是使用最频繁的那一个。

它的底层是一个动态数组。

它有随机访问非常快，尾部插入/删除效率高，中间插入/删除较慢，因为需要移动元素。

所以适用于需要随机访问，数据量较小，数据主要在尾部增删的场景中。

如果频繁在头部或中间插入/删除数据，会导致性能瓶颈。

string —— 专为字符串优化的容器

string虽然属于非典型容器，但常作为序列容器使用。

它的底层是一个动态字符数组，专门用于存储字符序列，支持字符串操作。

和vector一样，它的随机访问快，尾部操作高效，中间插入/删除较慢。

适用于字符串处理的场景。

如果需要频繁拼接小字符串（如str += “x”），会导致性能低下。

map —— 有序键值对容器

map的底层结构是一个红黑树。

它按键值对存储，查找、插入、删除的效率非常高。

非常适合于需要根据唯一的键快速查找对应值的场景中。

但是当数据量很小时，简单数组或线性查找可能更快，因为 MAP 的红黑树维护本身有一定开销。

unordered_map —— 哈希表实现的无序映射

unordered_map的底层结构是一个哈希表。

它也按键值对存储，键唯一但无序。

在理想情况下，因为unordered_map 使用哈希函数将键映射到唯一的存储位置，使得查找、插入、删除操作只需常数时间。

它非常适合追求快速查找（如缓存、词频统计）的场景中。

然而如果哈希函数设计不佳或键分布不均匀（例如大量键映射到同一桶），查找/插入性能可能会退化。

set —— 有序唯一值集合

set底层结构也是一个红黑树。

它会存储唯一值，查找、插入、删除时间复杂度是O(log n) 【大 O 对数 n】。

它适用于需要去重且保持有序（如唯一ID集合）的场景中。

有些可能会误以为set比unordered_set更快，但对于大数据量unordered_set 通常更快；小数据量下，set 可能因简单结构更高效。

unordered_set —— 快速去重的哈希集合

unordered_set和unordered_map一样底层结构是一个哈希表。

主要用于快速去重（如检查元素是否存在），不需要排序的场景。

deque —— 双端队列

deque底层结构是一个分块数组。

它的头尾插入/删除快，中间插入/删除较慢。

随机访问较快，但稍慢于vector。

所以适用于频繁头尾增删的场景中。

list —— 双向链表

list底层是一个双向链表。

它的插入/删除快，无法支持高效的随机访问，因为每个节点需要存指针，内存开销较大。

适用于频繁插入/删除，不需要随机访问的场景中，例如动态列表。

很多程序员在使用List时会忽略内存碎片问题以及对list进行随机访问。

stack —— 后进先出栈

stack底层结构默认基于deque，支持后进先出。

适用于后进先出场景（如函数调用栈、表达式求值）的场景中。

queue —— 先进先出队列

queue底层结构默认基于deque，支持先进先出。

适用先进先出（如任务队列）的场景中。

priority_queue —— 优先级队列

priority_queue底层结构基于vector，默认使用最大堆。

它会自动按优先级排序，非常适用于优先级调度的场景中。

array —— 固定大小数组

array底层是一个固定大小的连续数组。

它的大小在编译期确定，不可动态调整。

随机访问快，内存效率高，无动态分配开销，非常适合固定大小的数据（如小型矩阵）中使用。

array常被很多新手程序员认为可以动态扩展的。

multimap 与 multiset

multimap底层也是一个红黑树，它允许重复键，适合于需要重复键的场景中。

multiset底层也是红黑树，它存储重复值，适用于存在重复元素且保持有序的场景中。

forward_list —— 轻量级单向链表

forward_list应该是所有容器中最少被使用的，有些C++程序员甚至不知道它的存在。

它的底层是一个单向链表。

它插入/删除快，单向遍历无随机访问，也因为它只是前向指针，所以内存开销低。

它比较适合内存敏感场景，例如嵌入式开发，或者仅需要单向遍历和频繁插入/删除的场景中。

容器选择总结

做一个总结：

如果需要高频随机访问选vector/array，需要高频头尾操作选deque，需要高频插入/删除选list/forward_list。

快速查找用unordered_map/unordered_set，需要排序用map/set。

重复键值用multimap/multiset，优先级用priority_queue。

怎么样，你学懵了吗？