C++ STL 编程指北

C++ STL 编程指北

未避免歧义，所有容器的swap方法和不常用方法均未写

1. vector 向量容器

用一句话来说，vector就是可变长数组。

但vector所支持的可变长特性，并不是在原空间之后接续新空间来实现的，因为无法保证之后尚有可供分配的空间。

底层实现上当增加新元素时，如果当前vector容器已满，vector会开辟一个比自身大小更大的一块内存，然后把自己所有的数据copy过去，然后再增加新元素。最后再释放原空间。

至于内存扩容策略，有多种不同的实现，依具体的编译器实现而不同：

1. 以等长个数进行扩容，如早期VS采用每次加3的扩容方法；
2. 以倍数方式进行扩容，如VS2019中以1.5倍扩容，GCC以2倍扩容。

vector的创建

略

遍历

可以使用类似数组的下标访问的形式进行使用，例如：

std::vector<int> vec = {0, 1, 2};
for (int i = 0; i < vec.size(); i++) {
	cout << arr[i] << endl;
}

范围for循环：

std::vector<int> vec = {0, 1, 2};
for (int num : vec) {
	cout << num << endl;
}

迭代器访问：

// 迭代器：vector<int>::iterator  顺序访问
for (vector<int>::iterator it = arr.begin(); it != arr.end(); it++) {
    cout << *it << endl;
}
// 迭代器：vector<int>::reverse_iterator  逆序访问
for (vector<int>::reverse_iterator it = arr.rbegin(); it != arr.rend(); it++) {
    cout << *it << endl;
}
// 与上相同，演示变量类型可缩写为auto, auto为此而生
for (auto it = arr.rbegin(); it != arr.rend(); it++) {
    cout << *it << endl;
}

迭代器

1. begin 返回指向容器中第一个元素的迭代器。
2. end 返回指向容器最后一个元素所在位置后一个位置的迭代器
3. rbegin 返回容器逆序的第一个元素的迭代器
4. rend 返回容器逆序的最后一个元素的前一个位置的迭代器
5. cbegin 和begin()功能相同，在其基础上增加了 const 属性，不能用于修改元素。
6. cend 和end()功能相同，在其基础上增加了 const 属性，不能用于修改元素。
7. crbegin 和rbegin()功能相同，在其基础上增加了 const 属性，不能用于修改元素。
8. crend 和rend()功能相同，在其基础上增加了 const 属性，不能用于修改元素。

方法

Capacity（容量）

1. size 返回实际元素的个数
2. capacity 返回总共可以容纳的元素个数
3. max_size 返回元素个数的最大值。这个值非常大，一般是2^32-1
4. empty 判断vector是否为空，为空返回true否则false
5. reserve 增加容器的容量，控制vector的预留空间
6. shrink_to_fit 减少capacity到size的大小，即减小到size的大小

Element access（元素访问）

1. at vector.at(i)等同于vector[i]，访问数组下表的元素
2. front 返回第一个元素
3. back 返回最后一个元素
4. data 返回指向容器中第一个元素的指针

Modifiers（修改器）

1. push_back 在容器的尾部插入元素
2. pop_back 删除最后一个元素
3. insert 插入元素
4. erase 删除元素
5. clear 清除容器内容，size=0，存储空间不变
6. assign 用新元素替换原有内容。
7. emplace 插入元素，和insert实现原理不同，速度更快
8. emplace_back 在容器的尾部插入元素，和push_back不同，速度更快
9. resize 改变实际元素的个数，对应于size

非成员函数

1. erase 从容器中擦除所有比较等于 value 的元素
2. erase_if 从容器中擦除所有满足 pred 的元素

2. queue 队列容器

queue（普通队列）是一个专为 FIFO 设计的容器适配器，也即只能从一端插入、从另一端删除。

默认情况下，queue 的默认容器是 deque ，也可以使用其他容器，例如使用 list 自定义队列。

queue 可以接纳任何一个至少支持下列接口的容器作为底层容器：

empty(); size(); front(); back(); push_back(); pop_front()

方法

