C++ STL 教程

---

希望您已经理解了我们之前讨论过的 C++ 模板的概念。C++ STL（标准模板库）是一套强大的 C++ 模板类，它使用模板提供通用类和函数，实现了许多流行且常用的算法和数据结构，例如向量、列表、队列和栈。

C++ 标准模板库的核心是以下三个结构良好的组件：

我们将在下一章讨论 C++ 标准库时讨论所有三个 C++ STL 组件。现在，请记住所有三个组件都有一套丰富的预定义函数，这些函数可以帮助我们以非常简单的方式完成复杂的任务。

示例

让我们来看以下程序，它演示了 vector 容器（一个 C++ 标准模板），它类似于数组，区别在于它在增长时会自动处理自己的存储需求：

#include <iostream>
#include <vector>
using namespace std;
 
int main() {

   // create a vector to store int
   vector<int> vec; 
   int i;

   // display the original size of vec
   cout << "vector size = " << vec.size() << endl;

   // push 5 values into the vector
   for(i = 0; i < 5; i++) {
      vec.push_back(i);
   }

   // display extended size of vec
   cout << "extended vector size = " << vec.size() << endl;

   // access 5 values from the vector
   for(i = 0; i < 5; i++) {
      cout << "value of vec [" << i << "] = " << vec[i] << endl;
   }

   // use iterator to access the values
   vector<int>::iterator v = vec.begin();
   while( v != vec.end()) {
      cout << "value of v = " << *v << endl;
      v++;
   }

   return 0;
}

当以上代码编译并执行时，会产生以下结果：

vector size = 0
extended vector size = 5
value of vec [0] = 0
value of vec [1] = 1
value of vec [2] = 2
value of vec [3] = 3
value of vec [4] = 4
value of v = 0
value of v = 1
value of v = 2
value of v = 3
value of v = 4

以下是一些关于我们在上述示例中使用的各种函数需要注意的事项：

• push_back() 成员函数在向量的末尾插入值，根据需要扩展其大小。
• size() 函数显示向量的尺寸。
• begin() 函数返回指向向量开头的迭代器。
• end() 函数返回指向向量末尾的迭代器。

C++ 标准模板库组件

C++ 标准模板库的核心是以下四个结构良好的组件：

• 容器
• 算法
• 迭代器
• 仿函数（函数对象）

容器

容器是用于存储和管理数据或对象集合（例如向量、列表、集合和映射）的数据结构。在这里，我们将看到几种类型的容器。

1. 顺序容器

它们是按特定线性顺序存储元素的容器。它们允许直接访问元素以及管理元素顺序和排列的功能。

• 数组 − 这些是固定大小的元素集合。
• 向量 − 它是一个动态数组，可以根据需要调整其大小。
• 双端队列 − 双端队列，允许在两端快速插入和删除。
• 列表 − 一个双向链表，允许双向迭代。
• 前向列表 − 它是一个单向链表，允许高效插入和删除，但只能单向遍历。
• 字符串 − 在 C++ 中，字符串也被认为是顺序容器，它被实现为字符的动态数组，其行为类似于其他顺序容器。

2. 关联容器

它以排序的顺序存储元素，允许根据键快速检索。这些容器以键值对结构工作，其中每个元素都与一个唯一的键关联。此键用于快速访问相应的键值。

• 集合 − 它是一个按特定顺序排序的唯一元素的集合。
• 映射 − 它是一组键值对，其中键是唯一的。
• 多重集 − 它类似于集合，但允许重复元素。
• 多重映射 − 它类似于映射，但允许重复键。

3. 无序关联容器

它以无序的方式存储元素，允许根据键高效访问、插入和删除。它们不维护元素的排序顺序，而是使用哈希来组织数据。

• 无序集合 − 它是一组唯一的元素，没有任何特定顺序。
• 无序映射 − 它是一组键值对，没有任何特定顺序。
• 无序多重集 − 它允许重复元素，没有任何特定顺序。
• 无序多重映射 − 它允许重复键，没有任何特定顺序。

4. 容器适配器

它为现有容器提供不同的接口。

• 栈 − 它是一种遵循后进先出 (LIFO) 原则的数据结构。
• 队列 − 它是一种遵循先进先出 (FIFO) 原则的数据结构。
• 优先级队列 − 它是一种特殊的队列，其中元素根据优先级删除。

算法

C++ 标准模板库 (STL) 中的算法是一个大型函数集合，专门设计用于对容器执行操作。其中，这些算法使用迭代器来遍历容器，而无需了解其内部结构。

