C++标准模板库学习笔记

zxl19 2021-09-19

我的C++标准模板库（Standard Template Library，STL）学习笔记。

STL Hello World

STL包括以下4种基本组件：

容器（Container）：容器是容纳、包含一组元素的对象。容器类库中包括7种基本容器：向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）、多重映射（multimap）；

按照容器中元素的组织方式，可以将容器分为两种基本类型：顺序容器（sequence container）和关联容器（associative container）：
- 顺序容器：将一组具有相同类型的元素以严格线性形式组织起来，向量、双端队列和列表容器就属于这一种；
- 关联容器：具有根据一组索引来快速提取元素的能力，集合和映射容器就属于这一种；
按照容器关联的迭代器类型，容器具有可逆容器（reversible container）这一子概念，可逆容器又具有随机访问容器（random access container）这一子概念，STL提供的标准容器都至少是可逆容器；
使用不同的容器，需要包含不同的头文件，STL中基本容器对应的头文件和分类如下表所示：

容器名	中文名	头文件	分类
`vector`	向量	`#include <vector>`	随机访问容器，顺序容器
`deque`	双端队列	`#include <deque>`	随机访问容器，顺序容器
`list`	列表	`#include <list>`	可逆容器，顺序容器
`array`	数组	`#include <array>`	随机访问容器，顺序容器，C++11引入
`set`	集合	`#include <set>`	可逆容器，关联容器
`multiset`	多重集合	`#include <set>`	可逆容器，关联容器
`map`	映射	`#include <map>`	可逆容器，关联容器
`multimap`	多重映射	`#include <map>`	可逆容器，关联容器

迭代器（Iterator）：迭代器用于遍历对象集合的元素，这些集合可能是容器，也可能是容器的子集；
- 迭代器是泛化的指针；
- 使用独立于STL容器的迭代器，需要包含头文件#include <iterator>；
函数对象（Function Object）：函数对象是一个行为类似函数的对象，对它可以像调用函数一样调用；
- 函数对象是泛化的函数；
- 使用STL的函数对象，需要包含头文件#include <functional>；
算法（Algorithm）：算法作用于容器，它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作；
- 使用STL的算法，需要包含头文件#include <algorithm>；

容器

符号说明：

S：容器类型；
s：S类型的实例；
T：元素类型；
t：T类型的实例；
K：键的类型；
k：K类型的实例；
n：整型数据；
p：指向s中元素的迭代器；
q：任何指向T类型元素的输入迭代器（未必指向S中的元素，也未必具有S::iterator类型）；

容器基本功能

// 调用默认构造函数初始化
S s1, s2;
// op为比较运算符，对两个容器之间的元素按字典顺序进行比较
s1 op s2
// 返回迭代器
S::iterator s1.begin()              // 前向迭代器，指向容器第一个元素
S::iterator s1.end()                // 前向迭代器，指向容器最后一个元素的下一个位置
S::reverse_iterator s1.rbegin()     // 逆向迭代器，指向容器最后一个元素
S::reverse_iterator s1.rend()       // 逆向迭代器，指向容器第一个元素的前一个位置
// 成员函数
void s1.clear()
bool s1.empty()
size_t s1.size()
void s1.swap(s2)

不推荐使用size()成员函数判断容器是否为空，因为在某些容器中需要通过遍历整个容器获得元素个数，效率较低，相比之下使用empty()成员函数判断容器是否为空效率更高；
不推荐在循环控制条件中使用i < s1.size() - 1进行循环条件判断，因为size()成员函数返回的是无符号整型，当容器为空时，s1.size() - 1会导致范围溢出，获得一个很大的数，相比之下使用i + 1 < s1.size()进行循环条件判断更加合理；
不推荐使用临时变量手动交换容器内容，因为这会带来大量元素复制、动态内存分配和释放，效率较低，相比之下使用swap()成员函数交换容器内容效率更高，swap()成员函数通过交换数据成员实现，效率更高；

顺序容器

包括vector、deque、list，常用基本功能如下所示：

// 构造函数
S s(n, t)                   // 构造一个由n个t元素构成的容器实例s
S s(n)                      // 构造一个有n个元素的容器实例s，每个元素都是T()
S s(q1, q2)                 // 使用将迭代器[q1, q2)区间内的数据作为s的元素构造s
// 赋值函数
void s.assign(n, t)         // 赋值后的容器由n个t元素构成
void s.assign(n)            // 赋值后的容器有n个t元素的容器实例s，每个元素都是T()
void s.assign(q1, q2)       // 赋值后的容器的元素为[q1, q2)区间内的数据
// 改变容器的大小
void s.resize(n, t)         // 超出新容器大小的元素被舍弃，超出原容器大小的部分由t元素构成
void s.resize(n)            // 超出新容器大小的元素被舍弃，超出原容器大小的部分由T()构成
// 首尾元素的直接访问
value_type& s.front()
value_type& s.back()
// 在容器尾部插入、删除元素
void s.push_back(t)
void s.pop_back()
// 在容器头部插入、删除元素（deque、list）
void s.push_front(t)
void s.pop_front()
// 在容器头部插入、删除元素（vector）
void s.insert(s.begin(), t)
void s.erase(s.begin())

