C++ Containers
梳理 C++ STL 序列容器、关联容器、无序容器与容器适配器的特性、接口差异和使用方式
C++系列:第 1 篇,共 6 篇
C++ 标准库和语言特性的用法整理,以及进程间通信
容器是一些模板类的集合,其中封装的是组织数据的方法(也就是数据结构)。STL 提供有 3 类标准容器,分别是序列容器、关联容器和无序容器(哈希容器),另外还有在它们之上封装出的容器适配器
| 容器种类 | 包含的容器 | 特点 |
|---|---|---|
| 序列容器 | std::arraystd::vectorstd::dequestd::liststd::forward_list | 元素的位置与值无关,放在什么位置就位于什么位置 |
| 关联容器 | std::setstd::multisetstd::mapstd::multimap | 元素按键排序,插入时自动放到合适的位置 |
| 无序容器 | std::unordered_setstd::unordered_multisetstd::unordered_mapstd::unordered_multimap | 元素的位置由哈希函数确定,不保证顺序 |
| 容器适配器 | std::stackstd::queuestd::priority_queue | 在其他容器之上限制接口,只提供特定的访问方式 |
容器的选择
各容器的底层结构,以及访问和查找元素的复杂度
| 容器 | 底层结构 | 随机访问 | 查找 |
|---|---|---|---|
std::array | 固定长度数组 | O(1) | O(n) |
std::vector | 动态数组 | O(1) | O(n) |
std::deque | 分段连续数组 | O(1) | O(n) |
std::list | 双向链表 | 不支持 | O(n) |
std::forward_list | 单向链表 | 不支持 | O(n) |
| 关联容器 | 红黑树 | 不支持 | O(log n) |
| 无序容器 | 哈希表 | 不支持 | 平均 O(1),最坏 O(n) |
序列容器在不同位置插入和删除元素的复杂度
| 容器 | 头部增删 | 尾部增删 | 中间增删 |
|---|---|---|---|
std::array | 不支持 | 不支持 | 不支持 |
std::vector | O(n) | 均摊 O(1) | O(n) |
std::deque | O(1) | O(1) | O(n) |
std::list | O(1) | O(1) | O(1) |
std::forward_list | O(1) | 不支持 | O(1) |
关联容器和无序容器的元素位置由键决定,没有头部、尾部之分,插入和删除的复杂度与查找相同
- 链表在中间增删的 O(1) 指已经持有该位置的迭代器,找到该位置本身仍需 O(n)
- 没有特殊需求时优先使用
std::vector,连续内存对缓存友好,实际性能通常优于链表 - 需要按键查找时,不要求顺序用无序容器,需要有序遍历或范围查询用关联容器
通用接口
以下成员函数为大多数容器所共有,后文不再重复
| 成员函数 | 功能 |
|---|---|
begin() / end() | 返回指向第一个元素、最后一个元素之后一个位置的迭代器 |
cbegin() / cend() | 同上,返回的是const迭代器,不能通过它修改元素 |
rbegin() / rend() | 返回反向迭代器,用于逆序遍历(std::forward_list和无序容器没有) |
empty() | 判断容器是否为空 |
size() | 返回元素个数(std::forward_list没有) |
max_size() | 返回理论上可容纳的最大元素个数,与实现和元素类型有关 |
clear() | 移除所有元素(std::array没有) |
swap() | 交换两个同类型容器的内容 |
迭代器的能力由底层结构决定
| 迭代器类型 | 支持的操作 | 对应容器 |
|---|---|---|
| 随机访问迭代器 | ++、--、+n、-n、[] | std::array、std::vector、std::deque |
| 双向迭代器 | ++、-- | std::list、关联容器 |
| 前向迭代器 | ++ | std::forward_list、无序容器 |
std::sort要求随机访问迭代器,因此不能用于链表,链表需使用自带的sort()成员函数
序列容器
各序列容器提供的成员函数对比如下
| 成员函数 | array | vector | deque | list | forward_list | 功能 |
|---|---|---|---|---|---|---|
operator[] | ✓ | ✓ | ✓ | — | — | 按下标访问,不检查边界 |
at() | ✓ | ✓ | ✓ | — | — | 按下标访问,越界时抛出异常 |
front() | ✓ | ✓ | ✓ | ✓ | ✓ | 返回第一个元素的引用 |
back() | ✓ | ✓ | ✓ | ✓ | — | 返回最后一个元素的引用 |
data() | ✓ | ✓ | — | — | — | 返回指向底层数组的指针 |
fill() | ✓ | — | — | — | — | 把所有元素设为同一个值 |
assign() | — | ✓ | ✓ | ✓ | ✓ | 用新元素替换全部内容 |
resize() | — | ✓ | ✓ | ✓ | ✓ | 改变元素个数 |
capacity()reserve() | — | ✓ | — | — | — | 查询、预留容量 |
shrink_to_fit() | — | ✓ | ✓ | — | — | 请求释放多余的内存(非强制) |
push_back()emplace_back()pop_back() | — | ✓ | ✓ | ✓ | — | 在尾部添加、就地构造、移除元素 |
push_front()emplace_front()pop_front() | — | — | ✓ | ✓ | ✓ | 在头部添加、就地构造、移除元素 |
insert()emplace()erase() | — | ✓ | ✓ | ✓ | — | 在指定位置插入、就地构造、移除元素 |
insert_after()emplace_after()erase_after() | — | — | — | — | ✓ | 在指定位置之后插入、就地构造、移除元素 |
splice()merge()sort()reverse()unique()remove()remove_if() | — | — | — | ✓ | ✓ | 链表特有操作 |
front()、back()、pop_back()、pop_front()和operator[]都不检查容器是否为空或下标是否越界,对空容器调用是未定义行为。std::forward_list中与splice()对应的是splice_after()
std::array
定义在<array>头文件中。长度在编译期确定,不能增加或删除元素,只能修改元素的值,是对内置数组的封装,没有额外开销
1
2
3
4
5
6
7
#include <array>
std::array<double, 10> values1; // 10个元素,值未初始化
std::array<double, 10> values2{}; // 所有元素初始化为0.0
std::array<double, 10> values3{0.5, 1.0, 1.5, 2.0}; // 初始化前4个元素,其余为0.0
values2.fill(3.14); // 所有元素设为3.14
std::vector
定义在<vector>头文件中。元素存放在一段连续内存中,空间不足时会申请一块更大的内存,并把原有元素移动过去
1
2
3
4
5
6
7
8
#include <vector>
std::vector<double> values1; // 空容器
std::vector<int> primes{2, 3, 5, 7, 11, 13, 17, 19}; // 含有8个元素
std::vector<double> values2(20); // 20个元素,初始值都为0.0
std::vector<double> values3(20, 1.0); // 20个元素,初始值都为1.0
std::vector<double> values4(values3); // 拷贝另一个容器
std::vector<int> values5(primes.begin(), primes.begin() + 3); // 拷贝一段区间:2,3,5
注意圆括号与花括号的区别:std::vector<int> v(20, 1)是 20 个 1,std::vector<int> v{20, 1}是 20 和 1 两个元素
size()是实际元素个数,capacity()是不重新分配内存时最多能容纳的元素个数。已知元素个数时先reserve()可以避免多次扩容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
int main()
{
std::vector<int> values;
values.reserve(4);
for (int i = 1; i <= 6; i++)
{
values.push_back(i);
std::cout << "size: " << values.size()
<< ", capacity: " << values.capacity() << std::endl;
}
values.insert(values.begin() + 1, 10); // 1 10 2 3 4 5 6
values.erase(values.begin()); // 10 2 3 4 5 6
for (int x : values)
{
std::cout << x << ' ';
}
std::cout << std::endl;
return 0;
}
push_back()接收一个已有的对象,emplace_back()接收构造函数的参数并在容器内就地构造,可以省去一次临时对象的构造
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <string>
#include <utility>
#include <vector>
int main()
{
std::vector<std::pair<std::string, int>> items;
items.push_back({"a", 1}); // 先构造pair,再移动到容器中
items.emplace_back("b", 2); // 直接在容器中构造pair
return 0;
}
迭代器失效:std::vector扩容后,原有的迭代器、指针和引用全部失效;insert()、erase()会使操作位置及其之后的迭代器失效。遍历过程中删除元素要使用erase()的返回值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
int main()
{
std::vector<int> values{1, 2, 3, 4, 5, 6};
for (auto it = values.begin(); it != values.end();)
{
if (*it % 2 == 0)
{
it = values.erase(it); // erase返回被删除元素的下一个位置
}
else
{
++it;
}
}
// C++20起可以直接写成:std::erase_if(values, [](int x) { return x % 2 == 0; });
for (int x : values)
{
std::cout << x << ' '; // 1 3 5
}
std::cout << std::endl;
return 0;
}
std::deque
定义在<deque>头文件中。由多段连续内存组成,头部和尾部的增删都是 O(1),支持随机访问,但元素整体并不连续,因此没有data()、capacity()和reserve()
1
2
3
4
5
6
7
8
9
10
#include <deque>
std::deque<int> d1; // 空容器
std::deque<int> d2(10); // 10个元素,初始值都为0
std::deque<int> d3(10, 5); // 10个元素,初始值都为5
std::deque<int> d4{1, 2, 3};
d4.push_front(0); // 0 1 2 3
d4.push_back(4); // 0 1 2 3 4
d4.pop_front(); // 1 2 3 4
在头尾插入元素会使所有迭代器失效,但指向已有元素的指针和引用仍然有效;在中间插入或删除则全部失效
std::list
定义在<list>头文件中。以双向链表组织元素,在任何位置增删都不会移动其他元素,指向其他元素的迭代器始终有效;不支持随机访问,访问第n个元素需要从头遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <list>
int main()
{
std::list<int> a{3, 1, 2};
std::list<int> b{6, 5, 4};
a.sort();
b.sort();
a.merge(b); // 合并两个有序链表,a: 1 2 3 4 5 6,b变为空
a.remove_if([](int x) { return x > 4; }); // 1 2 3 4
a.reverse(); // 4 3 2 1
std::list<int> c{0, 0};
a.splice(a.begin(), c); // 把c的元素移到a的开头:0 0 4 3 2 1
a.unique(); // 相邻的重复元素只保留一个:0 4 3 2 1
for (int x : a)
{
std::cout << x << ' ';
}
std::cout << std::endl;
return 0;
}
std::forward_list
定义在<forward_list>头文件中。以单向链表组织元素,每个节点比std::list少一个指针,只能从前向后遍历。由于无法访问前一个节点,插入和删除都作用在指定位置之后,并提供before_begin()用于在头部操作;为节省空间不提供size()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <forward_list>
#include <iostream>
int main()
{
std::forward_list<int> values{2, 3};
values.push_front(1); // 1 2 3
values.insert_after(values.before_begin(), 0); // 0 1 2 3
values.erase_after(values.begin()); // 删除第一个元素之后的元素:0 2 3
for (int x : values)
{
std::cout << x << ' ';
}
std::cout << std::endl;
return 0;
}
关联容器
关联容器按键的大小排序存储元素,默认使用std::less升序排列
| 容器 | 说明 |
|---|---|
std::set | 定义在<set>头文件中,元素本身就是键,不能重复 |
std::multiset | 定义在<set>头文件中,元素可以重复 |
std::map | 定义在<map>头文件中,存储键值对,键不能重复 |
std::multimap | 定义在<map>头文件中,键可以重复 |
除通用接口外,4 种关联容器共有的成员函数如下
| 成员函数 | 功能 |
|---|---|
find(key) | 返回指向键等于key的元素的迭代器,没找到返回end() |
contains(key) | 判断是否存在键等于key的元素(C++20) |
count(key) | 返回键等于key的元素个数,set和map的结果只会是 0 或 1 |
lower_bound(key) | 返回指向第一个键大于或等于key的元素的迭代器 |
upper_bound(key) | 返回指向第一个键大于key的元素的迭代器 |
equal_range(key) | 返回一对迭代器,分别等价于lower_bound(key)和upper_bound(key) |
insert() | 插入元素 |
emplace() | 就地构造并插入元素 |
emplace_hint() | 同emplace(),额外提供一个表示插入位置的迭代器作为提示 |
erase() | 按迭代器、键或区间删除元素 |
extract() | 取出一个节点而不销毁元素,可用于修改键后重新插入(C++17) |
merge() | 把另一个容器中的元素转移过来(C++17) |
元素的键是只读的,不能通过迭代器修改,否则会破坏排序。插入和删除不会使指向其他元素的迭代器失效
std::map
1
2
3
4
5
6
7
#include <map>
#include <string>
std::map<std::string, int> map1; // 空容器
std::map<std::string, int> map2{ {"C++", 10}, {"Container", 20} }; // 包含2个键值对
std::map<std::string, int> map3(map2); // 拷贝另一个容器
std::map<std::string, int> map4(++map2.begin(), map2.end()); // 拷贝一段区间:{"Container", 20}
std::map在共有接口之外,还提供按键访问值的成员函数
| 成员函数 | 功能 |
|---|---|
operator[key] | 返回键对应的值的引用,键不存在时会插入一个值为默认值的元素 |
at(key) | 返回键对应的值的引用,键不存在时抛出std::out_of_range |
try_emplace(key, args...) | 键不存在时才构造并插入,键已存在时不做任何事(C++17) |
insert_or_assign(key, value) | 键不存在时插入,键已存在时覆盖其值(C++17) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <map>
#include <string>
int main()
{
std::map<std::string, int> scores{ {"Alice", 90}, {"Bob", 80} };
scores["Carol"] = 85; // 键不存在,插入
scores.insert({"Alice", 0}); // 键已存在,不插入也不修改
scores.insert_or_assign("Bob", 95); // 键已存在,覆盖
scores.try_emplace("Dave", 70); // 键不存在,插入
if (auto it = scores.find("Eve"); it == scores.end())
{
std::cout << "Eve not found" << std::endl;
}
scores.erase("Carol");
for (const auto &[name, score] : scores) // 按键升序遍历
{
std::cout << name << ": " << score << std::endl;
}
return 0;
}
输出结果:
1
2
3
4
Eve not found
Alice: 90
Bob: 95
Dave: 70
只是查询某个键是否存在时,应使用find()或contains()。scores["Eve"]会在键不存在时插入一个值为 0 的元素,并且不能用于const容器
std::set
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set>
int main()
{
std::set<int> values{3, 1, 2, 3}; // 重复的3只保留一个
auto [it, inserted] = values.insert(2); // 元素已存在,inserted为false
std::cout << std::boolalpha << inserted << std::endl;
for (int x : values)
{
std::cout << x << ' '; // 1 2 3
}
std::cout << std::endl;
return 0;
}
std::multimap 与 std::multiset
键可以重复,因此没有operator[]和at(),count()的结果可以大于 1。同一个键对应的所有元素通过equal_range()获取
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <map>
#include <string>
int main()
{
std::multimap<std::string, int> records{ {"a", 1}, {"b", 2}, {"a", 3} };
std::cout << records.count("a") << std::endl; // 2
auto [first, last] = records.equal_range("a");
for (auto it = first; it != last; ++it)
{
std::cout << it->second << ' '; // 1 3
}
std::cout << std::endl;
return 0;
}
自定义排序规则
排序规则通过模板参数指定,可以是标准库的函数对象,也可以是自定义的比较类型。两个元素互相都不”小于”对方时被视为等价,在set和map中只会保留一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <functional>
#include <iostream>
#include <set>
#include <string>
struct ByLength
{
bool operator()(const std::string &a, const std::string &b) const
{
return a.size() < b.size();
}
};
int main()
{
std::set<int, std::greater<int>> desc{1, 3, 2}; // 降序:3 2 1
std::set<std::string, ByLength> words{"ccc", "a", "bb", "dd"};
for (const auto &word : words)
{
std::cout << word << ' '; // a bb ccc,"dd"与"bb"长度相同,被视为重复
}
std::cout << std::endl;
return 0;
}
无序容器
无序容器用哈希表存储元素,查找、插入、删除的平均复杂度为 O(1),但遍历顺序不确定
| 容器 | 说明 |
|---|---|
std::unordered_set、std::unordered_multiset | 定义在<unordered_set>头文件中 |
std::unordered_map、std::unordered_multimap | 定义在<unordered_map>头文件中 |
用法与对应的关联容器基本相同,区别在于:
- 没有
lower_bound()、upper_bound(),equal_range(key)返回所有键等于key的元素构成的范围 - 迭代器是前向迭代器,没有
rbegin()、rend() - 键的类型需要支持哈希和
==比较,而不是<比较
另外提供一组与哈希表有关的成员函数
| 成员函数 | 功能 |
|---|---|
bucket_count() | 返回桶的数量 |
bucket_size(n) | 返回第n个桶中的元素个数 |
bucket(key) | 返回键key所在桶的编号 |
load_factor() | 返回负载因子,即size()与bucket_count()的比值 |
max_load_factor() | 返回或设置最大负载因子,默认为 1.0,超过后自动增加桶并重新哈希 |
rehash(n) | 把桶的数量设置为至少n,并重新哈希 |
reserve(n) | 预留至少能容纳n个元素而不触发重新哈希的桶 |
hash_function() | 返回容器使用的哈希函数对象 |
重新哈希会使所有迭代器失效,但指向元素的指针和引用仍然有效。已知元素个数时先reserve()可以避免多次重新哈希
自定义类型作为键
标准库只为内置类型、std::string等提供了std::hash,自定义类型作为键时需要提供哈希函数和==运算符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
struct Point
{
int x;
int y;
bool operator==(const Point &other) const
{
return x == other.x && y == other.y;
}
};
struct PointHash
{
std::size_t operator()(const Point &p) const noexcept
{
return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
}
};
int main()
{
std::unordered_map<Point, std::string, PointHash> names;
names[{1, 2}] = "A";
names[{3, 4}] = "B";
std::cout << names.at({1, 2}) << std::endl; // A
std::cout << names.size() << std::endl; // 2
return 0;
}
容器适配器
容器适配器在已有容器之上只暴露特定的接口,没有迭代器,不能遍历
| 适配器 | 默认底层容器 | 特点 | 主要成员函数 |
|---|---|---|---|
std::stack | std::deque | 后进先出 | push()pop()top() |
std::queue | std::deque | 先进先出 | push()pop()front()back() |
std::priority_queue | std::vector | 每次取出优先级最高的元素 | push()pop()top() |
std::stack定义在<stack>头文件中,std::queue和std::priority_queue定义在<queue>头文件中
pop()只移除元素,不返回值,需要先用top()或front()取得元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
int main()
{
std::stack<int> stack;
stack.push(1);
stack.push(2);
std::cout << stack.top() << std::endl; // 2
std::queue<int> queue;
queue.push(1);
queue.push(2);
std::cout << queue.front() << std::endl; // 1
std::priority_queue<int> max_heap; // 默认为大顶堆
for (int x : {3, 1, 2})
{
max_heap.push(x);
}
std::cout << max_heap.top() << std::endl; // 3
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; // 小顶堆
for (int x : {3, 1, 2})
{
min_heap.push(x);
}
std::cout << min_heap.top() << std::endl; // 1
return 0;
}