非修改顺序算法

• for_each − 它应用于查找范围内的每个元素的函数。
• count − 它计算范围内某个值的出现次数。
• find() − 它查找范围内某个值的第一次出现。
• find_if − 它查找满足谓词的第一个元素。
• find_if_not − 它查找不满足谓词的第一个元素。
• equal − 它检查两个范围是否相等。
• search − 它在一个序列中搜索子序列。

1. 修改顺序算法

• copy() − 它将元素从一个范围复制到另一个范围。
• copy_if − 它将满足谓词的元素复制到另一个范围。
• copy_n − 它将特定数量的元素从一个范围复制到另一个范围。
• move − 它将元素从一个范围移动到另一个范围。
• transform() − 它将函数应用于范围并存储结果。
• remove − 它从范围内删除具有特定值的元素。
• remove_if − 它删除满足谓词的元素。
• unique − 它删除连续的重复元素。
• reverse() − 它反转范围内元素的顺序。
• swap() − 它交换元素。

2. 排序算法

• sort − 它对范围内的元素进行排序。
• stable_sort − 它对元素进行排序，同时保持等效元素的相对顺序。
• partial_sort − 它对范围的一部分进行排序。
• nth_element − 它对范围进行分区，以便第 n 个元素位于其最终位置。

3. 搜索算法

• binary_search − 它检查元素是否存在于排序范围内。
• lower_bound − 它搜索可以插入元素以保持顺序的第一个位置。
• upper_bound − 它搜索大于指定值的第一个元素的位置。
• binary_search − 它检查元素是否存在于排序范围内。
• lower_bound − 它查找可以插入元素以保持顺序的第一个位置。
• upper_bound − 它搜索大于指定值的第一个元素的位置。
• equal_range − 它返回相等元素的范围。

4. 堆算法

• make_heap − 从一个区间创建堆。
• push_heap − 向堆中添加一个元素。
• pop_heap − 从堆中删除最大元素。
• sort_heap − 对堆中的元素进行排序。

5. 集合算法

• set_union − 计算两个集合的并集。
• set_intersection − 计算两个集合的交集。
• set_difference − 计算两个集合的差集。
• set_symmetric_difference − 计算两个集合的对称差集。

6. 数值算法

• accumulate − 计算一个区间的和（或其他操作）。
• inner_product − 计算两个区间的内积。
• adjacent_difference − 计算相邻元素之间的差。
• Partial_sum − 计算一个区间的部分和。

7. 其他算法

• generate − 使用函数生成的值填充一个区间。
• shuffle − 随机打乱一个区间内的元素。
• partition − 根据谓词将元素划分为两组。

迭代器

C++ 标准模板库 (STL) 中的迭代器是充当容器内元素指针的对象，它提供了一个统一的接口来访问和操作数据。它们充当算法和容器之间的桥梁。

• 输入迭代器 − 允许只读访问元素。
• 输出迭代器 − 允许只写访问元素。
• 前向迭代器 − 允许读写，可以递增。
• 双向迭代器 − 可以递增和递减。
• 随机访问迭代器 − 支持算术运算，可以直接访问元素。

函数对象（仿函数）

C++ 中的仿函数（或函数对象）是可以像函数一样调用的对象。它可以像普通函数一样被调用。此功能是通过重载函数调用运算符()来实现的。

在这里，您将根据它们执行的操作探索不同类型的仿函数。

1. 算术仿函数

在 C++ 中，算术运算符用于执行基本的数学运算。以下是常见的算术运算符以及示例。

• 加法 (+) − 将两个值组合起来以产生它们的和。
• 减法 (-) − 计算两个值之间的差。
• 乘法 (*) − 将两个值相乘以产生它们的积。
• 除法 (/) − 将一个值除以另一个值，得到商。
• 模 (%) − 返回一个值除以另一个值的余数。
• 取反 (-) − 返回参数的取反值。

2. 比较仿函数

比较仿函数用于比较值，尤其是在容器中进行排序或搜索时。

• 小于 (<) − 比较并返回第一个值是否小于第二个值。
• 大于 (>) − 比较并返回第一个值是否大于第二个值。
• 小于等于 (≤) − 比较并返回第一个值是否小于等于第二个值。
• 大于等于 (≥) − 比较并返回第一个值是否大于等于第二个值。
• 等于 (=) − 比较并返回两个值是否相等。
• 不等于 (≠) − 比较并返回两个值是否不相等。

3. 逻辑仿函数

逻辑仿函数执行逻辑运算，在涉及布尔逻辑的场景中可能很有用。

