C++ 标准库概览

作为一名 C++ 程序员，你最重要、也最常用的库，就是 C++ 标准库。正如它的名字所暗示的，这个库本身就是 C++ 标准的一部分，因此任何符合标准的编译器都应当附带它。标准库并不是一个铁板一块的整体，它由若干彼此不同的组件构成，其中有些你其实早就已经在使用了。你甚至可能一直以为它们属于语言核心本身。标准库中的所有类和函数，都定义在 std 命名空间，或者 std 的某个子命名空间中。

C++ 标准库的核心，是其泛型容器（containers）和算法（algorithms）。有些人仍然把这一部分称为 Standard Template Library，简称 STL，因为它最初确实源于一个名为 Standard Template Library 的第三方库，而那个库大量使用了模板。不过，STL 这个术语本身并不是 C++ 标准正式定义的术语，因此本书不采用这种叫法。标准库真正强大的地方，在于它以一种统一而高效的方式，提供了泛型容器与泛型算法，使得大多数算法都能作用于大多数容器，而无需关心容器中到底存放的是什么类型的数据。性能也是标准库非常重要的一项设计目标：它力图让标准库中的容器和算法至少不比手写代码慢，最好还能更快。

C++ 标准库还收录了大部分来自 C11 标准的 C 头文件，只不过名字做了调整。例如，原本 C 的 <stdio.h> 可以在 C++ 中通过包含 <cstdio> 来访问其功能。前者会把内容放到全局命名空间中；后者则放入 std 命名空间。当然，技术上前者也允许把内容放进 std 中，而后者也允许额外把内容放进全局命名空间。C11 的 <stdnoreturn.h>、<threads.h> 以及它们对应的 <c…> 版本，并不包含在 C++ 标准中。C11 的 <stdatomic.h> 从 C++23 起开始可用，但并没有提供与之对应的 <cstdatomic>。此外，C++17 弃用了以下这些 C 头文件，而 C++20 已将其移除：

<ccomplex> 和 <ctgmath>：应改用 <complex> 和/或 <cmath>。
<ciso646>、<cstdalign> 和 <cstdbool>：这些头文件在 C++ 中毫无意义，因为它们要么是空的，要么定义的是在 C++ 中本来就是关键字的宏。

C 头文件不保证可被 import。要访问其中定义的功能，请使用 #include，而不是 import。

如果一个 C++ 程序员想自称对语言足够熟悉，那么他理应了解标准库。与其自己去写和调试各种容器与算法，不如直接把标准库的容器与算法纳入你的程序中，这会为你节省难以估量的时间和精力。现在正是掌握标准库的时候。

作为标准库专题的第一章，本章会先给出一幅整体地图，帮助你从宏观层面理解标准库提供了哪些能力。接下来的若干章，会更深入地讨论标准库中的多个方面，包括容器、迭代器、泛型算法、预定义函数对象类、正则表达式、随机数生成等等。另外，第 25 章“定制与扩展标准库”还会专门讨论如何编写你自己的、符合标准库规范的算法与数据结构，以对标准库进行定制和扩展。

尽管本章及后续章节已经覆盖了大量内容，但标准库的规模依然远超本书所能穷尽的范围。阅读这些章节，可以帮你建立对标准库的整体理解，但你也要记住：书中不会逐一列出各个类提供的每一个成员函数与数据成员，也不会把所有算法的完整原型全部写出来。附录 C“标准库头文件”总结了标准库中的全部头文件。如果你需要最完整、最精确的参考信息，仍应查阅你惯用的标准库参考资料。

编码原则

标准库大量使用了两项 C++ 特性：模板（templates）和 运算符重载（operator overloading）。

模板的使用

模板的存在，是为了支持 泛型编程（generic programming）。它让你能够编写一种代码，这种代码不仅能处理你当前已经知道的对象类型，也能处理那些在写代码时尚未知晓的类型。编写模板代码的程序员，其职责是明确说明“这些对象所属类必须满足哪些要求”，例如它们需要支持比较运算符、拷贝构造函数，或者其他被视为必要的能力；然后确保模板代码只依赖这些已声明的能力。而编写具体对象类型的程序员，则有责任提供模板所要求的这些运算符和成员函数。

遗憾的是，很多程序员都把模板视为 C++ 中最难掌握的部分，因此总是下意识地回避它们。但即便你从不自己写模板，你也必须理解模板的语法与能力，才能真正用好标准库。模板会在第 12 章“使用模板编写泛型代码”中详细讨论。如果你当时跳过了那一章，或者你对模板还不熟悉，那么我建议你先回去读完第 12 章，再继续深入学习标准库。

运算符重载的使用

运算符重载是另一项在 C++ 标准库中被大量使用的特性。第 9 章“精通类与对象”中专门有一节讨论运算符重载。请确保你已经读过那部分内容，并在继续阅读本章及后续章节之前理解它的基本思路。此外，第 15 章“重载 C++ 运算符”还会更深入地展开这一主题。不过，要理解接下来的标准库章节，并不需要你掌握那一章中的全部高级细节。

C++ 标准库概览

本节会从设计视角出发，介绍标准库中的各个组成部分。你将知道有哪些设施可供使用，但这里不会讲太多具体编码细节；那些内容会在其他章节详细展开。

字符串

C++ 提供了内建的 string 类，定义在 <string> 中。这个 C++ 的 string 类几乎在所有方面都优于 C 风格的字符数组字符串：它负责内存管理；提供某种程度的边界检查、赋值语义与比较能力；并支持拼接、提取子串、替换子串或字符等操作。

标准库还提供了 string_view 类，定义在 <string_view> 中。它是对任意字符串表示形式的一种只读视图，可以在很多场景下直接替代 const string&，但几乎没有额外开销。它从不复制字符串！

C++ 还支持 Unicode 和 本地化（localization）。Unicode 让你能够编写可处理多语言文本的程序，例如阿拉伯语、中文、日语等。定义在 <locale> 中的 locale，则允许你根据某个国家或地区的规则来格式化数字、日期等数据。

C++ 还提供了一套功能强大且类型安全的字符串格式化库，可通过 std::format() 使用，并定义在 <format> 中。这套库可以扩展到你自己的自定义类型。C++23 进一步加入了辅助函数 std::print() 和 println()，让格式化文本输出到控制台变得更加方便。

如果你前面错过了，第 2 章“使用字符串与字符串视图”会详细介绍 string、string_view 与字符串格式化库；而第 21 章“字符串本地化与正则表达式”则会讨论 Unicode 与本地化。

正则表达式

正则表达式相关功能由 <regex> 提供。它让你可以轻松执行 模式匹配（pattern-matching），这在文本处理场景中非常常见。模式匹配允许你在字符串中搜索满足某种模式的内容，并可选地将其替换成新的模式。正则表达式会在第 21 章中详细讨论。

I/O 流

C++ 内建了一套输入输出模型，称为 stream。C++ 库提供了从文件、控制台/键盘以及字符串中读取和写入内建类型的能力；同时也提供了用于为你自己的对象编写读写逻辑的机制。大部分 I/O 功能定义在 <fstream>、<iomanip>、<ios>、<iosfwd>、<iostream>、<istream>、<ostream>、<sstream>、<streambuf> 和 <strstream> 中。C++23 还引入了基于 span 的 stream，定义在 <spanstream> 中。第 1 章“C++ 与标准库速成”回顾了 I/O stream 的基础，而第 13 章“揭开 C++ I/O 的面纱”会对其进行详细讨论。

智能指针

