1. 序列容器（Sequence Containers）
存储元素的顺序与插入顺序一致，支持随机访问或顺序访问。
容器
描述
底层实现
主要特点
std::vector
动态数组
连续内存
快速随机访问，尾部插入/删除高效
std::deque
双端队列
分段连续内存
头尾插入/删除高效，支持随机访问
std::list
双向链表
链表
任意位置插入/删除高效，不支持随机访问
std::forward_list (C++11)
单向链表
链表
仅支持前向遍历，内存占用更小
std::array (C++11)
固定大小数组
连续内存
编译时确定大小，无动态内存分配
2. 关联容器（Associative Containers）
基于红黑树实现，元素按键值有序存储，查找效率高（O(log n)）。
容器
描述
是否允许重复
底层实现
std::set
有序集合
❌（唯一键）
红黑树
std::multiset
有序多重集合
✅（允许重复）
红黑树
std::map
有序键值对
❌（唯一键）
红黑树
std::multimap
有序多重键值对
✅（允许重复）
红黑树
3. 无序关联容器（Unordered Associative Containers, C++11）
基于哈希表实现，元素无序存储，平均查找效率 O(1)（最坏 O(n)）。
容器
描述
是否允许重复
底层实现
std::unordered_set
无序集合
❌（唯一键）
哈希表
std::unordered_multiset
无序多重集合
✅（允许重复）
哈希表
std::unordered_map
无序键值对
❌（唯一键）
哈希表
std::unordered_multimap
无序多重键值对
✅（允许重复）
哈希表
4. 容器适配器（Container Adapters）
基于其他容器封装，提供特定接口。
容器
描述
默认底层容器
std::stack
后进先出（LIFO）
std::deque
std::queue
先进先出（FIFO）
std::deque
std::priority_queue
优先级队列
std::vector
5. C++11 新增容器
• std::array：固定大小数组，替代C风格数组。
• std::forward_list：单向链表，比 std::list 更节省内存。
• 无序容器（unordered_set, unordered_map 等）：基于哈希表，提供更快的查找（但无序）。
总结
类别
容器
特点
序列容器
vector, deque, list, forward_list, array
顺序存储，支持随机/顺序访问
关联容器
set, multiset, map, multimap
基于红黑树，有序存储
无序容器
unordered_set, unordered_multiset, unordered_map, unordered_multimap
基于哈希表，无序存储
容器适配器
stack, queue, priority_queue
封装底层容器，提供特定接口
如何选择？
• 需要快速随机访问？ → std::vector 或 std::array
• 频繁头尾插入/删除？ → std::deque
• 需要快速查找？ → std::set（有序）或 std::unordered_set（无序）
• 需要键值对？ → std::map 或 std::unordered_map
• 内存敏感？ → std::forward_list（单向链表）
在C++11中，STL容器提供了一系列成员函数用于操作数据。以下是常见容器的核心函数及其示例，按容器分类说明：
1. 序列容器（Sequence Containers）
(1) std::vector
函数
作用
示例
push_back(val)
尾部插入元素
v.push_back(10);
pop_back()
删除尾部元素
v.pop_back();
insert(it, val)
在迭代器位置插入
v.insert(v.begin(), 5);
erase(it)
删除迭代器位置元素
v.erase(v.begin());
front() / back()
访问首/尾元素
int x = v.front();
begin() / end()
返回迭代器
auto it = v.begin();
size()
返回元素数量
int n = v.size();
clear()
清空容器
v.clear();
示例：
#include
std::vector
v.push_back(4); // v = {1, 2, 3, 4}
v.insert(v.begin() + 1, 9); // v = {1, 9, 2, 3, 4}
v.pop_back(); // v = {1, 9, 2, 3}
int first = v.front(); // first = 1
(2) std::deque
函数
作用
示例
push_front(val)
头部插入元素
d.push_front(10);
pop_front()
删除头部元素
d.pop_front();
其他同 vector
示例：
#include
std::deque
d.push_front(1); // d = {1, 2, 3}
d.pop_back(); // d = {1, 2}
(3) std::list（双向链表）
函数
作用
示例
push_front(val) / pop_front()
头插/删
l.push_front(1);
remove(val)
删除所有等于 val 的元素
l.remove(2);
unique()
删除连续重复元素
l.unique();
sort()
排序（成员函数）
l.sort();
merge(list2)
合并有序链表
l.merge(other);
示例：
#include
std::list
l.sort(); // l = {1, 2, 3}
l.remove(2); // l = {1, 3}
(4) std::forward_list（单向链表）
（仅支持单向操作，无 size() 和 back()）
函数
作用
示例
push_front(val)
头插
fl.push_front(1);
insert_after(it, val)
在迭代器后插入
fl.insert_after(fl.before_begin(), 0);
erase_after(it)
删除迭代器后元素
fl.erase_after(fl.begin());
示例：
#include
std::forward_list
fl.push_front(1); // fl = {1, 2, 3}
(5) std::array（固定大小数组）
（不支持插入/删除，但支持迭代器）
函数
作用
示例
fill(val)
填充所有元素为 val
a.fill(0);
front() / back()
访问首/尾元素
int x = a.back();
begin() / end()
迭代器
auto it = a.begin();
示例：
#include
std::array
a.fill(5); // a = {5, 5, 5}
2. 关联容器（Associative Containers）
(1) std::set / std::multiset
函数
作用
示例
insert(val)
插入元素
s.insert(4);
erase(val)
删除元素
s.erase(3);
find(val)
查找元素（返回迭代器）
auto it = s.find(2);
count(val)
统计元素出现次数
int n = s.count(1);
lower_bound(val)
返回第一个 ≥ val 的迭代器
auto it = s.lower_bound(2);
示例：
#include
std::set
s.insert(4); // s = {1, 2, 3, 4}
auto it = s.find(2); // it指向2
(2) std::map / std::multimap
函数
作用
示例
emplace(key, val)
插入键值对
m.emplace("a", 1);
erase(key)
删除键值对
m.erase("b");
find(key)
查找键
auto it = m.find("a");
at(key)
访问值（抛出异常）
int v = m.at("a");
operator[]
访问或插入值（仅 map）
m["b"] = 2;
示例：
#include
std::map
m["b"] = 2; // m = {{"a", 1}, {"b", 2}}
int x = m.at("a"); // x = 1
3. 无序容器（Unordered Containers）
(1) std::unordered_set / std::unordered_map
（接口类似关联容器，但无序）
函数
作用
示例
insert(val)
插入元素
us.insert(3);
bucket_count()
返回桶数量
int n = us.bucket_count();
load_factor()
返回负载因子
float lf = us.load_factor();
示例：
#include
std::unordered_set
us.insert(3); // us = {1, 2, 3}（顺序不确定）
4. 容器适配器（Container Adapters）
(1) std::stack
函数
作用
示例
push(val)
压栈
s.push(1);
pop()
弹栈（无返回值）
s.pop();
top()
访问栈顶
int x = s.top();
示例：
#include
std::stack
s.push(1); s.push(2); // s = [1, 2]
int top = s.top(); // top = 2
(2) std::queue
函数
作用
示例
push(val)
入队
q.push(1);
pop()
出队
q.pop();
front() / back()
访问队首/队尾
int x = q.front();
示例：
#include
std::queue
q.push(1); q.push(2); // q = [1, 2]
int front = q.front(); // front = 1
总结
• 序列容器：支持 push_back、insert、erase 等。
• 关联容器：提供 find、insert、lower_bound 等。
• 无序容器：类似关联容器，但基于哈希表。
• 适配器：stack 和 queue 限制操作（如栈只能 push/pop）。
在C++11中，STL容器本身并不直接提供 sort() 这样的通用算法，但可以通过
1. 标准算法（
(1) sort() 排序
• 支持容器：
• std::vector、std::deque、std::array（支持随机访问，可以用 std::sort）
• std::list 和 std::forward_list 有专门的成员函数 sort()（因为 std::sort 需要随机访问迭代器）
• 示例：
#include
#include
std::vector
std::sort(v.begin(), v.end()); // 升序排序
#include
std::list
l.sort(); // list 必须用成员函数 sort()
(2) find() 查找
• 支持容器：
• 所有序列容器（vector、deque、list、forward_list、array）
• 关联容器（set、map 等） 有更高效的 .find() 成员函数（O(log n)）
• 无序容器（unordered_set、unordered_map） 也有 .find()（平均 O(1)）
• 示例：
#include
#include
std::vector
auto it = std::find(v.begin(), v.end(), 3); // 返回迭代器
#include
std::set
auto it = s.find(3); // 比 std::find 更快
(3) binary_search() 二分查找
• 支持容器：
• 已排序的 vector、deque、array（必须先 sort()）
• set、map 等关联容器 本身有序，可以直接用 .count() 或 .find()
• 示例：
#include
#include
std::vector
bool found = std::binary_search(v.begin(), v.end(), 3); // 必须已排序
#include
std::set
bool found = s.count(3); // 等效于 binary_search
2. 不同容器的算法支持总结
容器
sort()
find()
binary_search()
备注
vector
✅（std::sort）
✅（std::find）
✅（需先排序）
随机访问
deque
✅（std::sort）
✅（std::find）
✅（需先排序）
随机访问
list
❌（用 list.sort()）
✅（std::find）
❌（不支持随机访问）
双向链表
forward_list
❌（用 forward_list.sort()）
✅（std::find）
❌
单向链表
array
✅（std::sort）
✅（std::find）
✅（需先排序）
固定大小
set
❌（本身有序）
✅（.find() 更快）
✅（.count()）
红黑树
map
❌（按键有序）
✅（.find()）
✅（.count()）
红黑树
unordered_set
❌（哈希表无序）
✅（.find()）
❌（无序）
哈希表
unordered_map
❌（哈希表无序）
✅（.find()）
❌（无序）
哈希表
3. 特殊成员函数
某些容器提供了专属的成员函数，比通用算法更高效：
• list / forward_list：
• sort()、merge()、reverse()、unique()
• 关联容器（set、map）：
• find()、count()、lower_bound()、upper_bound()
• 无序容器（unordered_set、unordered_map）：
• find()、count()、bucket 相关操作
4. 如何选择合适的算法？
需要排序？
• 如果是 vector/deque/array，用 std::sort。
• 如果是 list/forward_list，用 list.sort()。
• 关联容器本身有序，无需排序。
• 无序容器无法排序。
需要查找？
• 关联容器用 .find()（O(log n)）。
• 无序容器用 .find()（平均 O(1)）。
• 序列容器用 std::find（O(n)），如果已排序可以用 binary_search。
需要去重？
• 先用 sort()，再用 std::unique（适用于 vector/deque）。
• list/forward_list 可以直接用 unique() 成员函数。
• set/unordered_set 本身就去重。
5. 总结
• 通用算法（如 sort、find） 适用于序列容器（vector、deque、array）。
• 关联容器 和 无序容器 有更高效的成员函数（如 .find()）。
• 链表（list、forward_list） 必须用成员函数（如 sort()）。
•
合理选择算法能大幅提升性能，例如：
• 在 vector 上频繁查找 → 先 sort()，再用 binary_search。
• 在 unordered_map 上查找 → 直接用 .find()（比 std::find 快得多）。