STL 六大组件

C++ STL（标准模板库）主要由六大组件构成，它们相互协作，为C++程序员提供了功能强大且高效的通用数据结构和算法工具，以下是对这六大组件的详细介绍：

1. 容器（Containers）

• 概述：
  容器是用于存储和管理数据元素的对象，它们提供了不同的数据组织方式以及相应的操作接口，以满足各种不同的编程需求。就像是现实生活中的各种容器（如箱子、柜子等）用来存放不同物品一样，C++ STL中的容器用来存放各种类型的数据，并且每种容器都有其独特的特性，例如在元素访问效率、插入删除元素的效率、内存管理方式等方面各有差异。
• 常见容器类型及特点：
  • 顺序容器（Sequential Containers）：
    • vector：可以看作是一个动态大小的数组，它内部使用连续的内存空间来存储元素，支持快速的随机访问（通过下标运算符 [] 或者 at 函数访问元素时间复杂度为常数时间 O(1)），在末尾添加和删除元素（push_back 和 pop_back 操作）通常比较高效，但在中间或开头插入删除元素相对较慢（时间复杂度为 O(n)，n 为元素个数），会自动管理内存分配和扩容等操作，适合需要频繁随机访问以及在末尾进行元素操作的场景，比如存储一组同类型的数据记录等。
    • list：是一个双向链表结构的容器，元素在内存中不是连续存储的，它的优势在于可以在任意位置快速插入和删除元素（时间复杂度为 O(1)），但随机访问效率较低（需要遍历链表，时间复杂度为 O(n)），适用于需要频繁在中间进行插入删除操作，而对随机访问要求不高的情况，例如实现一个可以动态调整顺序的任务列表等。
    • deque（双端队列）：它结合了 vector 和 list 的一些特点，既能在两端高效地插入和删除元素（时间复杂度接近 O(1)），也支持一定程度的随机访问（不过效率比 vector 稍低些），内部通常是分段连续存储结构，适合那种需要在两端频繁操作元素同时又偶尔有随机访问需求的场景，比如排队系统中对队列两端元素的处理等。
  • 关联容器（Associative Containers）：
    • set：是一种集合容器，它内部会根据元素的值自动进行排序（默认按照小于比较运算符 < 来确定元素顺序），并且保证每个元素的唯一性，不允许有重复元素存在，适合用于快速查找某个元素是否存在以及遍历有序的元素集合等场景，例如存储一些不重复的关键词，方便后续判断某个关键词是否在集合中。
    • multiset：与 set 类似，但允许存在重复元素，同样会对元素进行排序，常用于需要统计某个元素出现次数或者处理存在重复情况的有序数据集合，比如统计一篇文章中每个单词出现的频次等场景（单词作为元素，相同单词可以重复出现）。
    • map：是一种键值对形式的关联容器，每个元素由一个键（key）和一个值（value）组成，内部会根据键的大小自动排序，通过键可以快速查找对应的值（时间复杂度通常为 O(log n)，n 为元素个数），常用于建立映射关系，比如将学生的学号作为键，学生的成绩等信息作为值，方便通过学号快速查询成绩情况。
    • multimap：类似于 map，但允许键重复，也就是一个键可以对应多个不同的值，适用于需要一个键关联多个相关值的场景，比如一个图书分类（键）对应多本不同的图书（值）这种情况。
  • 容器适配器（Container Adapters）：
    • stack：它是基于其他容器（默认通常是 deque，也可以指定为 vector 或 list）实现的适配器，模拟了栈这种后进先出（LIFO）的数据结构，提供了 push（入栈）、pop（出栈）、top（获取栈顶元素）等操作，常用于实现函数调用栈、表达式求值等符合栈操作逻辑的场景。
    • queue：同样基于其他容器实现，模拟了队列这种先进先出（FIFO）的数据结构，有 push（入队）、pop（出队）、front（获取队首元素）等操作，常见于处理需要按照先后顺序依次处理元素的情况，比如任务排队等待执行等场景。
    • priority_queue：基于堆数据结构实现（底层容器默认一般是 vector），它会按照元素的优先级来排序，每次出队的是优先级最高的元素，常用于需要根据某种优先级来处理任务或者数据的场景，比如操作系统中的进程调度，按照进程优先级来决定哪个进程先执行。

2. 算法（Algorithms）

• 概述：
  STL 中的算法是一组通用的、独立于具体容器的函数模板，它们实现了各种常见的数据处理操作，如排序、查找、遍历、复制、变换等功能，可以作用于不同类型的容器或者容器的部分区间上，大大提高了代码的复用性和编程效率，程序员无需自己从头实现这些常见的数据处理逻辑。
