C++ STL 容器（Containers）详细指南

1. 功能说明

本指南基于 stl_containers.cpp 文件，详细介绍了 C++ 标准模板库（STL）中各种容器的使用方法和特性，包括：

  • 序列容器：vector、list、deque、array
  • 容器适配器：stack、queue、priority_queue
  • 关联容器：set、multiset、map、multimap
  • 无序关联容器：unordered_set、unordered_map
  • 元组和对：pair、tuple

每个容器都有其特定的用途和性能特点，本指南将详细介绍它们的使用方法、优缺点以及适用场景。

2. 代码解析

2.1 序列容器

2.1.1 std::vector（动态数组）

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
// 创建并初始化vector
std::vector<int> vec = {1, 2, 3, 4, 5};
// 在末尾添加元素
vec.push_back(6);
// 插入元素
vec.insert(vec.begin() + 2, 100);

std::cout << "Vector元素: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << "\n大小: " << vec.size() << std::endl;
std::cout << "容量: " << vec.capacity() << std::endl;
std::cout << "是否为空: " << (vec.empty() ? "是" : "否") << std::endl;

// 删除元素
vec.erase(vec.begin() + 2);
std::cout << "删除元素后: ";
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 清空vector
vec.clear();
std::cout << "清空后大小: " << vec.size() << std::endl;

解析：

  • std::vector 是最常用的序列容器，底层实现为动态数组
  • 支持随机访问，时间复杂度为 O(1)
  • 在末尾添加和删除元素的时间复杂度为均摊 O(1)
  • 在中间插入和删除元素的时间复杂度为 O(n)
  • 自动管理内存，会根据需要扩容（通常是翻倍）
  • size() 返回当前元素个数，capacity() 返回当前容量

2.1.2 std::list（双向链表）

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
// 创建并初始化list
std::list<int> lst = {10, 20, 30};
// 在头部添加元素
lst.push_front(5);
// 在尾部添加元素
lst.push_back(40);
// 在指定位置插入元素
auto it = lst.begin();
++it; // 移动到第二个元素
lst.insert(it, 15);

std::cout << "List元素: ";
for (int x : lst) {
    std::cout << x << " ";
}
std::cout << "\n大小: " << lst.size() << std::endl;

// 删除元素
lst.remove(20); // 删除所有值为20的元素
std::cout << "删除元素后: ";
for (int x : lst) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 排序
lst.sort();
std::cout << "排序后: ";
for (int x : lst) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

  • std::list 是双向链表，每个节点包含数据和前后指针
  • 不支持随机访问，访问元素的时间复杂度为 O(n)
  • 在任意位置插入和删除元素的时间复杂度为 O(1)（需要先找到位置）
  • 内存开销较大，每个元素需要额外的指针空间
  • 提供了很多成员函数，如 sort()、remove()、unique() 等

2.1.3 std::deque（双端队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 创建并初始化deque
std::deque<int> dq = {1, 2, 3};
// 在头部添加元素
dq.push_front(0);
// 在尾部添加元素
dq.push_back(4);

std::cout << "Deque元素: ";
for (int x : dq) {
    std::cout << x << " ";
}
std::cout << "\n大小: " << dq.size() << std::endl;

// 删除头部和尾部元素
dq.pop_front();
dq.pop_back();
std::cout << "删除头尾后: ";
for (int x : dq) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

  • std::deque 是双端队列，支持在两端高效插入和删除
  • 支持随机访问，时间复杂度为 O(1)
  • 在两端插入和删除元素的时间复杂度为 O(1)
  • 内存布局为分段连续，内部使用多个缓冲区
  • 适用于需要在两端频繁操作的场景

2.1.4 std::array（固定大小数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 创建array（固定大小）
std::array<int, 5> arr = {1, 2, 3, 4, 5};

std::cout << "Array元素: ";
for (int x : arr) {
    std::cout << x << " ";
}
std::cout << "\n大小: " << arr.size() << std::endl;
std::cout << "是否为空: " << (arr.empty() ? "是" : "否") << std::endl;

// 访问元素
std::cout << "第一个元素: " << arr.front() << std::endl;
std::cout << "最后一个元素: " << arr.back() << std::endl;
std::cout << "索引2的元素: " << arr[2] << std::endl;

解析：

  • std::array 是固定大小的数组，在编译时确定大小
  • 支持随机访问，时间复杂度为 O(1)
  • 内存分配在栈上，效率高
  • 提供了与容器一致的接口，如 size()、empty()、front()、back() 等
  • 适用于需要固定大小数组且希望使用容器接口的场景

