前言

《C++17 STL Cookbook》将结合C++代码实例和标准库(STL)，教会你如何充分使用C++17。这里要说明的是，本书会尽可能的去使用STL，从而教会大家使用C++17。

C++是一门伟大且具有力量的语言。它使用简单的高级接口，将隐藏复杂的解决方式隐藏于背后，不过这样就意味着需要编写高效和低开销的底层代码实现。国际标准化组织(ISO)C++标准委员会致力于改进C++标准。C++11标准为C++带来了大量不错的特性，C++14和C++17也为C++加入了些新的特性。

目前为止，C++作为一门编程语言提供了语言相应的语言特性个标准库工具，用于处理复杂的标准数据结构和算法，包括：智能指针、Lambda表达式、常量表达式、便捷式可控线程的并发编程、正则表达式、随机数发生器、异常、可变参数模板(C++的部分模板类是图灵完备的!)、自定义文字、便捷式文件系统遍历等等。这些功能使它成为一种通用的语言，并在软件行业的所有领域，用于实现高质量和高性能的软件。

不过，很多编程者只将C++当做一门编程语言学习，而不太重视标准库(STL)的使用。不使用C++所带的标准库，将会让C++看起来就像是具有class的C语言，21世纪的现代化程序不应该写成这样。并且，这样的使用令人沮丧，就像是卸掉了它的一条手臂一样。

Bjarne Stroustrup(C++之父)在他的《C++程序设计语言》(C++11版本)中写到

请牢记，标准库和语言功能都是为了支撑以软件质量为目标的编程技术。他们应被组合起来发挥作用——如同建房子的砖块——而非个别地采用来相对孤立地去解决某个特定问题。

这段话能很明确的概括我写这本书的目的。本书的所有例子都与实际息息相关，处理这些问题时，只依赖与STL，不依赖其他的库。少了其他库的依赖，就能很容易的将程序运行起来，不必去为开发环境所困扰。 我希望你们受这些例子的启发，找到使用标准库的灵感，用伟大的编程语言作为解决更高级问题的基石。

关于本书

本书中所有的例子都很简单，都可以很容易编译和运行，不过读者们还是需要注意一下自己所选择的操作系统和编译器。下面就让我们来看一下在编译和运行本书例程时，所要注意的一些内容。

编译和运行例程

本书的所有例子都在Linux和Mac OS进行开发和验证，我们使用GNU的C++编译器g++，和LLVM的C++编译器 clang++。

shell环境下可以使用如下的命令使用g++编译例程：

$ g++ -std c++lz —o recipe_app recipe_code.cpp

要使用clang++的话，命令行类似:

$ clang++ -std C++ Iz -o recipe_app recipe_code.cpp

上面两个例子都假设我们的C++例程写在 recipe_code.cpp文件中。完成编译后，生成可执行二进制文件recipe_app，然后使用如下命令执行它：

$ . /recipe_app

书中很多例子，都是通过标准输入读取整个文件的内容。遇到这样的例子时，我们使用标准UNIX管道和cat命令直接将文件内容传输给我们的应用，命令如下所示：

$ cat file.txt | ./recipe_app

上面的方法适用于Linux和Mac OS系统。在微软Windows Shell中，需要使用如下的命令:

> recipe app.exe < file.txt

如果你不想在Shell命令行中运行，你可以在Microsoft Visual Studio IDE中运行，不过需要你修改一下配置, "Configuration properties > Debugging ",并且添加"< file. txt" ，使用 Visual Studio加载应用就能直接运行程序了。(Visual Studio IDE的话选定对应的解决方案，右键后选择“属性”，在“调试”页面输入相应的命令行参数)

前期准备

如果最近你阅读了本书中C++17的新特性，并使用前卫的编译器编译了这些代码，你可能会在编译阶段遇到一些问题。因为你使用到的一些C++17 STL新特性可能还没有在编译器中进行实现。

运行本书代码时，需要给<execution_policy> 和<filesystem>头文件添加前缀experimental/ 。其会将你将是用到的一些STL算法、数值等等包含入你的代码中，不过这也取决于编译器标准库的更新程度和稳定性。

这同样使用于命名空间的新特性。标准库中，实验部分的实现并不在std命名空间中，而是在std::experimental中。

适读群体

如果你没有编写过C++程序的经验，那么请将本书放回书架。如果你只想学习有关语言基础的知识，那么本书不是你理想的选择。当你了解完语言基础后，本书会对你的语言技巧进行升级。

除此之外，如果你符合如下的描述的话，可以继续阅读本书：

• 已经了解过C++的基础，不过现在你不知道下一步自己该怎么走，这是因为你与资深C++达人还有很大的差距。
• C++基础十分牢靠，但是你对STL知之甚少。
• 对C++的某个老版本比较了解，比如C++98、C++11或C++14。

以上这些描述，都是基于你使用C++的频度而论。本书储备了很多优秀的STL新特性，等待你去发现。

章节设计

本书中你会发现几个经常出现的标题：

(译者：这些副标题只在本节翻译，正文中使用英文原文作为副标题)

• Getting ready
• How to do it
• How it works
• There's more
• See also

下面简单介绍一些这几个副标题所涵盖的内容：

准备开始 Getting ready

本节会说明我们的期望，以及如何在初期对环境或软件进行配置。

如何完成 How to do it...

本节包含实现所需的步骤。

如何工作 How it works...

本节会对前一节所发生的事情，进行详细解释。

信息补充 There's more...

本节包含了一些式例相关的补充信息，以便读者对式例有更深入的了解。

更多信息 See also

为式例提供一些帮助链接，有助于了解C++的更多知识。

文本样式

本书中，使用不同的文本样式区分不同种类的信息。下面的一些例子会解释这些风格的含义。

文本的代码，数据库表名，文件夹名，文件名，文件的扩展名，路径名，虚拟的URL，用户输入和推特引用，会展示成这种样式： "下一步需要修改build.properties 文件。"

代码块为这种样式：

my_wrapper<T1, T2, T3> make wrapper (Tl t 1, T 2 t2, T3 t3) 
{
  return t 1, t2, t3;
}

新术语和关键字使用粗体。你在屏幕上看到的单词，例如菜单或对话框，会是这种样式: "完成后，点击执行。"

警告或重要说明会显示在一个方框中。

提示和技巧会用斜体样式

读者反馈

我们欢迎读者的反馈。这样我们就知道这本书哪里好，哪里不好。读者的反馈对于我们来说十分重要，并且能帮助我们确定读者关注的重点，从而让读者在阅读本书时的收获最大化。一般的反馈可以通过发送电子邮件到 feedback@packtpub.com，并在主题中提到这本书的名字即可。如果您是某个方便的专家，并且对写作或写书感兴趣的话， 可以了解一下我们的作者指南www.packtpub.com/authors 。

客户支持

现在您已经是本书的主人，我们会为您购买本书的行为，提供相应的支持服务。

源码下载

可使用您在 http://www.packtpub.com 的账号下载本书式例代码。 如果您在别处购买了本书，可以通过访问 http://wmv.packtpub.com/support ，客服会将注册文件直接发送给您。

您可以按照以下步骤下载代码：

• 网页端使用您的电子邮件地址和密码进行登录或注册。将鼠标悬停在“SUPPORT”标签上。点击“Downloads & Errata”。搜索框内键入本书的名字。选择你所查找的书籍，并下载其代码包。只需您在购买本书的下拉菜单中点击“Code Download”即可。
• 压缩包下载完毕后，请确认您所使用的解压缩软件的版本和所解压的文件夹地址。Windows：WinRAR / 7-Zip；Mac ：Zipeg / iZip / UnRarX；Linux ：7-Zip / PeaZip。

本书代码github的托管地址为 https://github.com/PacktPublishing/Cpp17-STL-Cookbook

其他书籍的代码包和视频目录在 https://github.com/PacktPublishing/ 下都能看到。

快去看一下吧！

勘误列表

尽管我们很认真的保证本书内容的正确性，但难免还是会出现错误。如果您在我们的书或代码中发现了疑似错误的地方，请反馈给我们，我们将感激不尽。如果这真是个错误，我们将在后续的版本中修复这个问题，以免误导更多的读者。如果您发现了任何错误，请访问 http://mvw.packtpub.com/submit-errata 选择本书，点击勘误提交的链接，然后详述你发现的问题。当您的勘误得到了验证，您的勘误将会记录在我们的勘误列表上。

想要了解之前的勘误列表, 可以在 https://mwv.packtpub.com/books/content/support 上面输入书籍的名字查找对应的勘误列表。想要看到的内容将会出现在勘误栏下。

盗版必究

互联网上存在着盗版问题。Packt非常重视我们的版权和许可证。如果您在网上发现我们的作品的非法副本，请提供地址或网站名称，以便我们进行维权。

请通过 copyright@packtpub.com 联系我们，麻烦在邮件内附上与涉嫌盗版的相关资料。感谢您帮助我们保护相关作品的只是产权。

问题解答

如果您对本书有任何的问题，您可以通过向 questions@packtpub.com发送邮件告诉我们，我们会尽可能的解答您所提出的问题。

各章梗概

第1章，C++17新特性。介绍那些对C++语言来说很重大的改变，以便后续的章节中将精力集中在STL上。

第2章，STL容器。STL容器在C++17标准中进行了升级，让我们见识一下STL容器的数据类型是多么的丰富。粗略的了解一下容器后，再仔细了解其添加的内容。

第3章，迭代器。迭代器是STL中很重要的概念，其将STL算法和容器数据类型二者紧密联系在一起。我们将用实际例子来了解如何使用迭代器，从而更好的了解迭代器的概念。

第4章，Lambda表达式。这是一种很有意思的编程模式，其为纯函数式编程的方式。C++11标准引入Lambda表达式，C++14和C++17标准为其添加了一些新特性。

第5章，STL基础算法。介绍了STL的标准算法的特点，简单易用、高效、鲁棒性好和高度通用。我们将学习如何使用它们，这样就可以集中精力在解决问题上，而不是浪费时间去重新发明轮子。

第6章，STL算法的高级使用方式。演示如何通过使用STL基本算法，以更简洁的方式编写更复杂的算法，而无需重复代码。本章中，充分利用STL解决更复杂问题的同时，将学习如何结合现有的算法，来创建真正符合需求的新算法。

第7章，字符串，流和正则表达。对STL中关于字符串、通用I/O流和正则表达式的类型进行详细概述。

第8章，工具类。了解STL如何生成随机数、测量时间、管理动态内存、优雅地提示错误等等。我们会来了解一下这些极为有用、高可移植性的工具类，并且会介绍C++17带来的全新STL工具。

第9章，并行和并发。多处理器领域编写代码时，并行和并发就变得很重要。C++11标准首先引入并行和并发的概念，随后C++17进行加强，这对于我们编写并发程序来说有很大的帮助。

第10章，文件系统。虽然之前的STL提供对单个文件读取和操作，但这还无法达到用户的需求。C++17添加了很多新的操作(独立于操作系统库)用于处理文件系统路径，以及对目录进行遍历。

第1章 C++17的新特性

C++11，C++14和C++17标准为C++添加了许多新特性。当前的C++已经和10年前的C++完全不同了。C++标准并不是用来规范语言的，其实为了让相应编译器理解相应的语义，也是为了更好的理解C++标准模板库(STL)。

这本书中的例子展示了如何充分的利用STL。不过，作为本书的第1章，我们还是需要了解一下那些比较重要的新语言特性。掌握了这些新的语言特性，有助于你编写可读性高、可维护性强和表达性清晰的代码。

我们将了解到如何单独访问组对、元组和结构化绑定的数据结构的成员，以及如何使用新的if和switch限制变量的作用范围。新的括号初始化语法于C++11的语法有歧义，虽然看上去是相同的，不过这个已经被新括号初始化规则所修复。模板类实例的类型现在可以从构造函数的参数中自动推断出来，如果对一个模板类进行不同类型的特化，将会产生完全不同的代码，不过现在用constexpr-if就能很容易的表示。大多数情况下，使用折叠表达式处理模板函数的可变参数包，会变得更加容易。最后，在只有头文件的库中使用声明内联变量，来定义全局静态对象会变得更加舒服，这之前的标准中只能在函数中进行。

库的实现者可能比实现应用程序的开发者对本章的示例更感兴趣。虽然我们有足够的理由去了解这些特性，但为了理解本书的其余部分，无需立即理解本章的所有示例。

使用结构化绑定来解包绑定的返回值

C++17配备了一种新的特性——结构化绑定，其可以结合语法糖来自动推到类型，并可以从组对、元组和结构体中提取单独的变量。其他编程语言中，这种特性也被成为解包。

How to do it...

使用结构化绑定是为了能够更加简单的，为绑定了多个变量的结构体进行赋值。我们先来看下在C++17标准之前是如何完成这个功能的。然后，我们将会看到一些使用C++17实现该功能的例子：

• 访问std::pair中的一个元素：假设我们有一个数学函数divide_remainder，需要输入一个除数和一个被除数作为参数，返回得到的分数的整数部分和余数。可以使用一个std::pair来绑定这两个值:

  std::pair<int, int> divide_remainder(int dividend, int divisor);

考虑使用如下的方式访问组对中的单个值：

const auto result (divide_remainder(16, 3));
std::cout << "16 / 3 is " <<
          << result.first << " with a remainder of "
          << result.second << '\n';

与上面的代码段不同，我们现在可以将相应的值赋予对应的变量，这样写出来的代码可读性更高:

auto [fraction, remainder] = divide_remainder(16, 3);
std::cout << "16 / 3 is "
          << fraction << " with a remainder of "
          << remainder << '\n';

• 也能对std::tuple进行结构化绑定：让我们使用下面的实例函数，获取股票的在线信息：

std::tuple<std::string, std::chrono::system_clock::time_point, unsigned>
stock_info(const std::string &name);

我们可以使用如下的方式获取这个例子的各个变量的值：

const auto [name, valid_time, price] = stock_info("INTC");

• 结构化绑定也能用在自定义结构体上。假设有这么一个结构体：

struct employee{
    unsigned id;
    std::string name;
    std::string role;
    unsigned salary;
};

现在我们来看下如何使用结构化绑定访问每一个成员。我们假设有一组employee结构体的实例，存在于vector中，下面使用循环将其内容进行打印：

int main(){
    std::vector<employee> employees{
        /* Initialized from somewhere */
    };
    
    for (const auto &[id, name, role, salary] : employees){
        std::cout << "Name: " << name
                  << "Role: " << role
                  << "Salary: " << salary << '\n';
    }
}

How it works...

结构化绑定以以下方式进行应用：

auto [var1, var2, ...] = <pair, tuple, struct, or array expression>;

• var1, var2, ...表示一个变量列表，其变量数量必须匹配表达式所对应的结构。
• <pair, tuple, struct, or array expression>必须是下面的其中一种：
  • 一个std::pair实例。
  • 一个std::tuple实例。
  • 一个结构体实例。其所有成员都必须是非静态成员，每个成员以基础类定义。结构体中的第一个声明成员赋予第一个变量的值，第二个声明的编程赋予第二个变量的值，依次类推。
  • 固定长度的数组。
• auto部分，也就是var的类型，可以是auto,const auto,const auto&和auto&&。

Note:

不仅为了性能，还必须确保在适当的时刻使用引用，尽量减少不必要的副本。

如果中括号中变量不够，那么编译器将会报错:

std::tuple<int, float, long> tup(1, 2.0, 3);
auto [a, b] = tup; // Does not work

这个例子中想要将三个成员值，只赋予两个变量。编译器会立即发现这个错误，并且提示我们:

error: type 'std::tuple<int, float, long>' decomposes into 3 elements, but only 2 names were provided
auto [a, b] = tup;

There's more...

STL中的基础数据结构都能通过结构结构化绑定直接进行访问，而无需修改任何东西。考虑下面这个例子，循环中打印std::map中的元素：

std::map<std::string, size_t> animal_population {
  {"humans", 7000000000},
  {"chickens", 17863376000},
  {"camels", 24246291},
  {"sheep", 1086881528},
  /* ... */
};

for (const auto &[species, count] : animal_population) {
  std::cout << "There are " << count << " " << species
            << " on this planet.\n";
}

从std::map容器中获取元素的方式比较特殊，我们会在每次迭代时获得一个std::pair<const key_type, value_type>实例。另外每个实例都需要进行结构化绑定(key_type绑定到species字符串上，value_type为一个size_t格式的统计数字)，从而达到访问每一个成员的目的。

在C++17之前，使用std::tie可达到类似的效果:

int remainder;
std::tie(std::ignore, remainder) = divide_remainder(16, 5);
std::cout << "16 % 5 is " << remainder << '\n';

这个例子展示了如何将结果组对解压到两个变量中。std::tie的能力远没有结构化绑定强，因为在进行赋值的时候，所有变量需要提前定义。另外，本例也展示了一种在std::tie中有，而结构化绑定没有的功能：可以使用std::ignore的值，作为虚拟变量。分数部分将会赋予到这个虚拟变量中，因为这里我们不需要用到分数值，所以使用虚拟变量忽略分数值。

Note:

使用结构化绑定时，就不能再使用std::tie创建虚拟变量了，所以我们不得不绑定所有值到命名过的变量上。对部分成员进行绑定的做法是高效的，因为编译器可以很容易的对未绑定的变量进行优化。

回到之前的例子，divide_remainder函数也可以通过使用传入输出参数的方式进行实现：

bool divide_remainder(int dividend, int divisor, int &fraction, int &remainder);

调用该函数的方式如下所示：

int fraction, remainder;
const bool success {divide_remainder(16, 3, fraction, remainder)};
if (success) {
  std::cout << "16 / 3 is " << fraction << " with a remainder of "
            << remainder << '\n';
}