在健壮程序设计中，一个典型难题是：到底什么时候该删除一个对象。这里可能出现多种失败方式。第一类问题，是对象根本没有被删除（也就是没有释放其存储）；这会形成 内存泄漏（memory leaks），对象不断堆积，占据空间，却再也不会被使用。第二类问题，是某段代码释放了某块存储，而另一段代码却仍持有指向那块存储的指针；这些指针会指向一块“不再属于该对象”甚至已被分配给其他用途的内存，这就是所谓的 悬空指针（dangling pointers）。还有一种问题，是同一块存储被释放了两次，也就是 重复释放（double deletion）。

所有这些问题，最终都会以某种方式导致程序失败。有些失败很容易观察到，可能直接导致程序崩溃；另一些则会让程序输出错误结果，而且往往更难定位。绝大多数这类错误都非常难以排查与修复。

C++ 通过智能指针来解决这些问题：unique_ptr、shared_ptr 和 weak_ptr，它们都定义在 <memory> 中。这些智能指针会在第 7 章“内存管理”中详细讲解。

异常

C++ 语言支持异常（exceptions），它允许函数把各种类型的错误向上传递给调用者。C++ 标准库提供了一套异常类层次结构，你既可以直接使用它们，也可以从中派生出你自己的异常类型。大多数异常支持相关内容定义在 <exception>、<stdexcept> 和 <system_error> 中。第 14 章“处理错误”会系统介绍异常及标准异常类。

标准整数类型

头文件 <cstdint> 定义了一组标准整数类型，例如 intx_t 和 uintx_t，其中 x 可以是 8、16、32 或 64。它还包含了用于描述这些类型最小值与最大值的宏。这些整数类型会在第 34 章“开发跨平台与跨语言应用”中，结合跨平台编程场景进行讨论。

数值库

C++ 标准库提供了一整套数学相关的工具类与函数。

你可以使用大量常见数学函数，例如 abs()、remainder()、fma()、exp()、log()、pow()、sqrt()、sin()、atan2()、sinh()、erf()、tgamma()、ceil()、floor() 等等。标准库还支持若干数学特殊函数，用于处理 Legendre 多项式、beta 函数、椭圆积分、Bessel 函数、圆柱 Neumann 函数等。这些特殊函数都有成熟的名称与记号体系，广泛用于数学分析、泛函分析、几何学、物理学及其他应用。lerp() 函数用于计算线性插值或外推：lerp(a, b, t) 的计算结果是 a + t(b - a)。线性插值用于在给定数据点之间估算某个中间值，而外推则用于估算超出最小或最大数据点范围之外的值。这些函数大多定义在 <cmath> 中，也有一些定义在 <cstdlib> 中。

<numeric> 中定义了 gcd() 与 lcm()，分别用于计算两个整数类型的 最大公约数（greatest common divisor）和 最小公倍数（least common multiple）。midpoint() 用于求两个值（整数、浮点数或指针）的中点。

从 C++23 开始，其中相当一部分函数被标记为 constexpr（见第 9 章），因此可以用于编译期计算。要确切知道哪些函数是 constexpr，仍然需要查阅你惯用的标准库参考资料。

标准库中还提供了一个名为 complex 的复数类，定义在 <complex> 中，用于处理同时包含实部和虚部的数值。

编译期有理数运算库提供了 ratio 类模板，定义在 <ratio> 中。这个 ratio 类模板可以通过分子与分母，精确表示任意有限有理数。该库会在第 22 章“日期与时间工具”中讨论。

标准库中还有一个名为 valarray 的类，定义在 <valarray> 中。它和 vector 有些相似，但针对高性能数值应用做了更强的优化。该库还提供了若干相关类，用于表示向量切片（vector slices）的概念，并可在此基础上构建执行矩阵计算的类。标准库本身并没有内建矩阵类；不过，像 Boost 这样的第三方库则提供了矩阵支持。valarray 在本书中不再进一步讨论。

标准库还在 <numbers> 中、std::numbers 命名空间下，提供了一组常用数学常量。下面仅列出其中几个：

常量	说明	近似值
`pi`	π 的值	3.141592653589793
`inv_pi`	π 的倒数	0.3183098861837907
`sqrt2`	2 的平方根	1.4142135623730951
`e`	欧拉常数 e	2.718281828459045
`phi`	黄金比例	1.618033988749895

整数比较

标准库提供了以下比较函数：std::cmp_equal()、cmp_not_equal()、cmp_less()、cmp_less_equal()、cmp_greater() 和 cmp_greater_equal()，它们都定义在 <utility> 中。它们用于比较两个整数，并且能够安全地处理有符号与无符号整数混合比较的问题。

例如，下面这段代码使用 operator> 比较有符号值 -1 与无符号值 0u。输出结果是 1（也就是 true），因为 -1 会先被转换成无符号整数，从而变成一个非常大的数，例如 4,294,967,295，自然大于 0：

println("{}", (-1 > 0u));            // true

使用 cmp_greater() 则会得到正确结果：

println("{}", cmp_greater(-1, 0u));  // false

位操作

标准库还提供了若干用于处理 bit 的函数，全部定义在 <bit> 中。这些函数都要求第一个参数是无符号整数类型：

函数	说明
`has_single_bit()`	如果某个值只包含单个置位 bit，也就是它是 2 的整数幂，则返回 `true`。
`bit_ceil()`	返回大于等于给定值的最小 2 的整数幂。
`bit_floor()`	返回小于等于给定值的最大 2 的整数幂。
`bit_width()`	返回存储给定值所需的 bit 数。
`rotl()` / `rotr()`	将给定值的 bit 向左或向右旋转若干位。
`countl_zero()` / `countl_one()`	从左侧（最高有效位开始）统计连续的 0 bit 或 1 bit 数量。
`countr_zero()` / `countr_one()`	从右侧（最低有效位开始）统计连续的 0 bit 或 1 bit 数量。
`popcount()`	返回给定值中为 1 的 bit 个数。
`byteswap()`	反转整数类型中各个 byte 的顺序。

下面是一些示例：

println("{}", popcount(0b10101010u)); // 4

uint8_t value { 0b11101011u };
println("{}", countl_one(value));     // 3
println("{}", countr_one(value));     // 2

value = 0b10001000u;
println("{:08b}", rotl(value, 2));    // 00100010

value = 0b00001011u;
println("bit_ceil({0:08b} = {0}) = {1:08b} = {1}",
    value, bit_ceil(value));          // bit_ceil(00001011 = 11) = 00010000 = 16
println("bit_floor({0:08b} = {0}) = {1:08b} = {1}",
    value, bit_floor(value));         // bit_floor(00001011 = 11) = 00001000 = 8

uint32_t before { 0x12345678u };
println("{:x}", before);              // 12345678
uint32_t after { byteswap(before) };   // C++23 std::byteswap().
println("{:x}", after);               // 78563412

时间与日期工具

标准库包含 chrono 库，定义在 <chrono> 中。这个库让你能够方便地处理日期和时间、测量时长等等。它支持日历与时区，并提供在不同时区之间转换时间的功能。<ctime> 头文件则提供若干 C 风格的时间日期工具。

第 22 章会详细讨论这些时间与日期工具。

随机数

C++ 很早以前就通过 srand() 与 rand() 支持伪随机数生成了。不过，这两个函数只能提供比较基础、质量也不高的随机数。例如，你无法控制它们的分布特性。

从 C++11 起，标准库提供了一整套功能强大的随机数生成库。它定义在 <random> 中，包含 随机数引擎（random number engines）、随机数引擎适配器（random number engine adapters）和 随机数分布（random number distributions）。借助这些组件，你可以生成高质量随机数，并支持不同分布，例如正态分布、负指数分布等等。

关于这部分内容，请参见第 23 章“随机数设施”。

初始化列表

初始化列表定义在 <initializer_list> 中。它让你可以轻松编写“接收可变数量参数”的函数；相关内容已在第 1 章中讨论。

Pair 与 Tuple

