Post

一文看懂C++标准库

Posted
By Evan
27 min read
一文看懂C++标准库

标准模板库（standard template library，STL）是基于泛型编程的，即C++官方通过函数模板和类模板提前写好大量通用的数据类型和算法，并内置在支持C++的编译器中，以方便程序员开发软件时快速调用，而不必关注具体的数据类型。STL是容器（即类模板）的集合，这些容器在算法库的支持下使程序开发变得简单、高效。STL无须额外安装，使用起来非常方便。

以在C++中定义一个数组为例，如果使用传统方法，需要先声明数组的大小，然后定义数组：

1

int arr[10];

这种定义数组的方法需要事先知道数组的长度，因为n必须为常量。如果无法确定数组长度，就需要将数组长度设为可能的最大值，这会导致存储空间的极大浪费。为了解决这个问题，还可以采用在堆空间中动态申请内存的方法：

1

int *arr = new int[10];  // 在堆空间中申请10个int类型的内存

这种方法虽然解决了数组长度不确定的问题，但如果程序执行过程中出现空间不足的情况，需要加大存储空间时，就需要进行如下4步操作。

1
2
3
4

int *temp = new int[20];  // 重新申请20个int类型的内存
memcpy(temp, arr, 10 * sizeof(int));  // 将arr中的数据复制到temp中
delete[] arr;  // 释放arr的内存
arr = temp;  // 将temp的地址赋值给arr

如果使用STL，上面的操作会简单很多，只需要定义一个可以动态存储数据的容器vector，不用再关心内存操作细节。

1
2
3
4
5
6
7
8

vector<int> arr;
for (int i = 0; i < 10; i++) {
    arr.push_back(i);
}
arr.resize(20);  // 重新申请20个int类型的内存
arr[19] = 19;
arr.pop_back();  // 删除最后一个元素
arr.resize(10, -1);  // 将arr的大小调整为10，并将所有元素设置为-1

常见的数据结构

  • 数组：最典型的线性结构，其基本特点是数据元素是有限且有序的。数组会为每个存储的元素分配一个下标（索引），此下标从0开始，连续自增，通过数组名和下标可快速访问所有的元素。数组中，各元素在内存中是连续存放的，因此可通过数组名（或指针）和偏移量快速访问任意一个元素，但添加和删除数据却比较麻烦和耗时。因此，数组结构适用于需要频繁查询数据，但对存储空间要求不大，数据增、删操作较少的情况。
  • 栈：一种特殊的线性结构，数据的存储和访问仅能在线性表的一端（即栈顶）进行，栈底则不允许操作。栈的结构特点决定了其数据进出顺序为后进先出（LIFO）。栈不擅长在随机位置插入和删除对象（需要借助其他方法才能实现），比较耗时。若存储的对象超过自身容量，会发生栈溢出。
  • 队列：一种特殊的线性结构，数据的存储和访问仅能在线性表的一端（即队尾）进行，另一端（即队头）则不允许操作。队列的结构特点决定了其数据进出顺序为先进先出（FIFO）。
  • 链表：一种非连续、非顺序的线性结构，由一系列结点组成。第一个元素的位置由头指针（head）给出，其后每个结点中都含有数据部分和指针部分，通过指针可访问下一个元素，链表尾部结点的指针指向空（NULL）。链表的存储空间是随机、分散的，无法通过索引快速定位元素，只能通过遍历自身找到元素，因此查找元素效率较低。
  • 树：是一种由多个结点组成的具有层次关系的集合，根结点在上，叶结点在下，所有结点都可用来存储数据。二叉树中，每个结点最多有两个子结点，左子树和右子树是有顺序的，次序不能颠倒。使用二叉树添加和删除数据都非常快，查找数据方面也有很多优化的算法。所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
  • 图：一种复杂的非线性数据结构，可表示多对多的数据关系。图由顶点和边组成，每条边连接一对顶点。根据边是否具有方向，可将图分为有向图和无向图。
  • 哈希表：一种先建立映射关系，然后通过关键字访问其对应值的数据结构。哈希表中数据以键值对的形式存储。通过哈希函数，将键（key）映射为一个固定大小的数组索引，将值（value）存储在以该数字为下标的数组空间里。这种存储方式可以充分利用数组的优势来查找元素。散列表的关键是哈希函数的设计。散列表支持高效的数据插入、查找和删除操作。