• 逻辑与仿函数 (&&) − 如果两个布尔参数中至少有一个或两个为假，则返回假，否则返回真。
• 逻辑或仿函数 (||) − 如果两个布尔参数中至少有一个或两个为真，则返回真。
• 逻辑非仿函数 (!) − 如果布尔参数为假则返回真，反之亦然，它返回提供布尔值的相反值。

4. 位运算仿函数

• bit_and − 对两个操作数执行按位与运算。
• bit_or − 对两个操作数执行按位或运算。
• Bit_xor − 对两个操作数执行按位异或 (XOR) 运算，并返回相应的输出。

实用工具

实用工具是指一系列通用组件，它们在编程中提供基本功能，并允许对数据和类型进行高效操作。

1. 对和元组

• pair − 它是一个容器，包含两个可能不同类型的值，作为第一个和第二个成员。
• tuple − 一个固定大小的集合，可以存储多种不同类型的多个值，可以通过 std::get 访问每个元素。

2. 智能指针

• unique_ptr − 它是一个智能指针，拥有一个动态分配的对象，当指针超出范围时会自动释放它。
• Shared_ptr − 它是一个智能指针，允许多个指针共享一个动态分配对象的拥有权，通过使用引用计数来管理生命周期。
• Weak_ptr − 它是一个智能指针，提供对由 std::shared_ptr 管理的对象的非拥有引用，这可以防止循环引用。

3. 可选、变体和任何类型 (C++17)

• Optional − 它是一个包装器，表示一个可选的值，指示值是否存在。
• variant − 它是一个类型安全的联合，可以保存多个指定类型之一，提供了一种在不产生歧义的情况下处理多种类型的方法。
• any − 它是一个类型安全的容器，用于存储任何类型的值，允许动态类型擦除和运行时类型检查。

4. 内存管理和数值限制

• allocator − 用于管理动态内存。
• numeric_limits − 提供有关基本数据类型属性的信息。

5. 类型特征

它是一组模板，允许您执行编译时类型检查。

• is_same − 它是一个类型特征，检查两个类型是否相同，如果相同则返回真，否则返回假。
• is_integral − 它是一个类型特征，确定给定类型是否为整型（例如，int、char、long），对于整型返回真，对于其他类型返回假。
• is_floating_point − 它是一个类型特征，检查给定类型是否为浮点类型（例如，float、double、long double），对于浮点类型返回真，对于非浮点类型返回假。
• enable_if − 它是一个实用工具，根据编译时条件启用或禁用模板实例化，通常用于 SFINAE（替换失败不是错误）。

基本 STL 功能：简单示例

这是一个演示一些基本 STL 功能的简单示例

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
   std::vector<int> vec = {5, 2, 8, 1, 3};

   // Sorting the vector
   std::sort(vec.begin(), vec.end());

   // Displaying sorted elements
   std::cout << "Sorted vector: ";
   for (int num : vec) {
      std::cout << num << " ";
   }
   std::cout << std::endl;

   // Finding an element
   auto it = std::find(vec.begin(), vec.end(), 3);
   if (it != vec.end()) {
      std::cout << "Element 3 found at position: " 
         << std::distance(vec.begin(), it) << std::endl;
   } else {
      std::cout << "Element 3 not found" << std::endl;
   }

   return 0;
}

输出

Sorted vector: 1 2 3 5 8 
Element 3 found at position: 2

解释

此代码在多个地方提供了 STL 的使用，

• std::vector<int> vec − 上述程序使用了 std::vector，它是一个 STL 容器，允许动态数组管理。
• std::sort(vec.begin(), vec.end()) − 此函数是 STL 算法的一部分，它作用于容器，按升序对向量的元素进行排序。
• std::find(vec.begin(), vec.end(), 3) − 此函数在向量中搜索值 3，如果找到则返回指向它的迭代器。
• begin() 和 vec.end() − 这些函数分别返回指向向量开头和向量末尾之后的迭代器。
• std::distance(vec.begin(), it) − 此函数计算两个迭代器之间的元素数量（在本例中，从向量的开头到找到的迭代器），有效地给出找到的元素的索引。

使用 STL 的好处

在 C++ 中使用标准模板库 (STL) 有很多好处，因为它提供了一个庞大的预定义数据结构和算法集合，从而节省了时间和精力，减少了从头实现这些结构和算法的需要。它还促进了代码重用、模块化、类型安全和灵活性。这使得相同的代码可以与不同的数据类型一起工作。总的来说，它提高了编程效率和代码质量。