2.2 容器适配器

2.2.1 std::queue（队列）

1
2
3
4
5
6
7
8
9
10
11
12
13
// 创建queue
std::queue<int> q;
// 入队
q.push(1);
q.push(2);
q.push(3);

std::cout << "Queue元素（FIFO）: ";
while (!q.empty()) {
    std::cout << q.front() << " "; // 访问队首元素
    q.pop(); // 出队
}
std::cout << std::endl;

解析：

  • std::queue 是队列适配器，基于 deque 实现
  • 遵循先进先出（FIFO）原则
  • 只允许在队尾插入，在队首删除
  • 不支持随机访问，只能访问队首元素

2.2.2 std::stack（栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
// 创建stack
std::stack<int> st;
// 入栈
st.push(1);
st.push(2);
st.push(3);

std::cout << "Stack元素（LIFO）: ";
while (!st.empty()) {
    std::cout << st.top() << " "; // 访问栈顶元素
    st.pop(); // 出栈
}
std::cout << std::endl;

解析：

  • std::stack 是栈适配器，基于 deque 实现
  • 遵循后进先出（LIFO）原则
  • 只允许在栈顶插入和删除
  • 不支持随机访问，只能访问栈顶元素

2.2.3 std::priority_queue（优先队列）

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
// 创建优先队列（默认是最大堆）
std::priority_queue<int> pq;
// 入队
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);

std::cout << "优先队列元素（从大到小）: ";
while (!pq.empty()) {
    std::cout << pq.top() << " "; // 访问优先级最高的元素
    pq.pop(); // 出队
}
std::cout << std::endl;

// 创建最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(30);
min_pq.push(10);
min_pq.push(50);
min_pq.push(20);

std::cout << "最小堆元素（从小到大）: ";
while (!min_pq.empty()) {
    std::cout << min_pq.top() << " ";
    min_pq.pop();
}
std::cout << std::endl;

解析：

  • std::priority_queue 是优先队列适配器，默认基于 vector 实现，使用最大堆
  • 元素按照优先级自动排序，默认情况下最大元素优先级最高
  • 可以通过第三个模板参数自定义比较方式，如使用 std::greater<int> 实现最小堆
  • 插入和删除操作的时间复杂度为 O(log n)
  • 适用于需要自动排序的场景，如任务调度

2.3 关联容器

2.3.1 std::set（有序集合）

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
// 创建并初始化set（自动排序，去重）
std::set<int> s = {5, 2, 8, 1, 9, 2, 5};
// 插入元素
s.insert(7);

std::cout << "Set元素（有序，唯一）: ";
for (int x : s) {
    std::cout << x << " ";
}
std::cout << "\n大小: " << s.size() << std::endl;
std::cout << "是否包含5: " << (s.count(5) ? "是" : "否") << std::endl;

// 查找元素
auto find_it = s.find(8);
if (find_it != s.end()) {
    std::cout << "找到元素: " << *find_it << std::endl;
}

// 删除元素
s.erase(5);
std::cout << "删除5后: ";
for (int x : s) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

  • std::set 是有序集合，基于红黑树实现
  • 元素自动排序，且不允许重复
  • 插入、删除和查找操作的时间复杂度为 O(log n)
  • 适用于需要有序且无重复元素的场景
  • 不支持通过迭代器修改元素，因为这会破坏排序

2.3.2 std::multiset（有序多重集合）

1
2
3
4
5
6
7
8
// 创建并初始化multiset（自动排序，允许重复）
std::multiset<int> ms = {5, 2, 8, 1, 9, 2, 5};

std::cout << "Multiset元素（有序，允许重复）: ";
for (int x : ms) {
    std::cout << x << " ";
}
std::cout << "\n5的数量: " << ms.count(5) << std::endl;

解析：

  • std::multiset 是有序多重集合，基于红黑树实现
  • 元素自动排序，但允许重复
  • 插入、删除和查找操作的时间复杂度为 O(log n)
  • 适用于需要有序且允许重复元素的场景

2.3.3 std::map（有序映射）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 创建map
std::map<std::string, int> m;
// 插入键值对
m["apple"] = 5;
m["banana"] = 3;
m["cherry"] = 8;
m.insert({"date", 2});

std::cout << "Map元素（键值对）:" << std::endl;
for (const auto& pair : m) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}
std::cout << "banana的值: " << m["banana"] << std::endl;

// 查找元素
auto map_it = m.find("cherry");
if (map_it != m.end()) {
    std::cout << "找到键: " << map_it->first << ", 值: " << map_it->second << std::endl;
}