• 常见算法分类及示例：
  • 排序算法：
    • std::sort：是一种快速排序的变体，用于对给定区间内的元素进行排序，可以应用于各种支持随机访问迭代器的容器（如 vector、array 等），它的平均时间复杂度为 O(n log n)，在实际使用中效率较高，例如对一个存储整数的 vector 进行排序：std::vector<int> numbers = {5, 3, 1, 4, 2}; std::sort(numbers.begin(), numbers.end());，执行后 numbers 中的元素就会按照从小到大的顺序排列。
    • std::stable_sort：与 std::sort 类似，但它保证相等元素的相对顺序在排序前后不会改变，属于稳定排序算法，不过通常在性能上可能比 std::sort 稍慢一点，适用于对排序后相等元素顺序有严格要求的场景，比如对学生成绩列表排序，如果成绩相同希望按照学号顺序保持先后关系，就可以用 std::stable_sort。
  • 查找算法：
    • std::find：用于在给定区间内查找指定元素，返回指向第一个匹配元素的迭代器，如果没找到则返回区间末尾的迭代器，例如在一个 vector 中查找某个整数：std::vector<int> vec = {1, 2, 3, 4}; auto it = std::find(vec.begin(), vec.end(), 3); if (it!= vec.end()) { std::cout << "找到了元素" << std::endl; }，通过判断返回的迭代器是否不等于区间末尾迭代器来确定是否找到元素。
    • std::binary_search：前提是区间内的元素已经是有序的，它采用二分查找的方式快速查找指定元素是否存在，返回布尔值表示是否找到，相比 std::find 在有序区间上查找效率更高（时间复杂度为 O(log n)），比如：std::vector<int> sortedVec = {1, 2, 3, 4}; bool found = std::binary_search(sortedVec.begin(), sortedVec.end(), 3);。
  • 遍历算法：
    • std::for_each：可以对给定区间内的每个元素执行一个指定的函数（通常以函数对象、lambda表达式或者普通函数指针形式提供），例如对一个 vector 中的每个元素进行打印输出：std::vector<int> elements = {1, 2, 3}; std::for_each(elements.begin(), elements.end(), [](int element) { std::cout << element << " "; });，通过 lambda 表达式实现了对每个元素的打印操作，输出为 1 2 3。
  • 变换算法：
    • std::transform：可以根据给定的操作规则对区间内的元素进行变换，将变换后的结果存放到另一个区间或者覆盖原区间元素（取决于使用方式），例如将一个 vector 中的每个整数都乘以2：std::vector<int> source = {1, 2, 3}; std::vector<int> destination(source.size()); std::transform(source.begin(), source.end(), destination.begin(), [](int num) { return num * 2; });，执行后 destination 向量中的元素就变为 2, 4, 6，实现了对原元素的变换操作。

3. 迭代器（Iterators）

• 概述：
  迭代器可以看作是一种抽象的指针，它提供了一种统一的方式来遍历容器中的元素，隐藏了不同容器内部数据结构的差异，使得算法能够以一种通用的方式作用于各种容器。就好比不同的交通工具（对应不同容器），而迭代器就是统一的驾驶操作方式，让你能按照一定规则去访问它们里面的“乘客”（元素），无论容器内部是数组结构、链表结构还是其他复杂结构，都可以通过迭代器实现顺序访问、随机访问等操作。
• 迭代器类型及功能：
  • 输入迭代器（Input Iterators）：
    它支持读取容器中的元素，并且可以进行一次遍历操作（通常用于从容器中读取数据的单向操作，比如从输入流读取数据到容器中时可能用到），支持 ++（自增操作，用于移动到下一个元素位置）、*（解引用操作，获取当前位置元素的值）、== 和 !=（用于比较两个迭代器是否相等）等基本操作，但不支持多次遍历以及元素修改等操作。例如在使用 std::istream_iterator 从标准输入流读取数据到一个容器时就用到了输入迭代器的特性。
  • 输出迭代器（Output Iterators）：
    主要用于向容器中写入元素，也是单向操作，支持 ++（自增操作，移动到下一个可写入位置）以及 *（解引用操作，用于在当前位置写入元素）等基本操作，常用于将算法产生的结果输出到容器中，比如使用 std::ostream_iterator 将容器中的元素输出到标准输出流时的操作体现了输出迭代器的功能。
  • 前向迭代器（Forward Iterators）：
    在前述输入迭代器的基础上，增加了可以多次遍历同一区间以及可修改元素的功能，也就是在一个有效的迭代器区间内，可以多次通过 ++ 操作遍历所有元素，并且能对元素进行修改赋值等操作，例如在一些单向链表结构的容器遍历以及修改元素时会用到这种迭代器类型。
  • 双向迭代器（Bidirectional Iterators）：
    在正向迭代器基础上，还支持 --（自减操作，用于反向移动到前一个元素位置），使得可以双向遍历容器中的元素，像 list 容器的迭代器就是双向迭代器，方便在链表中向前或向后访问元素。
  • 随机访问迭代器（Random Access Iterators）：
    它提供了最全面的功能，除了具备双向迭代器的所有功能外，还支持像指针那样的算术运算（如 +、-、+=、-= 等）以及通过下标形式访问元素（例如 it[n] 等价于 *(it + n)），可以快速随机地访问容器中的任意元素，像 vector、array 等容器的迭代器就是随机访问迭代器类型，这使得对这些容器元素的访问操作非常灵活高效。

4. 函数对象（Function Objects）