<utility> 定义了 pair 类模板，它可以存放两个类型可能不同的元素。这叫做存放异构（heterogeneous）元素。本章稍后会介绍的标准库容器，则都存放同构（homogeneous）元素，也就是同一个容器中的所有元素都必须拥有相同类型。pair 则让你能够在单个对象中保存两个完全不相关类型的值。pair 类模板在第 1 章中已经介绍过。

定义在 <tuple> 中的 tuple，则是 pair 的推广。它是一个固定大小的序列，可以容纳异构元素。某个 tuple 实例所包含元素的数量与类型，都会在编译期固定下来。tuple 会在第 24 章“附加词汇类型”中讨论。

词汇类型

词汇类型（vocabulary types）是那些你会频繁使用的类型，使用频率几乎不亚于 int、double 这类原生类型。使用词汇类型，可以让你的代码更安全、更高效，也更易编写、阅读与维护。本书前面已经介绍过的一些词汇类型示例，包括 vector、optional、string、unique_ptr、shared_ptr 等等。

第 24 章还会讨论以下这些额外的词汇类型：

variant，定义在 <variant> 中，可以保存“给定一组类型中的某一种类型”的单个值。
any，定义在 <any> 中，可以保存任意类型的单个值。
tuple，定义在 <tuple> 中，是 pair 的推广。它可以保存任意数量的值，并且每个值都可以有自己的类型。
optional，定义在 <optional> 中，用于表示“某种特定类型的值”或“没有值”。它可用于类的数据成员、函数参数、函数返回类型等场景，只要你想表达“某个值是可选的”。它在第 1 章中已经介绍过。第 24 章还会解释：optional 支持 monadic operation，这让你能够轻松链式操作多个 optional，而不必在每一步都手工检查它是否为空。
expected，定义在 <expected> 中，用来保存“某种特定类型的值”或“某种可能不同类型的错误值”。这在函数返回类型中尤其有用，因为函数就可以要么返回调用者想要的数据，要么返回出错原因。

函数对象

实现了函数调用运算符的类，叫做 函数对象（function object）。函数对象可以例如作为某些标准库算法中的谓词。<functional> 中定义了若干预定义函数对象，也支持你基于现有函数对象构造出新的函数对象。

函数对象会在第 19 章“函数指针、函数对象与 Lambda 表达式”中详细讨论。

文件系统

文件系统支持库的全部内容，都定义在 <filesystem> 中，并位于 std::filesystem 命名空间下。它让你能够以可移植的方式编写操作文件系统的代码。你可以用它来判断某个东西是目录还是文件、遍历目录内容、操作路径、读取文件大小、扩展名、创建时间等信息。文件系统支持库会在第 13 章中讨论。

多线程

如今主流 CPU 厂商几乎都在销售多核处理器，它们被广泛用于服务器、个人电脑，甚至智能手机。如果你希望软件充分利用这些核心，就必须编写多线程代码。标准库为此提供了若干基础构件。单个线程可以通过 <thread> 中的 thread 类来创建；标准库还提供了 jthread，这是一种可取消、并且在析构时会自动执行 join 的线程。

在多线程代码中，你必须小心，避免多个线程同时读写同一片数据，否则就会造成数据竞争。为了解决这一点，你可以使用定义在 <atomic> 中的原子类型，它们提供对共享数据的线程安全原子访问。其他线程同步机制则由 <condition_variable> 和 <mutex> 提供。此外，标准库还支持以下同步原语：信号量（<semaphore>）、latch（<latch>）和 barrier（<barrier>）。

如果你只是需要在某个线程上计算某件事，并在之后取回结果且带有正确的异常处理，那么可以使用 async 和 future。它们定义在 <future> 中，并且通常比直接操作 thread 或 jthread 更容易使用。

多线程编程会在第 27 章“使用 C++ 进行多线程编程”中详细讨论。

类型萃取

类型萃取（type traits）定义在 <type_traits> 中，用于在编译期获取类型信息。它们在编写高级模板时非常有用，并会在第 26 章“高级模板”中讨论。

标准库特性测试宏

标准库也提供了 特性测试宏（feature-test macros）。它们和核心语言特性测试宏（见第 11 章“模块、头文件与其他杂项主题”）的作用类似，可以用来判断某项标准库特性是否被当前实现支持。所有这些宏都以 __cpp_lib_ 开头。下面列出几个示例；如需完整清单，请查阅你惯用的标准库参考资料。

__cpp_lib_concepts
__cpp_lib_ranges
__cpp_lib_scoped_lock
__cpp_lib_atomic_float
__cpp_lib_constexpr_vector
__cpp_lib_constexpr_tuple
__cpp_lib_filesystem
__cpp_lib_three_way_comparison
…

这类宏的值，是一个表示“某项特性被加入或更新时的年月”的数字，格式为 YYYYMM。例如，__cpp_lib_filesystem 的值是 201703，也就是 2017 年 3 月。

正如第 11 章所解释的，核心语言的特性测试宏无需包含任何头文件就始终可用；但标准库特性测试宏定义在 <version> 中。而由于特性测试宏本质上是宏，你也已经知道，导入命名模块 std 或 std.compat 并不会让这些宏变得可用。第 11 章同时也说明：所有 C++ 头文件（例如 <version>）都可以被导入。因此，要访问 <version> 中定义的这些宏，你有两种方式：

import <version>;

或者：

#include <version>

下面是一个完整示例：

import std;
import <version>; // Important to get access to the feature-test macros!
using namespace std;

int main()
{
#ifdef __cpp_lib_constexpr_vector
    println("std::vector is constexpr!");
#else
    println("Bummer! std::vector is NOT constexpr!");
#endif
}

`<version>`

<version> 还可以用于查询与你正在使用的 C++ 标准库实现相关的实现依赖信息。它具体暴露哪些内容，取决于你所使用的标准库实现。通常可能包括：版本号、发布日期、版权信息等。

此外，正如上一节所述，<version> 还会暴露全部标准库特性测试宏。

源位置

定义在 <source_location> 中的 std::source_location，可以用来获取源代码相关信息，例如文件名、函数名、行号与列号，用来替代旧式 C 风格宏 __FILE__ 和 __LINE__。典型用途包括在记录日志或抛出异常时附带源代码位置。第 14 章中给出了这两种使用场景的示例。

栈追踪

<stacktrace> 定义了 std::stacktrace 与 std::stacktrace_entry 类。它们可以在任意时刻获取调用栈，并逐一遍历与检查其中每个条目（称为 frame）。第 14 章中会给出相应示例。

容器

标准库提供了诸如链表、队列这类常用数据结构的实现。既然你使用的是 C++，理论上就不应该再自己手写这些基本数据结构。标准库通过容器（containers）这一抽象来实现这些数据结构；容器中保存的信息被称为元素（elements），而容器会以适合该数据结构（例如链表、队列等）的方式来组织它们。不同数据结构在插入、删除、访问行为及性能特征上都不相同。想为某个具体任务选出最合适的数据结构，你就必须熟悉标准库中都有哪些可用选项。

标准库中的所有容器都是类模板，因此你可以用它们来存储任意类型，从 int、double 这样的内建类型，到你自己定义的类都可以。每个具体容器实例只会存储同一种类型的对象，也就是说，它们都是 同构集合（homogeneous collections）。如果你需要“大小不固定”的异构集合，那么可以把每个元素包在一个 std::any 里，再把这些 any 存进容器中。另一种办法是把 std::variant 放进容器里；当所需支持的类型数量有限且在编译期已知时，variant 会很合适。你还可以设计一个带有多个派生类的类层次结构，让每个派生类包装你所需的某一种对象类型。any 与 variant 都会在第 24 章中讨论。

C++ 标准只规定了每个容器与算法的接口，而不是其实现。因此，不同厂商完全可以给出不同实现。不过，标准也同时规定了作为接口组成部分的性能要求，而这些实现都必须满足这些要求。