STL容器与迭代器

C++ STL有六大组件：容器、算法、迭代器、函数对象、适配器和记忆体配置器。其中最重要的是前3个组件：容器、算法和迭代器。

  • 容器（container）：用于存放数据的类模板，STL就是各类容器的集合。
  • 算法（algorithm）：对容器中元素进行操作的函数模板。STL提供了大量算法，可对数据进行查找、排序、遍历、复制、替换、删除、去重等。这些算法具有高度的通用性和可扩展性，可适用于不同类型的容器和元素。
  • 迭代器（iterator）：遍历容器中元素的类模板。可将迭代器看作是指针，它可以指向容器中的元素，并支持自增、自减、解除引用等操作。

容器

容器就是存放数据的类模板。STL中的容器分为两类，即序列式容器和关联式容器。

序列式容器

序列式容器采用线性结构存储数据，其中可存储基本数据类型（如int、double、float、string等）或结构体类型的元素。序列式容器不会自动对存储的元素按值进行排序，也就是说其元素大小是无序的。将元素插入序列式容器中时，指定什么位置，元素就会位于什么位置。

序列式容器包括：

  1. array：数组。以类模板array<T,N>的形式定义，是一个内存长度固定、由N个T类型元素组成的容器。array对象一旦建立，其在内存中的长度就是固定不变的，不能增加和删除元素，只能改变某个元素的值。array对象使用的是一段连续的内存空间，因此可通过索引快速访问其中的任意一个元素，访问效率非常高。
  2. vector：向量，又称为动态连续数组。以类模板vector<T>的形式定义，是一个内存长度可变、由多个T类型元素组成的容器。vector对象中，在尾部插入和删除元素的效率非常高，在其他位置插入和删除元素的效率较低。插入和删除元素时，会动态调整占用的内存空间。
  3. deque：双端队列。以类模板deque<T>的形式定义，是一个内存长度可变、由多个T类型元素组成的容器。deque对象中，在头部和尾部插入和删除元素的效率都非常高，在其他位置插入和删除元素的效率较低。插入和删除元素时，会动态调整占用的内存空间。
  4. list：双向链表。以类模板list<T>的形式定义，是一个内存长度可变、由多个T类型元素组成的容器，元素的存储位置是随机、分散的（并非连续的内存空间），前后元素的顺序靠指针来维系。其每个元素都配备了两个指针，分别指向前一个元素和后一个元素，第一个元素的前向指针为null，最后一个元素的后向指针为null。list对象中，在任意位置插入和删除元素的效率都非常高，但访问元素的效率较低。
  5. forward_list：正向链表，是C++ 11中新增加的容器。以类模板forward_list<T>的形式定义，是一个内存长度可变、由多个T类型元素组成的容器，其底层实现和list容器非常接近，但每个元素只配备一个指针，指向其后一个元素（最后一个元素指向null）。同样，forward_list对象中，增加和删除元素效率较高，访问元素效率较低。forward_list容器比list容器更快、更节省内存。

关联式容器

关联式容器在存储元素值时，会为元素额外配备一个键，根据键（key）可快速锁定目标元素。也就是说，关联式容器存储的是表示某种对应关系的键值对（<key,value>），这是和序列式容器最大的不同。

关联式容器没有所谓的头、尾端，只有最大元素和最小元素。插入元素时，可根据其键值大小和容器的排序规则，直接将其放置于合适位置。查找、删除、修改元素时，可根据其键值快速定位到具体元素，执行相应的操作。在数据检索时比序列式容器效率更高。