解析：

  • std::map 是有序映射，基于红黑树实现
  • 存储键值对，键自动排序，且不允许重复
  • 插入、删除和查找操作的时间复杂度为 O(log n)
  • 可以通过键快速查找对应的值
  • 适用于需要键值对且键有序的场景

2.3.4 std::multimap（有序多重映射）

1
2
3
4
5
6
7
8
9
10
11
// 创建multimap（允许重复键）
std::multimap<std::string, int> mm;
// 插入键值对
mm.insert({"fruit", 1});
mm.insert({"fruit", 2});
mm.insert({"vegetable", 3});

std::cout << "Multimap元素:" << std::endl;
for (const auto& pair : mm) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

解析：

  • std::multimap 是有序多重映射，基于红黑树实现
  • 存储键值对，键自动排序，但允许重复
  • 插入、删除和查找操作的时间复杂度为 O(log n)
  • 适用于需要键值对且允许重复键的场景

2.4 无序关联容器

2.4.1 std::unordered_set（无序集合）

1
2
3
4
5
6
7
8
9
// 创建并初始化unordered_set（无序，去重，哈希表实现）
std::unordered_set<int> us = {5, 2, 8, 1, 9, 2, 5};

std::cout << "Unordered set元素（无序，唯一）: ";
for (int x : us) {
    std::cout << x << " ";
}
std::cout << "\n大小: " << us.size() << std::endl;
std::cout << "是否包含3: " << (us.count(3) ? "是" : "否") << std::endl;

解析：

  • std::unordered_set 是无序集合，基于哈希表实现
  • 元素无序，且不允许重复
  • 插入、删除和查找操作的平均时间复杂度为 O(1)，最坏情况为 O(n)
  • 适用于需要快速查找且不关心顺序的场景
  • 内存开销较大，需要存储哈希表结构

2.4.2 std::unordered_map（无序映射）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 创建unordered_map（无序，哈希表实现）
std::unordered_map<std::string, int> um;
// 插入键值对
um["one"] = 1;
um["two"] = 2;
um["three"] = 3;

std::cout << "Unordered map元素（无序）:" << std::endl;
for (const auto& pair : um) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

// 查看桶信息
std::cout << "桶数: " << um.bucket_count() << std::endl;
std::cout << "最大桶数: " << um.max_bucket_count() << std::endl;

解析：

  • std::unordered_map 是无序映射，基于哈希表实现
  • 存储键值对，键无序，且不允许重复
  • 插入、删除和查找操作的平均时间复杂度为 O(1)，最坏情况为 O(n)
  • 适用于需要快速查找键值对且不关心键顺序的场景
  • 内存开销较大，需要存储哈希表结构

2.5 元组和对

2.5.1 std::pair（键值对）

1
2
3
4
5
6
7
8
// 创建pair
std::pair<std::string, int> myPair("age", 25);
// 访问pair元素
std::cout << "Pair: " << myPair.first << " = " << myPair.second << std::endl;

// 使用make_pair创建pair
auto anotherPair = std::make_pair("height", 180);
std::cout << "Another pair: " << anotherPair.first << " = " << anotherPair.second << std::endl;

解析：

  • std::pair 是模板类，用于存储两个不同类型的值
  • 可以通过 first 和 second 成员访问两个值
  • 常用于返回两个值的函数，或作为 map 的元素类型
  • std::make_pair 函数可以自动推导类型创建 pair

2.5.2 std::tuple（元组）

1
2
3
4
5
6
7
8
9
10
11
12
// 创建tuple
std::tuple<std::string, int, double> myTuple("John", 30, 3.14);
// 访问tuple元素（通过索引）
std::cout << "Tuple: " << std::get<0>(myTuple) << ", " 
          << std::get<1>(myTuple) << ", " 
          << std::get<2>(myTuple) << std::endl;

// 使用make_tuple创建tuple
auto anotherTuple = std::make_tuple("Alice", 25, 2.718);
// 使用结构化绑定（C++17特性）
auto [name, age, value] = anotherTuple;
std::cout << "Another tuple: " << name << ", " << age << ", " << value << std::endl;

解析：

  • std::tuple 是模板类，用于存储多个不同类型的值
  • 可以通过 std::get<Index>(tuple) 访问指定索引的元素
  • std::make_tuple 函数可以自动推导类型创建 tuple
  • C++17 引入了结构化绑定，可以更方便地访问 tuple 元素
  • 适用于需要返回多个值的函数，或存储不同类型的值

3. 编译和运行说明

3.1 编译命令