很多人都很喜欢使用特别复杂的结构，比如组对、元组和结构体，他们认为这样避免了中间拷贝过程，所以代码会更快。对于现代编译器来说，这种想法不再是正确的了，这里编译器并没有刻意避免拷贝过程，而是优化了这个过程。(其实拷贝过程还是存在的)。

Note:

与C的语法特征不同，将复杂结构体作为返回值传回会耗费大量的时间，因为对象需要在返回函数中进行初始化，之后将这个对象拷贝到相应容器中返回给调用端。现代编译器支持**返回值优化**(RVO, return value optimization)技术，这项技术可以省略中间副本的拷贝。

将变量作用域限制在if和switch区域内

将变量的生命周期尽可能的限制在指定区域内，是一种非常好的代码风格。有时我们需要在满足某些条件时获得某个值，然后对这个值进行操作。

为了让这个过程更简单，C++17中为if和switch配备了初始化区域。

How to do it...

这个案例中，我们使用初始化语句，来了解下其使用方式：

• if：假设我们要在一个字母表中查找一个字母，我们std::map的成员find完成这个操作：

if (auto itr (character_map.find(c)); itr != character_map.end()) {
  // *itr is valid. Do something with it.
} else {
  // itr is the end-iterator. Don't dereference.
}
// itr is not available here at all

• switch：这个例子看起来像是从玩家输入的字母决定某个游戏中的行为。通过使用switch查找字母相对应的操作：

switch (char c (getchar()); c) {
  case 'a': move_left(); break;
  case 's': move_back(); break;
  case 'w': move_fwd(); break;
  case 'd': move_right(); break;
  case 'q': quit_game(); break;
  case '0'...'9': select_tool('0' - c); break;
  default:
    std::cout << "invalid input: " << c << '\n';
}

How it works...

带有初始化的if和switch相当于语法糖一样。

// if: before C++17
{
    auto var(init_value);
    if (condition){
        // branch A. var is accessible
    } else {
        // branch B. var is accessible
    }
    // var is still accessible
}

// if: since C++17
if (auto var (init_value); condition){
    // branch A. var is accessible
} else {
    // branch B. var is accessible
}
// var is not accessible any longer

// switch: before C++17
{
    auto var (init_value);
    switch (var) {
      case 1: ...
      case 2: ...
      ...
    }
    // var is still accessible
}

// switch: since C++17
switch(auto var (init_value); var){
    case 1: ...
    case 2: ...
    ...
}
// var is not accessible any longer

这些有用的特性保证了代码的简洁性。C++17之前只能使用外部括号将代码包围，就像上面的例子中展示的那样。减短变量的生命周期，能帮助我们保持代码的整洁性，并且更加易于重构。

There's more...

另一个有趣的例子是临界区限定变量生命周期。

先来看个栗子：

if (std::lock_guard<std::mutex> lg {my_mutex}; some_condition) {
  // Do something
}

首先，创建一个std::lock_guard。这个类接收一个互斥量和作为其构造函数的参数。这个类在其构造函数中对互斥量上锁，之后当代码运行完这段区域后，其会在析构函数中对互斥量进行解锁。这种方式避免了忘记解锁互斥量而导致的错误。C++17之前，为了确定解锁的范围，需要一对额外的括号对。

另一个例子中对弱指针进行区域限制：

if (auto shared_pointer (weak_pointer.lock()); shared_pointer != nullptr) {
  // Yes, the shared object does still exist
} else {
  // shared_pointer var is accessible, but a null pointer
}
// shared_pointer is not accessible any longer

这个例子中有一个临时的shared_pointer变量，虽然if条件块或外部括号会让其保持一个无用的状态，但是这个变量确实会“泄漏”到当前范围内。

当要使用传统API的输出参数时，if初始化段就很有用：

if (DWORD exit_code; GetExitCodeProcess(process_handle, &exit_code)) {
  std::cout << "Exit code of process was: " << exit_code << '\n';
}
// No useless exit_code variable outside the if-conditional

GetExitCodeProcess函数是Windows操作系统的内核API函数。其通过返回码来判断给定的进程是否合法的处理完成。当离开条件域，变量就没用了，也就可以销毁这个变量了。

具有初始化段的if代码块在很多情况下都特别有用，尤其是在使用传统API的输出参数进行初始化时。

Note:

使用带有初始化段的if和switch能保证代码的紧凑性。这使您的代码紧凑，更易于阅读，在重构过程中，会更容易改动。

新的括号初始化规则

C++11引入了新的括号初始化语法{}。其不仅允许集合式初始化，而且还是对常规构造函数的调用。遗憾的是，当与auto类型变量结合时，这种方式就很容易出现错误。C++17将会增强这一系列初始化规则。本节中，我们将了解到如何使用C++17语法正确的初始化变量。

How to do it...

一步初始化所有变量。使用初始化语法时，注意两种不同的情况：

• 不使用auto声明的括号初始化：

// Three identical ways to initialize an int:
int x1 = 1;
int x2{1};
int x3(1);

std::vector<int> v1{1, 2, 3}; // Vector with three ints
std::vector<int> v2 = {1, 2, 3}; // same here
std::vector<int> v3(10, 20); // Vector with 10 ints, each have value 20

• 使用auto声明的括号初始化：

auto v {1}; // v is int
auto w {1, 2}; // error: only single elements in direct
              // auto initialization allowed! (this is new)
auto x = {1}; // x is std::initializer_list<int>
auto y = {1, 2}; // y is std::initializer_list<int>
auto z = {1, 2, 3.0}; // error: Cannot deduce element type

How it works...

无auto类型声明时，{}的操作没什么可大惊小怪的。当在初始化STL容器时，例如std::vector，std::list等等，括号初始化就会去匹配std::initializer_list(初始化列表)的构造函数，从而初始化容器。其构造函数会使用一种“贪婪”的方式，这种方式就意味着不可能匹配非聚合构造函数(与接受初始化列表的构造函数相比，非聚合构造函数是常用构造函数)。

std::vector就提供了一个特定的非聚合构造函数，其会使用任意个相同的数值填充vector容器：std::vector<int> v(N, value)。当写成std::vector<int> v{N, value}时，就选择使用initializer_list的构造函数进行初始化，其会将vector初始化成只有N和value两个元素的变量。这个“陷阱”大家应该都知道。

{}与()调用构造函数初始化的方式，不同点在于{}没有类型的隐式转换，比如int x(1.2);和int x = 1.2;通过静默的对浮点值进行向下取整，然后将其转换为整型，从而将x的值初始化为1。相反的，int x{1.2};将会遇到编译错误，初始化列表中的初始值，需要与变量声明的类型完全匹配。

Note:

哪种方式是最好的初始化方式，目前业界是有争议的。括号初始化的粉丝们提出，使用括号的方式非常直观，直接可以调用构造函数对变量进行初始化，并且代码行不会做多于的事情。另外，使用{}括号将会是匹配构造函数的唯一选择，这是因为使用()进行初始化时，会尝试匹配最符合条件的构造函数，并且还会对初始值进行类型转换，然后进行匹配(这就会有处理构造函数二义性的麻烦)。

C++17添加的条件也适用于auto(推断类型)——C++11引入，用于正确的推导匹配变量的类型。auto x{123};中std::initializer_list<int>中只有 一个元素，这并不是我们想要的结果。C++17将会生成一个对应的整型值。

经验法则：

• auto var_name {one_element};将会推导出var_name的类型——与one_element一样。
• auto var_name {element1, element2, ...};是非法的，并且无法通过编译。
• auto var_name = {element1, element2, ...};将会使用std::initializer_list<T>进行初始化，列表中elementN变量的类型均为T。

C++17加强了初始化列表的鲁棒性。

Note:

使用C++11/C++14模式的编译器解决这个问题时，有些编译器会将auto x{123};的类型推导成整型，而另外一些则会推导成 std::initializer_list<int>。所以，这里需要特别注意，编写这样的代码，可能会导致有关可移植性的问题！

构造函数自动推导模板的类型

C++中很多类都需要指定类型，其实这个类型可以从用户所调用的构造函数中推导出来。不过，在C++17之前，这是一个未标准化的特性。C++17能让编译器自动的从所调用的构造函数，推导出模板类型。

How to do it...

使用最简单的方法创建std::pair和std::tuple实例。其可以实现一步创建。

std::pair my_pair (123, "abc"); // std::pair<int, const char*>
std::tuple my_tuple (123, 12.3, "abc"); // std::tuple<int, double, const char*>

How it works...

让我们定义一个类，了解自动化的对模板类型进行推断的价值。

template <typename T1, typename T2, typename T3>
class my_wrapper {
  T1 t1;
  T2 t2;
  T3 t3;
public:
  explicit my_wrapper(T1 t1_, T2 t2_, T3 t3_)
  : t1{t1_}, t2{t2_}, t3{t3_}
  {}
/* ... */
};

好！我们定义了一个模板类。C++17之前，我们为了创建该类的实例：

my_wrapper<int, double, const char *> wrapper {123, 1.23, "abc"};

我们省略模板特化的部分：

my_wrapper wrapper {123, 1.23, "abc"};

C++17之前，我们可能会通过以下的方式实现一个工厂函数：

my_wrapper<T1, T2, T3> make_wrapper(T1 t1, T2 t2, T3 t3)
{
  return {t1, t2, t3};
}

使用工厂函数：

auto wrapper (make_wrapper(123, 1.23, "abc"));

Note:

STL中有很多工厂函数，比如std::make_shared、std::make_unique、std::make_tuple等等。C++17中，这些工厂函数就过时了。当然，考虑到兼容性，这些工厂函数在之后还会保留。

There's more...

我们已经了解过隐式模板类型推导。但一些例子中，不能依赖类型推导。如下面的例子：

// example class
template <typename T>
struct sum{
    T value;
    
    template <typename ... Ts>
    sum(Ts&& ... values) : value{(values + ...)} {}
};

结构体中，sum能接受任意数量的参数，并使用折叠表达式将它们添加到一起(本章稍后的一节中，我们将讨论折叠表达式，以便了解折叠表达式的更多细节)。加法操作后得到的结果保存在value变量中。现在的问题是，T的类型是什么？如果我们不显式的进行指定，那就需要通过传递给构造函数的变量类型进行推导。当我们提供了多个字符串实例，其类型为std::string。当我们提供多个整型时，其类型就为int。当我们提供多个整型、浮点和双浮点时，编译器会确定哪种类型适合所有的值，而不丢失信息。为了实现以上的推导，我们提供了指导性显式推导：

template <typename ... Ts>
sum(Ts&& ... ts) -> sum<std::common_type_t<Ts...>>;

指导性推导会告诉编译器使用std::common_type_t的特性，其能找到适合所有值的共同类型。来看下如何使用：

sum s {1u, 2.0, 3, 4.0f};
sum string_sum {std::string{"abc"}, "def"};
std::cout << s.value << '\n'
          << string_sum.value << '\n';

第1行中，我们创建了一个sum对象，构造函数的参数类型为unsigned, double, int和float。std::common_type_t将返回double作为共同类型，所以我们获得的是一个sun<double>实例。第2行中，我们创建了一个std::string实例和一个C风格的字符串。在我们的指导下，编译器推导出这个实例的类型为sum<std::string>。

当我们运行这段代码时，屏幕上会打印出10和abcdef。其中10为数值sum的值，abcdef为字符串sum的值。

使用constexpr-if简化编译

模板化编程中，通常要以不同的方式做某些事情，比如特化模板类型。C++17带了constexpr-if表达式，可以在很多情况下简化代码。

How to do it...

本节中，我们会实现一个很小的辅助模板类。它能处理不同模板类型的特化，因为它可以在完全不同的代码中，选取相应的片段，依据这些片段的类型对模板进行特化：

1. 完成代码中的通用部分。在我们的例子中，它是一个简单的类，它的成员函数add，支持对U类型值与T类型值的加法:

   template <typename T>
   class addable
   {
     T val;
   public:
     addable(T v) : val{v} {}
     template <typename U>
     T add(U x) const {
       return val + x;
     }
   };
   

2. 假设类型T是std::vector<something>，而类型U是int。这里就有问题了，为整个vector添加整数是为了什么呢？其应该是对vector中的每个元素加上一个整型数。实现这个功能就需要在循环中进行：

   template <typename U>
   T add(U x)
   {
     auto copy (val); // Get a copy of the vector member
     for (auto &n : copy) {
       n += x;
     }
     return copy;
   }
   

3. 下一步也是最后一步，将两种方式结合在一起。如果T类型是一个vector，其每个元素都是U类型，择进行循环。如果不是，则进行普通的加法：

   template <typename U>
   T add(U x) const{
       if constexpr(std::is_same<T, std::vector<U>>::value){
           auto copy(val);
           for (auto &n : copy){
               n += x;
           }
           return copy;
       } else {
           return val + x;
       }
   }
   

4. 现在就可以使用这个类了。让我们来看下其对不同类型处理的是多么完美，下面的例子中有int,float, std::vector<int>和std::vector<string>:

   addable<int> {1}.add(2); // is 3
   addable<float> {1.f}.add(2); // is 3.0
   addable<std::string> {"aa"}.add("bb"); // is "aabb"
   
   std::vector<int> v{1, 2, 3};
   addable<std::vector<int>> {v}.add(10); // is std::vector<int> {11, 12, 13}
   
   std::vector<std::string> sv{"a", "b", "c"};
   addable<std::vector<std::string>> {sv}.add(std::string{"z"}); // is {"az", "bz", "cz"}
   

How it works...

新特性constexpr-if的工作机制与传统的if-else类似。不同点就在于前者在编译时进行判断，后者在运行时进行判断。所以，使用constexpr-if的代码在编译完成后，程序的这一部分其实就不会有分支存在。有种方式类似于constexpr-if，那就是#if-#else的预编译方式进行宏替换，不过这种方式在代码的构成方面不是那么优雅。组成constexpr-if的所有分支结构都是优雅地，没有使用分支在语义上不要求合法。

为了区分是向vector的每个元素加上x，还是普通加法，我们使用std::is_same来进行判断。表达式std::is_same<A, B>::value会返回一个布尔值，当A和B为同样类型时，返回true，反之返回false。我们的例子中就写为std::is_same<T, std::vector<U>>::value()(is_same_v = is_same<T, U>::value;)，当返回为true时，且用户指定的T为std::vector<X>，之后试图调用add，其参数类型U = X。

当然，在一个constexpr-if-else代码块中，可以有多个条件(注意：a和b也可以依赖于模板参数，并不需要其为编译时常量)：

if constexpr(a){
    // do something
} else if constexpr(b){
    // do something else
} else {
    // do something completely different
}

C++17中，很多元编程的情况更容易表达和阅读。

There's more...

这里对比一下C++17之前的实现和添加constexpr-if后的实现，从而体现出这个特性的加入会给C++带来多大的提升：

template <typename T>
class addable{
    T val;
public:
    addable(T v):val{v}{}
    
    template <typename U>
    std::enable_if_t<!std::is_same<T, std::vector<U>>::value, T> 
    add(U x) const {
        return val + x;
    }
    
    template <typename U>
    std::enable_if_t<!std::is_same<T, std::vector<U>>::value, std::vector<U>>
    add (U x) const{
        auto copy(val);
        for (auto &n: copy){
            n += x;
        }
        return copy;
    }
};

在没有了constexpr-if的帮助下，这个类看起特别复杂，不像我们所期望的那样。怎么使用这个类呢？

简单来看，这里重载实现了两个完全不同的add函数。其返回值的类型声明，让这两个函数看起里很复杂；这里有一个简化的技巧——表达式，例如std::enable_if_t<condition, type>，如果条件为真，那么就为type类型，反之std::enable_if_t表达式不会做任何事。这通常被认为是一个错误，不过我们能解释为什么什么都没做。

对于第二个add函数，相同的判断条件，但是为反向。这样，在两个实现不能同时为真。

当编译器看到具有相同名称的不同模板函数并不得不选择其中一个时，一个重要的原则就起作用了：替换失败不是错误(SFINAE, Substitution Failure is not An Error)。这个例子中，就意味着如果函数的返回值来源一个错误的模板表示，无法推断得出，这时编译器不会将这种情况视为错误(和std::enable_if中的条件为false时的状态一样)。这样编译器就会去找函数的另外的实现。

很麻烦是吧，C++17中实现起来就变得简单多了。

只有头文件的库中启用内联变量

这种库在声明函数时，始终是内联的，C++17中允许声明内联变量。C++17之前只能使用其他变通的方法实现内联变量，新标准的支持让实现只有头文件的库更加的容易。

How it's done...

本节中，我们创建一个类，可以作为典型头文件库的成员。其目的就是给定一个静态成员，然后使用inline关键字对其进行修饰，使得其实例在全局范围内都能访问到，在C++17之前这样做是不可能的。

1. process_monitor类必须包含一个静态成员，并且能全局访问。当该单元被重复包含时，会产生符号重定义的问题。

   // foo_lib.hpp
   class process_monitor {
   public:
   static const std::string standard_string{
       "some static globally available string"};
   };
   process_monitor global_process_monitor;
   

2. 多个.cpp文件中包含这个头文件时，链接阶段会出错。为了修复这个问题，添加了inline关键字：

   // foo_lib.hpp
   class process_monitor {
   public:
   static const inline std::string standard_string{
       "some static globally available string"};
   };
   inline process_monitor global_process_monitor;
   

瞧，就是这样！

How it works...

C++程序通常都有多个C++源文件组成(其以.cpp或.cc结尾)。这些文件会单独编译成模块/二进制文件(通常以.o结尾)。链接所有模块/二进制文件形成一个单独的可执行文件，或是动态库/静态库则是编译的最后一步。