1. push 在队尾插入一个元素
2. emplace 在尾部原位构造元素
3. pop 删除队列第一个元素
4. size 返回队列中元素个数
5. empty 如果队列空则返回true
6. front 返回队列中的第一个元素
7. back 返回队列中最后一个元素

3. deque 双端队列容器

deque是 double-ended queue 的缩写，是一个可以在首尾两端进行动态增删的顺序容器。

迭代器、容量与元素访问与vector相同（采用相同名称的接口）

Modifiers（修改器）

1. push_back 在容器的尾部插入元素
2. pop_back 删除最后一个元素
3. push_front 在容器的头部插入元素
4. pop_front 删除第一个元素
5. insert 插入元素
6. erase 删除元素
7. clear 清除容器内容
8. emplace 插入元素
9. emplace_back 在容器的尾部插入元素
10. emplace_front 在容器的头部插入元素
11. resize 改变实际元素的个数

4. priority_queue 优先队列容器

priority_queue<int, vector, greater > h; // 此为小顶堆，默认的是大顶堆

大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

元素访问

​ top 访问栈顶元素，大顶堆访问的是当前最大值，最小值访问的是当前最小值

容量

​ empty 检查底层容器是否为空

​ size 返回容纳的元素数

修改器

​ push 插入元素，并对底层容器排序

​ emplace 原位构造元素并排序底层容器

​ pop 删除队首元素

5. stack 栈容器

栈

元素访问

​ top 访问栈顶元素

容量

​ empty 检查底层容器是否为空

​ size 返回容纳的元素数

修改器

​ push 向栈顶插入元素

​ emplace 在顶部原位构造元素

​ pop 删除栈顶元素

6. map

map 容器存储的都是 pair 类型的键值对元素，更确切的说，该容器存储的都是 pair<const K, T> 类型（其中 K 和 T 分别表示键和值的数据类型）的键值对元素。也就是用 pair 类模板创建的键值对。

底层是红黑树

迭代器

​ begin() 返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
​ end() 返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
​ rbegin() 返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
​ rend() 返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
​ cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
​ cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
​ crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
​ crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。

查找

​ find(key) 在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
​ lower_bound(key) 返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
​ upper_bound(key) 返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
​ equal_range(key) 该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。

​ count(key) 在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。

容量

​ empty() 若容器为空，则返回 true；否则 false。
​ size() 返回当前 map 容器中存有键值对的个数。
​ max_size() 返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。

修改器

​ insert() 向 map 容器中插入键值对。
​ erase() 删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。
​ clear() 清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。
​ emplace() 在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
​ emplace_hint() 在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。

7. multimap

和 map 容器的区别在于，multimap 容器中可以同时存储多（≥2）个键相同的键值对。

与map成员函数唯一不同的是：

​ find(key) 在 multimap 容器中查找首个键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。

8. unordered_map，unordered_multimap

unordered_map 无序 map 容器，就是哈希表

由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。

无序容器中存储的各个键值对，都会哈希存到各个桶（本质为链表）中。而对于 unordered_multimap 容器来说，其存储的所有键值对中，键相等的键值对会被哈希到同一个桶中存储。

迭代器

​ begin() 返回指向容器中第一个键值对的正向迭代器。
​ end() 返回指向容器中最后一个键值对之后位置的正向迭代器。
​ cbegin() 和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
​ cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。

容量

​ empty() 若容器为空，则返回 true；否则 false。
​ size() 返回当前容器中存有键值对的个数。
​ max_size() 返回容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。

查找

​ find(key) 查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。
​ count(key) 在容器中查找以 key 键的键值对的个数。
​ equal_range(key) 返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。

修改器

​ emplace() 向容器中添加新键值对，效率比 insert() 方法高。
​ emplace_hint() 向容器中添加新键值对，效率比 insert() 方法高。
​ insert() 向容器中添加新键值对。
​ erase() 删除指定键值对。
​ clear() 清空容器，即删除容器中存储的所有键值对。

桶接口