使用以下命令编译 stl_containers.cpp 文件：

1
g++ -std=c++11 -fexec-charset=GBK -o stl_containers stl_containers.cpp

参数说明：

  • -std=c++11：使用 C++11 标准
  • -fexec-charset=GBK：确保输出的中文字符正确显示
  • -o stl_containers：指定输出可执行文件名为 stl_containers

3.2 运行命令

编译成功后，使用以下命令运行程序：

1
2
./stl_containers  # Linux/macOS
.\stl_containers.exe  # Windows

3.3 预期输出

运行程序后，您将看到类似以下的输出：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
=== 1. std::vector（动态数组）===
Vector元素: 1 2 100 3 4 5 6
大小: 7
容量: 10
是否为空: 否
删除元素后: 1 2 3 4 5 6
清空后大小: 0

=== 2. std::list（双向链表）===
List元素: 5 15 10 20 30 40
大小: 6
删除元素后: 5 15 10 30 40
排序后: 5 10 15 30 40

=== 3. std::deque（双端队列）===
Deque元素: 0 1 2 3 4
大小: 5
删除头尾后: 1 2 3

=== 4. std::queue（队列）===
Queue元素（FIFO）: 1 2 3 

=== 5. std::stack（栈）===
Stack元素（LIFO）: 3 2 1

=== 6. std::priority_queue（优先队列）===
优先队列元素（从大到小）: 50 30 20 10
最小堆元素（从小到大）: 10 20 30 50

=== 7. std::set（有序集合）===
Set元素（有序，唯一）: 1 2 5 7 8 9
大小: 6
是否包含5: 是
找到元素: 8
删除5后: 1 2 7 8 9

=== 8. std::multiset（有序多重集合）===
Multiset元素（有序，允许重复）: 1 2 2 5 5 8 9
5的数量: 2

=== 9. std::map（有序映射）===
Map元素（键值对）:
apple: 5
banana: 3
cherry: 8
date: 2
banana的值: 3
找到键: cherry, 值: 8

=== 10. std::multimap（有序多重映射）===
Multimap元素:
fruit: 1
fruit: 2
vegetable: 3

=== 11. std::unordered_set（无序集合）===
Unordered set元素（无序，唯一）: 9 1 8 2 5
大小: 5
是否包含3: 否

=== 12. std::unordered_map（无序映射）===
Unordered map元素（无序）:
three: 3
two: 2
one: 1
最大桶数: 164703072086692425

=== 13. std::pair（键值对）===
Pair: age = 25
Another pair: height = 180

=== 14. std::tuple（元组）===
Tuple: John, 30, 3.14
Another tuple: Alice, 25, 2.718

=== 15. std::array（固定大小数组）===
Array元素: 1 2 3 4 5
大小: 5
是否为空: 否
第一个元素: 1
最后一个元素: 5
索引2的元素: 3

4. 技术要点

4.1 容器选择指南

容器类型 底层实现 随机访问 插入/删除（头部） 插入/删除（中间） 插入/删除（尾部） 查找 排序 适用场景
vector 动态数组 O(1) O(n) O(n) 均摊O(1) O(n) O(n log n) 需要随机访问，主要在尾部操作
list 双向链表 O(n) O(1) O(1) O(1) O(n) O(n log n) 需要频繁在任意位置插入删除
deque 分段连续 O(1) O(1) O(n) O(1) O(n) O(n log n) 需要在两端频繁操作
array 固定数组 O(1) O(n) O(n) O(n) O(n) O(n log n) 固定大小，需要栈分配
stack deque 不支持 不支持 不支持 O(1) 不支持 不支持 后进先出操作
queue deque 不支持 O(1) 不支持 O(1) 不支持 不支持 先进先出操作
priority_queue vector 不支持 不支持 不支持 O(log n) 不支持 自动排序 优先级操作
set 红黑树 不支持 O(log n) O(log n) O(log n) O(log n) 自动排序 有序无重复元素
multiset 红黑树 不支持 O(log n) O(log n) O(log n) O(log n) 自动排序 有序允许重复元素
map 红黑树 不支持 O(log n) O(log n) O(log n) O(log n) 自动排序 有序键值对
multimap 红黑树 不支持 O(log n) O(log n) O(log n) O(log n) 自动排序 有序允许多重复键
unordered_set 哈希表 不支持 平均O(1) 平均O(1) 平均O(1) 平均O(1) 不支持 快速查找无重复元素
unordered_map 哈希表 不支持 平均O(1) 平均O(1) 平均O(1) 平均O(1) 不支持 快速查找键值对