本节将概览标准库中各种可用的容器。

顺序容器

标准库提供了五种顺序容器：vector、list、forward_list、deque 和 array。

`vector`

vector 定义在 <vector> 中，用来保存一串元素，并提供对这些元素的随机访问。你可以把 vector 看成一种“会随着你不断插入元素而自动增长的数组”，同时它还额外提供了某种程度的边界检查。和普通数组一样，vector 中的元素在内存中是连续存放的。

vector 在末尾插入和删除元素都很快（摊销常数时间，amortized constant time）。所谓“摊销常数时间插入”，意味着绝大多数时候插入都是常数时间 O(1)（关于大 O 记法，见第 4 章“设计专业级 C++ 程序”）。不过，有时 vector 为了容纳新元素，需要扩大容量，而这一步的复杂度是 O(N)。从平均效果来看，这依然可以视作 O(1)，也就是摊销常数时间；具体细节会在第 18 章“标准库容器”中解释。相反，如果在 vector 中间位置插入或删除元素，性能会变慢（线性时间），因为它必须把后续元素整体向后或向前移动，以腾出空间或填补空位。和数组一样，vector 对任意元素的访问都非常快（常数时间）。

尽管在 vector 中间插入或删除元素需要移动其他元素，但 vector 仍然应当是你的默认容器！在很多情况下，即便涉及中间插入和删除，vector 仍然可能比链表更快。原因是 vector 的元素在内存中连续存放，而链表则散落在内存各处。现代计算机对连续内存的数据处理效率极高，这使得 vector 的实际表现通常非常好。只有当性能分析器（见第 29 章“编写高效 C++”）明确告诉你链表在你的具体场景下更快时，你才应考虑改用它。

标准库还为 vector<bool> 提供了一个模板特化，用来在 vector 中存储布尔值。这个特化会对布尔元素的空间分配做优化；不过，标准并没有规定具体要如何优化。vector<bool> 与本章稍后会介绍的 bitset 的区别在于：bitset 大小固定，而 vector<bool> 则可以根据需要自动增长或收缩。

`list`

list 是一种 双向链表（doubly linked list）结构，定义在 <list> 中。和数组或 vector 一样，它保存的是一串元素；但不同之处在于，list 中的元素不要求在内存中连续。相反，list 中的每个元素都会记录下一个元素和前一个元素的位置（通常通过指针），这也正是它被称为双向链表的原因。

list 的性能特征，几乎正好与 vector 相反：元素查找与访问较慢（线性时间），但在一旦你已经找到目标位置之后，插入与删除元素则很快（常数时间）。不过，正如上一节所说，即便如此，vector 在实际中往往仍比 list 更快。是否真有必要选择 list，应当交给 profiler 来决定（见第 29 章）。

`forward_list`

定义在 <forward_list> 中的 forward_list，与 list 类似，但它是 单向链表（singly linked list），而 list 是双向链表。forward_list 只支持向前遍历，因此占用的内存也会比 list 略少。和 list 一样，只要已经找到相关位置，forward_list 也允许在任意位置以常数时间插入和删除元素；但它同样不支持快速随机访问。

`deque`

deque 这个名字是 double-ended queue 的缩写。定义在 <deque> 中的 deque 支持快速（常数时间）的元素访问。它还支持在序列两端进行快速（常数时间）的插入与删除，但在中间位置的插入和删除仍然较慢（线性时间）。由于 deque 的元素不是连续存放在内存中的，因此它在实际中可能会比 vector 慢。

当你需要从序列两端插入或删除元素，同时又仍然需要快速访问所有元素时，可以考虑用 deque 替代 vector。不过，这种需求并不算常见；在大多数情况下，仍然推荐使用 vector。

`array`

定义在 <array> 中的 array，是对传统 C 风格数组的替代。有时候，你一开始就已经知道容器中元素的确切数量，也不需要 vector 或 list 那种可以动态扩容的灵活性。对于这种固定大小的集合，array 就非常合适，而且相较 vector 它的额外开销更小；你几乎可以把它看成只是 C 风格数组上的一层轻量封装。和 C 风格数组相比，使用 array 有若干明显好处：它始终知道自己的大小，并且不会自动衰减成指针，从而避免一类常见 bug。另一方面，array 不支持插入和删除，因为它的大小是固定的。固定大小的一个优势在于：它可以被分配在栈上，而不像 vector 那样通常需要使用自由存储区（free store）。它的元素访问和 vector 一样快，都是常数时间。

顺序视图

标准库提供了两种顺序视图：span 和 mdspan。

`span`

定义在 <span> 中的 span，表示对某段连续数据序列的一种视图。它既可以是只读视图，也可以是可读写底层元素的视图。span 让你可以编写一个统一的函数，同时处理来自 vector、array、C 风格数组等不同来源的数据。第 18 章会更详细地讨论 span。

`mdspan`

定义在 <mdspan> 中的 mdspan，和 span 类似，但它表示的是对一段连续数据的多维视图。和 span 一样，它既可以是只读视图，也可以是可读写底层元素的视图。第 18 章会更详细地讨论 mdspan。

容器适配器

标准库提供了三种非关联容器适配器：queue、priority_queue 和 stack。

`queue`

queue 这个名字，直接来自英语单词 queue，也就是“排队”的意思。定义在 <queue> 中的 queue 容器，提供标准的 先进先出（first in, first out，FIFO）语义。queue 是这样一种容器：你从一端插入元素，再从另一端取出元素。无论插入（摊销常数时间）还是删除（常数时间），都非常高效。

当你需要模拟现实世界中的“先来先服务”行为时，就应考虑使用 queue。例如，想象一家银行：顾客到来后排队；柜员一旦空闲，就服务排在最前面的顾客，这正是“先来先服务”。如果你要写一个银行仿真程序，就完全可以把顾客对象存进一个 queue。顾客到达时加到 queue 尾部；柜员服务时则从 queue 头部开始处理。

`priority_queue`

同样定义在 <queue> 中的 priority_queue，提供的是一种“带优先级”的 queue 行为：元素并不是严格按 FIFO 顺序被移除，而是按优先级顺序被取出。当优先级相同时，元素被取出的相对顺序是未定义的。由于要维护优先级顺序，因此 priority_queue 的插入与删除通常都比普通 queue 更慢。

你可以用 priority_queue 来模拟“有例外规则的队列”。还是以前面的银行为例：假设商业账户顾客优先于普通顾客。现实中的银行往往通过两条独立队伍来实现：商业客户一条，普通客户一条，且商业客户始终先于普通客户被服务。但你也可以把这种行为建模成“单一队列中，商业客户能自动排到普通客户前面”。在程序里，这就可以通过 priority_queue 来实现：顾客要么属于“商业”优先级，要么属于“普通”优先级。这样一来，所有商业顾客都会先于所有普通顾客被处理。

`stack`

<stack> 定义了 stack 类，它提供标准的 先进后出（first-in, last-out，FILO）语义，也常被称为 后进先出（last-in, first-out，LIFO）。和 queue 一样，stack 也允许插入与删除元素；但不同在于，stack 中最后插入的元素会最先被移除。stack 这个名字来自一个非常形象的比喻：你可以把它想成一摞叠起来的物体，只有最上面的那个当前“可见”。每当你把一个新对象压上去，下面的对象就都被遮住了。

stack 提供快速（常数时间）的插入与删除。如果你想要 FILO/LIFO 的行为，就应该使用 stack。例如，一个错误处理工具可能会把错误压入 stack 中，这样“最近发生的错误”就会最先被管理员读到。按 FILO 顺序处理错误，往往是合理的，因为较新的错误有时会让较旧的错误失去意义。

有序关联容器