当链接器发现一个特定的符号，被定义了多次时就会报错。举个栗子，现在我们有一个函数声明int foo();，当我们在两个模块中定义了同一个函数，那么哪一个才是正确的呢？链接器自己不能做主。这样没错，但是这也可能不是开发者想看到的。

为了能提供全局可以使用的方法，通常会在头文件中定义函数，这可以让C++的所有模块都调用头文件中函数的实现(C++中，头文件中实现的函数，编译器会隐式的使用inline来进行修饰，从而避免符号重复定义的问题)。这样就可以将函数的定义单独的放入模块中。之后，就可以安全的将这些模块文件链接在一起了。这种方式也被称为定义与单一定义规则(ODR，One Definition Rule)。看了下图或许能更好的理解这个规则：

如果这是唯一的方法，就不需要只有头文件的库了。只有头文件的库非常方便，因为只需要使用#include语句将对应的头文件包含入C++源文件/头文件中后，就可以使用这个库了。当提供普通库时，开发者需要编写相应的编译脚本，以便连接器将库模块链接在一起，形成对应的可执行文件。这种方式对于很小的库来说是不必要的。

对于这样例子，inline关键字就能解决不同的模块中使用同一符号采用不同实现的方式。当连接器找到多个具有相同签名的符号时，这些函数定义使用inline进行声明，链接器就会选择首先找到的那个实现，然后认为其他符号使用的是相同的定义。所有使用inline定义的符号都是完全相同的，对于开发者来说这应该是常识。

我们的例子中，连接器将会在每个模块中找到process_monitor::standard_string符号，因为这些模块包含了foo_lib.hpp。如果没有了inline关键字，连接器将不知道选择哪个实现，所以其会将编译过程中断并报错。同样的原理也适用于global_process_monitor符号。

使用inline声明所有符号之后，连接器只会接受其找到的第一个符号，而将后续该符号的不同实现丢弃。

C++17之前，解决的方法是通过额外的C++模块文件提供相应的符号，这将迫使我们的库用户强制在链接阶段包含该文件。

传统的inline关键字还有另外一种功能。其会告诉编译器，可以通过实现直接放在调用它的地方来消除函数调用的过程。这样的话，代码中的函数调用会减少，这样我们会认为程序会运行的更快。如果函数非常短，那么生成的程序段也会很短(假设函数调用也需要若干个指令，保护现场等操作，其耗时会高于实际工作的代码)。当内联函数非常长，那么二进制文件的大小就会变得很大，有时并无法让代码运行的更快。因此，编译器会将inline关键字作为一个提示，可能会对内联函数消除函数调用。当然，编译器也会将一些函数进行内联，尽管开发者没有使用inline进行提示。

There's more...

C++17之前的解决方法就是将对应函数声明为静态函数，这个函数会返回某个静态对象的引用：

class foo{
public:
    static std::string& standard_string(){
        static std::string s{"some standard string"};
        return s;
    }    
};

通过这种方式，将头文件包含在多个模块中是完全合法的，但仍然可以访问相同的实例。不过，对象并没有在程序开始时立即构造，而是在第一次调用这个获取函数时才进行构造。对于一些特定的情况来说，这也个问题。假设我们想要在程序开始时就构造静态和全局函数，从而完成一些比较重要的事情(就和我们的例程库一样)，不过当程序运行后，在调用时去构造这些对象，就会带来比较大的性能开销。

另一个解决方法是将非模板类看做一个模板类，因此非模板类也适用于这项规则。

不过，以上的两种策略在C++17中不太适用了，C++17已经使用新的inline完美解决。

使用折叠表达式实现辅助函数

自C++11起，加入了变长模板参数包，能让函数结构任意数量的参数。有时，这些参数都组合成一个表达式，从中得出函数结果。C++17中使用折叠表达式，可以让这项任务变得更加简单。

How to do it...

首先，实现一个函数，用于将所有参数进行累加：

1. 声明该函数：

   template <typename ... Ts>
   auto sum(Ts ... ts);
   

2. 那么现在我们拥有一个参数包ts，并且函数必须将参数包展开，然后使用表达式进行求和。如果我们对这些参数进行某个操作(比如：加法)，那么为了将这个操作应用于该参数包，就需要使用括号将表达式包围：

   template<typename ... Ts>
   auto sum(Ts ... ts){
   	return (ts + ...);
   }
   

3. 现在我们可以调用这个函数：

   int the_sum {sum(1, 2, 3, 4, 5)}; // value: 15
   

4. 这个操作不仅对int类型起作用，我们能对任何支持加号的类型使用这个函数，比如std::string:

   std::string a{"Hello "};
   std::string b{"World"};
   
   std::cout << sum(a, b) << '\n'; // output: Hello World
   

How it works...

这里只是简单的对参数集进行简单的递归，然后应用二元操作符+将每个参数加在一起。这称为折叠操作。C++17中添加了折叠表达式，其能用更少的代码量，达到相同的结果。

其中有种称为一元折叠的表达式。C++17中的折叠参数包支持如下二元操作符：+ - * / % ^ & | = < > << >> += -= *= /= %= ^= &= |= <<= >>= == != <= >= && || , .* ->*。

这样的话，在我们的例子中表达式(ts+...)和(...+ts)等价。不过，对于某些其他的例子，这就所有不同了——当...在操作符右侧时，称为有“右折叠”；当...在操作符左侧时，称为”左折叠“。

我们sum例子中，一元左折叠的扩展表达式为1+(2+(3+(4+5)))，一元右折叠的扩展表达式为(((1+2)+3)+4)+5。根据操作符的使用，我们就能看出差别。当用来进行整数相加，那么就没有区别。

There's more...

如果在调用sum函数的时候没有传入参数，那么可变参数包中就没有可以被折叠的参数。对于大多数操作来说，这将导致错误(对于一些例子来说，可能会是另外一种情况，我们后面就能看到)。这时我们就需要决定，这时一个错误，还是返回一个特定的值。如果是特定值，显而易见应该是0。

如何返回一个特定值：

template <typenme ... Ts>
auto sume(Ts ... ts){
	return (ts + ... + 0);
}

sum()会返回0，sum(1, 2, 3)返回(1+(2+(3+0)))。这样具有初始值的折叠表达式称为二元折叠。

当我们写成(ts + ... + 0)或(0 + ... + ts)时，不同的写法就会让二元折叠表达式处于不同的位置(二元右折叠或二元左折叠)。下图可能更有助于理解左右二元折叠：

为了应对无参数传入的情况，我们使用二元折叠表达式，这里标识元素这个概念很重要——本例中，将0加到其他数字上不会有任何改变，那么0就一个标识元素。因为有这个属性，对于加减操作来说，可以将0添加入任何一个折叠表达式，当参数包中没有任何参数时，我们将返回0。从数学的角度来看，这没问题。但从工程的角度，我们需要根据我们需求，定义什么是正确的。

同样的原理也适用于乘法。这里，标识元素为1：

template <typename ... Ts>
auto product(Ts ... ts){
	return (ts * ... * 1);
}

product(2, 3)的结果是6，product()的结果是1。

逻辑操作符and(&&)和or(||)具有内置的标识元素。&&操作符为true，||操作符为false。

对于逗号表达式来说，其标识元素为void()。

为了更好的理解这特性，让我们可以使用这个特性来实现的辅助函数。

匹配范围内的单个元素

如何告诉函数在一定范围内，我们提供的可变参数至少包含一个值：

template <typename R, typename ... Ts>
auto matches(const R& range, Ts ... ts)
{
	return (std::count(std::begin(range), std::end(range), ts) + ...);
}

辅助函数中使用STL中的std::count函数。这个函数需要三个参数：前两个参数定义了迭代器所要遍历的范围，第三个参数则用于与范围内的元素进行比较。std::count函数会返回范围内与第三个参数相同元素的个数。

在我们的折叠表达式中，我们也会将开始和结束迭代器作为确定范围的参数传入std::count函数。不过，对于第三个参数，我们将会每次从参数包中放入一个不同参数。最后，函数会将结果相加返回给调用者。

可以这样使用:

std::vector<int> v{1, 2, 3, 4, 5};

matches(v, 2, 5); // return 2
matches(v, 100, 200); // return 0
matches("abcdefg", 'x', 'y', 'z'); // return 0
matches("abcdefg", 'a', 'b', 'f'); // return 3

如我们所见，matches辅助函数十分灵活——可以直接传入vector或string直接调用。其对于初始化列表也同样适用，也适用于std::list，std::array，std::set等STL容器的实例。

检查集合中的多个插入操作是否成功

我们完成了一个辅助函数，用于将任意数量参数插入std::set实例中，并且返回是否所有插入操作都成功完成：

template <typename T, typename ... Ts>
bool insert_all(T &set, Ts ... ts)
{
	return (set.insert(ts).second && ...);
}

那么这个函数如何工作呢？std::set的insert成员函数声明如下：

std::pair<iterator, bool> insert(const value_type& value);

手册上所述，当我们使用insert函数插入一个元素时，该函数会使用一个包含一个迭代器和一个布尔值的组对作为返回值。当该操作成功，那么迭代器指向的就是新元素在set实例中的位置。否则，迭代器指向某个已经存在的元素，这个元素与插入项有冲突。

我们的辅助函数在完成插入后，会访问.second区域，这里的布尔值反映了插入操作成功与否。如果所有插入操作都为true，那么都是成功的。折叠标识使用逻辑操作符&&链接所有插入结果的状态，并且返回计算之后的结果。

可以这样使用它：

std::set<int> my_set{1, 2, 3};

insert_all(my_set, 4, 5, 6); // Returns true
insert_all(my_set, 7, 8, 2); // Returns false, because the 2 collides

需要注意的是，当在插入3个元素时，第2个元素没有插入成功，那么&&会根据短路特性，终止插入剩余元素：

std::set<int> my_set{1, 2, 3};

insert_all(my_set, 4, 2, 5); // Returns flase
// set contains {1, 2, 3, 4} now, without the 5!

检查所有参数是否在范围内

当要检查多个变量是否在某个范围内时，可以多次使用查找单个变量是否在某个范围的方式。这里我们可以使用折叠表达式进行表示：

template <typename T, typename ... Ts>
bool within(T min, T max, Ts ...ts)
{
	return ((min <= ts && ts <= max) && ...);
}

表达式(min <= ts && ts <= max)将会告诉调用者参数包中的每一个元素是否在这个范围内。我们使用&&操作符对每次的结果进行处理，从而返回最终的结果。

如何使用这个辅助函数：

within(10, 20, 1, 15, 30); // --> false
within(10, 20, 11, 12, 13); // --> true
within(5.0, 5.5, 5.1, 5.2, 5.3) // --> true

这个函数也是很灵活的，其只需要传入的参数类型可以进行比较，且支持<=操作符即可。并且该规则对于std::string都是适用的：

std::string aaa {"aaa"};
std::string bcd {"bcd"};
std::string def {"def"};
std::string zzz {"zzz"};

within(aaa, zzz, bcd, def); // --> true
within(aaa, def, bcd, zzz); // --> false

将多个元素推入vector中

可以编写一个辅助函数，不会减少任何结果，又能同时处理同一类的多个操作。比如向std::vector传入元素:

template <typename T, typename ... Ts>
void insert_all(std::vector<T> &vec, Ts ... ts){
	(vec.push_back(ts), ...);
}

int main(){
	std::vector<int> v{1, 2, 3};
	insert_all(v, 4, 5, 6);
}

需要注意的是，使用了逗号操作符将参数包展开，然后推入vector中。该函数也不惧空参数包，因为逗号表达式具有隐式标识元素，void()可以翻译为什么都没做。

第2章 STL容器

C++标准库中有大量的标准容器。容器通常包含一组数据或对象的集合。容器的厉害之处在于几乎可以和任何类型的对象一起使用，所以我们只需要为程序选择合适的容器即可。STL带给我们栈、自动增长的vector、map等等。这样我们就可以集中精力于我们的应用，而不用重复制作轮子。了解所有容器，对于C++开发者来说至关重要。

STL容器的分类如下，会在各节中进行详细描述：

• 连续存储
• 列表存储
• 搜索树
• 哈希表
• 容器适配器

连续存储

想要存储一组对象最简单的方式，就是将其一个接一个的存在一块比较大的内存当中。内存可以使用随机访问的方式进行，其时间复杂度为O(1)。

最简单的方式就是使用std::array，其就是对C风格数组的一种包装。不过，std::array要比C风格数组要先进的多，因为其没有运行时开销，而且进行元素添加时，也会十分舒适和安全。还有一点和C风格数组一样，一旦创建，其长度就是固定的，创建过后无法改变长度。

std::vector和std::array很类似，不过std::vector的长度可变。其会使用堆上的内存来存储对象。当新元素添加到vector中后，当前长度超过了原始的长度，那么std::vector会自动新分配一段更大的内存，用来放置包括新插入元素的所有元素，并且释放之前所占用的内存。此外，当新元素需要插入到两个旧元素之间时，std::vector会移动当前已有的元素。当要删除vector中间的一个已存在元素，那么vector类会自动地移动其他对象，将删除后的缝隙填补起来。

如果有大量元素在std::vector的头部或尾部进行插入或删除，那么为了填补空隙和移动已有元素，将会耗费很多时间。如遇到这样的情况，建议你考虑使用std::deque。对象集合会存储在多段固定长度的连续内存中，这些内存段是相互独立的。这就使得双向队列变得很简单，并且增长也很容易，因为不同的内存段相对独立，只需要将新分配的内存段加入就可以了，无需对其他已存在的内存段进行移动。减少的场景也是一样的。

列表存储

std::list是一个典型的双向链表。如果是单向列表，那就需要进行遍历，所以std::forward_list的优势在维护的复杂性上，因为其指针方向只有一个方向。列表遍历的时间复杂度是线性的O(n)。其在特定位置上插入和删除元素的时间复杂度为O(1)。

搜索树

当对象集具有可进行排序的自然属性时，可以使用小于的关系将这些元素进行排序，我们就可以使用搜索树来保存这个排序关系。从名字就可以看出，搜索树可以帮助我们很容易的通过一个关键字查找到对应元素，其搜索的时间复杂度为O(log(n))。

STL提供了不同种类的树，std::set是其中最简单的一种，保存元素不重复，存储的元素是可排序的(用一种树的结构)。

std::map使用的是另一种方式，将存储的数据使用组对进行存储。一个组对有一个key值和一个对应值构成。搜索树会对key值部分进行排序，使组对能作为std::map的一种关联容器。std::map的key值和std::set的值一样，在整个树中只能存在一个。

std::multiset和std::multimap是被特化的，key对象可以是重复的。

哈希表

讨论关联容器时，搜索树并不是唯一的方式。使用哈希表查找元素的时间复杂度只有O(1)，不过这就会忽略其自然序，所以不能简单的使用排序的方式进行遍历。哈希表大小可由用户控制，并且可以单独选择哈希函数，这是一项很重要的特性，因为其性能与空间复杂度依赖于此。

std::unordered_set和std::unordered_map具有很多接口与std::set和std::map一样，它们之间几乎可以相互替换。

搜索树的实现中，容器都具有多个变种： std::unordered_multiset和std::unordered_multimap，这两种方法都取消了对象/键的唯一性，因此我们可以用相同的键存储多个元素。

容器适配器

数组、列表、树和哈希表并不是存储和访问数据的唯一方式，这里还有栈、队列等其他的方式也可以存储和访问数据。类似的，越复杂的结构可以使用越原始的方式实现，并且STL使用以下形式的容器适配器进行操作：std::stack、std::queue和std::priotity_queue。

最牛X的是当我们需要这样的数据结构时，我们可以选择一种适配器。然后，当我们觉得到它们性能较差时，就可以改变一个模板参数，以便让适配器使用不同的容器实现。实践中，这也就意味着我们可以将std::stack实例中的元素类型从std::vector切换成std::deque。

擦除/移除std::vector元素

由于std::vector能自动增长，并且使用方式简单，很受C++开发新手的喜爱。可以通过查阅手册，来了解这个容器该如何使用，比如删除元素。这样使用STL容器，只是了解容器的皮毛，容器应该帮助我们写出更简洁、维护性好和更快的代码。