​ bucket_count() 返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量。
​ max_bucket_count() 返回当前系统中，unordered_map 容器底层最多可以使用多少桶。
​ bucket_size(n) 返回第 n 个桶中存储键值对的数量。
​ bucket(key) 返回以 key 为键的键值对所在桶的编号。

哈希策略

​ load_factor() 返回 unordered_map 容器中当前的负载因子。负载因子，指的是的当前容器中存储键值对的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
​ max_load_factor() 返回或者设置当前 unordered_map 容器的负载因子。
​ rehash(n) 将当前容器底层使用桶的数量设置为 n。
​ reserve() 将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。

观察器

​ hash_function() 返回当前容器使用的哈希函数对象。

9. set

底层红黑树

和 map 容器不同，使用 set 容器存储的各个键值对，要求键 key 和值 value 必须相等。

ste没有重载[]操作符

set没有元素访问，所以除元素访问外set与map所包含的成员方法一样

10. multiset

multiset 之于 set 就如同 multimap 之于 map

multiset 与 set 所包含的成员方法一样

11. unordered_set，unordered_multiset

所有unordered_XXX类容器的特点都是以哈希表作为底层结构；所有 XXX_set 类容器的特点都是元素自身也作为key来标识自己。我们在把两类特性叠加到一起，就得到了 unordered_set。

unordered_multiset，顾名思义，就是集齐了“哈希表为底层结构”，“元素自身即key”，“允许不同元素值相同”这三个特性的容器，是对 unordered_set 的简单拓展。

所包含方法与unordered_map，unordered_multimap相同

12. list 双向链表容器

底层是以双向链表的形式实现的。

迭代器

​ begin() 返回指向容器中第一个元素的双向迭代器。
​ end() 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
​ rbegin() 返回指向最后一个元素的反向双向迭代器。
​ rend() 返回指向第一个元素所在位置前一个位置的反向双向迭代器。
​ cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
​ cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
​ crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
​ crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。

容量

​ empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
​ size() 返回当前容器实际包含的元素个数。
​ max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。

元素访问

​ front() 返回第一个元素的引用。
​ back() 返回最后一个元素的引用。

修改器

​ emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。
​ push_front() 在容器头部插入一个元素。
​ pop_front() 删除容器头部的一个元素。
​ emplace_back() 在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同，但效率更高。
​ push_back() 在容器尾部插入一个元素。
​ pop_back() 删除容器尾部的一个元素。
​ emplace() 在容器中的指定位置插入元素。该函数和 insert() 功能相同，但效率更高。
​ insert() 在容器中的指定位置插入元素。
​ erase() 删除容器中一个或某区域内的元素。
​ swap() 交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。
​ resize() 调整容器的大小。
​ clear() 删除容器存储的所有元素。

操作

​ splice() 将一个 list 容器中的元素插入到另一个容器的指定位置。
​ remove(val) 删除容器中所有等于 val 的元素。
​ remove_if() 删除容器中满足条件的元素。
​ unique() 删除容器中相邻的重复元素，只保留一个。
​ merge() 合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。
​ sort() 通过更改容器中元素的位置，将它们进行排序。
​ reverse() 反转容器中元素的顺序。

13. forward_list 单向链表容器

设计 forward_list 的目的是为了达到不输于任何一个C风格手写链表的极值效率！为此，forward_list 是一个最小链表设计，它甚至没有size()接口，因为内部维护一个size变量会降低增删元素的效率。如果想要获取 forward_list 的 size，一个通常的做法是，用 std::distance 计算 begin 到 end 的距离得出 size。一句话总结：list 兼顾了接口丰富性牺牲了效率，而 forward_list 舍弃了不必要的接口只为追求极致效率。

迭代器

​ before_begin() 返回一个前向迭代器，其指向容器中第一个元素之前的位置。
​ begin() 返回一个前向迭代器，其指向容器中第一个元素的位置。
​ end() 返回一个前向迭代器，其指向容器中最后一个元素之后的位置。
​ cbefore_begin() 和 before_begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
​ cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
​ cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。

容量

​ empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
​ max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。

元素访问

​ front() 返回第一个元素的引用。

修改器