标准库提供了四种有序关联容器：set、multiset、map 和 multimap。之所以称它们为有序（ordered）或 排序型（sorted）关联容器，是因为它们会对元素进行排序。

`set`

set 类模板定义在 <set> 中。顾名思义，它表示一个元素集合，在概念上与数学上的集合十分相似：每个元素都是唯一的，在集合中至多出现一次。标准库中的 set 与数学概念上的集合有一个重要差别：标准库中的元素始终处于某种顺序中。之所以需要这种顺序，是因为有序能让“判断某个元素是否已存在于 set 中”这件事变得快得多。当使用者枚举 set 中元素时，它们会按照该元素类型的 operator< 所定义的顺序（或你提供的自定义比较器）输出。set 的插入、删除与查找都具有对数复杂度。从理论上看，这意味着：相对 vector 来说，它的插入和删除更快，但比 list 慢；而查找又比 list 快，但比 vector 慢。和往常一样，具体是否更适合你的场景，还是要交给 profiler 判断。

当你既需要元素保持某种顺序，又希望插入、删除与查找三种操作的性能比较均衡、整体也尽可能高时，set 就是一个不错的选择。例如，一家繁忙书店的库存跟踪程序，就可以使用 set 来保存书籍清单。书籍到货或售出时，库存都要更新，因此插入和删除必须足够快；同时，顾客又经常需要快速查找某本书，因此系统还应提供高效查找。

set 中的元素不能被原地修改，因为那会破坏元素的顺序。如果你确实需要改变一个元素，就应该先把旧元素移除，再插入一个新值。

set 不允许重复元素。也就是说，set 中的每个元素都必须唯一。

`multiset`

同样定义在 <set> 中的 multiset，几乎与 set 完全一致，唯一的区别是：multiset 允许存放重复元素。

`map`

<map> 定义了 map 类模板，它本质上就是一种 关联数组（associative array）。你可以把它看成一种“索引不再局限于整数，而可以是任意类型（例如 string）”的数组。map 保存的是 key/value pair，并且会基于 key（而不是 value）来对元素进行排序。它还提供 operator[]，这是 set 所没有的。除此之外，在多数方面它都和 set 相似。当你需要把 key 与 value 关联起来时，map 就很适合。例如，在前面书店的例子中，你可以使用 map 来保存书籍，其中 key 是图书的 ISBN 编号，而 value 是包含该书详细信息的 Book 对象。

`multimap`

<map> 还定义了 multimap 类模板，它几乎与 map 完全相同，唯一区别是：multimap 允许多个元素拥有相同的 key。

无序关联容器 / 哈希表

标准库还支持 哈希表（hash tables），也叫 无序关联容器（unordered associative containers）。一共有四种：

unordered_map 和 unordered_multimap
unordered_set 和 unordered_multiset

前两个定义在 <unordered_map> 中，后两个定义在 <unordered_set> 中。更直观的名字本来应该是 hash_map、hash_set 之类；但不幸的是，在 C++11 之前，哈希表并不是标准库的一部分，很多第三方库早就各自实现了带有“hash_”前缀的名字，例如 hash_map。为了避免命名冲突，标准委员会最终选择了使用“unordered”而不是“hash”作为正式前缀。

这些无序关联容器的行为，与它们的有序对应物非常相似。比如，unordered_map 与普通 map 基本一致，区别只是后者会对元素排序，而前者不会。

对于这些无序关联容器来说，插入、删除和查找在平均情况下都能达到常数时间；最坏情况下则退化为线性时间。当容器中元素数量很大时，在无序容器中进行查找，往往会明显快于普通的 map 或 set。

第 18 章会解释这些无序关联容器是如何工作的，以及它们为什么被称为哈希表。

Flat 关联容器适配器

C++23 新引入了四种 flat 关联容器适配器：

flat_map 和 flat_multimap，定义在 <flat_map> 中
flat_set 和 flat_multiset，定义在 <flat_set> 中

它们建立在顺序容器之上，并提供关联容器式的接口。被适配的顺序容器必须支持随机访问 iterator，例如 vector 或 deque。flat_map 与 flat_multimap 需要两个底层顺序容器：一个用来保存 key，另一个保存 value；而 flat_set 与 flat_multiset 则只需要一个底层顺序容器来保存 key。

这些适配器提供的接口，与它们对应的有序关联容器几乎完全一致。主要区别在于：flat 适配器不是基于 node 的数据结构，因此不提供与 node 相关的成员函数。除此之外，它们在很多场景下几乎可以直接无缝替换对应的有序容器。

第 18 章会更详细地介绍这些 flat 关联容器适配器。

`bitset`

C 和 C++ 程序员常常会用一个 int 或 long 来存放一组标志位，每一位对应一个布尔状态。位的设置与读取，则通过位运算符 &、|、^、~、<< 和 >> 来完成。C++ 标准库提供了 bitset 类，用来把这些位字段操作抽象出来，因此在类似场景中，你通常不再需要直接手写位运算。

<bitset> 定义了 bitset 容器，但它并不是传统意义上的容器，因为它并没有实现某种“可以插入或删除元素”的具体数据结构。bitset 的大小是固定的。你可以把它看成一串可读写的布尔值。不过，与 C 风格的 bit 操作方式不同，bitset 不会受限于 int 或其他基础整数类型的位宽。你完全可以拥有一个 40 bit 的 bitset，也可以拥有一个 213 bit 的 bitset。当你写下 bitset<N> 时，实现会自动分配足够存储 N 个 bit 的空间。

标准库容器总结

下表总结了标准库提供的容器。它使用第 4 章中介绍的大 O 记法，给出一个包含 N 个元素的容器在若干操作下的性能特征。表格中的 N/A 表示该操作并不属于该容器的语义范围：

名称	类型	插入性能	删除性能	查找性能
`vector`	顺序容器	末尾摊销 O(1)；其他位置 O(N)	末尾 O(1)；其他位置 O(N)	O(1)
适用场景：它应当是你的默认容器。只有在 profiler 明确证明其他容器更快时，才考虑改用别的。
`list`	顺序容器	开头、末尾，以及已定位到插入位置后为 O(1)	开头、末尾，以及已定位到删除位置后为 O(1)	访问首尾元素为 O(1)；其他情况 O(N)
适用场景：很少需要。除非 profiler 明确表明 `list` 更快，否则请使用 `vector`。
`forward_list`	顺序容器	开头，以及已定位到插入位置后为 O(1)	开头，以及已定位到删除位置后为 O(1)	访问首元素为 O(1)；其他情况 O(N)
适用场景：很少需要。除非 profiler 明确表明 `forward_list` 更快，否则请使用 `vector`。
`deque`	顺序容器	开头或末尾 O(1)；其他位置 O(N)	开头或末尾 O(1)；其他位置 O(N)	O(1)
适用场景：一般不常需要；通常直接用 `vector` 更合适。
`array`	顺序容器	N/A	N/A	O(1)
适用场景：当你需要一个固定大小数组，来替代 C 风格数组时。
`queue`	容器适配器	取决于底层容器；对 `list` 与 `deque` 为 O(1)	取决于底层容器；对 `list` 与 `deque` 为 O(1)	N/A
适用场景：当你需要 FIFO 结构时。
`priority_queue`	容器适配器	取决于底层容器；对 `vector` 为摊销 O(log(N))，对 `deque` 为 O(log(N))	取决于底层容器；对 `vector` 与 `deque` 为 O(log(N))	N/A
适用场景：当你需要带优先级的队列时。
`stack`	容器适配器	取决于底层容器；对 `list` 与 `deque` 为 O(1)，对 `vector` 为摊销 O(1)	取决于底层容器；对 `list`、`vector` 与 `deque` 为 O(1)	N/A
适用场景：当你需要 FILO/LIFO 结构时。
`set` / `multiset`	有序关联容器	O(log(N))	O(log(N))	O(log(N))
适用场景：当你需要有序元素集合，并希望查找、插入与删除拥有接近的性能时。若你还希望元素不重复，则使用 `set`。
`map` / `multimap`	有序关联容器	O(log(N))	O(log(N))	O(log(N))
适用场景：当你需要一个有序集合来关联 key 与 value，也就是一种关联数组，同时希望查找、插入与删除拥有接近的性能时。
`unordered_map` / `unordered_multimap`	无序关联容器 / 哈希表	平均 O(1)；最坏 O(N)	平均 O(1)；最坏 O(N)	平均 O(1)；最坏 O(N)
适用场景：当你需要关联 key 与 value，并希望查找、插入与删除拥有接近性能，同时又不要求元素排序时。性能可能优于普通 `map`，但也取决于元素本身。
`unordered_set` / `unordered_multiset`	无序关联容器 / 哈希表	平均 O(1)；最坏 O(N)	平均 O(1)；最坏 O(N)	平均 O(1)；最坏 O(N)
适用场景：当你需要一个元素集合，并希望查找、插入与删除拥有接近性能，同时又不要求元素排序时。性能可能优于普通 `set`，但也取决于元素本身。
`flat_set` / `flat_multiset`	Flat set 关联容器适配器	O(N)	O(N)	O(log(N))
适用场景：当你需要一个有序元素集合时。由于这些适配器底层使用顺序容器，内存布局对缓存非常友好，因此它们的性能往往优于对应的有序容器。
`flat_map` / `flat_multimap`	Flat map 关联容器适配器	O(N)	O(N)	O(log(N))
适用场景：当你需要一个有序集合来关联 key 与 value 时。由于这些适配器底层使用顺序容器，内存布局对缓存非常友好，因此它们的性能往往优于对应的有序容器。
`bitset`	特殊	N/A	N/A	O(1)
适用场景：当你需要一组标志位集合时。