三种顺序容器的特性不同，需要根据实际应用场景进行选择，各容器适合的场景如下表所示：

容器	随机访问	扩展方式
`vector`	需要大量	只需要向容器尾部加入新的元素
`deque`	需要少量	需要在容器两端插入或删除元素
`list`	不需要	需要在中间位置插入或删除元素

详细比较可参考《C++语言程序设计》P422表10-2。

向量`vector`

访问元素方式的区别：

 s[i]                    // 无越界检查，需要确保下标不超过容器容量
 s.at(i)                 // 有越界检查，下标越界时会抛出std::out_of_range异常

push_back()和emplace_back()的区别：

 void s.push_back()      // 在容器尾部插入一个元素，创建+拷贝或移动（拷贝优先）
 void s.emplace_back()   // 在容器尾部创建一个元素，直接在容器中创建，C++11引入，执行效率高

类似的还有insert()和emplace()：

 void s.insert(p, t)     // 在容器中p指向的位置插入一个元素，创建+拷贝或移动（拷贝优先）
 void s.emplace(p, t)    // 在容器中p指向的位置创建一个元素，直接在容器中创建，C++11引入，执行效率高

size()和capacity()的区别：

 size_t s.size()         // 返回向量容器的大小
 void s.resize(n)        // 改变向量容器的大小
 size_t s.capacity()     // 返回向量容器的容量
 void s.reserve(n)       // 改变向量容器的容量

顺序容器的适配器

以顺序容器为基础构建一些常用数据结构，STL提供的容器适配器栈stack和队列queue，就是对顺序容器的封装。

栈：先进后出（FILO），即最先被压入栈的元素总是最后被弹出；
队列：先进先出（FIFO），即最先入队的元素总是最先出队；

顺序容器适配器的基本功能

// op为比较运算符，对两个容器之间的元素按字典顺序进行比较
s1 op s2
// 成员函数
size_t s.size()
bool s.empty()
void s.push()
void s.pop()

容器适配器不支持迭代器，因为它们不允许对任意元素进行访问。

栈`stack`

使用时需要包含头文件：

#include <stack>

对于栈来说，只有栈顶的元素是可以访问到的：

value_type& s.top()

队列`queue`

使用时需要包含头文件：

#include <queue>

对于队列来说，只有队头和队尾的元素是可以访问到的：

value_type& s.front()
value_type& s.back()

关联容器

关联容器中元素的顺序按照键的取值升序排列。

类型	简单关联容器	二元关联容器
单重关联容器	集合`set`	映射`map`
多重关联容器	多重集合`multiset`	多重映射`multimap`

单重关联容器：键是唯一的，不允许重复；
多重关联容器：相同的键允许重复出现；
简单关联容器：以元素本身作为键，只有一个类型参数，该类型既是键类型，又是容器类型；
二元关联容器：元素是由键和某种类型的附加数据共同构成的，键只是元素的一部分，有两个类型参数，前一个是键类型，后一个是附加数据的类型；

常用基本功能如下：

// 构造函数
S s(q1, q2);
// 元素的插入
// 单重关联容器：只有当不存在相同键的元素时才能成功插入
pair<S::iterator, bool> s.insert(t);                // 创建+拷贝或移动（拷贝优先）
pair<S::iterator, bool> s.emplace(t);               // 直接在容器中创建，C++11引入，执行效率高
// 多重关联容器：插入总会成功
S::iterator s.insert(t);                            // 创建+拷贝或移动（拷贝优先）
S::iterator s.emplace(t);                           // 直接在容器中创建，C++11引入，执行效率高
// 元素的删除
size_t s.erase(k);                                  // 删除所有键为k的元素，返回被删除元素的个数
// 基于键的查找和计数
S::iterator s.find(k);                              // 找到任意一个键为k的元素，返回该元素的迭代器，如果s中没有键为k的元素，则返回s.end()
S::iterator s.lower_bound(k);                       // 得到s中第一个键值不小于k的元素的迭代器
S::iterator s.upper_bound(k);                       // 得到s中第一个键值大于k的元素的迭代器
pair<S::iterator, S::iterator> s.equal_range(k);    // 得到包含所有键为k的元素的区间[p1, p2)，满足p1 == s.lower_bound(k)且p2 == s.upper_bound(k)
size_t s.count(k);                                  // 得到s容器中键为k的元素个数

