【C++】C++ 基础进阶【四】STL 容器基础

I - 概述 STL

1.1 - 范围与定义

Standard Template Library (标准模板库) 包含于 Standard Library (标准库) 中，都封装于命名空间 std 中。

属于泛型编程 (Generic Programming) ，使用模板 (template) 为主要工具来编写的程序。

1.2 - 组成与关系

STL 包含六大组件 :

1. 容器 (Containers)
2. 分配器 (Allocators)
3. 算法 (Algorithms)
4. 迭代器 (Iterators)
5. 适配器 (Adapters)
6. 仿函数 (Functors)

这六大组件之间的关系图如下：

容器 用来存储数据，数据占用内存，容器背后有一个部件负责内存的分配与释放，这个组件就是分配器 ，此操作对用户透明，所以在使用容器时，基本不需要去管内存的分配与释放。

算法 ，如常用的 sort 排序和查找等，算法通过 迭代器 去访问容器的内容，有时我们排序需要自定义排序方式，这些自定义的方法就是 仿函数 ，其他的一些细节的操作就是通过 适配器 来完成的。

1.3 - 实用举例

如下，使用了六个组件的一段代码：

int arr[6] = {
    19, 23, 52, 18, 50, 9 };

std::vector<int, allocator<int>> vec(arr, arr+6);

std::cout << count_if(vec.begin(), vec.end(), 
not1(bind2nd(less<int>(), 50)));

首先来识别一下代码中的各个元素：

代码中首先创建一个 6 个元素的整型数组，然后基于数组构建一个 整型容器 vector<int> vec ，容器使用整型的默认分配器，count_if 为算法，通过 vec 的首尾迭代器访问容器中的全部元素，此算法为条件计数，仿函数 less<int>() 比较任意两个元素的小于是否满足。

bind2nd 为仿函数适配器，将仿函数的第二个元素绑定为 50 ，即所有小于 50 的元素，not1 同样为仿函数适配器，将原来的结果取反，即 vec 中所有大于等于 50 的元素个数，所以输出结果为 2。

II - 概述容器

2.1 - 迭代器

迭代器是一种泛化的指针，可以使用 ++ 和 -- 去访问容器中的元素，需要注意它的访问区间是一个 前闭后开 的区间。

c.begin() 解引用是容器的第一个元素，
c.end() 指向的是容器最后一个元素的下一个元素，所以不能解引用，即 *(c.end()); 可能导致程序异常，程序崩溃异常退出。

基于范围的 for 循环 (range-based for loop)，使用迭代器遍历元素语法：

for (decl : coll) {
   
    statement;
}

// 遍历
for (auto elem : container)  {
   
    // ...
}
// 修改
for (auto& elem : container) {
   
    //...
} 
// 查找，建议使用 算法
auto iter = std::find(c.begin(), c.end(), target);

示例

std::vector<double> vec = {
   /* ... */}; 
// 遍历
for (double elem : vec) {
   
    std::cout << elem << std::endl;
}
// 修改
for (double& elem : vec) {
   
    elem *= 3;
}
// 查找
std::vector<double>::iterator iter = std::find(vec.begin(), vec.end(), 1.0);

2.2 - 容器的结构与分类

• 序列式容器

• 关联式容器 (associative containers) ，基于红黑树的实现

• 不定序容器 (unordered containers)， 或者叫无序容器，基于哈希表实现

2.3 - 序列式容器

• array，数组：固定大小，初始时需指定长度，不可更改。元素数量不能动态增长，支持随机访问。

• vector，向量，可变长度数组：可单向动态增长，两倍扩容或会造成内存空置。支持下标，随机访问，尾部以外的位置插入/删除可能会比较慢。
  插入使用 insert ，尾部添加元素 push_back 和 emplace_back，不提供 push_front 和 emplace_front 接口，由于首部添加需要移动所有元素，耗时操作。

• deque，双向增长，实质上伪双边增长，实现为映射管理多个分段连续内存。
  两端操作都比较快，支持 push_back ，emplace_back 和 push_front ，emplace_front 。

• list，双向链表，每个元素包含两个指针，支持双向顺序访问。在链表任何位置插入/删除都很快。动态单个增长， “一个萝卜，一个坑” ，没有空置内存，但相同元素情况下，占用内存大于 vector 。
  非连续内存，不支持随机访问，但遍历缓慢