pair类模板

pair类模板是C++ 11标准库中新增的模板类，，它有两个成员变量first和second，作用是创建“键值对”形式的元素<first, second>。pair类模板定义在头文件utility中。

1
2
3
4
5

template <class T1, class T2>
struct pair {
    T1 first;
    T2 second;
};

关联式容器包括：

  1. map：映射。一般情况下，map容器中存储的键值对都是string类型。map容器存储的键值对，键的值必须唯一，不能重复，也不能被修改。当map容器中存储了多个键值对时，会自动根据键的大小进行排序。默认情况下，排序规则为less，即根据键做升序排序。也可以设置为greater，即根据键做降序排序。其中，T为键的数据类型。
  2. multimap：多重映射，与map容器类似，不同之处在于multimap容器可以同时存储多个键相同的键值对，即键不要求唯一。
  3. set：集合，是一个内容自动有序且不含重复元素的容器。使用set容器存储的键值对，要求键（key）和值（value）必须相等。　存储数据时，自动根据元素值的大小进行排序，默认为升序排序。存储到set容器中的元素，元素值无法修改。存储的元素必须互不相等。
  4. multiset：多重集合，和set容器相似，区别在于它可以存储多个值相同的元素。

C++ 11标准库又加入了4种无序关联式容器，即哈希容器。其中的元素是未排序的，元素位置由哈希函数确定。哈希容器包括如下4类。

  1. unordered_map：哈希映射。
  2. unordered_multimap：哈希多重映射。
  3. unordered_set：哈希集合。
  4. unordered_multiset：哈希多重集合。

容器适配器

容器适配器主要针对序列式容器，它通过定义新的接口，将不适用的容器变为适用的容器。这有点类似于生活中的电源适配器，将不兼容（如不同电压标准）的电源转换为适合的电源。

常见的容器适配器如下：

  1. stack：栈。
  2. queue：队列。
  3. priority_queue：优先级队列。

迭代器

访问容器中的元素需要通过迭代器。迭代器可以指向容器中的某个元素，进而读写该元素的值。从这一点上看，迭代器和指针非常类似。迭代器分为如下5种。

  • 输入迭代器：又称为只读迭代器，它从容器中读取元素，一次只能读入一个元素并向前移动。只支持一遍算法，即同一个输入迭代器不能遍历一个序列两次。
  • 输出迭代器：又称为只写迭代器，它往容器中写入元素，一次只能写入一个元素并向前移动。同一个输出迭代器不能遍历一个序列两次。
  • 正向迭代器：组合了输入迭代器和输出迭代器的功能，且可以多次解析一个迭代器指定位置，可以对一个值进行多次读/写。
  • 双向迭代器：组合了正向迭代器的功能，且可通过操作符向后移动位置。
  • 随机访问迭代器：组合了双向迭代器的功能，可以向前、向后跳过任意个位置，且可以直接访问容器中任意位置的元素。

不同容器对应的迭代器类型如下表所示：

容器类型对应的迭代器类型
array随机访问迭代器
vector随机访问迭代器
deque随机访问迭代器
list双向迭代器
map/multimap双向迭代器
set/multiset双向迭代器
forward_list正向迭代器
unordered_map/unordered_multimap正向迭代器
unordered_set/unordered_multiset正向迭代器
stack不支持迭代器
queue不支持迭代器

算法

STL中，算法是参数化一个或多个迭代器类型的函数模板，它与具体对象在容器中的位置无关。标准算法包括非修正序列算法、修正序列算法、排序算法和数值算法4类。

非修正序列算法

非修正序列算法是指不修改容器中元素的值，也不会改变元素的次序，如统计元素个数、查找某个元素等。