注意，从技术上说，string 本身也是容器。因此，后面章节中介绍的一些算法，同样也可以作用于 string。

算法

除了容器之外，标准库还提供了大量泛型算法实现。算法（algorithm）是用来完成特定任务的一套策略，例如排序、搜索等。这些算法被实现为函数模板，因此可以适用于多数不同类型的容器。注意，这些算法通常并不是容器本身的一部分。标准库采取的是把数据（容器）与功能（算法）分离的设计方式。尽管这看上去似乎有些违背面向对象编程的直觉，但若想在标准库中支持真正的泛型编程，这种设计就是必要的。其背后的核心原则是 正交性（orthogonality）：算法与容器彼此独立，几乎任意算法都可以作用于几乎任意容器。

请注意，泛型算法并不是直接对容器本身操作；相反，它们要么通过 iterator 工作，要么基于 range 工作。这两者都会在第 17 章“理解迭代器与 Ranges 库”中详细讨论。

本节只会概览标准库中可用算法的种类，而不会展开编码细节。第 20 章“精通标准库算法”会选取其中一部分算法，结合代码示例进行讲解。至于所有可用算法的精确原型，仍请查阅你惯用的标准库参考资料。

标准库中包含 100 多个算法。下面的几个小节会按类别对它们进行划分。除非另有说明，这些算法都定义在 <algorithm> 中。需要注意的是，当下文说某个算法作用于一段“元素序列”时，这段序列总是通过 iterator 传递给算法的。

不修改序列的算法

不修改算法会查看一段元素序列，并返回关于这些元素的某些信息。既然它们是“不修改”算法，那么它们既不会改变元素值，也不会改变元素在序列中的顺序。这一类算法主要包括三种：搜索、比较和计数。接下来的小节会分别简要概括这些算法。掌握它们之后，你就几乎不再需要自己写 for 循环来遍历一段值序列了。

搜索算法

这些算法不要求输入序列已经排序。这里的 N 表示被搜索序列的大小，M 表示待匹配模式的大小：

名称	概要	复杂度
`adjacent_find()`	找到第一对相邻且彼此相等，或按给定谓词等价的元素。	O(N)
`find()` / `find_if()`	找到第一个匹配某个值，或让谓词返回 `true` 的元素。	O(N)
`find_first_of()`	类似 `find`，但一次同时搜索多个候选元素中的任意一个。	O(N*M)
`find_if_not()`	找到第一个让谓词返回 `false` 的元素。	O(N)
`find_end()`	找到序列中最后一个匹配另一序列的子序列，或按给定谓词等价的最后一个子序列。	O(M**(N - M))
`search()`	找到序列中第一个匹配另一序列的子序列，或按给定谓词等价的第一个子序列。¹	O(N*M)¹
`search_n()`	找到第一段长度为 n 的连续元素序列，这些元素等于某个给定值，或按谓词与该值匹配。	O(N)

比较算法

标准库提供以下比较算法。它们都不要求源序列有序，并且最坏情况下都具有线性复杂度：

名称	概要
`equal()`	通过检查对应位置元素是否相等，或是否满足给定谓词，来判断两个序列是否相等。
`mismatch()`	返回两个序列中第一对彼此不匹配的位置。
`lexicographical_compare()`	比较两个序列的“字典序”先后。它会逐个比较两个序列对应位置的元素；如果某一对元素一大一小，那么较小一方所在序列在字典序上更靠前；若当前元素相等，就继续比较后续元素。
`lexicographical_compare_three_way()`	使用三路比较来比较两个序列的“字典序”，并返回一个比较类别类型（`strong_ordering`、`weak_ordering` 或 `partial_ordering`）。
`all_of()`	如果给定谓词对序列中所有元素都返回 `true`，或者序列为空，则返回 `true`；否则返回 `false`。
`any_of()`	如果给定谓词对序列中至少一个元素返回 `true`，则返回 `true`；否则返回 `false`。
`none_of()`	如果给定谓词对序列中所有元素都返回 `false`，或者序列为空，则返回 `true`；否则返回 `false`。

计数算法

标准库提供以下计数算法。它们都不要求源序列有序，并且最坏情况下都具有线性复杂度：

名称	概要
`count()` / `count_if()`	统计与某个值匹配的元素数量，或统计让某个谓词返回 `true` 的元素数量。

修改序列的算法

修改算法会更改序列中的某些或全部元素。有些算法是 in place 地在原序列上直接修改，因此原序列会发生改变；另一些则把结果复制到另一段序列中，从而保持原序列不变。它们全部都具有线性最坏复杂度。下表概括了这类算法：

名称	概要
`copy()` / `copy_backward()`	把一个序列中的元素复制到另一个序列中。
`copy_if()`	把那些使谓词返回 `true` 的元素，从一个序列复制到另一个序列。
`copy_n()`	从一个序列中复制 n 个元素到另一个序列。
`fill()`	把序列中的全部元素设置为新值。
`fill_n()`	把序列中前 n 个元素设置为新值。
`generate()`	调用给定函数，为序列中每个元素生成一个新值。
`generate_n()`	调用给定函数，为序列中前 n 个元素生成新值。
`move()` / `move_backward()`	使用高效移动语义（见第 9 章）把元素从一个序列移动到另一个序列。
`remove()` / `remove_if()` / `remove_copy()` / `remove_copy_if()`	删除所有匹配给定值、或使谓词返回 `true` 的元素；既可以原地执行，也可以把结果复制到另一个序列。
`replace()` / `replace_if()` / `replace_copy()` / `replace_copy_if()`	把所有匹配给定值、或使谓词返回 `true` 的元素替换为新元素；既可以原地执行，也可以把结果复制到另一个序列。
`reverse()` / `reverse_copy()`	反转序列中元素的顺序；既可以原地执行，也可以把结果复制到另一个序列。
`rotate()` / `rotate_copy()`	交换序列的前后两段“子序列”；两段不要求等长。既可以原地执行，也可以把结果复制到另一个序列。
`sample()`	从序列中随机选出 n 个元素。
`shift_left()` / `shift_right()`	把序列中的元素整体左移或右移若干位。元素会被移动到新位置，从两端掉出去的元素会被移除。`shift_left()` 返回新序列末尾 iterator，`shift_right()` 返回新序列开头 iterator。
`shuffle()` / `random_shuffle()`	通过随机重排元素来打乱序列。可指定打乱所使用的随机数生成器特性。`random_shuffle()` 从 C++14 起被弃用，并从 C++17 起被移除。
`transform()`	对单个序列中的每个元素应用一元函数，或对两个序列中对应位置元素应用二元函数，并将结果写入目标序列。如果源与目标是同一序列，则变换会原地发生。
`unique()` / `unique_copy()`	删除序列中连续重复的元素；既可以原地执行，也可以把结果复制到不同序列。