关联容器的最大优势在于，可以高效地根据键来查找容器中的一个元素；
关联容器的键之间必须能够使用<比较大小，对于自定义数据类型需要重载<运算符，C++规定<运算符必须构成严格弱序关系，必须满足以下三条性质：
- 非自反性：(a < a) == false；
- <传递性：如果(a < b) == true，则(b < a) == false；
- ==传递性：如果(a == b) == true且(b == c) == true，则(a == c) == true；
关联容器的插入和删除操作不会使任何已有的迭代器、指针或引用失效；

集合`set`

使用时需要包含头文件：

#include <set>

原型声明：

template <class T,                      // 指定元素的类型
          class Compare = less<T>,      // 指定排序规则
          class Alloc = allocator<T>    // 指定分配器对象的类型
          >
class set;

映射`map`

使用时需要包含头文件：

#include <map>

原型声明：

template <class Key,                                    // 指定键（key）的类型
          class T,                                      // 指定值（value）的类型
          class Compare = less<Key>,                    // 指定排序规则
          class Alloc = allocator<pair<const Key, T>>   // 指定分配器对象的类型
          >
class map;

映射map重载了下标运算符[]，可以用于插入和查找元素：

s[k]    // 如果键k存在，则返回对应的值，如果键k不存在，则插入键k，对应的值取默认值并返回
s.at(k) // 如果键k存在，则返回对应的值，如果键k不存在，则抛出std::out_of_range异常

无序关联容器

无序关联容器，又称哈希容器，C++11引入。

类型	简单无序关联容器	二元无序关联容器
单重无序关联容器	无序集合`unordered_set`	无序映射`unordered_map`
多重无序关联容器	无序多重集合`unordered_multiset`	无序多重映射`unordered_multimap`

关联容器的底层实现使用红黑树的存储结构，适用于使用迭代器遍历容器中存储的元素；
无序关联容器的底层实现使用哈希表的存储结构，适用于通过指定键查找对应的值（平均时间复杂度为O(1)）；

无序集合`unordered_set`

使用时需要包含头文件：

#include <unordered_set>

原型声明：

template <class Key,                    // 指定元素的类型
          class Hash = hash<Key>,       // 确定元素存储位置所用的哈希函数
          class Pred = equal_to<Key>,   // 判断各个元素是否相等所用的函数
          class Alloc = allocator<Key>  // 指定分配器对象的类型
          >
class unordered_set;

默认哈希函数hash<Key>只支持基本数据类型，默认比较函数equal_to<Key>只支持可直接用==运算符比较的数据类型，对于自定义数据类型需要重新实现，以三维向量为例：

// hash of vector
template <int N>
struct hash_vec {
    inline size_t operator()(const Eigen::Matrix<int, N, 1>& v) const;
};

// equal of vector
template <int N>
struct equal_to {
    inline bool operator()(const Eigen::Matrix<int, N, 1>& v1, const Eigen::Matrix<int, N, 1>& v2) const;
};

// vec 3 hash
/// @see Optimized Spatial Hashing for Collision Detection of Deformable Objects, Matthias Teschner et. al., VMV 2003
template <>
inline size_t hash_vec<3>::operator()(const Eigen::Matrix<int, 3, 1>& v) const {
    return size_t(((v[0]) * 73856093) ^ ((v[1]) * 471943) ^ ((v[2]) * 83492791)) % 10000000;
}

// vec 3 equal
template <>
inline bool equal_to<3>::operator()(const Eigen::Matrix<int, 3, 1>& v1, const Eigen::Matrix<int, 3, 1>& v2) const {
    return ((v1[0] == v2[0]) && (v1[1] == v2[1]) && (v1[2] == v2[2]));
}

无序映射`unordered_map`

使用时需要包含头文件：

#include <unordered_map>

原型声明：

template <class Key,                                   // 指定键（key）的类型
          class T,                                     // 指定值（value）的类型
          class Hash = hash<Key>,                      // 确定键值对存储位置所用的哈希函数
          class Pred = equal_to<Key>,                  // 判断各个键值对的键是否相等所用的函数
          class Alloc = allocator<pair<const Key, T>>  // 指定分配器对象的类型
          >
class unordered_map;

无序映射unordered_map重载了下标运算符[]，可以用于插入和查找元素：