本节的全部内容都是在一个vector实例中删除元素。当vector中部的一个元素消失了，那么位于消失元素右边的所有元素都要往左移(这种操作的时间复杂度为O(n)。新手们会用循环来做这件事，因为循环的确好用。不过，循环会降低代码的优化空间。最后，比起STL的方法，循环是既不快，也不美，

How to do it...

首先，我们使用整数来填充一个std::vector实例，之后剔除一些特定元素。我们演示的从vector实例中删除元素正确的方法。

1. 包含文件是首要任务。

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

2. 声明我们所要使用的命名空间。

   using namespace std;
   

3. 现在我们来创建一个vector实例，并用整数填满它。

   int main(){
       vector<int> v{1, 2, 3, 2, 5, 2, 6, 2, 4, 8};
   

4. 然后移除一些元素。需要我们移除哪些呢？2出现的太多次了，就选择2吧。让我们移除它们吧。

   	const auto new_end(remove(begin(v), end(v), 2)); 
   

5. 已经完成了两步中的一步。vector在删除这些元素之后，长度并没有发生变化。那么下一步就让这个vector变得短一些。

   	v.erase(new_end, end(v));
   

6. 我们在这里暂停一下，输出一下当前vector实例中所包含的元素。

       for(auto i : v){
           cout << i << ", "; 
       }
       cout << '\n';
   

7. 现在，让我们来移除一组指定的数据。为了完成这项工作，我们先定义了一个谓词函数，其可接受一个数作为参数，当这个数是奇数时，返回true。

   	const auto odd([](int i){return i % 2 != 0;});
   

8. 这里我们使用remove_if函数，使用上面定义的谓词函数，来删除特定的元素。这里我们将上面删除元素的步骤合二为一。

   	v.erase(remove_if(begin(v), end(v), odd), end(v));
   

9. 所有的奇数都被删除，不过vector实例的容量依旧是10。最后一步中，我们将其容量修改为正确的大小。需要注意的是，这个操作会让vector重新分配一段内存，以匹配相应元素长度，vector中已存的元素会移动到新的内存块中。

   	v.shrink_to_fit();
   

10. 打印一下现在vector实例中的元素。

    	for (auto i : v) {
    		cout << i << ", ";
    	}
    	cout << '\n';
    }
    

11. 编译完成后，运行程序，就可以了看到两次删除元素后vector实例中所存在的元素。

    $ ./main
    1, 3, 5, 6, 4, 8,
    6, 4, 8,
    

How it works...

我们可以清楚的看到，要从一个vector实例中移除一个元素，首先要进行删除，然后进行擦除，这样才算真正的移除。这会让人感到困惑，那就让我们近距离观察一下这些步骤是如何工作的。

从vector中移除2的代码如下所示：

const auto new_end (remove(begin(v), end(v), 2));
v.erase(new_end, end(v));

std::begin和std::end函数都以一个vector实例作为参数，并且返回其迭代器，迭代器分别指向第一个元素和最后一个元素，就如下图所示。

std::remove在删除2的时候，会先将非2元素进行移动，然后修改end迭代器的指向。该算法将严格保留所有非2个值的顺序。

在2步中，2的值仍然存在，并且vector应该变短。并且4和8在现有的vector中重复了。这是怎么回事？

让我们再来看一下所有的元素，目前vector的范围并不是原来那样了，其是从begin迭代器，到new_end迭代器。new_end之后的值其实就不属于vector实例了。我们会注意到，在这个范围内的数值，就是我们想要的正确结果，也就是所有的2都被移除了。

最后，也就是为什么要调用erase函数：我们需要告诉vector实例，new_end到end之间的元素我们不需要了。我们仅需要保留begin到new_end间的元素就好了。erase函数会将end指向new_end。这里需要注意的是std::remove会直接返回new_end迭代器，所以我们可以直接使用它。

Note:

vector在这里不仅仅移动了内部指针。如果vector中元素比较复杂，那么在移除的时候，会使用其析构函数来销毁相应的对象。

最后，这个向量就如步骤3所示：的确变短了。那些旧的元素已经不在vector的访问范围内了，不过其仍存储在内存中。

为了不让vector浪费太多的内存，我们在最后调用了shrink_to_fit。该函数会为元素分配足够的空间，将剩余的元素移到该空间内，并且删除之前那个比较大的内存空间。

在上面的第8步中，我们定义了一个谓词函数，并在std::remove_if中使用了它。因为不论删除函数返回怎么样的迭代器，在对vector实例使用擦除函数都是安全的。如果vector中全是偶数，那么std::remove_if不会做任何事情，并且返回end迭代器。之后的调用就为v.erase(end, end);，同样没有做任何事情。

There's more...

std::remove函数对其他容器同样有效。当使用std::array时，其不支持erase操作，因为其内存空间固定，无法进行自动化处理。因为std::remove只是将要删除的元素移动到容器末尾，而不是将其真正删除，所以这个函数也可以用于不支持空间大小变化的数据类型。当然也有其他类似的方法，例如字符串中，可以用哨兵值\0来覆盖原始的end迭代所指向的值。

以O(1)的时间复杂度删除未排序std::vector中的元素

因为其他元素要填补删除元素所留下来的空隙，从而需要进行移动，所以从std::vector中删除元素的时间复杂度为O(n)。

移动其他元素也与此类似，当很多很大或很复杂的元素需要移动，那么就会花费很长的时间。当无法保证顺序时，我们需要对其进行优化，这就是本节的内容。

How to do it...

我们继续使用一些数字来填充std::vector实例，并且实现一个快速删除函数，以O(1)的时间复杂度删除vector中的元素。

1. 首先，包含必要的头文件：

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

2. 定义主函数，并定义一个vector实例：

   int main(){
       std::vector<int> v{123, 456, 789, 100, 200}; 
   

3. 下一步就要删除索引为2的元素(789)。我们所要用的来删除元素的函数在后面进行实现，我们先假设已经实现好了。执行完成后，来看下vector中的内容。

       quick_remove_at(v, 2);
       for (int i : v){
           std::cout << i << ", ";
       }
       std::cout << '\n';
   

4. 现在，我们将删除另外一个元素。我们想删除123，但是要假装不知道其索引。因此，我们要使用std::find函数在vector的合法范围内查找这个值，并返回其位置信息。得到索引信息后，我们就可以用quick_remove_at将对应元素删除了，这里所使用到的是一个重载版本，能接受迭代器作为输入参数。

       quick_remove_at(v, std::find(std::begin(v), std::end(v), 123));
       for (int i : v) {
      		std::cout << i << ", ";
       }
       std::cout << '\n';
   }
   

5. 我们实现了两种quick_remove_at函数。具体实现代码中，需要注意与main函数的前后关系。两个函数都能接收一个vector实例的引用，所以这里允许用户使用各种类型的变量作为元素。对于我们来说，其类型就是T。第一个 quick_remove_at函数用来接收索引值，是一个具体的数，所以其接口如下所示：

   template <typename T>
   void quick_remove_at(std::vector<T> &v, std::size_t idx)
   {
   

6. 现在来展示一下本节的重点——如何在不移动其他元素的情况下，快速删除某个元素？首先，将vector中最后一个元素进行重写。第二，删除vector中最后一个元素。就这两步。我们的代码会对输入进行检查。如果输入的索引值超出了范围，函数不会做任何事情。另外，该函数会在传入空vector的时候崩溃。

       if (idx < v.size()) {
           v[idx] = std::move(v.back());
           v.pop_back();
       }
   }
   

7. 另一个quick_remove_at实现也很类似。用std::vector<T>的迭代器替换了具体的索引数值。因为泛型容器已经定义了这样的类型，所以获取它的类型并不复杂。

   template <typename T>
   void quick_remove_at(std::vector<T> &v,
   				    typename std::vector<T>::iterator it)
   {
   

8. 现在我们来访问这些迭代器所指向的值。和另一个函数一样，我们会将最后一个元素进行重写。因为这次处理的是迭代器，所以我们要对迭代器指向的位置进行检查。如果其指向了一个错误的位置，我们就会阻止其解引用。

   	if (it != std::end(v)) {
   

9. 在该代码块中，我们会做和之前一样的事情——我们要覆盖最后一个位置上的值——然后将最后一个元素从vector中剪掉。

           *it = std::move(v.back());
           v.pop_back();
       }
   }
   

10. 这就完事了。让我们来编译程序，并运行：

$ ./main
123, 456, 200, 100,
100, 456, 200,

How it works...

quick_remove_at函数移除元素非常快，而且不需要动其他元素。这个函数使用了更加具有创造性的做法：这是一种与实际元素交换的方式，然后将最后一个元素从vector中删除。虽然，最后一个元素与选中的元素没有实际的关联，但是它在这个特别的位置上，而且删除最后一个元素的成本最低！vector的长度在删除完成后，也就减少1，这就是这个函数所要做的。并且无需移动任何元素。看一下下面的图，可能有助于你理解这个函数的原理。

完成这两步的代码如下：

v.at(idx) = std::move(v.back());
v.pop_back();

迭代器版本实现几乎一模一样：

*it = std::move(v.back());
v.pop_back();

逻辑上，我们将选定元素与最后一个元素进行交换。不过，在代码中元素并没有进行交换，代码直接使用最后一个值覆盖了选定元素的值。为什么要这样？当我们交换元素时，就需要将选定的元素存储在一个临时变量中，并在最后将这个临时变量中的值放在vector的最后。这个临时变量是多余的，而且要删除的值对于我们来说是没有意义的，所以这里选择了直接覆盖的方式，更加高效的实现了删除。

好了，交换是无意义的，覆盖是一种更好的方式。让我们来看下这个，当我们要获取vector最后元素的迭代器时，只需要简单的执行*it = v.back();就行了，对吧？完全正确，不过试想我们存储了一些非常长的字符串在vector中，或存储了另一个vector或map——这种情况下，简单的赋值将对这些值进行拷贝，那么就会带来非常大的开销。这里使用std::move可将这部分开销优化掉：比如字符串，指向堆内存上存储的一个大字符串。我们无需拷贝它。只需要移动这个字符串即可，就是将目标指针指向这块地址即可。移动源保持不变，不过出于无用的状态，这样做可以类似的让目标指针指向源指针所在的位置，然后将原始位置的元素删除，这样做即完成了元素移动，又免去了移动消耗。

快速或安全的访问std::vector实例的方法

std::vector可能是STL容器中适用范围最广的，因为其存储数据的方式和数组一样，并且还有相对完善的配套设施。不过，非法访问一个vector实例还是十分危险的。如果一个vector实例具有100个元素，那当我们想要访问索引为123的元素时，程序就会崩溃掉。如果不崩溃，那么你就麻烦了，未定义的行为会导致一系列奇奇怪怪的错误，查都不好查。经验丰富的开发者会在访问前，对索引进行检查。这样的检查其实比较多余，因为很多人不知道std::vector有内置的检查机制。

How to do it...

本节我们将使用两种不同的方式访问一个std::vector实例，并且利用其特性编写更加安全的代码。

1. 先包含相应的头文件，并且用1000个123填满一个vector实例：

   #include <iostream>
   #include <vector>
   using namespace std;
   int main()
   {
       const size_t container_size{1000};
       vector<int> v(container_size, 123);
   

2. 我们通过[]操作符访问范围之外的元素：

       cout << "Out of range element value: "
            << v[container_size + 10] << '\n';
   

3. 之后我们使用at函数访问范围之外的元素：

       cout << "Out of range element value: "
            << v.at(container_size + 10) << '\n';
   }
   

4. 让我们运行程序，看下会发生什么。下面的错误信息是由GCC给出。其他编译器也会通过不同方式给出类似的错误提示。第一种方式得到的结果比较奇怪。超出范围的访问方式并没有让程序崩溃，但是访问到了与123相差很大的数字。第二种方式中，我们看不到打印出来的结果，因为在打印之前程序已经崩溃了。当越界访问发生的时候，我们可以通过异常的方式更早的得知！

   Out of range element value: -726629391
   terminate called after throwing an instance of 'std::out_of_range'
   what(): array::at: __n (which is 1010) >= _Nm (which is 1000)
   Aborted (core dumped)
   

How it works...

std::vector提供了[]操作符和at函数，它们的作用几乎是一样的。at函数会检查给定的索引值是否越界，如果越界则返回一个异常。这对于很多情景都十分适用，不过因为检查越界要花费一些时间，所以at函数会让程序慢一些。

当需要非常快的索引成员时，并能保证索引不越界，我们会使用[]快速访问vector实例。很多情况下，at函数在牺牲一点性能的基础上，有助于发现程序内在的bug。

Note：

默认使用at函数是一个好习惯。当代码的性能很差，但没有bug存在时，可以使用性能更高的操作符来替代at函数。

There's more...

当然，我们需要处理越界访问，避免整个程序崩溃。为了对越界访问进行处理，我们可以使用截获异常的方式。可以用try代码块将调用at函数的部分包围，并且定义错误处理的catch代码段。

try {
	std::cout << "Out of range element value: "
        	  << v.at(container_size + 10) << '\n';
} catch (const std::out_of_range &e) {
	std::cout << "Ooops, out of range access detected: "
              << e.what() << '\n';
}

Note:

顺带一提，std::array也提供了at函数。

保持对std::vector实例的排序

array和vector不会对他们所承载的对象进行排序。有时我们去需要排序，但这不代表着我们总是要去切换数据结构，需要排序能够自动完成。在我们的例子有如有一个std::vector实例，将添加元素后的实例依旧保持排序，会是一项十分有用的功能。

How to do it...

本节中我们使用随机单词对std::vector进行填充，然后对它进行排序。并在插入更多的单词的同时，保证vector实例中单词的整体排序。

1. 先包含必要的头文件。

   #include <iostream>
   #include <vector>
   #include <string>
   #include <algorithm>
   #include <iterator>
   #include <cassert>
   

2. 声明所要使用的命名空间。

   using namespace std;
   

3. 完成主函数，使用一些随机单词填充vector实例。

   int main()
   {
       vector<string> v {"some", "random", "words",
                         "without", "order", "aaa",
                         "yyy"};
   

4. 对vector实例进行排序。我们使用一些断言语句和STL中自带的is_sorted函数对是否排序进行检查。

       assert(false == is_sorted(begin(v), end(v)));
       sort(begin(v), end(v));
       assert(true == is_sorted(begin(v), end(v)));
   

5. 这里我们使用insert_sorted函数添加随机单词到已排序的vector中，这个函数我们会在后面实现。这些新插入的单词应该在正确的位置上，并且vector实例需要保持已排序的状态。

       insert_sorted(v, "foobar");
       insert_sorted(v, "zzz");
   

6. 现在，我们来实现insert_sorted函数。

   void insert_sorted(vector<string> &v, const string &word)
   {
       const auto insert_pos (lower_bound(begin(v), end(v), word));
       v.insert(insert_pos, word);
   }
   

7. 回到主函数中，我们将vector实例中的元素进行打印。

       for (const auto &w : v) {
       	cout << w << " ";
       }
       cout << '\n';
   }	
   

8. 编译并运行后，我们得到如下已排序的输出。

   aaa foobar order random some without words yyy zzz
   

How it works...

程序整个过程都是围绕insert_sorted展开，这也就是本节所要说明的：对于任意的新字符串，通过计算其所在位置，然后进行插入，从而保证vector整体的排序性。不过，这里我们假设的情况是，在插入之前，vector已经排序。否则，这种方法无法工作。

这里我们使用STL中的lower_bound对新单词进行定位，其可接收三个参数。头两个参数是容器开始和结尾的迭代器。这确定了我们单词vector的范围。第三个参数是一个单词，也就是要被插入的那个。函数将会找到大于或等于第三个参数的首个位置，然后返回指向这个位置的迭代器。

获取了正确的位置，那就使用vector的成员函数insert将对应的单词插入到正确的位置上。

There's more...

insert_sorted函数很通用。如果需要其适应不同类型的参数，这样改函数就能处理其他容器所承载的类型，甚至是容器的类似，比如std::set、std::deque、std::list等等。(这里需要注意的是成员函数lower_bound与 std::lower_bound等价，不过成员函数的方式会更加高效，因为其只用于对应的数据集合)

template <typename C, typename T>
void insert_sorted(C &v, const T &item)
{
    const auto insert_pos (lower_bound(begin(v), end(v), item));
    v.insert(insert_pos, item);
}

当我们要将std::vector类型转换为其他类型时，需要注意的是并不是所有容器都支持std::sort。该函数所对应的算法需要容器为可随机访问容器，例如std::list就无法进行排序。

向std::map实例中高效并有条件的插入元素

我们需要用键值对填充一个map实例时，会碰到两种不同的情况：

1. 键不存在。创建一个全新的键值对。
2. 键已存在。修改键所对应的值。

我通常会使用insert或emplace函数对map插入新元素，如果插入不成功，那么就是第二种情况，就需要去修改现有的元素。insert和emplace都会创建一个新元素尝试插入到map实例中，不过在第二种情况下，这个新生成的元素会被扔掉。两种情况下，我们都会多余调用一次构造函数。

C++17中，添加了try_emplace函数，其只有在满足条件的情况下，才能插入新元素。让我们实现一个程序，建立一张表，列出各国亿万富翁的数量。我们例子中不会使用很大开销进行元素创建，不过我们的例子来源于生活，其能让你明白如何使用try_emplace。

How to do it...

本节中，我们将实现一个应用，其能创建一张百万富翁的列表。这个列表中按国家区分，里面记录了各国富人的数量。

1. 包含头文件和声明命名空间。

   #include <iostream>
   #include <functional>
   #include <list>
   #include <map>
   
   using namespace std;
   

2. 定义一个结构器，代表对应的富翁。

   struct billionaire {
       string name;
       double dollars;
       string country;
   };
   

3. 主函数中，我们定义了一个百万富翁的列表。世界上有很多百万富翁，所以我们创建一个有限列表来存储这些富翁的信息。这个列表是已排序的。2017年福布斯富豪名单，世界百万富翁排行榜可以在 https://www.forbes.com/billionaires/list 查到。

   int main()
   {
       list<billionaire> billionaires {
           {"Bill Gates", 86.0, "USA"},
           {"Warren Buffet", 75.6, "USA"},
           {"Jeff Bezos", 72.8, "USA"},
           {"Amancio Ortega", 71.3, "Spain"},
           {"Mark Zuckerberg", 56.0, "USA"},
           {"Carlos Slim", 54.5, "Mexico"},
           // ...
           {"Bernard Arnault", 41.5, "France"},
           // ...
           {"Liliane Bettencourt", 39.5, "France"},
           // ...
           {"Wang Jianlin", 31.3, "China"},
           {"Li Ka-shing", 31.2, "Hong Kong"}
           // ...
       };
   

4. 现在让我们定义一个表。这个表由表示国家名的字符串和一个组对构成。组对中会具有上面列表的一个(const)副本。这也就是每个国家最富有的人。组对中另一个变量是一个计数器，其会统计某国的富豪人数。

   	map<string, pair<const billionaire, size_t>> m;	
   

5. 现在，让我们将列表中的数据尝试插入到组对中。每个组对中都包含了对应国家的百万富翁，并将计数器的值置成1。

   	for (const auto &b : billionaires) {
   		auto [iterator, success] = m.try_emplace(b.country, b, 1);
   

6. 如果这一步成功，那就不用再做其他事了。我们使用b和1创建的组对已经插入到表中。如果因为键已存在而插入失败，那么组对就不会构建。当我们百万富翁结构体非常大时，我们需要将运行时拷贝的时间节省下来。不过，在不成功的情况下，我们还是要对计数器进行增加1的操作。

       if (!success) {
           iterator->second.second += 1;
           }
       }
   

7. 现在，我们来打印一下每个国家百万富翁的数量，以及各个国家中最富有的人。

       for (const auto & [key, value] : m) {
           const auto &[b, count] = value;
           cout << b.country << " : " << count
          	     << " billionaires. Richest is "
                << b.name << " with " << b.dollars
                << " B$\n";
       }
   }
   

8. 编译并运行程序，就会得到下面的输出(这里的输出是不完整的，因为列表比较长)。

   $ ./efficient_insert_or_modify
   China : 1 billionaires. Richest is Wang Jianlin with 31.3 B$
   France : 2 billionaires. Richest is Bernard Arnault with 41.5 B$
   Hong Kong : 1 billionaires. Richest is Li Ka-shing with 31.2 B$
   Mexico : 1 billionaires. Richest is Carlos Slim with 54.5 B$
   Spain : 1 billionaires. Richest is Amancio Ortega with 71.3 B$
   USA : 4 billionaires. Richest is Bill Gates with 86 B$
   

How it works...

本节围绕着std::map中的try_emplace函数展开，这个函数是C++17添加的。下面是其函数声明之一：

std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);