4.2 迭代器

  • 迭代器：是一种抽象的设计概念，提供了一种方法来访问容器中的元素，而不暴露容器的底层表示
  • 迭代器类型：
    • InputIterator：只读，只能单向移动
    • OutputIterator：只写，只能单向移动
    • ForwardIterator：可读可写，只能单向移动
    • BidirectionalIterator：可读可写，可双向移动
    • RandomAccessIterator：可读可写，可随机访问
  • 迭代器操作：
    • ++it：移动到下一个元素
    • --it：移动到上一个元素（双向及以上）
    • it + n：移动到n个元素之后（随机访问）
    • *it：访问当前元素
    • it->：访问当前元素的成员

4.3 内存管理

  • 容器的内存分配：
    • vector：动态分配，当容量不足时会重新分配更大的内存
    • list：每个节点单独分配内存
    • deque：分段分配内存
    • array：在栈上分配内存（如果是局部变量）
    • 关联容器：通常使用动态内存分配
  • 内存优化：
    • 对于 vector，可以使用 reserve() 预分配内存，减少重新分配
    • 对于频繁插入删除的场景，优先使用 list 或 deque
    • 对于小而固定大小的数组，使用 array 可以提高性能

4.4 线程安全性

  • STL容器的线程安全性：
    • 多个线程同时读取是安全的
    • 多个线程同时写入是不安全的
    • 一个线程写入，其他线程读取是不安全的
  • 线程安全的使用：
    • 使用互斥锁保护容器访问
    • 考虑使用 C++11 中的并发容器
    • 对于只读操作，可以共享容器；对于读写操作，使用同步机制

4.5 自定义类型的使用

  • 在容器中使用自定义类型：
    • 对于 set、map 等有序容器，需要定义 < 运算符
    • 对于 unordered_set、unordered_map 等无序容器，需要定义哈希函数和 == 运算符
    • 对于所有容器，自定义类型应该有适当的拷贝构造函数和赋值运算符
  • 示例：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Person {
    public:
        std::string name;
        int age;
        
        bool operator<(const Person& other) const {
            return age < other.age;
        }
    };

    // 可以在set中使用
    std::set<Person> people;

5. 常见问题解答

5.1 如何选择合适的容器？

解答：选择容器时应考虑以下因素：

  • 访问模式：是否需要随机访问？
  • 插入删除模式：插入删除操作主要在哪些位置？
  • 排序需求：是否需要元素有序？
  • 查找频率：查找操作是否频繁？
  • 内存限制：内存使用是否受限？
  • 线程安全性：是否需要在多线程环境中使用？

5.2 vector 和 list 的区别是什么？

解答：

  • 底层实现：vector 是动态数组，list 是双向链表
  • 访问速度：vector 支持随机访问（O(1)），list 只能顺序访问（O(n)）
  • 插入删除：vector 在中间插入删除较慢（O(n)），list 在任意位置插入删除较快（O(1)）
  • 内存使用：vector 内存连续，内存使用更高效；list 每个节点有额外指针，内存开销较大
  • 缓存友好性：vector 内存连续，缓存命中率高；list 内存分散，缓存命中率低

5.3 map 和 unordered_map 的区别是什么？

解答：

  • 底层实现：map 基于红黑树，unordered_map 基于哈希表
  • 元素顺序：map 中的元素按键有序，unordered_map 中的元素无序
  • 查找速度：map 查找时间复杂度为 O(log n)，unordered_map 平均为 O(1)
  • 内存使用：map 内存使用较少，unordered_map 内存使用较多
  • 稳定性：map 在元素插入删除时迭代器不会失效（除非删除的是当前迭代器指向的元素），unordered_map 在元素插入时可能会因为重新哈希而使所有迭代器失效
  • 自定义类型：map 需要自定义类型实现 < 运算符，unordered_map 需要实现哈希函数和 == 运算符

5.4 什么是容器适配器？

解答：容器适配器是对现有容器的封装，提供特定的接口和行为。STL 中的容器适配器包括：

  • stack：提供后进先出（LIFO）的接口
  • queue：提供先进先出（FIFO）的接口
  • priority_queue：提供优先级队列的接口

容器适配器默认使用 deque 作为底层容器，但也可以指定其他容器，只要满足相应的接口要求。

5.5 如何在容器中存储自定义类型？

解答：

  • 对于序列容器（如 vector、list）：只需要自定义类型有适当的构造函数和析构函数
  • 对于有序容器（如 set、map）：需要自定义类型实现 < 运算符，或者在声明容器时提供自定义比较器
  • 对于无序容器（如 unordered_set、unordered_map）：需要为自定义类型提供哈希函数和 == 运算符，或者在声明容器时提供自定义哈希器和相等性比较器