s[k]    // 如果键k存在，则返回对应的值，如果键k不存在，则插入键k，对应的值取默认值并返回
s.at(k) // 如果键k存在，则返回对应的值，如果键k不存在，则抛出std::out_of_range异常

算法

算法分类

一般来说，STL的算法可以分为4大类：

不可变序列算法：不直接修改所操作的容器内容的算法；
可变序列算法：可以修改所操作的容器内容的算法；
排序和搜索算法：对序列元素进行比较操作的算法；
数值算法：4个通用数值算法；

使用时需要包含头文件：

#include <algorithm>                            // 大部分算法
#include <numeric>                              // 数值算法

不可变序列算法

遍历函数`for_each()`

void for_each(s.begin(), s.end(), fn);          // 对区间内的每一个元素进行某操作，fn常结合C++11引入的Lambda表达式使用
void for_each(std::execution::par_unseq, s.begin(), s.end(), fn);   // 使用并发，C++17引入，需要`#include <execution>`

原型声明：

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function fn);

实现：

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function fn) {
    while (first != last) {
        fn(*first);
        ++first;
    }
    return fn;  // or, since C++11: return move(fn);
}

可变序列算法

void reverse(s.begin(), s.end());               // 反转区间元素次序
void swap(s.at(i), s.at(j));                    // 交换（对调）元素

排序和搜索算法

void sort(s.begin(), s.end());                  // 对区间元素进行排序，默认以元素值的大小做升序排序
bool binary_search(s.begin(), s.end(), t);      // 在有序区间内按照二分查找方法查找是否存在与某一特定值相等的元素
pair<S::iterator, S::iterator> equal_range(s.begin(), s.end(), t);  // 在有序区间内按照二分查找方法查找是否存在与某一特定值相等的元素，并返回一个上下限区间
value_type& min(s.at(i), s.at(j));              // 返回最小值元素
value_type& max(s.at(i), s.at(j));              // 返回最大值元素
S::iterator min_element(s.begin(), s.end());    // 返回最小值元素所在位置
S::iterator max_element(s.begin(), s.end());    // 返回最大值元素所在位置

排序函数`sort()`

void sort(s.begin(), s.end());                  // 对区间元素进行排序，默认以元素值的大小做升序排序
void sort(s.begin(), s.end(), comp);            // 对区间元素进行排序，指定比较函数

原型声明：

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

sort()函数基于快速排序算法实现，出于效率上的考虑，要求迭代器类型必须为随机访问迭代器RandomAccessIterator，因此只支持vector、deque、array这三个容器；
sort()函数默认以元素值的大小做升序排序，要求元素类型必须支持<运算符，如果使用STL提供的其他排序规则，元素类型也必须支持该规则底层实现所使用的比较运算符；
sort()函数在实现排序时，需要交换容器中元素的存储位置，如果容器中存储的元素是自定义的类对象，则类的内部必须提供移动构造函数和移动赋值运算符；
sort()函数对于左闭右开区间[first, last)进行排序，当容器为空或者容器中只有一个元素时，sort()函数会在判断后自动返回，不需要用户检查容器大小；
sort()函数在对于自定义数据类型进行排序时需要定义比较函数comp，实现<运算符对应的逻辑：
- 比较函数comp必须构成严格弱序关系，否则会引起程序崩溃；
  - 不建议在比较函数comp内部实现复杂的排序规则，因为可能不满足严格弱序关系；
  - 建议在比较函数comp外部计算排序规则对应的指标，将索引和指标分别保存为二元组的键和值，在比较函数comp内部对于二元组的值进行排序；
- 比较函数comp通常定义为类中的静态函数成员或lambda表达式；
- 以对于二元组std::pair<int, Eigen::Vector2f>的值进行排序为例：
```
  static bool comp(const std::pair<int, Eigen::Vector2f>& a, const std::pair<int, Eigen::Vector2f>& b) {
    return a.second.x() < b.second.x();
  }
```

数值算法

value_type& accumulate(s.begin(), s.end(), init);           // 计算序列中所有元素的和
S::iterator partial_sum(s.begin(), s.end(), init);          // 累加序列中部分元素的值，并将结果保存在另一个序列中
S::iterator adjacent_difference(s.begin(), s.end(), 0);     // 计算序列中相邻元素的差，并将结果保存在另一个序列中
value_type& inner_product(s.begin(), s.end(), 0);           // 累加两个序列对应元素的乘积，也就是序列的内积

求和函数`accumulate()`

原型声明：

template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init,
             BinaryOperation binary_op);

实现：

template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init) {
    while (first != last) {
        init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
        ++first;
    }
    return init;
}

部分和函数`partial_sum()`

原型声明：

template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result);
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result, BinaryOperation binary_op);