• forward_list，单链表，与 list 相同，在任何位置插入删除都很快。相较 list，一个指针更节约内存，但迭代器不支持递减运算符 ( -- )，不提供 push_back 和 emplace_back 尾端插入函数，由于过于耗时。

• stack 与 queue 栈与队列 ，为容器适配器，表示两种数据结构 栈 和 队列 ，栈先进后出 (FILO first in last out)，队列先进先出 (FIFO first in first out) 。插入方式 push ，删除方式 pop 。不属于容器，不对外提供迭代器访问，不提供随机访问，会破坏结构设计。

2.4 - 关联式容器

关联式容器底层实现为红黑树，查询快，但插入耗时较久，由于每次插入都需要排序。

• set，集合，元素只存在一份，不重复。
• multiset，相同的元素可存在多份。

• map，键值对 (key value pair)，键存在时，insert , emplace 都会插入失败，[] 赋值会覆盖。使用 [] 访问时，键不存在会创建。C++ 17 为提高性能，增加 try_emplace 接口，在键存在时，不会构造参数，在值复杂时可较多节省内存，提升性能。
• multimap，相同的键可存在多份，不支持 [] 访问。

2.5 - 不定序容器

不定序容器底层实现为哈希表，插入元素，对其计算哈希值，分配到对应的 bucket （桶）上，哈希值计算可能会产生哈希冲突，即不同的值计算的哈希值相同。哈希表的查找时间复杂度为 O(1)，虽然元素哈希值相同时，还是会进行顺序查找，但不改变不定序容器查找基本为 O(1) 的情况。

为了避免较多的顺序查找，当 bucket 数量与元素个数相同时，bucket 会进行两倍扩容，之前的元素会被打散，重新计算哈希值，分布到新的 bucket 后。也会产生较多的内存空置，如 bucket 后无任何的元素。

• unordered_map
• unordered_set
• unordered_multimap
• unordered_multiset

先哈希查找，后循序查找。

2.6 - 总述

• 查询

序列式容器查找为顺序查找时间复杂度为 O(n)，关联式容器为红黑树时间复杂度 O(log n)，不定序容器为哈希表基本上为 O(1)。
查询效率：不定序容器 > 关联式容器 > 序列式容器

关联式容器和不定序容器都提供自身的 find 函数， STL 算法也提供 std::find 查找，但使用容器自身的查找会更快捷

• 排序

list 容器自身也提供 sort 接口，STL 算法提供的 std::sort 查找无法对 list 进行查找，因为 std::sort 接收的迭代器需要为随机访问迭代器类型，而 list 的迭代器为双向顺序访问迭代器。编码时若使用则会产生编译错误。

std::list<int> container = {
    5, 6, 10, 1, 4, 8 };
std::sort(container.begin(), container.end(), greater<int>());

编译报错：

C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2676: binary '-': 'const std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<_Ty>>>' does not define this operator or a conversion to a type acceptable to the predefined operator
1>        with
1>        [
1>            _Ty=int
1>        ]
1>D:\GZC\Work\Train\TrainDemo\TrainDemo\TrainDemo\TrainDemo.cpp(17): note: see reference to function template instantiation 'void std::sort<std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>,std::greater<_Ty>>(const _RanIt,const _RanIt,_Pr)' being compiled
1>        with
1>        [
1>            _Ty=int,
1>            _RanIt=std::_List_iterator<std::_List_val<std::_List_simple_types<int>>>,
1>            _Pr=std::greater<int>
1>        ]
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2672: '_Sort_unchecked': no matching overloaded function found
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3358): error C2780: 'void std::_Sort_unchecked(_RanIt,_RanIt,iterator_traits<_Iter>::difference_type,_Pr)': expects 4 arguments - 3 provided
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.20.27508\include\algorithm(3328): note: see declaration of 'std::_Sort_unchecked'

需要修改为

std::list<int> container = {
    5, 6, 10, 1, 4, 8 };
container.sort(greater<int>());

III - 参考书目

《STL源码剖析》 — 侯捷
《C++ Primer》— 中文版 第 5 版