5.6 如何处理容器的内存泄漏？

解答：

  • 使用智能指针：对于存储指针的容器，使用 std::unique_ptr 或 std::shared_ptr 管理内存
  • 手动释放：如果使用原始指针，确保在容器销毁前手动释放所有指针指向的内存
  • 避免循环引用：使用 std::weak_ptr 避免 std::shared_ptr 的循环引用
  • 使用 RAII 原则：资源获取即初始化，确保资源在对象销毁时自动释放

5.7 如何提高容器的性能？

解答：

  • 预分配内存：对于 vector，使用 reserve() 预分配内存
  • 选择合适的容器：根据实际使用场景选择最适合的容器
  • 使用移动语义：对于大对象，使用移动构造和移动赋值减少拷贝开销
  • 避免不必要的拷贝：使用引用传递和 const 引用
  • 合理设置哈希表参数：对于无序容器，合理设置桶大小和负载因子
  • 使用 emplace 系列函数：直接在容器中构造元素，避免拷贝或移动

6. 代码优化建议

6.1 容器的选择和使用

  • 根据访问模式选择容器：

    • 需要随机访问：vector、deque、array
    • 需要频繁插入删除：list
    • 需要两端操作：deque
    • 需要自动排序：set、map
    • 需要快速查找：unordered_set、unordered_map

  • 避免不必要的拷贝：

    • 使用 emplace_back() 代替 push_back() 插入元素
    • 使用移动语义（std::move）转移所有权
    • 对于大对象，考虑使用指针或引用

  • 内存管理：

    • 对于 vector，使用 reserve() 预分配内存
    • 对于不再使用的容器，及时 clear() 或析构
    • 对于存储指针的容器，使用智能指针管理内存

6.2 迭代器的使用

  • 避免无效迭代器：

    • 在插入删除操作后，注意迭代器可能失效
    • 对于 vector，插入操作可能导致所有迭代器失效
    • 对于 unordered_map，插入操作可能导致所有迭代器失效

  • 使用范围 for 循环：

    • 对于遍历整个容器，使用范围 for 循环更简洁
    • 对于需要修改元素的情况，使用引用

  • 使用 const_iterator：

    • 对于只读操作，使用 const_iterator 提高安全性和可读性

6.3 性能优化

  • 使用适当的算法：

    • 对于排序，使用 std::sort
    • 对于查找，使用 std::find 或容器的 find 成员函数
    • 对于计数，使用 std::count 或容器的 count 成员函数

  • 批量操作：

    • 对于多个插入操作，考虑批量插入
    • 对于需要多次修改的操作，考虑先修改再插入

  • 避免频繁重新哈希：

    • 对于无序容器，预先设置足够的桶大小
    • 使用 reserve() 预分配空间

6.4 代码可读性和可维护性

  • 使用类型别名：

    • 使用 typedef 或 using 为复杂的容器类型创建别名
    • 提高代码可读性和可维护性

  • 添加注释：

    • 对于复杂的容器操作，添加注释说明
    • 说明选择特定容器的原因

  • 异常安全：

    • 确保容器操作的异常安全性
    • 使用 RAII 原则管理资源

7. 总结

C++ STL 提供了丰富的容器类型，每种容器都有其特定的用途和性能特点。选择合适的容器对于提高程序的性能和可维护性至关重要。

7.1 容器分类总结

  • 序列容器：保持元素的插入顺序，包括 vector、list、deque、array
  • 容器适配器：提供特定的接口，包括 stack、queue、priority_queue
  • 关联容器：按键排序，包括 set、multiset、map、multimap
  • 无序关联容器：基于哈希表，包括 unordered_set、unordered_map
  • 元组和对：用于存储多个值，包括 pair、tuple

7.2 容器选择指南

  1. 首先考虑使用 vector：

    • 大多数情况下，vector 是最通用和高效的选择
    • 只有在特定场景下才考虑其他容器

  2. 需要频繁插入删除时：

    • 考虑使用 list 或 deque

  3. 需要有序元素时：

    • 考虑使用 set、map 等关联容器

  4. 需要快速查找时：

    • 考虑使用 unordered_set、unordered_map 等无序容器

  5. 需要固定大小数组时：

    • 考虑使用 array

  6. 需要特定的数据结构时：

    • 栈操作：stack
    • 队列操作：queue
    • 优先级操作：priority_queue