实现：

template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result) {
    if (first != last) {
        typename iterator_traits<InputIterator>::value_type val = *first;
        *result = val;
        while (++first != last) {
            val = val + *first; // or: val = binary_op(val,*first)
            *++result = val;
        }
        ++result;
    }
    return result;
}

相邻差函数`adjacent_difference()`

原型声明：

template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result);
template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result,
                                   BinaryOperation binary_op);

实现：

template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result) {
    if (first != last) {
        typename iterator_traits<InputIterator>::value_type val, prev;
        *result = prev = *first;
        while (++first != last) {
            val = *first;
            *++result = val - prev; // or: *++result = binary_op(val,prev)
            prev = val;
        }
        ++result;
    }
    return result;
}

内积函数`inner_product()`

原型声明：

template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init);
template <class InputIterator1, class InputIterator2, class T,
          class BinaryOperation1, class BinaryOperation2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init, BinaryOperation1 binary_op1,
                BinaryOperation2 binary_op2);

实现：

template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init) {
    while (first1 != last1) {
        init = init + (*first1) * (*first2);
        // or: init = binary_op1 (init, binary_op2(*first1,*first2));
        ++first1;
        ++first2;
    }
    return init;
}

函数对象

使用时需要包含头文件：

#include <functional>

函数模板`function`

原型声明：

template <class T>
class function; // undefined
template <class Ret, class... Args>
class function<Ret(Args...)>;

function模板类是一种通用、多态的函数封装，C++11引入；
function模板类的实例可以存储、拷贝、调用任何可拷贝构造（CopyConstructible）、可调用（Callable）的目标实体，包括普通函数、函数指针、Lambda表达式、函数对象等；
未指向目标实体的function模板类实例称为空实例，在调用空实例时会抛出std::bad_function_call异常；

函数适配器辅助函数`bind`

原型声明：

template <class Fn, class... Args>
/* unspecified */ bind(Fn&& fn, Args&&... args);
template <class Ret, class Fn, class... Args>
/* unspecified */ bind(Fn&& fn, Args&&... args);

bind函数可以看做是一个通用的函数适配器（function adaptor）辅助函数，将一种函数对象转化为另一种符合要求的函数对象，C++11引入；
bind函数返回参数绑定的函数对象，参数可以绑定到一个值，也可以是一个占位符（placeholder）：
- 如果参数绑定到一个值，则调用返回的函数对象时始终使用该值作为参数；
- 如果参数是占位符，则调用返回的函数对象时会将调用参数转发（forward）给原函数对象；
- 占位符指定了调用参数在原函数对象参数列表中的顺序，使用_N表示原函数对象的第N个参数，例如：_1、_2；

转为常引用`cref`

原型声明：

template <class T>
reference_wrapper<const T> cref(const T& elem) noexcept;
template <class T>
reference_wrapper<const T> cref(reference_wrapper<T>& x) noexcept;
template <class T>
void cref(const T&&) = delete;

cref函数用于将值转为reference_wrapper类模拟的常引用，C++11引入；
reference_wrapper类可被拷贝构造（copy-constructible）和拷贝赋值（copy-assignable）；

转为引用`ref`

原型声明：

template <class T>
reference_wrapper<T> ref(T& elem) noexcept;
template <class T>
reference_wrapper<T> ref(reference_wrapper<T>& x) noexcept;
template <class T>
void ref(const T&&) = delete;

ref函数用于将值转为reference_wrapper类模拟的引用，C++11引入；
reference_wrapper类可被拷贝构造和拷贝赋值；

C++标准模板库学习笔记

STL Hello World

容器

容器基本功能

顺序容器

向量vector

顺序容器的适配器

顺序容器适配器的基本功能

栈stack

队列queue

关联容器

集合set

映射map

无序关联容器

无序集合unordered_set

无序映射unordered_map

算法

算法分类

不可变序列算法

遍历函数for_each()

可变序列算法

排序和搜索算法

排序函数sort()

数值算法

求和函数accumulate()

部分和函数partial_sum()

相邻差函数adjacent_difference()

内积函数inner_product()

函数对象

函数模板function

函数适配器辅助函数bind

转为常引用cref

转为引用ref

参考

向量`vector`

栈`stack`

队列`queue`

集合`set`

映射`map`

无序集合`unordered_set`

无序映射`unordered_map`

遍历函数`for_each()`

排序函数`sort()`

求和函数`accumulate()`

部分和函数`partial_sum()`

相邻差函数`adjacent_difference()`

内积函数`inner_product()`

函数模板`function`

函数适配器辅助函数`bind`

转为常引用`cref`

转为引用`ref`