操作型算法

操作型算法会对序列中的单个元素执行某个函数。标准库只提供了两个这类算法。它们都具有线性复杂度，并且不要求源序列有序：

名称	概要
`for_each()`	对序列中每个元素执行一个函数。序列通过 begin/end iterator 指定。
`for_each_n()`	类似 `for_each()`，但只处理序列中的前 n 个元素。序列由一个 begin iterator 和元素个数 n 指定。

交换算法

标准库提供以下交换算法：

名称	概要
`iter_swap()` / `swap_ranges()`	交换两个元素，或两段元素序列。

Partition 算法

若一个序列满足这样一种性质：所有让某个谓词返回 true 的元素，都位于所有让该谓词返回 false 的元素之前，那么就说该序列已经按这个谓词完成了 partition。序列中第一个“不满足该谓词”的元素位置，被称为 partition point。标准库提供以下 partition 算法：

名称	概要	复杂度
`is_partitioned()`	如果所有让谓词返回 `true` 的元素都位于所有让谓词返回 `false` 的元素之前，则返回 `true`。	线性
`partition()`	重新排列序列，使所有让谓词返回 `true` 的元素都位于所有让谓词返回 `false` 的元素之前，但不保证每个分区内部原有元素顺序。	线性
`stable_partition()`	重新排列序列，使所有让谓词返回 `true` 的元素都位于所有让谓词返回 `false` 的元素之前，并保留每个分区内部原有元素顺序。	线性对数
`partition_copy()`	把一个序列中的元素复制到两个不同目标序列；元素被送到哪个目标，由谓词结果 `true` / `false` 决定。	线性
`partition_point()`	返回一个 iterator，使得该 iterator 之前的元素对谓词都返回 `true`，而之后的元素都返回 `false`。	对数

排序算法

标准库提供若干种排序算法，它们在性能保证方面各不相同：

名称	概要	复杂度
`is_sorted()`	如果序列已排序则返回 `true`，否则返回 `false`。	线性
`is_sorted_until()`	找出从给定区间起始处开始、最长的那段已排序子区间。	线性
`nth_element()`	重排序列，使得位置 nth 上的元素，恰好等于“若整个序列被完全排序后该位置上的元素”；同时保证它前面的元素都不大于它、后面的元素都不小于它。	线性
`partial_sort()` / `partial_sort_copy()`	对序列进行部分排序：前 n 个元素（由 iterator 指定）会被排好序，其余元素则不保证顺序。可以原地执行，也可以复制到新序列中。	线性对数
`stable_sort()` / `sort()`	原地排序元素；前者保留重复元素的相对顺序，后者则不保证。	线性对数

二分查找算法

以下二分查找算法通常用于已排序序列。严格来说，它们只要求序列至少相对于待查找元素完成了 partition。比如你也可以先调用 std::partition() 来满足这一前提；而一个已排序序列显然天然满足这一点。以下算法全部都具有对数复杂度：

名称	概要
`lower_bound()`	找到序列中第一个“不小于”（也就是大于等于）给定值的元素。
`upper_bound()`	找到序列中第一个“大于”给定值的元素。
`equal_range()`	返回一个 `pair`，其中同时包含 `lower_bound()` 与 `upper_bound()` 的结果。
`binary_search()`	如果序列中找到了给定值，则返回 `true`；否则返回 `false`。

作用于排序序列的集合算法

集合算法是一类特殊的修改算法，用于对序列执行集合运算。它们最适合处理来自 set 容器的序列，但同样适用于大多数容器中“已经排序”的序列：

名称	概要	复杂度
`includes()`	判断某个已排序序列中的每个元素，是否都存在于另一个已排序序列中。	线性
`set_union()` / `set_intersection()` / `set_difference()` / `set_symmetric_difference()`	对两个已排序序列执行对应的集合运算，并把结果复制到第三个已排序序列中。	线性

其他作用于排序序列的算法

标准库还提供了下列额外算法，用于处理已排序序列：

名称	概要	复杂度
`inplace_merge()`	原地合并两个已排序序列。	线性对数
`merge()`	把两个已排序序列合并到一个新序列中。	线性

Heap 算法

堆（heap）是一种标准数据结构，其中数组或序列中的元素按照某种“半排序”方式排列，因此可以非常快地找到“顶部”元素。例如，heap 常被用来实现 priority_queue。标准库提供了 6 个算法来支持 heap 操作：

名称	概要	复杂度
`is_heap()`	如果某个元素区间构成堆，则返回 `true`；否则返回 `false`。	线性
`is_heap_until()`	找到从给定区间起始处开始、最长的那段 heap 子区间。	线性
`make_heap()`	从一段元素区间创建堆。	线性
`push_heap()` / `pop_heap()`	向堆中加入一个元素，或从堆中移除一个元素。	对数
`sort_heap()`	把一个 heap 转换成升序排序元素区间。	线性对数

最小值 / 最大值算法

标准库还提供了以下算法，用于查找最小值、最大值以及执行夹取（clamp）：

名称	概要
`clamp()`	确保某个值 v 落在给定最小值 lo 与最大值 hi 之间。若 v < lo，返回对 lo 的引用；若 v > hi，返回对 hi 的引用；否则返回对 v 的引用。
`min()` / `max()`	返回两个或多个值中的最小值或最大值。
`minmax()`	以 `pair` 的形式同时返回两个或多个值中的最小值与最大值。
`min_element()` / `max_element()`	返回序列中的最小元素或最大元素。
`minmax_element()`	以 `pair` 的形式同时返回序列中的最小元素与最大元素。

数值处理算法

以下数值处理算法定义在 <numeric> 中。它们都不要求源序列有序，并且都具有线性复杂度：

名称	概要
`iota()`	用从某个给定值开始、依次递增的值填充一段序列。
`adjacent_difference()`	生成一个新序列，其中每个元素是源序列中相邻两个元素（或按指定二元操作）的差值结果。
`partial_sum()`	生成一个新序列，其中每个元素是源序列中该元素及其之前所有元素之和（或按其他二元操作累积）的结果。
`exclusive_scan()` / `inclusive_scan()`	与 `partial_sum()` 类似。若所给求和操作是结合的，则 inclusive scan 与 partial sum 等价。不过 `inclusive_scan()` 采用不确定顺序求和，而 `partial_sum()` 总是从左到右，因此若求和操作不满足结合性，则前者的结果是不确定的。`exclusive_scan()` 也采用不确定顺序。对 `inclusive_scan()` 来说，第 i 个元素会被计入第 i 次求和值；而对 `exclusive_scan()` 来说，第 i 个元素不会被计入第 i 次求和值。
`transform_exclusive_scan()` / `transform_inclusive_scan()`	先对序列中每个元素执行一次变换，再执行 exclusive / inclusive scan。
`accumulate()`	对序列中全部元素进行“累积”。默认行为是求和，但调用者也可以提供其他二元函数。
`inner_product()`	类似 `accumulate()`，但作用于两个序列。它会先对两个序列中对应位置元素调用某个二元函数（默认是乘法），再通过另一个二元函数（默认是加法）对结果进行累积。如果两个序列表示数学向量，那么该算法计算的是它们的点积。
`reduce()`	类似 `accumulate()`，但支持并行执行。`reduce()` 的求值顺序是不确定的，而 `accumulate()` 则总是从左到右。因此，如果给定二元操作不满足结合律或交换律，前者的行为就会是不确定的。
`transform_reduce()`	先对序列中每个元素做变换，再执行 `reduce()`。