其函数第一个参数k是插入的键，args表示这个键对应的值。如果我们成功的插入了元素，那么函数就会返回一个迭代器，其指向新节点在表中的位置，组对中布尔变量的值被置为true。当插入不成功，组对中的布尔变量值会置为false，并且迭代器指向与新元素冲突的位置。

这个特性在我们的例子中非常有用——可以完美处理第一次访问到，和之后访问到的情况。

Note：

std::map中insert和emplace方法完全相同。try_emplace与它们不同的地方在于，在遇到已经存在的键时，不会去构造组对。当相应对象的类型需要很大开销进行构造时，这对于程序性能是帮助的。

There's more...

如果我们将表的类型从std::map换成std::unordered_map，程序照样能工作。这样的话，当不同类型的表具有较好的性能特性时，我们就可以快速的进行切换。例子中，唯一可观察到的区别是，亿万富翁表不再按字母顺序打印，因为哈希表和搜索树不同，其不会对对象进行排序。

了解std::map::insert新的插入提示语义

std::map中查找元素的时间复杂度为OParseError: KaTeX parse error: Can't use function '\(' in math mode at position 4: log\̲(̲n)，与插入元素的时间复杂相同，因为要在对应位置上插入元素，那么就先要找到这个位置。通常，插入M个新元素的时间复杂度为OParseError: KaTeX parse error: Undefined control sequence: \* at position 2: M\̲*̲log\(n)。

为了让插入更加高效，std::map插入函数接受一个迭代器参数hint。自C++11起，该参数为指向将插入新元素到其前的位置的迭代器。如果这个迭代器给定正确，那么插入的时间复杂度就为O$1$。

How to do it...

本节会是用传入迭代器的方式向std::map实例中插入多个新元素，从而减少耗时：

1. 包含必要的头文件。

   #include <iostream>
   #include <map>
   #include <string>
   

2. 创建一个map实例，并填充一些内容。

   int main()
   {
       std::map<std::string, size_t> m { {"b", 1}, {"c", 2}, {"d", 3} };
   

3. 我们将插入多个元素，对于每次插入，我们都会传入一个hint迭代器。第一次插入我们不指定其开始位置，只将插入位置指向map的end迭代器之前。

       auto insert_it (std::end(m));
   

4. 我们将以字母表的反序进行元素的插入，然后使用hint迭代器，然后使用insert函数的返回值重新初始化迭代器的值。下一个元素将在hint迭代器前插入。

       for (const auto &s : {"z", "y", "x", "w"}) {
           insert_it = m.insert(insert_it, {s, 1});
       }
   

5. 为了展示在什么情况下insert函数不工作，我们将要插入最左侧位置的元素插入到最右侧。

       m.insert(std::end(m), {"a", 1});
   

6. 最后我们打印当前的map。

       for (const auto & [key, value] : m) {
           std::cout << "\"" << key << "\": " << value << ", ";
       }
       std::cout << '\n';
   }
   

7. 编译运行程序，错误的插入并没有对结果又什么影响，map实例中对象的顺序仍然是对的。

   "a": 1, "b": 1, "c": 2, "d": 3, "w": 1, "x": 1, "y": 1, "z": 1,
   

How it works...

本例与常用的方式不同，多了一个迭代器。并且我们提到了这个迭代器的正确与否。

正确的迭代器将会指向一个已存在的元素，其值要比要插入元素的键大，所以新元素会插在这个迭代器之前。如果用户提供的迭代器位置有误，那么插入函数会退化成未优化的版本，其时间复杂度恢复OParseError: KaTeX parse error: Can't use function '\(' in math mode at position 4: log\̲(̲n)。

对于第一次插入，我们选择了map实例的end迭代器，因为没有其他更好的选择。在插入“z”之后，函数会返回相应的迭代器，这样我们就知道了要插入“y”的位置。“x”也同理，后面的元素依次类推。

Note:

在C++11之前，hint迭代器只是建议作为搜索开始位置的迭代器。

There's more...

其中，比较有趣的事情是，在给定错误的迭代器，map实例依旧能保持其排序。那么他是如何工作的呢？还有插入的时间复杂度为O$1$意味着什么？

std::map通常使用二叉搜索树实现。当在搜索树中插入一个新键时，该键要和其他键进行比较，从末端到顶端。如果键小于或大于其他节点的键，搜索树的左侧或右侧分支则会成为更深的节点。不过，搜索算法会阻止节点达到当前搜索树的底端。否则会打破搜索树的平衡，所以为了保证正确性，需要使用一个平衡算法用来管理节点。

当我们将元素插入到树中时，这些键值就会成为邻居$就如整数1和2互邻一样$。如果有hint传入，那么很容易检查键是否正确。如果这种情况出现，则可以省去搜索的时间。而后，平衡算法会可能还要运行。虽然优化并不是总能成功，不过平均下来，性能上还是会有提升。可以使用多次插入的方式，来统计运行的耗时，这被称之为摊销复杂度。

如果插入的hint是错的，那么插入函数会放弃使用hint，转而使用搜索算法进行查找。虽然程序不会出什么问题，但这样做会让程序变慢。

高效的修改std::map元素的键值

在std::map数据结构中，键-值通常都对应存在，而且键通常是唯一并排序过的，而且键值一旦设定那么就不允许用户再进行修改。为了阻止用户修改键，键的类型声明使用了const。

这种限制是非常明智的，其可以保证用户很难在使用std::map的时候出错。不过，如果我们真的需要修改map的键值该怎么办呢？

C++17之前，因为对应的键已经存在，我们不得不将整个键-值对从树中移除，然后再插入。这种方法的确定很明显，其需要分配出一些不必要的内存，感觉上也会对性能有一定的影响。

从C++17起，我们无需重新分配内存，就可以删除和重新插入map键值对。下面的内容中将会展示如何操作。

How to do it...

我们使用std::map类型一个实现应用，用于确定车手在虚拟比赛中的排位。当车手在比赛中完成超越，那么我们将使用C++17的新方法改变其键值。

1. 包含必要的头文件和声明使用的命名空间。

   #include <iostream>
   #include <map>
   
   using namespace std;
   

2. 我们会在修改map的时候打印之前和之后结果，所以这里先实现了一个辅助函数。

   template <typename M>
   void print(const M &m)
   {
       cout << "Race placement:\n";
       for (const auto &[placement, driver] : m) {
      		cout << placement << ": " << driver << '\n';
       }
   }
   

3. 主函数中，我们实例化并初始化一个map，其键为整型，表示是当前的排位；值为字符型，表示驾驶员的姓名。我们在这里先打印一下这个map，因为我们会在下一步对其进行修改。

   int main()
   {
       map<int, string> race_placement {
           {1, "Mario"}, {2, "Luigi"}, {3, "Bowser"},
           {4, "Peach"}, {5, "Yoshi"}, {6, "Koopa"},
           {7, "Toad"}, {8, "Donkey Kong Jr."}
       };
       print(race_placement);
   

4. 让我来看下排位赛的某一圈的情况，Bowser因为赛车事故排在最后，Donkey Kong Jr. 从最后一名超到第三位。例子中首先要从map中提取节点，因为这是唯一能修改键值的方法。extract函数是C++17新加的特性。其可以从map中删除元素，并没有内存重分配的副作用。看下这里是怎么用的吧。

   {
       auto a(race_placement.extract(3));
       auto b(race_placement.extract(8)); 
   

5. 现在我们要交换Bowser和Donkey Kong Jr.的键。键通常都是无法修改的，不过我们可以通过extract方法来修改元素的键。

   	swap(a.key(), b.key());
   

6. std::map的insert函数在C++17中有一个新的重载版本，其接受已经提取出来的节点，就是为了在插入他们时，不会分配不必要的内存。

       race_placement.insert(move(a));
       race_placement.insert(move(b));
   }
   

7. 最后，我们打印一下目前的排位。

   	print(race_placement);
   }
   

8. 编译并运行可以得到如下输出。我们可以看到初始的排位和最后的排位。

   $ ./mapnode_key_modification
   Race placement:
   1: Mario
   2: Luigi
   3: Bowser
   4: Peach
   5: Yoshi
   6: Koopa
   7: Toad
   8: Donkey Kong Jr.
   Race placement:
   1: Mario
   2: Luigi
   3: Donkey Kong Jr.
   4: Peach
   5: Yoshi
   6: Koopa
   7: Toad
   8: Bowser
   

How it works...

在C++17中，std::map有一个新成员函数extract。其有两种形式：

node_type extract(const_iterator position);
node_type extract(const key_type& x)

在例子中，我们使用了第二个，能接受一个键值，然后找到这个键值，并提取对应的map节点。第一个函数接受一个迭代器，提取的速度会更快，应为给定了迭代器就不需要在查找。

当使用第二种方式去提取一个不存在的节点时，会返回一个空node_type实例。empty()成员函数会返回一个布尔值，用来表明node_type实例是否为空。以任何方式访问一个空的实例都会产生未定义行为。

提取节点之后，我们要使用key()函数获取要修改的键，这个函数会返回一个非常量的键。

需要注意的是，要将节点重新插会到map时，我们需要在insert中移动他们。因为extract可避免不必要的拷贝和内存分配。还有一点就是，移动一个node_type时，其不会让容器的任何值发生移动。

There's more...

使用extract方法提取的map节点实际上非常通用。我们可以从一个map实例中提取出来节点，然后插入到另一个map中，甚至可以插入到multimap实例中。这种方式在unordered_map和unordered_multimap实例中也适用。同样在set/multiset和unordered_set/unordered_multiset也适用。

为了在不同map或set结构中移动元素，键、值和分配器的类型都必须相同。需要注意的是，不能将map中的节点移动到unordered_map中，或是将set中的元素移动到unordered_set中。

std::unordered_map中使用自定义类型

当我们使用std::unordered_map代替std::map时，对于键的选择要从另一个角度出发。std::map要求键的类型可以排序。因此，元素可以进行排序。不过，当我们使用数学中的向量作为键呢？这样一来就没有判断哪个向量大于另一个向量，比如向量(0, 1)和(1, 0)无法相比较，因为它们指向的方向不同。在std::unordered_map中这都不是问题，因为不需要对键的哈希值进行排序。对于我们来说只要为类型实现一个哈希函数和等同==操作符的实现，等同操作符的是实现是为了判断两个对象是否完全相同。本节中，我们就来实验一下这个例子。

How to do it...

本节中，我们要定义一个简单的coord数据结构，其没有默认哈希函数，所以我们必须要自行定义一个。然后我们会使用coord对象来对应一些值。

1. 包含使用std::unordered_map所必须的头文件

   #include <iostream>
   #include <unordered_map> 
   

2. 自定义数据结构，这是一个简单的数据结构，还不具备对应的哈希函数：

   struct coord {
   	int x;
   	int y;
   };
   

3. 实现哈希函数是为了能让类型作为键存在，这里先实现比较操作函数：

   bool operator==(const coord &l, const coord &r)
   {
   	return l.x == r.x && l.y == r.y;
   }
   

4. 为了使用STL哈希的能力，我们打开了std命名空间，并且创建了一个特化的std::hash模板。其使用using将特化类型进行别名。

   namespace std
   {
   template <>
   struct hash<coord>
   {
       using argument_type = coord;
       using result_type = size_t;
   

5. 下面要重载该类型的括号表达式。我们只是为coord结构体添加数字，这是一个不太理想的哈希方式，不过这里只是展示如何去实现这个函数。一个好的散列函数会尽可能的将值均匀的分布在整个取值范围内，以减少哈希碰撞。

       result_type operator()(const argument_type &c) const
       {
           return static_cast<result_type>(c.x)
          		   + static_cast<result_type>(c.y);
       }
   };
   }
   

6. 我们现在可以创建一个新的std::unordered_map实例，其能结构coord结构体作为键，并且对应任意值。例子中对std::unordered_map使用自定义的类型来说，已经很不错了。让我们基于哈希进行实例化，并填充自定义类型的map表，并打印这个map表：

   int main()
   {
       std::unordered_map<coord, int> m { 
           { {0, 0}, 1}, 
           { {0, 1}, 2},
           { {2, 1}, 3}
       };
       for (const auto & [key, value] : m) {
           std::cout << "{(" << key.x << ", " << key.y
       			 << "): " << value << "} ";
       }
       std::cout << '\n';
   }
   

7. 编译运行这个例子，就能看到如下的打印信息：

   $ ./custom_type_unordered_map
   {(2, 1): 3} {(0, 1): 2} {(0, 0): 1}
   

How it works...

通常实例化一个基于哈希的map表(比如: std::unordered_map)时，我们会这样写：

std::unordered_map<key_type, value_type> my_unordered_map;

编译器为我们创建特化的std::unordered_map时，这句话背后隐藏了大量的操作。所以，让我们来看一下其完整的模板类型声明：

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

这里第一个和第二个模板类型，我么填写的是coord和int。另外的三个模板类型是选填的，其会使用已有的标准模板类。这里前两个参数需要我们给定对应的类型。

对于这个例子，class Hash模板参数是最有趣的一个：当我们不显式定义任何东西时，其就指向std::hash<key_type>。STL已经具有std::hash的多种特化类型，比如std::hash<std::string>、std::hash<int>、std::hash<unique_ptr>等等。这些类型中可以选择最优的一种类型类解决对应的问题。

不过，STL不知道如何计算我们自定义类型coord的哈希值。所以我们要使用我们定义的类型对哈希模板进行特化。编译器会从std::hash特化列表中，找到我们所实现的类型，也就是将自定义类型作为键的类型。

如果新特化一个std::hash<coord>类型，并且将其命名成my_hash_type，我们可以使用下面的语句来实例化这个类型：

std::unordered_map<coord, value_type, my_hash_type> my_unordered_map;

这样命名就很直观，可读性好，而且编译器也能从哈希实现列表中找到与之对应的正确的类型。

过滤用户的重复输入，并以字母序将重复信息打印出——std::set

std::set是一个奇怪的容器：工作原理和std::map很像，不过std::set将键作为值，没有键值对。所以没做办法与其他类型的数据进行映射。表面上看，std::set因为没有太多的例子，导致很多开发者几乎不知道有这样的容器。想要使用类似std::set的功能时，只有自己去实现一遍。

本节展示如何使用std::set收集很多不同的元素，过滤这些元素，最后只输出一个元素。

How to do it...

从标准输入流中读取单词，所有不重复的单词将放到一个std::set实例中。之后，枚举出所有输入流中不重复的单词。

1. 包含必要的头文件。

   #include <iostream>
   #include <set>
   #include <string>
   #include <iterator>
   

2. 为了分析我们的输入，会使用到std命名空间：

   using namespace std;
   

3. 现在来实现主函数，先来实例化一个std::set。

   int main()
   {
   	set<string> s;
   

4. 下一件事情就是获取用户的输入。我们只从标准输入中读取，这样我们就要用到istream_iterator。

       istream_iterator<string> it {cin};
       istream_iterator<string> end;
   

5. 这样就得到了一对begin和end迭代器，可以用来表示用户的输入，我们可以使用std::inserter来填满set实例。

   	copy(it, end, inserter(s, s.end()));
   

6. 这样就完成了填充。为了看到从标准输入获得的不重复单词，我们可以打印当前的set实例。

   	for (const auto word : s) {
       	cout << word << ", ";
       }
       cout << '\n';
   }
   

7. 最后，让我们编译并运行这个程序。从之前的输入中，重复的单词都会去除，获得不重复的单词，然后以字母序排序输出。

   $ echo "a a a b c foo bar foobar foo bar bar" | ./program
   a, b, bar, c, foo, foobar,
   

How it works...

程序中有两个有趣的部分。第一个是使用了std::istream_iterator来访问用户输入，另一个是将std::set实例使用std::inserter用包装后，在使用std::copy填充。这看起来像是变魔术一样，只需要一行代码，我们就能完成使用输入流填充实例，去除重复的单词和以字母序进行排序。

std::istream_iterator

这个例子的有趣之处在于一次性可以处理流中大量相同类型的数据：我们对整个输入进行逐字的分析，并以std::string实例的方式插入set。

std::istream_iterator只传入了一个模板参数。也就我们输入数据的类型。我们选择std::string是因为我们假设是文本输入，不过这里也可以是float型的输入。基本上任何类型都可以使用cin >> var;完成。构造函数接受一个istream实例。标准输入使用全局输入流std::cin表示，例子中其为istream的参数。

istream_iterator<string> it {cin};

输入流迭代器it就已经实例化完毕了，其可以做两件事情：当对其解引用(*it)时，会得到当前输入的符号。我们通过输入迭代器构造std::string实例，每个字符串容器中都包含一个单词；当进行自加++it时，其会跳转到下一个单词，然后再解引用访问下一个单词。

不过，每次自加后的解引用时都须谨慎。当标准输入为空，迭代器就不能再解引用。另外，我们需要终止使用解引用获取单词的循环。终止的条件就是通过和end迭代器进行比较，知道何时迭代器无法解引用。如果it==end成立，那么说明输入流已经读取完毕。

我们在创建it的同时，也创建了一个std::istream_iterator的end迭代器。其目的是于it进行比较，在每次迭代中作为中止条件。

当std::cin结束时，it迭代器将会与end进行比较，并返回true。

std::inserter

调用std::copy时，我们使用it和end作为输入迭代器。第三个参数必须是一个输出迭代器。因此，不能使用s.begin()或s.end()。一个空的set中，这二者是一致的，所以不能对set的迭代器进行解引用(无论是读取或赋值)。

这就使std::inserter有了用武之地。其为一个函数，返回一个std::insert_iterator，返回值的行为类似一个迭代器，不过会完成普通迭代器无法完成的事。当对其使用加法时，其不会做任何事。当我们对其解引用，并赋值给它时，它会连接相关容器，并且将赋值作为一个新元素插入容器中。

当通过std::inserter实例化std::insert_iterator时，我们需要两个参数：

auto insert_it = inserter(s, s.end());

其中s是我们的set，s.end()是指向新元素插入点的迭代器。对于一个空set来说，从哪里开始和从哪里结束一样重要。当使用其他数据结构时，比如vector和list，第二个参数对于定义插入新项的位置来说至关重要。

将二者结合

最后，所有的工作都在std::copy的调用中完成：

copy(input_iterator_begin, input_iterator_end, insert_iterator);

这个调用从std::cin中获取输入迭代器，并将其推入std::set中。之后，其会让迭代器自增，并且确定输入迭代器是否达到末尾。如果不是，那么可以继续从标准输入中获取单词。

重复的单词会自动去除。当set已经拥有了一个单词，再重复将这个单词添加入set时，不会产生任何效果。与std::multiset的表现不同，std::multiset会接受重复项。

实现简单的逆波兰表示法计算器——std::stack

std::stack是一个适配类，其能让用户使用自己定义的类型作为栈中的元素。本节中，我们会使用std::stack构造一个逆波兰(RPN，reverse polish notation)计算器，为了展示如何使用std::stack。

RPN是一种记号法，可以用一种非常简单的解析方式来表达数学表达式。在RPN中，1+2解析为1 2 +。操作数优先，然后是操作符。另一个例子：(1+2)*3表示为1 2 + 3 *。这两个例子已经展示了RPN可以很容易的进行解析，并且不需要小括号来定义子表达式。

How to do it...

本节中，我们将从标准输入中读取一个RPN表达式，然后根据表达式解析出正确的计算顺序，并得到结果。最后，我们将输出得到的结果。

1. 包含必要的头文件。

   #include <iostream>
   #include <stack>
   #include <iterator>
   #include <map>
   #include <sstream>
   #include <cassert>
   #include <vector>
   #include <stdexcept>
   #include <cmath>
   

2. 声明所使用的命名空间。

   using namespace std;
   

3. 然后，就来实现我们的RPN解析器。其能接受一对迭代器，两个迭代器分别指定了数学表达式的开始和结尾。

   template <typename IT>
   double evaluate_rpn(IT it, IT end)
   {
   

4. 在遍历输入时，需要记住所经过的所有操作数，直到我们看到一个操作符为止。这也就是使用栈的原因。所有数字将会被解析出来，然后以双精度浮点类型进行保存，所以保存到栈中的数据类型为double。

   	stack<double> val_stack;
   

5. 为了能更方便的访问栈中的元素，我们实现了一个辅助函数。其会修改栈中内容，弹出最顶端的元素，并返回这个元素。

       auto pop_stack ([&](){
           auto r (val_stack.top());
           val_stack.pop();
           return r;
       });
   

6. 另一项准备工作，就是定义所支持的数学操作符。我们使用map保存相关数学操作符的作用。每个操作符的实现我们使用Lambda函数实现。

       map<string, double (*)(double, double)> ops {
           {"+", [](double a, double b) { return a + b; }},
           {"-", [](double a, double b) { return a - b; }},
           {"*", [](double a, double b) { return a * b; }},
           {"/", [](double a, double b) { return a / b; }},
           {"^", [](double a, double b) { return pow(a, b); }},
           {"%", [](double a, double b) { return fmod(a, b); }},
       };
   

7. 现在就可以对输入进行遍历了。假设我们的输入是字符串，我们使用全新的std::stringstream获取每个单词，这样就可以将操作数解析为数字了。

       for (; it != end; ++it) {
       	stringstream ss {*it};
   

8. 我们获得的每个操作数，都要转换成double类型。如果当前解析的字符是操作数，那么我们将转换类型后，推入栈中。

           if (double val; ss >> val) {
           	val_stack.push(val);
           }
   

9. 如果不是操作数，那么就必定为一个操作符。我们支持的操作符都是二元的，所以当遇到操作符时，我们需要从栈中弹出两个操作数。

           else {
               const auto r {pop_stack()};
               const auto l {pop_stack()};
   

10. 现在我们可以从解引用迭代器it获取操作数。通过查询opsmap表，我们可以获得参与Lambda计算的l和r值。

                try {
                    const auto & op (ops.at(*it));
                    const double result {op(l, r)};
                    val_stack.push(result);
                }
    

11. 我们使用try代码块将计算代码包围，因为我们的计算可能会出错。在调用map的成员函数at时，可能会抛出一个out_of_range异常，由于用户具体会输入什么样的表达式，并不是我们能控制的。所以，我们将会重新抛出一个不同的异常，我们称之为invalid argument异常，并且携带着程序未知的操作符。

                catch (const out_of_range &) {
                    throw invalid_argument(*it);
                }
    

12. 这就是遍历循环的全部，我们会将栈中的操作数用完，然后得到对应的结果，并将结果保存在栈顶。所以我们要返回栈顶的元素。(我们对栈的大小进行断言，如果大小不是1，那么就有缺失的操作符)

    		}
    	}
    	return val_stack.top();
    }
    

13. 现在我们可以使用这个RPN解析器了。为了使用这个解析器，我们需要将标准输入包装成一个std::istream_iterator迭代器对，并且传入RPN解析器函数。最后，我们将输出结果：

    int main()
    {
        try {
            cout << evaluate_rpn(istream_iterator<string>{cin}, {})
            	 << '\n';
        }
    

14. 这里我们再次使用了try代码块，因为用户输入的表达式可能会存在错误，所以当解析器抛出异常时，需要在这里获取。我们需要获取对应的异常，并且打印出一条错误信息：

        catch (const invalid_argument &e) {
        	cout << "Invalid operator: " << e.what() << '\n';
        }
    }	
    

15. 完成编译步骤后，我们就可以使用这个解析器了。输入3 1 2 + * 2 /，其为(3*(1+2))/2数学表达式的RPN表达式，然后我们获得相应的结果：

    $ echo "3 1 2 + * 2 /" | ./rpn_calculator
    4.5
    

How it works...

整个例子通过解析我们的输入，持续向栈中压入操作数的方式完成相应的数学计算。本例中，我们会从栈中弹出最后两个操作数，然后使用操作符对这两个操作数进行计算，然后将其结果保存在栈中。为了理解本节中的所有代码，最重要的就是要理解，我们如何区分了输入中的操作数和操作符，如何管理我们的栈，以及如何选择正确的计算操作符。

栈管理

我们使用std::stack中的成员函数push将元素推入栈中：

val_stack.push(val);

出站元素的获取看起来有些复杂，因为我们使用了一个Lambda表达式完成这项操作，其能够引用val_stack对象。这里我们为代码添加了一些注释，可能会更好理解一些：

auto pop_stack ([&](){
    auto r (val_stack.top()); // 获取栈顶元素副本
    val_stack.pop(); // 从栈中移除顶部元素
    return r; // 返回顶部元素副本
});

这个Lambda表达式能够一键式获取栈顶元素，并且能删除顶部元素。在std::stack的设计当中，无法使用一步完成这些操作。不过，定义一个Lambda函数也是十分快捷和简介，所以我们可以使用这种方式获取值：

double top_value {pop_stack()};

从输入中区别操作数和操作符

主循环中执行evaluate_rpn时，我们会根据迭代器遍历标准输入，然后判断字符是一个操作数，还是一个操作符。如果字符可以被解析成double变量，那这就是一个数，也就是操作数。我们需要考虑有些比较难以解析的数值(比如，+1和-1)，这种数值可能会被解析成操作符(尤其是+1这种)。

用于区分操作数和操作符的代码如下所示：

stringstream ss {*it};
if (double val; ss >> val) {
	// It's a number!
} else {
	// It's something else than a number - an operation!
}

如果字符是一个数字，流操作符>>会告诉我们。首先，我们将字符串包装成一个std::stringstream。然后使用stringstream对象的能力，将流中std::string类型解析并转换成一个double变量。解析失败时也能知道是为什么，因为只解析器需要解析数字出来；否则，需要解析的就不是一个数字。

选择和应用正确的数学操作符

判断完当前用户的输入是否为一个数后，我们先假设输入了一个操作符，比如+或*。然后，查询map表ops，找到对应的操作，并返回相应的函数，其函数可以接受两个操作数，然后返回对应操作后的结果。

map表本身的类型看起来会相对复杂：

map<string, double (*)(double, double)> ops { ... };

其将string映射到double (*)(double, double)。后者是什么意思呢？这个类型是一个函数指针的声明，说明这个函数接受两个double类型的变量作为输入，并且返回值也是double类型。可以将(*)部分理解成函数的名字，例如double sum(double, double，这样就好理解多了吧。这里的重点在于我们的Lambda函数[](double, double) {return /* some double */ }，其可转换为实际匹配指针声明的函数。这里Lambda不获取任何东西，所以可以转化为函数指针。

这样，我们就可以方便的在map表中查询操作符是否支持：

const auto & op (ops.at(*it));
const double result {op(l, r)};

map会为我们隐式的做另一件事：当我们执行ops.at("foo")时，如果"foo"是一个合法键(实际中我们不会用这个名字存任何操作)，那么在这个例子中，map表将会抛出一个异常，例子中可以捕获这个异常。当我们捕获这个异常时，我们会重新抛出一个不同的异常，为了描述我们遇到了什么样的错误。相较于out of range，用户也能更好的了解invalid argument异常的含义，因此我们在使用的时候，程序的map表到底支持哪些操作，我们是不知道的。

There's more...

evaluate_rpn函数可以传入迭代器，感觉这样传递的方式要比传入标准输入更加容易理解。这让程序更容易测试，或适应来自于用户的不同类型的输入。

使用字符串流或字符串数组的迭代器作为输入，例如下面的代码，evaluate_rpn不用做任何修改：

int main()
{
    stringstream s {"3 2 1 + * 2 /"};
    cout << evaluate_rpn(istream_iterator<string>{s}, {}) << '\n';
    vector<string> v {"3", "2", "1", "+", "*", "2", "/"};
    cout << evaluate_rpn(begin(v), end(v)) << '\n';
}

Note:

在有意义的地方使用迭代器，会使得代码可重复利用度高，模块化好。

实现词频计数器——std::map

std::map在收集和统计数据方面非常有用，通过建立键值关系，将可修改的对象映射到对应键上，可以很容易的实现一个词频计数器。

How to do it...

本节中，我们将从标准输入中获取用户的输入，或是从记录一部小说的文本文件。我们会去标记输入单词，并统计一共有多少个单词。

1. 包含必要的头文件。

   #include <iostream>
   #include <map>
   #include <vector>
   #include <algorithm>
   #include <iomanip>
   

2. 声明所使用的命名空间。

   using namespace std;
   

3. 我们将使用一个辅助函数，对输入中的符号进行处理。

   string filter_punctuation(const string &s)
   {
       const char *forbidden {".,:; "};
       const auto idx_start (s.find_first_not_of(forbidden));
       const auto idx_end (s.find_last_not_of(forbidden));
       return s.substr(idx_start, idx_end - idx_start + 1);
   }
   

4. 现在，我们来实现真正要工作的部分。使用map表对输入的每个单词进行统计。另外，使用一个变量来保存目前为止看到的最长单词的长度。程序的最后，我们将打印这个map表。

   int main()
   {
       map<string, size_t> words;
       int max_word_len {0};
   

5. 将标准输入导入std::string变量中，标准输入由空格隔开。通过如下方法获取输入单词。

       string s;
       while (cin >> s) {
   

6. 我们获得的单词可能包含标点符号，因为这些符号可能紧跟在单词后面。使用辅助函数将标点符号去除。

   		auto filtered (filter_punctuation(s));
   

7. 如果当前处理的单词是目前处理最长的单词，我们会更新max_word_len变量。

   		max_word_len = max<int>(max_word_len, filtered.length());
   

8. 然后，我们将增加该词在words map中的频率。如果是首次处理该单词，那么将会隐式创建一个键值对，然后插入map，之后再进行自加操作。

       	++words[filtered];
       }	
   

9. 当循环结束时，words map会保存所有输入单词的频率。map中单词作为键，并且键以字母序排列。我们想要以频率多少进行排序，词频最高的排第一位。为了达到这样的效果，首先实现一个vector，将所有键值对放入这个vector中。

       vector<pair<string, size_t>> word_counts;
       word_counts.reserve(words.size());
       move(begin(words), end(words), back_inserter(word_counts));
   

10. 然后，vector中将将具有words map中的所有元素。然后，我们来进行排序，把词频最高的单词排在最开始，最低的放在最后。

    sort(begin(word_counts), end(word_counts),
        [](const auto &a, const auto &b) {
        return a.second > b.second;
        });

11. 现在所有元素如我们想要的顺序排列，之后将这些数据打印在用户的终端上。使用std::setw流控制器，可以格式化输出相应的内容。

        cout << "# " << setw(max_word_len) << "<WORD>" << " #<COUNT>\n";
        for (const auto & [word, count] : word_counts) {
            cout << setw(max_word_len + 2) << word << " #"
            	 << count << '\n';
        }
    }
    

12. 编译后运行，我们就会得到一个词频表：

    $ cat lorem_ipsum.txt | ./word_frequency_counter
    # <WORD> #<COUNT>
    et #574
    dolor #302
    sed #273
    diam #273
    sit #259
    ipsum #259
    ...
    

How it works...

本节中，我们使用std::map实例进行单词统计，然后将map中的所有元素放入vector中，然后进行排序，再打印输出。为什么要这么做？

先看一个例子。当我们要从a a b c b b b d c c字符串中统计词频时，我们的map内容如下：

a -> 2
b -> 4
c -> 3
d -> 1

不过，这是未排序的，这不是我们想要给用户展示的排序。我们的程序要首先输出b的频率，因为b的频率最高。然后是c，a，d。不幸的是，我们无法要求map使用键所对应的值进行排序。

这就需要vector帮忙了，将map中的键值对放入vector中。这个方法明确的将这些元素从map中删除了。

vector<pair<string, size_t>> word_counts;

然后，我们使用std::move函数将词-频对应关系填充整个vector。这样的好处是让单词不会重复，不过这样会将元素从map中完全删除。使用move方法，减少了很多不必要的拷贝。

move(begin(words), end(words), back_inserter(word_counts));

Note

一些STL的实现使用短字符优化——当所要处理的字符串过长，这种方法将无需再在堆上分配内存，并且可以将字符串直接进行存储。在这个例子中，移动虽然不是最快的方式，但也不会慢多少。

接下来比较有趣的就是排序操作，其使用了一个Lambda表达式作为自定义比较谓词：

sort(begin(word_counts), end(word_counts),
	[](const auto &a, const auto &b) { return a.second > b.second; });

排序算法将会成对的处理元素，比较两个元素。通过提供的Lambda函数，sort方法将不会再使用默认比较谓词，其会将a.second和b.second进行比较。这里的键值对中，第二个值为词频数，所以可以使用.second得到对应词频数。通过这种方式，将移动所有高频率的词到vector的开始，并且将低频率词放在末尾。

实现写作风格助手用来查找文本中很长的句子——std::multimap

当有超级多的元素需要排序时，某些键值描述可能会出现多次，那么使用std::multimap完成这项工作无疑是个不错的选择。

先找个应用场景：当使用德文写作时，使用很长的句子是没有问题的。不过，使用英文时，就不行了。我们将实现一个辅助工具来帮助德国作家们分析他们的英文作品，着重于所有句子的长度。为了帮助这些作家改善其写作的文本风格，工具会按句子的长度对每个句子进行分组。这样作家们就能挑出比较长的句子，然后截断这些句子。

How to do it...

本节中，我们将从标准输入中获取用户输入，用户会输入所有的句子，而非单词。然后，我们将这些句子和其长度收集在std::multimap中。之后，我们将对所有句子的长度进行排序，打印给用户看。

1. 包含必要的头文件。std::multimap和std::map在同一个头文件中声明。

   #include <iostream>
   #include <iterator>
   #include <map>
   #include <algorithm>
   

2. 声明所使用的命名空间。

   using namespace std;
   

3. 我们使用句号将输入字符串分成若干个句子，句子中的每个单词以空格隔开。句子中的一些对于句子长度无意义的符号，也会计算到长度中，所以，这里要使用辅助函数将这些符号过滤掉。

   string filter_ws(const string &s)
   {
       const char *ws {" \r\n\t"};
       const auto a (s.find_first_not_of(ws));
       const auto b (s.find_last_not_of(ws));
       if (a == string::npos) {
       	return {};
       }
       return s.substr(a, b);
   }
   

4. 计算句子长度函数需要接收一个包含相应内容的字符串，并且返回一个std::multimap实例，其映射了排序后的句子长度和相应的句子。

   multimap<size_t, string> get_sentence_stats(const string &content)
   {
   

5. 这里声明一个multimap结构，以及一些迭代器。在计算长度的循环中，我们需要end迭代器。然后，我们使用两个迭代器指向文本的开始和结尾。所有句子都在这个文本当中。

       multimap<size_t, string> ret;
       const auto end_it (end(content));
       auto it1 (begin(content));
       auto it2 (find(it1, end_it, '.'));
   

6. it2总是指向句号，而it1指向句子的开头。只要it1没有到达文本的末尾就好。第二个条件就是要检查it2是否指向字符。如果不满足这些条件，那么就意味着这两个迭代器中没有任何字符了：

   	while (it1 != end_it && distance(it1, it2) > 0) {	
   

7. 我们使用两个迭代器间的字符创建一个字符串，并且过滤字符串中所有的空格，只是为了计算句子纯单词的长度。

   		string s {filter_ws({it1, it2})};
   

8. 当句子中不包含任何字符，或只有空格时，我们就不统计这句。另外，我们要计算有多少单词在句子中。这很简单，每个单词间都有空格隔开，单词的数量很容易计算。然后，我们就将句子和其长度保存在multimap中。

           if (s.length() > 0) {
               const auto words (count(begin(s), end(s), ' ') + 1);
               ret.emplace(make_pair(words, move(s)));
           }
   

9. 对于下一次循环迭代，我们将会让it1指向it2的后一个字符。然后将it2指向下一个句号。

           it1 = next(it2, 1);
           it2 = find(it1, end_it, '.');
       } 
   

10. 循环结束后，multimap包含所有句子以及他们的长度，这里我们将其返回。

    	return ret;
    }
    

11. 现在，我们来写主函数。首先，我们让std::cin不要跳过空格，因为我们需要句子中有空格。为了读取整个文件，我们使用std::cin包装的输入流迭代器初始化一个std::string实例。

    int main()
    {
        cin.unsetf(ios::skipws);
        string content {istream_iterator<char>{cin}, {}};
    

12. 只需要打印multimap的内容，在循环中调用get_sentence_stats，然后打印multimap中的内容。

        for (const auto & [word_count, sentence]
        		: get_sentence_stats(content)) {
       	 cout << word_count << " words: " << sentence << ".\n";
        }
    }
    

13. 编译完成后，我们可以使用一个文本文件做例子。由于长句子的输出量很长，所以先把最短的句子打印出来，最后打印最长的句子。这样，我们就能首先看到最长的句子。

    $ cat lorem_ipsum.txt | ./sentence_length
    ...
    10 words: Nam quam nunc, blandit vel, luctus pulvinar,
    hendrerit id, lorem.
    10 words: Sed consequat, leo eget bibendum sodales,
    augue velit cursus nunc,.
    12 words: Cum sociis natoque penatibus et magnis dis
    parturient montes, nascetur ridiculus mus.
    17 words: Maecenas tempus, tellus eget condimentum rhoncus,
    sem quam semper libero, sit amet adipiscing sem neque sed ipsum.
    

How it works...

整个例子中，我们将一个很长的字符串，分割成多个短句，从而评估每个句子的长度，并且在multimap中进行排序。因为std::multimap很容易使用，所以变成较为复杂的部分就在于循环，也就是使用迭代器获取每句话的内容。

const auto end_it (end(content));

// (1) Beginning of string
auto it1 (begin(content)); 

// (1) First '.' dot
auto it2 (find(it1, end_it, '.')); 
while (it1 != end_it && std::distance(it1, it2) > 0) {
    string sentence {it1, it2};
    // Do something with the sentence string...
    
    // One character past current '.' dot
    it1 = std::next(it2, 1); 
    
    // Next dot, or end of string
    it2 = find(it1, end_it, '.'); 
}

将代码和下面的图结合起来可能会更好理解，这里使用具有三句话的字符串来举例。

it1和it2总是随着字符串向前移动。通过指向句子的开头和结尾的方式，确定一个句子中的内容。std::find算法会帮助我们寻找下一个句号的位置。

std::find的描述：

从当前位置开始，返回首先找到的目标字符迭代器。如果没有找到，返回结束迭代器。

这样我们就获取了一个句子，然后通过构造对应字符串的方式，将句子的长度计算出来，并将长度和原始句子一起插入multimap中。我们使用句子的长度作为元素的键，原句作为值存储在multimap中。通常一个文本中，长度相同的句子有很多。这样使用std::map就会比较麻烦。不过std::multimap就没有重复键值的问题。这些键值也是排序好的，从而能得到用户们想要的输出。

There's more...

将整个文件读入一个大字符串中后，遍历字符串时需要为每个句子创建副本。这是没有必要的，这里可以使用std::string_view来完成这项工作，该类型我们将会放在后面来介绍。

另一种从两个句号中获取句子的方法就是使用std::regex_iterator(正则表达式)，我们将会在后面的章节中进行介绍。

实现个人待办事项列表——std::priority_queue

std::priority_queue是另一种适配容器(类似于std::stack)。其实为另一种数据结构的包装器(默认的数据结构为std::vector)，并且提供类似队列的接口。同样也遵循队列的特性，先进先出。这与我们之前使用的std::stack完全不同。

这里仅仅是对std::queue的行为进行描述，本节将展示std::priority_queue是如何工作的。这个适配器比较特殊，其不仅有FIFO的特性，还混合着优先级。这就意味着，FIFO的原则会在某些条件下被打破，根据优先级的顺序形成子FIFO队列。

How to do it...

本节中，我们将创建一个待办事项的结构。为了程序的简明性就不从用户输入解析输入了。这次专注于std::priority_queue的使用。所以我们使用一些待办事项和优先级填充一个优先级序列，然后以FIFO的顺序读出这些元素(这些元素是通过优先级进行过分组)。

1. 包含必要的头文件。std::priority_queue在<queue>中声明。

   #include <iostream>
   #include <queue>
   #include <tuple>
   #include <string>
   

2. 我们怎么将待办事项存在优先级队列中呢？我们不能添加项目时，附加优先级。优先级队列将使用自然序对待队列中的所有元素。现在我们实现一个自定义的结构体struct todo_item，并赋予其优先级系数，和一个字符串描述待办事件，并且为了让该结构体具有可排序性，这里会实现比较操作符<。另外，我们将会使用std::pair，其能帮助我们聚合两个类型为一个类型，并且能完成自动比较。

   int main()
   {
   	using item_type = std::pair<int, std::string>;
   

3. 那么现在我们有了一个新类型item_type，其由一个优先级数字和一个描述字符串构成。所以，我们可以使用这种类型实例化一个优先级队列。

   	std::priority_queue<item_type> q;
   

4. 我们现在来填充优先级队列。其目的就是为了提供一个非结构化列表，之后优先级队列将告诉我们以何种顺序做什么事。比如，你有漫画要看的同时，也有作业需要去做，那么你必须先去写作业。不过，std::priority_queue没有构造函数，其支持初始化列表，通过列表我们能够填充优先级队列(使用vector或list都可以对优先级队列进行初始化)。所以我们这里定义了一个列表，用于下一步的初始化。

       std::initializer_list<item_type> il {
           {1, "dishes"},
           {0, "watch tv"},
           {2, "do homework"},
           {0, "read comics"},
       };
   

5. 现在我们可以很方便的遍历列表中的所有元素，然后通过push成员函数将元素插入优先级列表中。

       for (const auto &p : il) {
       	q.push(p);
       }
   

6. 这样所有的元素就都隐式的进行了排序，并且我们可以浏览列表中优先级最高的事件。

       while(!q.empty()) {
           std::cout << q.top().first << ": " << q.top().second << '\n';
           q.pop();
       }
       std::cout << '\n';
   }
   

7. 编译运行程序。结果如我们所料，作业是最优先的，看电视和看漫画排在最后。

   $ ./main
   2: do homework
   1: dishes
   0: watch tv
   0: read comics
   

How it works...

std::priority_queue使用起来很简单。我们只是用了其三个成员函数。

1. q.push(item)将元素推入队列中。
2. q.top()返回队首元素的引用。
3. q.pop()移除队首元素。

不过，如何做到排序的呢？我们将优先级数字和描述字符串放入一个std::pair中，然后就自然得到排序后的结果。这里有一个std::pair<int, std::string>的实例p，我们可通过p.first访问优先级整型数，使用p.second访问字符串。我们在循环中就是这样打印所有待办事件的。

如何让优先级队列意识到{2, "do homework"}要比{0, "watch tv"}重要呢？

比较操作符<在这里处理了不同的元素。我们假设现在有left < right，两个变量的类型都是pair。

1. left.first != right.first，然后返回left.first < right.first。
2. left.first == right.first，然后返回left.second < right.second。

以这种方式就能满足我们的要求。最重要的就是pair中第一个成员，然后是第二个成员。否则，std::priority_queue将会字母序将元素进行排序，而非使用数字优先级的顺序(这样的话，看电视将会成为首先要做的事情，而完成作业则是最后一件事。对于懒人来说，无疑是个完美的顺序)。

第3章 迭代器

迭代器是C++中非常重要的概念。STL旨在打造一组灵活和通用的工具集，迭代器是工具集中重要的一环。不过，有时候迭代器使用起来比较繁琐，所以很多编程人员还是喜欢用C的指针来完成相应的功能。一半的编程人员基本上会放弃使用STL中的迭代器。本章介绍了迭代器，并展示如何让它们很快的工作起来。快速地介绍是不能完全覆盖迭代器强大的功能，但是这种小例子能让你增加对迭代器的好感度。

大多数容器类(除了类似C风格的数组)，可包含一系列的数据项。许多日常任务会处理超大的数据量，这里先不关心如何获得这些数据。不过，如果我们考虑数组和链表，并且想要计算这两种结构所有项的和，那么将如下使用两种不同的算法：

• 通过查询数组的大小，来进行加和计算：

  int sum {0};
  for (size_t i {0}; i < array_size; ++i) { sum += array[i]; }
  

• 使用迭代器进行循环，直到数组的末尾：

  int sum {0};
  while (list_node != nullptr) {
  	sum += list_node->value; list_node = list_node->next;
  }
  

两种方法都能计算出所有项的加和，不过我们键入的代码，有多少用在实际加和任务中了呢？如果说要使用其他结构体来存储这些数据，例如std::map，难道我们还要在重新实现一个函数？使用迭代器是最佳的选择。

使用迭代器的代码才更加的通用：

int sum {0};
for (int i : array_or_vector_or_map_or_list) { sum += i; }

这段代码很简洁，只是使用C++11添加的for循环范围特性就完成了整体的叠加。其就像是个语法糖，将其扩展后类似如下代码：

{
    auto && __range = array_or_vector_or_map_or_list ;
    auto __begin = std::begin(__range);
    auto __end = std::end(__range);
    for ( ; __begin != __end; ++__begin) {
        int i = *__begin;
        sum += i;
    }
}

这段代码对于使用迭代器的老手来说并没有什么，不过对于刚接触迭代器的新手来说就像是在变魔术。

假设我们的vector内容如下所示：

std::begin(vector)和vector.begin()等价，并且返回vector中指向第一个元素的迭代器(指向1)。std::end(vector)与vector.end()等价，并返回指向vector末尾元素的迭代器(指向5的后方)。

每一次迭代，循环都会检查开始迭代器是否与末尾迭代器不同。如果是，那么可以对开始迭代器进行解引用，并获取其指向的值。然后，推动迭代器指向下一个元素，再与末尾迭代器进行比较，以此类推。这也能提升代码的可读性，这样的迭代器就类似于C风格的指针。实际上，C风格的指针也是一种迭代器。

迭代器的类型

C++中很多迭代器类型，都有各自的局限性。不用去死记这些限制，只要记住一种类型的能力是从更强大的类型继承过来的即可。当知道算法是使用何种迭代器实现时，编译器就可以以更好的方式优化这个算法。所以，开发者只要表达清楚自己想要实现的算法，那么编译器将选择优化后的实现来完成对应的任务。

让我们来看下这些迭代器吧(从左往右)：

输入迭代器

只能用来读取指向的值。当该迭代器自加时，之前指向的值就不可访问。也就是说，不能使用这个迭代器在一个范围内遍历多次。std::istream_iterator就是这样的迭代器。

前向迭代器

类似于输入迭代器，不过其可以在指示范围内迭代多次。std::forward_list就是这样的迭代器。就像一个单向链表一样，只能向前遍历，不能向后遍历，但可以反复迭代。

双向迭代器

从名字就能看出来，这个迭代器可以自增，也可以自减，迭代器可以向前或向后迭代。std::list，std::set和std::map都支持双向迭代器。

随机访问迭代器

与其他迭代器不同，随机访问迭代器一次可以跳转到任何容器中的元素上，而非之前的迭代器，一次只能移动一格。std::vector和std::deque的迭代器就是这种类型。

连续迭代器

这种迭代器具有前述几种迭代器的所有特性，不过需要容器内容在内存上是连续的，类似一个数组或std::vector。

输出迭代器

该迭代器与其他迭代器不同。因为这是一个单纯用于写出的迭代器，其只能增加，并且将对应内容写入文件当中。如果要读取这个迭代中的数据，那么读取到的值就是未定义的。

可变迭代器

如果一个迭代器既有输出迭代器的特性，又有其他迭代器的特性，那么这个迭代器就是可变迭代器。该迭代器可读可写。如果我们从一个非常量容器的实例中获取一个迭代器，那么这个迭代器通常都是可变迭代器。

建立可迭代区域

我们已经认识了STL中提供的各种迭代器。我们只需实现一个迭代器，支持前缀加法++，解引用*和比较操作==，这样我们就能使用C++11基于范围的for循环对该迭代器进行遍历。

为了更好的了解迭代器，本节中将展示如何实现一个迭代器。迭代该迭代器时，只输出一组数字。实现的迭代器并不支持任何容器，以及类似的结构。这些数字是在迭代过程中临时生成的。

How to do it...

本节中，我们将实现一个迭代器类，并且对该迭代器进行迭代：

1. 包含必要的头文件。

   #include <iostream> 
   

2. 迭代器结构命名为num_iterator:

   class num_iterator { 
   

3. 其数据类型只能是整型，仅用是用来计数的，构造函数会初始化它们。显式声明构造函数是一个好习惯，这就能避免隐式类型转换。需要注意的是，我们会使用position值来初始化i。这就让num_iterator可以进行默认构造。虽然我们的整个例子中都没有使用默认构造函数，但默认构造函数对于STL的算法却是很重要的。

   	int i;
   public:
   	explicit num_iterator(int position = 0) : i{position} {}
   

4. 当对迭代器解引用时*it`，将得到一个整数：

   	int operator*() const { return i; }
   

5. 前缀加法操作++it：

       num_iterator& operator++() {
           ++i;
           return *this;
       }
   

6. for循环中需要迭代器之间进行比较。如果不相等，则继续迭代：

       bool operator!=(const num_iterator &other) const {
       	return i != other.i;
       }
   };
   

7. 迭代器类就实现完成了。我们仍需要一个中间对象对应于for (int i : intermediate(a, b)) {...}写法，其会从头到尾的遍历，其为一种从a到b遍历的预编程。我们称其为num_range:

   class num_range {
   

8. 其包含两个整数成员，一个表示从开始，另一个表示结束。如果我们要从0到9遍历，那么a为0，b为10([0, 10))：

       int a;
       int b;
   public:
       num_range(int from, int to)
       	: a{from}, b{to}
       {}
   

9. 该类也只有两个成员函数需要实现：begin和end函数。两个函数都返回指向对应数字的指针：一个指向开始，一个指向末尾。

       num_iterator begin() const { return num_iterator{a}; }
       num_iterator end() const { return num_iterator{b}; }
   };
   

10. 所有类都已经完成，让我们来使用一下。让我们在主函数中写一个例子，遍历100到109间的数字，并打印这些数值：

int main()
{
    for (int i : num_range{100, 110}) {
    	std::cout << i << ", ";
    }
    std::cout << '\n';
}

11. 编译运行后，得到如下输出：

    100, 101, 102, 103, 104, 105, 106, 107, 108, 109,
    

How it works...

考虑一下如下的代码段：

for (auto x : range) { code_block; }

这段代码将被编译器翻译为类似如下的代码：

{
    auto __begin = std::begin(range);
    auto __end = std::end(range);
    for ( ; __begin != __end; ++__begin) {
        auto x = *__begin;
        code_block
    }
}

这样看起来就直观许多，也能清楚的了解我们的迭代器需要实现如下操作：

• operator!=
• operatpr++
• operator*

也需要begin和end方法返回相应的迭代器，用来确定开始和结束的范围。

Note:

本书中，我们使用std::begin(x)替代x.begin()。如果有begin成员函数，那么std::begin(x)会自动调用x.begin()。当x是一个数组，没有begin()方法是，std::begin(x)会找到其他方式来处理。同样的方式也适用于std::end(x)。当用户自定义的类型不提供begin/end成员函数时，std::begin/std::end就无法工作了。

本例中的迭代器是一个前向迭代器。再来看一下使用num_range的循环，从另一个角度看是非常的简单。

Note:

回头看下构造出迭代器的方法在range类中为const。这里不需要关注编译器是否会因为修饰符const而报错，因为迭代const的对象是很常见的事。

让自己的迭代器与STL的迭代器兼容

上一节中，我们实现了自己的迭代器，不过为了融合STL提供的迭代器的优点，我们需要提供一些迭代器接口。后面我们会来学习如果实现这些接口，不过将我们自定义的迭代器与STL的标准迭代器放在一起时，有时会发现有编译不通过的问题。这是为什么呢？

STL算法尝试寻找更多有关于我们所使用迭代器的信息。不同迭代器的能力是不同的，不大可能用同样的算法实现不同的迭代器。例如，我们只是简单的从一个std::vector将其中的数字拷贝到另一个时，我们的实现中可以直接调用memcpy快速实现这个功能。如果容器是std::list的话，memcpy的方式就不好用了，只能一个个的单独拷贝。实现者将大量的自动优化思想注入STL算法实现当中。为了能更好的使用，我们也会为我们的迭代器装备这些思想。

How to do it...

本节中，我们将实现一个简单的计数迭代器(与STL算法一起使用)，一开始这个实现是无法编译通过的。我们需要做一些兼容性操作，使得程序通过编译。

1. 包含必要的头文件。

   #include <iostream>
   #include <algorithm>
   

2. 实现一个计数迭代器，作为基础版本。当我们使用其进行遍历时，我们只需要增加计数器即可。num_range用来处理begin和end迭代器。

   class num_iterator
   {
   	int i;
   public:
       explicit num_iterator(int position = 0) : i{position} {}
       int operator*() const { return i; }
       num_iterator& operator++() {
           ++i;
           return *this;
       }
       bool operator!=(const num_iterator &other) const {
       	return i != other.i;
       }
       bool operator==(const num_iterator &other) const {
       	return !(*this != other);
       }
   };
   
   class num_range {
       int a;
       int b;
   public:	
       num_range(int from, int to)
       	: a{from}, b{to}
       {}
       num_iterator begin() const { return num_iterator{a}; }
       num_iterator end() const { return num_iterator{b}; }
   };
   

3. 声明所使用的命名空间。

   using namespace std;
   

4. 现在让我们来遍历100到109间的数字。这里需要注意的是，110这里是开区间，所以值无法遍历到110。

   int main()
   {
   	num_range r {100, 110};
   

5. 现在，我们使用一个STL算法std::minmax_element。这个算法会返回一个std::pair，其具有两个迭代器：一个指向最小值的迭代器和一个指向最大值的迭代器。在这个范围中100和109即为这两个迭代器所指向的位置。

       auto min_max(minmax_element(r.begin(), r.end()));
   	cout << *min_max.first << " - " << *min_max.second << '\n';
   }
   

6. 我们在编译的时候遇倒如下的错误信息。这个错误与std::iterator_traits有关。这个错误可能在使用其他编译器时，错误信息的格式不同，或者就没有错误。这个错误在clang 5.0.0 (trunk 299766)版本出现。

   

7. 为了修正这个错误，我们需要激活迭代器的迭代功能。之后定义一个num_iterator结构体，我们会对std::iterator_traits进行特化。这个特化就是告诉STL我们的num_iterator是一种前向迭代器，并且指向的对象是int类型的值。

namespace std {
template <>
struct iterator_traits<num_iterator> {
    using iterator_category = std::forward_iterator_tag;
    using value_type = int;
};
}

8. 让我们再对程序进行编译，之前的错误应该不存在了。输出了范围内的最大值和最小值:

   100 - 109
   

How it works...

一些STL算法需要知道其处理容器的迭代器类型，有些还需要知道迭代器所指向的类型。这就是要有不同实现的原因。

不过，所有STL算法将会通过std::iterator_traits<my_iterator>访问对应类型的迭代器(这里假设迭代器类型为my_iterator)。这个特性类需要包含五种不同类型的成员定义：

• difference_type: it1- it2结果的类型
• value_type: 迭代器解引用的数据的类型(这里需要注意void类型)
• pointer: 指向元素指针的类型
• reference: 引用元素的类型
• iterator_category: 迭代器属于哪种类型

pointer、reference和difference_type并没有在num_iterator中定义，因为其实际的内存值不重复(我们只是返回int值，不想数组一样是连续的)。因此num_iterator并不需要定义这些类型，因为算法是依赖于解引用后指定内存上的值。如果我们的迭代器定义了这些类型，就可能会出现问题。

There's more...

C++17标准之前，C++都鼓励自定义迭代器继承于std::iterator<...>，这样所有主流的类型都会自动定义。C++17中这条建议仍然能工作，但是不再推荐从std::iterator<...>继承了。

使用迭代适配器填充通用数据结构

大多数情况下，我们想要用数据来填充任何容器，不过数据源和容器却没有通用的接口。这种情况下，我们就需要人工的去编写算法，将相应的数据推入容器中。不过，这会分散我们解决问题的注意力。

不同数据结构间的数据传递现在可以只通过一行代码就完成，这要感谢STL中的迭代适配器。本节会展示如何使用迭代适配器。

How to do it...

本节中，我们使用一些迭代器包装器，展示如何使用包装器，并了解其如何在编程任务中给予我们帮助。

1. 包含必要的头文件。

   #include <iostream>
   #include <string>
   #include <iterator>
   #include <sstream>
   #include <deque>
   

2. 声明使用的命名空间。

   using namespace std;
   

3. 开始使用std::istream_iterator。这里我们特化为int类型。这样，迭代器就能将标准输入解析成整数。例如，当我们遍历这个迭代器，其就和std::vector<int>一样了。end迭代器的类型没有变化，但不需要构造参数:

   int main()
   {
       istream_iterator<int> it_cin {cin};
       istream_iterator<int> end_cin;
   

4. 接下来，我们实例化一个std::deque<int>，并且将标准输入中的所有数字拷贝到队列中。队列本身不是一个迭代器，所以我们使用std::back_inserter辅助函数将队列包装入std::back_insert_iterator中。这样指定的迭代器就能执行v.pack_back(item)，将标准输入中的每个元素放入容器中。这样就能让队列自动增长。

       deque<int> v;
       copy(it_cin, end_cin, back_inserter(v));	
   

5. 接下来，我们使用std::istringstream将元素拷贝到队列中部。先使用字符串，来定义一个字符流的实例：

   	istringstream sstr {"123 456 789"};
   

6. 我们需要选择列表的插入点。这个点必须在中间，我们使用队列的起始指针，然后使用std::next函数将其指向中间位置。函数第二个参数的意思就是让指针前进多少，这里选择v.size() / 2步，也就是队列的正中间位置(这里我们将v.size()强转为int类型，因为std::next第二个参数类型为difference_type，是和第一个迭代器参数间的距离。因此，该类型是个有符号类型。根据编译选项，如果我们不进行显式强制转化，编译器可能会报出警告)。

       auto deque_middle (next(begin(v),
       	 static_cast<int>(v.size()) / 2));
   

7. 现在，我们可以从输入流中一步步的拷贝整数到队列当中。另外，流的end包装迭代器为空的std::istream_iterator<int>。这个队列已经被包装到一个插入包装器中，也就是成为std::insert_iterator的一个实例，其指向队列中间位置的迭代器，我们用deque_middle表示:

   	copy(istream_iterator<int>{sstr}, {}, inserter(v, deque_middle));
   

8. 现在，让我们使用std::front_insert_iterator插入一些元素到队列中部：

       initializer_list<int> il2 {-1, -2, -3};
       copy(begin(il2), end(il2), front_inserter(v));
   

9. 最后一步将队列中的全部内容打印出来。std::ostream_iterator作为输出迭代器，在我们的例子中其就是从std::cout拷贝打印出的信息，并将各个元素使用逗号隔开：

       copy(begin(v), end(v), ostream_iterator<int>{cout, ", "});
       cout << '\n';
   }
   

10. 编译并运行，即有如下的输出。你能找到那些数字是由哪行的代码插入的吗？

    $ echo "1 2 3 4 5" | ./main
    -3, -2, -1, 1, 2, 123, 456, 789, 3, 4, 5,
    

How it works...

本节我们使用了很多不同类型的迭代适配器。他们有一点是共同的，会将一个对象包装成迭代器。

std::back_insert_iterator

back_insert_iterator可以包装std::vector、std::deque、std::list等容器。其会调用容器的push_back方法在容器最后插入相应的元素。如果容器实例不够长，那么容器的容量会自动增长。

std::front_insert_iterator

front_insert_iterator和back_insert_iterator一样，不过front_insert_iterator调用的是容器的push_front函数，也就是在所有元素前插入元素。这里需要注意的是，当对类似于std::vector的容器进行插入时，其已经存在的所有元素都要后移，从而空出位置来放插入元素，这会对性能造成一定程度的影响。

std::insert_iterator

这个适配器与其他插入适配器类似，不过能在容器的中间位置插入新元素。使用std::inserter包装辅助函数需要两个参数。第一个参数是容器的实例，第二个参数是迭代器指向的位置，就是新元素插入的位置。

std::istream_iterator

istream_iterator是另一种十分方便的适配器。其能对任何std::istream使用(文件流或标准输入流)，并且可以根据实例的具体特化类型，对流进行分析。本节中，我们使用了std::istram_iterator<int>(std::cin)，其会将整数从标准输入中拉出来。

通常，对于流来说，其长度我们是不知道的。这就存在一个问题，也就是end迭代器指向的位置在哪里？对于流迭代器来说，它就知道相应的end迭代器的位置。这样就使得迭代器的比较更加高效，不需要通过遍历来完成。这样就是为什么end流迭代器不需要传入任何参数的原因。

std::ostream_iterator

ostream_iterator和istream_iterator类似，不过是用来进行输出的流迭代器。与istream_iterator不同在于，构造时需要传入两个参数，且第二个参数必须要是一个字符串，这个字符串将会在各个元素之后，推入输出流中。这样我们就能很容易的在元素中间插入逗号或者换行的符号，以便用户进行观察。

使用迭代器实现算法

迭代器通常根据指向位置的移动，来遍历容器中的元素，但不需要迭代对应的数据类型。迭代器也会被用来实现算法，其可以通过++it指向下一个元素，并且通过*it解引用得到对应的值。

本节中，我们将用迭代器来实现斐波那契函数。斐波那契函数会有类似如下的迭代：F(n) = F(n - 1) + F(n - 2)。数列的初始值F(0) = 0和 F(1) = 1。这样下列序列就可以进行计算：

• F(0) = 0
• F(1) = 1
• F(2) = F(1) + F(0) = 1
• F(3) = F(2) + F(1) = 2
• F(4) = F(3) + F(2) = 3
• F(5) = F(4) + F(3) = 5
• F(6) = F(5) + F(4) = 8
• ...

我们要实现一个函数，可以输出斐波那契第n个数的值。通常我们都会使用函数迭代，或者是循环来实现这个函数。这样的话，我们只能一个个的将相应的值算出来，然后才能计算出下一个值。这里我们有两个选择——递归调用斐波那契函数计算整个数列，这样很浪费计算时间，或者将最后两个斐波那契数作为临时变量，并用它们来计算下一个数。第二种方法我们需要重新实现斐波那契算法循环。这样我们就可以将斐波那契数列计算的代码和我们实际的代码放在一起：

size_ta{0};
size_tb{1};
for(size_ti{0};i< N;++i){
    constsize_told_b{b};
    b+=a;
    a=old_b;
    // do something with b, which is the current fibonacci number
}

使用迭代器实现斐波那契数列是一件很有意思的事情。如何将循环中的迭代，使用迭代器的前向自加操作来代替呢？其实很简单，让我们来看一下。

How to do it...

本节中，我们主要关注如何用一个迭代器实现生成斐波那契数列。

1. 为了打印斐波那契数列在终端，我们需要包含标准输入输出流头文件。

   #include <iostream>
   

2. 我们调用斐波那契迭代器——fibit。其会指向一个值i，其保存的值为斐波那契数列对应的位置，a和b保存斐波那契数列中最后两个值。实例化迭代器时，需要将斐波那契迭代器初始化为F(0)的值：

   class fibit
   {
       size_t i {0};
       size_t a {0};
       size_t b {1};
   

3. 下一步，定义标准构造函数和另一个构造函数用来初始化迭代器。

   public:
       fibit() = default;
       explicit fibit(size_t i_)
           : i{i_}
       {}
   

4. 当我们对迭代器解引用时，迭代器将返回对应位置的数值。

   	size_t operator*() const { return b; }
   

5. 当移动迭代器++时，其会移动到下一个斐波那契数上。这里的实现与基于循环的实现几乎是一样的。

       fibit& operator++() {
           const size_t old_b {b};
           b += a;
           a = old_b;
           ++i;
           return *this;
       } 
   

6. 当使用循环时，增加后的迭代器将会和end迭代器进行比较，所以这里需要为迭代器实现不等于!=操作符。我们只比较当且迭代器所对应的步数，这比循环1000000次再结束迭代器简单许多，这样我们就不需要计算太多的斐波那契数：

   	bool operator!=(const fibit &o) const { return i != o.i; }
   };
   

7. 为了能让斐波那契迭代器适应for循环的范围写法，我们需要实现一个范围类。我们称这个类为fib_range，其构造函数只需要一个参数，这个参数能够告诉我们我们想要遍历的范围：

   class fib_range
   {
   	size_t end_n;
   public:
       fib_range(size_t end_n_)
       	: end_n{end_n_}
       {}
   

8. begin和end函数将会返回对应位置上的迭代器，也就是F(0)和F(end_n)对应的迭代器。

       fibit begin() const { return fibit{}; }
       fibit end() const { return fibit{end_n}; }
   };
   

9. 好了，其他与迭代器相关的代码我们就不管了。因为我们辅助类就能很好的帮助我们将这些细节的东西隐藏掉！让我们打印10个斐波那契数字：

   int main()
   {
       for (size_t i : fib_range(10)) {
      		std::cout << i << ", ";
       }
       std::cout << '\n';
   }
   

10. 编译运行后，我们会在终端上看到如下的打印：

    1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
    

There's more...

为了兼容STL中的迭代器，这里实现的迭代器必须支持std::iterator_traits类。想要知道怎么做，要参考一下3.2节(让自己的迭代器与STL的迭代器兼容)，其对如何兼容进行了明确地说明。

Note：

试着从迭代器的角度思考，这样的代码在很多情况下就显得十分优雅。不用担心性能，编译器会根据模板对迭代器相关的代码进行优化。

为了保证例子的简洁性，我们并没有对其做任何事情，不过要是作为斐波那契迭代器的发布库的话，其可用性还是比较差的——fibit传入一个参数的构造函数，可以直接使用end迭代器替换，因为fibit并没有包含任何一个合法的斐波那契值，这里的库并不强制使用这种方式。

还有些方面需要进行修复：

• 将fibit(size_t i_)声明为私有构造函数，并在fibit类中将fib_range类声明为一个友元类。这样用户就只能使用正确的方式进行迭代了。

• 可以使用迭代器哨兵，避免用户引用end迭代器。可以参考一下3.6节(使用哨兵终止迭代)中内容，以获得更多信息。

使用反向迭代适配器进行迭代

有时我们需要反向迭代一个范围内的内容。基于范围的for循环中，STL迭代通常都使用前向累加的方式进行迭代，那么当需要反向时，就需要对其进行递减。当然，这里可以将迭代器进行包装，将调用累加操作改为递减的操作。听起来要写好多冗余的代码，来对反向迭代进行支持。

STL中提供了反向迭代适配器，其能帮助我们对迭代器进行包装。

How to do it...

本节中，我们将用另一种方式使用反向迭代器，只为了展示如何使用它们：

1. 包含必要的头文件：

   #include <iostream>
   #include <list>
   #include <iterator>
   

2. 声明所使用的命名空间：

   using namespace std;
   

3. 为了有东西可以迭代，我们实例化一个整数列表：

   int main()
   {
   	list<int> l {1, 2, 3, 4, 5};
   

4. 现在，让我们来反向打印这些数字。为了完成反向打印，我们调用std::list的成员函数rbegin和rend获得反向迭代器，并且将数字推入输出流ostream_iterator适配器中:

       copy(l.rbegin(), l.rend(), ostream_iterator<int>{cout, ", "});
       cout << '\n';
   

5. 如果容器不提供rbegin和rend函数的话，就需要使用双向迭代器来帮忙了，这里可以使用工厂函数std::make_reverse_iterator创建双向迭代器。其能接受普通迭代器，然后将其转换为反向迭代器：

       copy(make_reverse_iterator(end(l)),
           make_reverse_iterator(begin(l)),
           ostream_iterator<int>{cout, ", "});
       cout << '\n';
   }
   

6. 编译并运行该程序，就能得到如下的输出：

   5, 4, 3, 2, 1,
   5, 4, 3, 2, 1,
   

How it works...

为了将一个普通迭代器转换为一个反向迭代器，容器至少要支持双向迭代。这就需要双向类别或更高级的迭代器才能满足条件。

反向迭代器是普通迭代器的一种，并且连接口和普通迭代器都一样，不过其累加操作会被当做递减操作来进行。

下面就来聊一下begin和end迭代器的位置。先来看一下图，迭代器区域里面是一串标准的数字序列。

如果序列是从1到5，begin迭代器将指向元素1所在的位置，并且end迭代器将指向元素5后面的位置。当定义了反向迭代器，rbegin迭代器就指向了元素5，并且rend迭代器指向元素1之前的位置。可以将书反过来看，可以发现这两个中方式是镜像的。

当我们想让我们自定义的容器类支持反向迭代，我们不用将所有细节一一实现；我们只需使用std::make_reverse_iterator工厂函数，将普通的迭代器包装成反向迭代器即可，背后的操作STL会帮我们完成。