​ push_front() 在容器头部插入一个元素。
​ emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。
​ pop_front() 删除容器头部的一个元素。
​ emplace_after() 在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器。和 insert_after() 的功能相同，但效率更高。
​ insert_after() 在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器。
​ erase_after() 删除容器中某个指定位置或区域内的所有元素。
​ resize() 调整容器的大小。
​ clear() 删除容器存储的所有元素。

操作

​ splice_after() 将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后。
​ remove(val) 删除容器中所有等于 val 的元素。
​ remove_if() 删除容器中满足条件的元素。
​ unique() 删除容器中相邻的重复元素，只保留一个。
​ merge() 合并两个事先已排好序的 forward_list 容器，并且合并之后的 forward_list 容器依然是有序的。
​ sort() 通过更改容器中元素的位置，将它们进行排序。
​ reverse() 反转容器中元素的顺序。

14. array 数组容器

它就是在 C++ 普通数组的基础上，添加了一些成员函数和全局函数。

array 和其它标准容器一个很重要的不同是：对两个 array 执行 swap 操作意味着真的会对相应 range 内的元素一一置换，因此其时间花销正比于置换规模；但同时，对两个 array 执行 swap 操作不会改变两个容器各自的迭代器的依附属性，这是由 array 的 swap 操作不交换内存地址决定的。

array 的另一个特性是：不同于其它容器，array 可以被当作 std::tuple 使用，因为 array 的头文件重载了get()以及tuple_size()和tuple_element()函数（注意这些函数非 array 的成员函数，而是外部函数）。

最后需要注意，虽然 array 和 C++语法中的[]符号无限接近，但两者是两个存在，array 毕竟是标准模板库的一员，是一个class，因此支持begin(), end(), front(), back(), at(), empty(), data(), fill(), swap(), ... 等等标准接口，而[]是真正的最朴素的数组。

迭代器与元素访问与vector相同

容量

​ empty 检查容器是否为空

​ size 返回容纳的元素数

​ max_size 返回可容纳的最大元素数

操作

​ fill 以指定值填充容器

15. 非STL的类模板：pair & tuple

tuple 叫作元组，它可以把一组类型相同或不同的元素组合到一起，且元素的数量不限。

在使用上，可以用std::make_tuple()来构造 tuple 对象，可以用std::get<index>()来获取 tuple 对象的某个元素，注意std::get<index>()返回的是 tuple 对象中某个元素的索引，因此是可以用作左值的！此外，也可以用std::tie()打包一组变量来作为左值接受 tuple 对象的赋值。tuple_size可在编译时获取tuple的大小。

具体方法可看cppreference。

pair 可以看作是把 tuple 的 size 限制为 2 的一个特例，pair 只能把一对元素组合到一起。

在使用上，可以用std::make_pair()来直接构建 pair 对象，可以用std::get<0>()和std::get<1>()来分别获取 pair 对象的两个元素，但更方便的做法是直接访问 pair 类型的两个数据成员pair对象.first和pair对象.second来访问元素。

16. 算法

算法部分函数很多，大都见名知意，注意联合使用即可

例如：erase和unique联合使用来删除重复元素

std::vector<int> result;
......
result.erase(unique(result.begin(), result.end()), result.end());

参考资料：

cppreference中文版
C++ STL 十六大容器 —— 底层原理与特性分析

本栏目推荐文章
• String 类和 STL (Standard Template Library)
• R语言用LOESS(局部加权回归)季节趋势分解（STL）进行时间序列异常检测
• 【STL】 vector
• 【STL】 pair/map的简介与用法
• 【STL】 lower_bound和upper_bound
• C++/模板变量的典型应用(STL)源码剖析
• Week1——STL 与基础数据结构专题训练
• （器件）STL33N60DM2 600V MOSFET、STLQ020PU28R低压差稳压器、STEC01PUR电源开关、STC3115IJT电池管理
• C++（STL标准库）
• C++U4-第09课-STL容器

STL模板stl 杂谈stl 容器stl stl基础 答案stl 源码stl 要点stl stl-multiset 教程stl 标准stl