排列算法

一个序列的排列（permutation），指的是它包含完全相同的元素，只是顺序不同。标准库提供以下算法来处理排列：

名称	概要	复杂度
`is_permutation()`	如果一个区间中的元素是另一区间元素的一种排列，则返回 `true`。	二次
`next_permutation()` / `prev_permutation()`	将序列修改为其“下一个”或“上一个”字典序排列。如果你从一个正确排序的序列开始，连续多次调用其中任意一个，就可以遍历出该序列所有可能的排列。当不存在更多排列时，算法返回 `false`。	线性

如何选择算法

一开始看到这么多算法及其能力，你很可能会觉得有些眼花缭乱。刚开始时，也许很难一下子想清楚该如何把它们用到自己的程序里。不过，现在你至少已经知道标准库大致提供了哪些选项，这会帮助你在设计程序时更有方向感。接下来的章节会进一步介绍这些算法在实际代码中的具体用法。

Ranges 库

Ranges 库让处理元素序列这件事变得更简单，也更优雅。Ranges 提供了更清晰、可读性更高的语法，同时消除了 begin/end iterator 不匹配的可能性。此外，range adapter 还允许你对底层序列进行惰性的变换和过滤，而 range factory 则可用于构造 ranges。

前面小节中讨论的大多数算法，都同时提供了“接收 ranges 而不是 iterator”的变体。这些变体通常被称为 基于 range 的算法（range-based algorithms）或 受约束算法（constrained algorithms），因为它们会通过 concepts 为模板类型参数施加真正的约束。这使得编译器在你错误使用这些算法时，能够给出更好的错误信息。

此外，C++23 还引入了下列只提供受约束版本的新算法。它们全部具有线性复杂度。

名称	概要
`contains()` / `contains_subrange()`	如果某个给定 range 包含某个给定值，或者包含某个给定子区间，则返回 `true`；否则返回 `false`。
`starts_with()` / `ends_with()`	如果某个给定 range 分别以另一个给定 range 开头或结尾，则返回 `true`；否则返回 `false`。
`find_last()` / `find_last_if()` / `find_last_if_not()`	在给定 range 中查找最后一个匹配给定值、或让给定谓词返回 `true`、或让给定谓词返回 `false` 的元素。返回结果是一个从找到的元素开始、直到 range 末尾的 subrange。
`fold_left()` / `fold_left_first()` / `fold_right()` / `fold_right_last()` / `fold_left_with_iter()` / `fold_left_first_with_iter()`	对给定 range 中的元素执行左折叠或右折叠。`fold_left()` 与 `fold_right()` 接收一个初始值，并返回折叠运算结果。`fold_left_first()` 使用给定 range 的第一个元素作为起始值，而 `fold_right_last()` 使用最后一个元素作为起始值。这两者都会返回一个 `optional`：若作用于空 range，则返回空 `optional`。后两个变体则返回 `fold_left_with_iter_result` 或 `fold_left_first_with_iter_result`，供你检查折叠运算的结果。

Ranges 库定义在 <ranges> 中，并位于 std::ranges 命名空间下。第 17 章会讲解 Ranges 库本身，而第 20 章则会通过代码示例介绍不受约束算法和受约束算法。

标准库中缺失的东西

标准库功能很强大，但它并不完美。下面举两个例子，说明它尚未覆盖的领域：

标准库并不保证“多个线程同时访问同一个容器”时具备线程安全性。
标准库并没有提供通用的树结构或图结构。虽然 map 和 set 通常内部都是平衡二叉树实现，但标准库并不会把这种实现细节暴露到接口层。如果你需要树或图结构来做例如 parser 这类工作，就必须自己实现，或者从其他库中寻找现成实现。

需要牢记的是，标准库是 可扩展的（extensible）。你完全可以编写自己的容器和算法，并让它们与现有标准库算法和容器协同工作。因此，如果标准库没有直接提供你想要的东西，请考虑把自己的实现写成“能够和标准库协作”的风格。第 25 章会讨论如何借助自定义算法与自定义容器来定制和扩展标准库。或者，你也可以考虑购买或授权使用一个符合标准库规范的第三方库，来满足你所需的功能。第 4 章“设计专业级 C++ 程序”讨论了如何使用第三方库，以及相关授权问题。

总结

本章概览了 C++ 标准库——这是你在编写 C++ 代码时最重要的库。它吸收了 C 语言库的大部分内容，并在其基础上提供了字符串、I/O、错误处理等额外能力。它还包含了泛型容器、算法以及 Ranges 库。后续章节会更详细地介绍标准库的这些组成部分。

练习

通过完成下面这些练习，你可以巩固本章讨论过的内容。所有习题解答都包含在本书网站 www.wiley.com/go/proc++6e 提供的代码下载包中。不过，如果你在某个练习上卡住了，建议先回头重读本章相关部分，尽量自己找到答案，再去查看网站上的解答。

练习 16-1： C++ 标准库为你提供了大量容器可选。那么，你的首选容器应该是什么？为什么？
练习 16-2： map 和 unordered_map 有什么区别？
练习 16-3： 什么是词汇类型？除了本书前面已经使用过的那些词汇类型外，本章还介绍了哪些由 C++ 标准库提供的额外词汇类型？
练习 16-4： 自助餐厅通常有一种带弹簧机构的盘子装置。作为顾客，你总是从最上面取一个盘子；而清洗完毕、重新可用的盘子，也会被放回现有盘子堆的最上面。你会如何在 C++ 中对这样的系统建模？
练习 16-5： 什么是 partition？

search() 还可以接收一个可选额外参数，用来指定所采用的搜索算法（default_searcher、boyer_moore_searcher 或 boyer_moore_horspool_searcher）。使用 Boyer–Moore 系列搜索器时，如果模式未找到，最坏复杂度是 O(N+M)；如果模式找到了，最坏复杂度是 O(N*M)。 ↩ ↩²

C++ 标准库概览

编码原则

模板的使用

运算符重载的使用

C++ 标准库概览

字符串

正则表达式

I/O 流

智能指针

异常

标准整数类型

数值库

整数比较

位操作

时间与日期工具

随机数

初始化列表

Pair 与 Tuple

词汇类型

函数对象

文件系统

多线程

类型萃取

标准库特性测试宏

<version>

源位置

栈追踪

容器

顺序容器

vector

list

forward_list

deque

array

顺序视图

span

mdspan

容器适配器

queue

priority_queue

stack

有序关联容器

set

multiset

map

multimap

无序关联容器 / 哈希表

Flat 关联容器适配器

bitset

标准库容器总结

算法

不修改序列的算法

搜索算法

比较算法

计数算法

修改序列的算法

操作型算法

交换算法

Partition 算法

排序算法

二分查找算法

作用于排序序列的集合算法

其他作用于排序序列的算法

Heap 算法

最小值 / 最大值算法

数值处理算法

排列算法

如何选择算法

Ranges 库

标准库中缺失的东西

总结

练习

Footnotes

`<version>`

`vector`

`list`

`forward_list`

`deque`

`array`

`span`

`mdspan`

`queue`

`priority_queue`

`stack`

`set`

`multiset`

`map`

`multimap`

`bitset`