• 概述：
  函数对象也叫仿函数（Functors），它本质上是一个类，不过这个类重载了 () 运算符（函数调用运算符），使得类的对象可以像函数一样被调用，在STL算法等场景中可以作为一种可调用的实体来替代普通函数或者函数指针，并且具有一些普通函数不具备的优势，比如可以携带状态（通过类的成员变量来记录信息等）。
• 示例及优势体现：
  例如，定义一个简单的函数对象用于计算整数的平方：

class Square {
public:
    int operator()(int num) const {
        return num * num;
    }
};

在使用 std::transform 算法时就可以这样用：

std::vector<int> numbers = {1, 2, 3};
std::vector<int> squaredNumbers(numbers.size());
std::transform(numbers.begin(), numbers.end(), squaredNumbers.begin(), Square());

这里 Square 类的对象就像一个函数一样被传递给 std::transform 算法，用于对 numbers 向量中的每个元素进行求平方的操作，计算结果存放到 squaredNumbers 向量中。

函数对象的优势在于它可以有自己的内部状态，比如可以修改上面的 Square 类，添加一个成员变量用于记录调用次数：

class SquareWithCount {
public:
    SquareWithCount() : count(0) {}
    int operator()(int num) {
        count++;
        return num * num;
    }
    int getCount() const { return count; }
private:
    int count;
};

在多次使用这个函数对象后，可以通过 getCount 函数获取它被调用的次数，这种记录状态的功能是普通函数很难方便实现的，在一些需要统计操作次数、根据之前操作结果影响后续操作等场景中，函数对象就非常有用。

5. 适配器（Adapters）

• 概述：
  适配器在STL中有多种含义和应用场景，总体来说它是一种用于改变其他组件接口或者行为，使其能适配不同需求的机制。比如将一种容器适配成另一种数据结构的行为模式（如前面提到的容器适配器把底层容器包装成栈、队列等数据结构），或者将一种函数对象的参数类型、返回类型等进行调整以适应特定算法的要求等情况都属于适配器的应用范畴。
• 不同类型适配器及示例：
  • 容器适配器（Container Adapters）：
    前面已经介绍过 stack、queue、priority_queue 这些基于其他容器实现的容器适配器，它们通过对底层容器的接口进行限制和包装，对外呈现出符合栈、队列、优先级队列这些数据结构特点的操作接口，方便程序员在需要相应数据结构时直接使用，无需关心底层具体是如何基于别的容器实现的。例如创建一个 stack：std::stack<int> myStack;，默认它是基于 deque 实现的，我们可以直接使用 myStack.push(5);（入栈操作）、myStack.pop();（出栈操作）等符合栈操作逻辑的接口，无需了解底层的 deque 具体细节。
  • 迭代器适配器（Iterator Adapters）：
    可以对原始迭代器进行功能扩展或者改变其行为，例如 std::reverse_iterator 就是一种迭代器适配器，它可以将普通的正向迭代器转换为反向迭代器，实现从后往前遍历容器的功能。比如对于一个 vector：std::vector<int> vec = {1, 2, 3}; std::vector<int>::reverse_iterator rit = vec.rbegin();，通过 rbegin 函数获取到反向迭代器 rit，然后可以通过 ++rit 操作从后往前遍历 vec 中的元素，输出为 3 2 1，这就是利用迭代器适配器改变了迭代器的遍历方向。
  • 函数适配器（Function Adapters）：
    用于调整函数对象的参数个数、顺序、类型等，或者组合多个函数对象来实现更复杂的功能。例如 std::bind 就是一种常用的函数适配器，它可以绑定函数对象或者普通函数的部分参数，生成一个新的可调用对象，改变原函数的调用方式。假设有函数 void printSum(int num1, int num2) { std::cout << num1 + num2 << std::endl; }，可以通过 std::bind 绑定第一个参数为固定值：auto newFunction = std::bind(printSum, 5, std::placeholders::_1);，这里 newFunction 就是一个新的可调用对象，调用它时只需要传入一个参数（对应原来的第二个参数），就像 newFunction(3); 会输出 8，通过函数适配器实现了对原函数调用方式的改变和参数绑定功能。

6. 空间配置器（Allocators）

• 概述：
  空间配置器负责管理容器中元素的内存分配和释放工作，它是STL中相对底层但又非常关键的一个组件，不同的空间配置器可以采用不同的内存分配策略，比如如何从系统堆中获取内存、如何管理内存块的复用、如何提高内存分配效率等，其目的是在满足容器对内存需求的同时，优化内存使用，减少内存碎片等问题，不过在日常简单的编程中，很多时候我们使用的是默认的空间配置器，不太会直接感知到它的存在和具体操作。
• 作用及应用场景示例：
  例如，当创建一个 vector 容器时，它需要不断地分配和释放内存来适应元素个数的变化（如扩容和缩容操作），空间配置器就在背后默默地工作，决定如何去获取合适大小的内存块，以及在删除元素释放内存时如何处理这块内存（是立即归还给系统堆还是保留备用等）。如果开发一个对内存使用效率要求极高、内存资源非常有限的嵌入式系统应用，可能就需要自定义空间配置器，采用特定的内存分配算法。

原文地址：https://blog.csdn.net/doubleintfloat/article/details/144708335

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！