STL中，常用的非修正序列算法如下所示：

  1. count(first, last, value)：统计容器中等于指定值的元素个数。
  2. count_if(first, last, func)：统计容器中符合条件的元素个数。
  3. find(first, last, value)：查找容器中等于指定值的元素。
  4. find_if(first, last, func)：查找容器中符合条件的元素。
  5. find_first_of(first, last, first2, last2)：查找容器中第一个符合条件的元素。
  6. find_end_of(first, last, first2, last2)：查找容器中最后一个符合条件的元素。
  7. adjacent_find(first, last)：查找容器中相邻且重复的元素。
  8. search(first, last, first2, last2)：查找容器中子序列。
  9. for_each(first, last, func)：遍历容器中的每个元素。
  10. min_element(first, last)：查找容器中最小的元素。
  11. max_element(first, last)：查找容器中最大的元素。

修正序列算法

修正序列算法的有些操作会改变容器的内容。例如，用指定的值填充容器，或把容器的部分内容复制到同一容器的另一部分。

STL中，常用的修正序列算法如下所示：

  1. fill(first, last, value)：用指定值填充容器。
  2. fill_n(first, n, value)：用指定值填充容器中前n个元素。
  3. copy(first, last, result)：把容器中从first到last的元素复制到result中。
  4. copy_n(first, n, result)：把容器中从first开始的n个元素复制到result中。
  5. copy_backward(first, last, result)：把容器中从first到last的元素复制到result中，但复制顺序是从后往前。
  6. move(first, last, result)：把容器中从first到last的元素移动到result中。
  7. move_backward(first, last, result)：把容器中从first到last的元素移动到result中，但移动顺序是从后往前。
  8. generate(first, last, func)：用func函数生成容器中的元素。
  9. random_shuffle(first, last)：随机打乱容器中元素的顺序。
  10. remove(first, last, value)：删除容器中等于指定值的元素。
  11. replace(first, last, old_value, new_value)：把容器中等于old_value的元素替换为new_value。
  12. rotate(first, middle, last)：把容器中从first到middle的元素和从middle到last的元素进行交换。
  13. reverse(first, last)：把容器中从first到last的元素进行反转。
  14. swap(a, b)：交换a和b的值。
  15. swap_ranges(first1, last1, first2)：交换first1到last1和first2开头的元素序列。
  16. transform(first, last, result, func)：对容器中从first到last的元素进行func函数操作，并将结果保存到result中。
  17. unique(first, last)：删除容器中相邻且重复的元素。

排序算法

排序算法用于对容器中的元素进行排序。STL中，常用的排序算法如下所示：

  1. sort(first, last)：对容器中从first到last的元素进行排序，默认为升序。
  2. stable_sort(first, last)：对容器中从first到last的元素进行稳定排序，即值相同的元素位置不变。
  3. partial_sort(first, middle, last)：对容器中从first到last的元素进行部分排序，即只排序出位置middle的元素。
  4. partial_sort_copy(first, last, result_first, result_last)：对容器中从first到last的元素进行部分排序，并将结果保存到result_first到result_last中。
  5. nth_element(first, nth, last)：对容器中从first到last的元素进行排序，并将第nth个元素放在第nth位置。
  6. is_sorted(first, last)：判断容器中从first到last的元素是否已排序。
  7. is_sorted_until(first, last)：判断容器中从first到last的元素是否已排序，并返回第一个未排序的元素位置。
  8. merge(first1, last1, first2, last2, result)：合并两个有序序列，并存储到result中。

数值算法

数值算法用于对容器中的元素进行数值操作。STL中，常用的数值算法如下所示：

  1. accumulate(first, last, init)：累加求和，计算容器中从first到last的元素的和，初始值为init。
  2. inner_product(first1, last1, first2, init)：内积求和，两个容器中从first1到last1和first2到last2的元素两两相乘后再求和，初始值为init。
  3. partial_sum(first, last, result)：部分求和，计算容器中从first到last的元素的和，并存储到result中。
  4. adjacent_difference(first, last, result)：相邻差，容器中从first到last的元素两两求差，并存储到result中。
SWE
C++ STL 一文看懂
This post is licensed under CC BY 4.0 by the author.