【C++】中14种常见容器及特性对比（map/set/list/vector等等）

本文链接：https://blog.csdn.net/Darlingqiang/article/details/124614074

本文深入探讨了C++标准模板库(STL)中的主要容器，包括set、multiset、map、multimap、unordered_set、unordered_map、unordered_multiset、unordered_multimap、vector、list、deque、stack、queue和priority_queue。详细阐述了它们的特点、底层实现、操作复杂度及适用场景。插入、删除和查找操作在不同容器中的时间复杂度各异，从常数时间到对数时间不等。此外，还对比了数组和链表实现带来的效率差异，帮助开发者选择合适的容器以优化程序性能。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

【C++】各个容器的对比表格：

容器类型	底层实现	是否有序	键是否可重复	插入复杂度	删除复杂度	查找复杂度
set	红黑树	有序	否	O(logN)	O(logN)	O(logN)
multiset	红黑树	有序	是	O(logN)	O(logN)	O(logN)
map	红黑树	有序	否	O(logN)	O(logN)	O(logN)
multimap	红黑树	有序	是	O(logN)	O(logN)	O(logN)
unordered_set	哈希表	无序	否	O(1) 平均，O(N) 最坏	O(1) 平均，O(N) 最坏	O(1) 平均，O(N) 最坏
unordered_multiset	哈希表	无序	是	O(1) 平均，O(N) 最坏	O(1) 平均，O(N) 最坏	O(1) 平均，O(N) 最坏
unordered_map	哈希表	无序	否	O(1) 平均，O(N) 最坏	O(1) 平均，O(N) 最坏	O(1) 平均，O(N) 最坏
unordered_multimap	哈希表	无序	是	O(1) 平均，O(N) 最坏	O(1) 平均，O(N) 最坏	O(1) 平均，O(N) 最坏
vector	动态数组	无序	N/A	push_back(): O(1), insert(): O(N)	pop_back(): O(1), erase(): O(N)	O(1) 查找
list	双向链表	无序	N/A	O(1) 插入	O(1) 删除	O(N) 查找
deque	分段连续数组	无序	N/A	push_front(), push_back(): O(1), insert(): O(N)	pop_front(), pop_back(): O(1), erase(): O(N)	O(1) 查找
stack	list 或 deque 封装	无序	N/A	push(): O(1)	pop(): O(1)	top(): O(1)
queue	list 或 deque 封装	无序	N/A	push(): O(1)	pop(): O(1)	front(): O(1)
priority_queue	堆	无序	N/A	push(): O(logN)	pop(): O(logN)	top(): O(1)

主要特点对比：

红黑树实现的容器（如set、map）有序，操作复杂度为O(logN)。
哈希表实现的容器（如unordered_set、unordered_map）无序，操作平均为O(1)，最坏为O(N)。
数组或链表实现的容器（如vector、list、deque）插入、删除复杂度依赖于操作位置。
栈和队列封装于双向链表或双端队列，操作限制在两端，插入删除复杂度为O(1)。
优先队列使用堆实现，支持快速取出最大（或最小）元素，插入、删除复杂度为O(logN)。

这个表格清晰地展示了各个容器的底层实现、是否有序、键的可重复性、以及不同操作的时间复杂度，帮助理解其适用场景。

set、multiset、map、multimap
特点：底层实现是红黑树，键值有序，set 和 map 键不可重复，而 multiset 和 multimap 可重复；
操作复杂度：
插入、删除、查找都为O(logN)；
unordered_set，unordered_map，unordered_multiset，unordered_multimap
特点：底层实现是哈希表，键值无序，unordered_set 和 unordered_map 键不可重复，而另外两个可以重复；
操作复杂度：
插入、删除、查找平均为O(1)，最坏为O(N)，空间换时间；
vector
特点：底层实现是数组，动态成倍扩容；
操作复杂度：
插入：push_back()，O(1)；insert()，O(N)
删除：pop_back()，O(1)；erase()，O(N)
查找：O(1)
list
特点：底层实现双向链表；
操作复杂度：
插入：push_front()，O(1)；push_back()，O(1)；insert()，O(1)
删除：pop_front()，O(1)；pop_back()，O(1)；erase()，O(1)
查找：O(N)
deque 双端队列
特点：底层是分段连续的线性空间，它是一种具有队列和栈的性质的数据结构，其插入和删除操作限定在两端进行；
操作复杂度：
插入：push_front()，O(1)；push_back()，O(1)；insert()，O(N)
删除：pop_front()，O(1)；pop_back()，O(1)；erase()，O(N)
查找：O(1)
stack 栈
特点：底层实现一般用 list 或 deque，封闭头部即可，数据先进后出，不支持随机访问；
操作复杂度：
插入：push()，O(1)
删除：pop()，O(1)
查找（栈顶）：top()，O(1)
queue 队列
特点：底层实现一般用 list 或 deque，数据先进先出，不支持随机访问；
操作复杂度：
插入：push()，O(1)
删除：pop()，O(1)
查找（队列头）：front()，O(1)
priority_queue 优先队列
特点：底层用堆实现，队列中各个元素被赋予优先级；
操作复杂度：
插入：push()，O(logN)
删除：pop()，O(logN)
查找（取堆顶）：top()，O(1)