7.3 最佳实践

  • 选择合适的容器：根据实际使用场景选择最适合的容器
  • 了解容器的性能特点：掌握各种容器的时间复杂度
  • 使用现代 C++ 特性：利用移动语义、emplace 操作、智能指针等
  • 注意内存管理：避免内存泄漏和不必要的内存使用
  • 编写清晰的代码：使用类型别名和注释提高代码可读性
  • 测试和基准测试：在关键场景下测试不同容器的性能

通过合理选择和使用 STL 容器，可以显著提高 C++ 程序的性能和可维护性。希望本指南能够帮助您更好地理解和使用 C++ STL 容器。

stl_containers.cpp

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <algorithm>
#include <tuple>
#include <array>

int main() {
    std::cout << "=== 1. std::vector（动态数组）===" << std::endl;
    // 创建并初始化vector
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 在末尾添加元素
    vec.push_back(6);
    // 插入元素
    vec.insert(vec.begin() + 2, 100);
    
    std::cout << "Vector元素: ";
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << "\n大小: " << vec.size() << std::endl;
    std::cout << "容量: " << vec.capacity() << std::endl;
    std::cout << "是否为空: " << (vec.empty() ? "是" : "否") << std::endl;
    
    // 删除元素
    vec.erase(vec.begin() + 2);
    std::cout << "删除元素后: ";
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 清空vector
    vec.clear();
    std::cout << "清空后大小: " << vec.size() << std::endl;

    std::cout << "\n=== 2. std::list（双向链表）===" << std::endl;
    // 创建并初始化list
    std::list<int> lst = {10, 20, 30};
    // 在头部添加元素
    lst.push_front(5);
    // 在尾部添加元素
    lst.push_back(40);
    // 在指定位置插入元素
    auto it = lst.begin();
    ++it; // 移动到第二个元素
    lst.insert(it, 15);
    
    std::cout << "List元素: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << "\n大小: " << lst.size() << std::endl;
    
    // 删除元素
    lst.remove(20); // 删除所有值为20的元素
    std::cout << "删除元素后: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    // 排序
    lst.sort();
    std::cout << "排序后: ";
    for (int x : lst) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 3. std::deque（双端队列）===" << std::endl;
    // 创建并初始化deque
    std::deque<int> dq = {1, 2, 3};
    // 在头部添加元素
    dq.push_front(0);
    // 在尾部添加元素
    dq.push_back(4);
    
    std::cout << "Deque元素: ";
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << "\n大小: " << dq.size() << std::endl;
    
    // 删除头部和尾部元素
    dq.pop_front();
    dq.pop_back();
    std::cout << "删除头尾后: ";
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 4. std::queue（队列）===" << std::endl;
    // 创建queue
    std::queue<int> q;
    // 入队
    q.push(1);
    q.push(2);
    q.push(3);
    
    std::cout << "Queue元素（FIFO）: ";
    while (!q.empty()) {
        std::cout << q.front() << " "; // 访问队首元素
        q.pop(); // 出队
    }
    std::cout << std::endl;

    std::cout << "\n=== 5. std::stack（栈）===" << std::endl;
    // 创建stack
    std::stack<int> st;
    // 入栈
    st.push(1);
    st.push(2);
    st.push(3);
    
    std::cout << "Stack元素（LIFO）: ";
    while (!st.empty()) {
        std::cout << st.top() << " "; // 访问栈顶元素
        st.pop(); // 出栈
    }
    std::cout << std::endl;

    std::cout << "\n=== 6. std::priority_queue（优先队列）===" << std::endl;
    // 创建优先队列（默认是最大堆）
    std::priority_queue<int> pq;
    // 入队
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    
    std::cout << "优先队列元素（从大到小）: ";
    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 访问优先级最高的元素
        pq.pop(); // 出队
    }
    std::cout << std::endl;
    
    // 创建最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(30);
    min_pq.push(10);
    min_pq.push(50);
    min_pq.push(20);
    
    std::cout << "最小堆元素（从小到大）: ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    std::cout << "\n=== 7. std::set（有序集合）===" << std::endl;
    // 创建并初始化set（自动排序，去重）
    std::set<int> s = {5, 2, 8, 1, 9, 2, 5};
    // 插入元素
    s.insert(7);
    
    std::cout << "Set元素（有序，唯一）: ";
    for (int x : s) {
        std::cout << x << " ";
    }
    std::cout << "\n大小: " << s.size() << std::endl;
    std::cout << "是否包含5: " << (s.count(5) ? "是" : "否") << std::endl;
    
    // 查找元素
    auto find_it = s.find(8);
    if (find_it != s.end()) {
        std::cout << "找到元素: " << *find_it << std::endl;
    }
    
    // 删除元素
    s.erase(5);
    std::cout << "删除5后: ";
    for (int x : s) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 8. std::multiset（有序多重集合）===" << std::endl;
    // 创建并初始化multiset（自动排序，允许重复）
    std::multiset<int> ms = {5, 2, 8, 1, 9, 2, 5};
    
    std::cout << "Multiset元素（有序，允许重复）: ";
    for (int x : ms) {
        std::cout << x << " ";
    }
    std::cout << "\n5的数量: " << ms.count(5) << std::endl;

    std::cout << "\n=== 9. std::map（有序映射）===" << std::endl;
    // 创建map
    std::map<std::string, int> m;
    // 插入键值对
    m["apple"] = 5;
    m["banana"] = 3;
    m["cherry"] = 8;
    m.insert({"date", 2});
    
    std::cout << "Map元素（键值对）:" << std::endl;
    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << "banana的值: " << m["banana"] << std::endl;
    
    // 查找元素
    auto map_it = m.find("cherry");
    if (map_it != m.end()) {
        std::cout << "找到键: " << map_it->first << ", 值: " << map_it->second << std::endl;
    }

    std::cout << "\n=== 10. std::multimap（有序多重映射）===" << std::endl;
    // 创建multimap（允许重复键）
    std::multimap<std::string, int> mm;
    // 插入键值对
    mm.insert({"fruit", 1});
    mm.insert({"fruit", 2});
    mm.insert({"vegetable", 3});
    
    std::cout << "Multimap元素:" << std::endl;
    for (const auto& pair : mm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    std::cout << "\n=== 11. std::unordered_set（无序集合）===" << std::endl;
    // 创建并初始化unordered_set（无序，去重，哈希表实现）
    std::unordered_set<int> us = {5, 2, 8, 1, 9, 2, 5};
    
    std::cout << "Unordered set元素（无序，唯一）: ";
    for (int x : us) {
        std::cout << x << " ";
    }
    std::cout << "\n大小: " << us.size() << std::endl;
    std::cout << "是否包含3: " << (us.count(3) ? "是" : "否") << std::endl;

    std::cout << "\n=== 12. std::unordered_map（无序映射）===" << std::endl;
    // 创建unordered_map（无序，哈希表实现）
    std::unordered_map<std::string, int> um;
    // 插入键值对
    um["one"] = 1;
    um["two"] = 2;
    um["three"] = 3;
    
    std::cout << "Unordered map元素（无序）:" << std::endl;
    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 查看桶信息
    std::cout << "桶数: " << um.bucket_count() << std::endl;
    std::cout << "最大桶数: " << um.max_bucket_count() << std::endl;

    std::cout << "\n=== 13. std::pair（键值对）===" << std::endl;
    // 创建pair
    std::pair<std::string, int> myPair("age", 25);
    // 访问pair元素
    std::cout << "Pair: " << myPair.first << " = " << myPair.second << std::endl;
    
    // 使用make_pair创建pair
    auto anotherPair = std::make_pair("height", 180);
    std::cout << "Another pair: " << anotherPair.first << " = " << anotherPair.second << std::endl;

    std::cout << "\n=== 14. std::tuple（元组）===" << std::endl;
    // 创建tuple
    std::tuple<std::string, int, double> myTuple("John", 30, 3.14);
    // 访问tuple元素（通过索引）
    std::cout << "Tuple: " << std::get<0>(myTuple) << ", " 
              << std::get<1>(myTuple) << ", " 
              << std::get<2>(myTuple) << std::endl;
    
    // 使用make_tuple创建tuple
    auto anotherTuple = std::make_tuple("Alice", 25, 2.718);
    // 使用结构化绑定（C++17特性）
    auto [name, age, value] = anotherTuple;
    std::cout << "Another tuple: " << name << ", " << age << ", " << value << std::endl;

    std::cout << "\n=== 15. std::array（固定大小数组）===" << std::endl;
    // 创建array（固定大小）
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    
    std::cout << "Array元素: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << "\n大小: " << arr.size() << std::endl;
    std::cout << "是否为空: " << (arr.empty() ? "是" : "否") << std::endl;
    
    // 访问元素
    std::cout << "第一个元素: " << arr.front() << std::endl;
    std::cout << "最后一个元素: " << arr.back() << std::endl;
    std::cout << "索引2的元素: " << arr[2] << std::endl;

    return 0;
}