C++性能优化指南

Posted on

C++代码优化策略总结

C++ 有一些热点代码是性能“惯犯”，其中包括函数调用、内存分配和循环。下面是一份改善 C++ 程序性能的方法的总结。

用好的编译器并用好编译器

关于如何选择 C++ 编译器的一条最重要的建议，是使用支持 C++11 的编译器。C++11 实现了右值引用（rvalue reference）和移动语义（move semantics），可以省去许多在以前的C++ 版本中无法避免的复制操作，

有时，用好的编译器也意味着用好编译器。默认情况下，许多编译器都不会进行任何优化，因为如果不进行优化，编译器就可以稍微缩短一点编译时间。当关闭优化选项时，调试也会变得更加简单，因为程序的执行流程与源代码完全一致。优化选项可能会将代码移出循环、移除一些函数调用和完全移除一些变量。仅仅是打开函数内联优化选项就可以显著地提升 C++ 程序的性能，因为编写许多小的成员函数去访问各个类的成员变量是一种优秀的 C++ 编码风格。

使用更好的算法

选择一个最优算法对性能优化的效果最大。

使用更好的库

C++ 编译器提供的标准 C++ 模板库和运行时库必须是可维护的、全面的和非常健壮的。Boost Project（http://www.boost.org）和 Google Code（https://code.google.com）等公开了很多可供使用的库，其中有一些用于 I/O、窗口、处理字符串和并发的库。它们虽然不是标准库的替代品，却可以帮助我们改善性能和加入新的特性。这些库在设计上的权衡与标准库不同，从而获得了处理速度上的提升。

减少内存分配和复制

减少对内存管理器的调用是一种非常有效的优化手段，以至于开发人员只要掌握了这一个技巧就可以变为成功的性能优化人员。绝大多数 C++ 语言特性的性能开销最多只是几个指令，但是每次调用内存管理器的开销却是数千个指令。

对缓存复制函数的一次调用也可能消耗数千个 CPU 周期。因此，很明显减少复制是一种提高代码运行速度的优化方式。大量复制的发生都与内存分配有关，所以修改一处往往也会消灭另一处。其他可能会发生复制的热点代码是构造函数和赋值运算符以及输入输出。

移除计算

除了内存分配和函数调用外，单条 C++ 语句的性能开销通常都很小。但是如果在循环中执行 100 万次这条语句，或是每次程序处理事件时都执行这条语句，那么这就是个大问题了。绝大多数程序都会有一个或多个主要的事件处理循环和一个或多个处理字符的函数。找出并优化这些循环几乎总是可以让性能优化硕果累累。

使用更好的数据结构

选择最合适的数据结构对性能有着深刻的影响，因为插入、迭代、排序和检索元素的算法的运行时开销取决于数据结构。除此之外，不同的数据结构在使用内存管理器的方式上也有所不同。另一个原因是数据结构可能有也可能没有优秀的缓存本地化。

提高并发性

现代计算机都可以使用多个处理核心来执行指令。如果一项工作被分给几个处理器执行，那么它可以更快地执行完毕。伴随并发执行而来的是用于同步并发线程让它们可以共享数据的工具。有人可以用好这些工具，有人则用不好。

优化内存管理

内存管理器作为 C++ 运行时库中的一部分，管理着动态内存分配。它在许多 C++ 程序中都会被频繁地执行。C++ 确实为内存管理提供了丰富的 API。

小结

本书将帮助开发人员识别和利用以下优化机会来改善代码性能。

  • 使用更好的编译器，打开编译选项
  • 使用最优算法
  • 使用更好的库并用好库
  • 减少内存分配
  • 减少复制
  • 移除计算
  • 使用最优数据结构
  • 提高并发
  • 优化内存管理

影响优化的计算机行为

C++所相信的计算机谎言

有一个与其他任何有效的内存地址都不同的特殊的地址，叫作nullptr。整数 0 会被转换为nullptr，尽管在地址 0 上不需要nullptr。有一个概念上的执行地址指向正在被执行的源代码语句。C++ 知道计算机远比这个简单模型要复杂。它在这台闪闪发亮的机器下提供了一些快
速功能。

  • C++ 程序只需要表现得好像语句是按照顺序执行的。C++ 编译器和计算机自身只要能够确保每次计算的含义都不会改变，就可以改变执行顺序使程序运行得更快。
  • 自 C++11 开始， C++ 不再认为只有一个执行地址。C++ 标准库现在支持启动和终止线程以及同步线程间的内存访问。在C++11之前，程序员对C++编译器隐瞒了他们的线程，有时候这会导致难以调试。
  • 某些内存地址可能是设备寄存器，而不是普通内存。这些地址的值可能会在同一个线程对该地址的两次连续读的间隔发生变化，这表示硬件发生了变化。在 C++ 中用volatile 关键字定义这些地址。声明一个volatile变量会要求编译器在每次使用该变量时都获取它的一份新的副本，而不用通过将该变量的值保存在一个寄存器中并复用它来优化程序。另外，也可以声明指向volatile内存的指针。
  • C++11 提供了一个名为std::atomic<>的特性，可以让内存在一段短暂的时间内表现得仿佛是字节的简单线性存储一样，这样可以远离所有现代处理器的复杂性，包括多线程执行、多层高速缓存等。

计算机的真相

内存很慢

通往主内存的接口是限制执行速度的瓶颈。这个瓶颈甚至有一个名字，叫冯 - 诺伊曼瓶颈。多个活动会争夺对内存总线的访问。处理器会不断地读取包含下一条需要执行的指令的内存。高速缓存控制器会将数据内存块保存至高速缓存中，刷新已写的缓存行。DRAM 控制器还会“偷用”周期刷新内存中的动态 RAM 基本存储单元的电荷。多核处理器的核心数量足以确保内存总线的通信数据量是饱和的。数据从主内存读取至某个核心的实际速率大概是每字 20 至 80 纳秒（ns）。

根据摩尔定律，每年处理器核心的数量都会增加。但是这也无法让连接主内存的接口变快。这些核心只能等待访问内存的机会。上述对性能的隐式限制被称为内存墙（memory wall）。

内存访问并非以字节为单位

当 C++ 获取一个多字节类型的数据，比如一个 int、 double 或者指针时，构成数据的字节可能跨越了两个物理内存字。这种访问被称为非对齐的内存访问（unaligned memory access）。此处优化的意义在于，一次非对齐的内存访问的时间相当于这些字节在同一个字中时的两倍，因为需要读取两个字。C++ 编译器会帮助我们对齐结构体，使每个字段的起始字节地址都是该字段的大小的倍数。

某些内存访问会比其他的更慢

为了进一步补偿主内存的缓慢速度，许多计算机中都有高速缓存（cache memory），一种非常接近处理器的快速的、临时的存储，来加快对那些使用最频繁的内存字的访问速度。高速缓存层次中每一层的速度大约是它下面一层的 10 倍。

当执行单元需要获取不在高速缓存中的数据时，有一些当前处于高速缓存中的数据必须被舍弃以换取足够的空余空间。通常，选择放弃的数据都是最近很少被使用的数据。这一点与性能优化有着紧密的关系，因为这意味着访问那些被频繁地访问过的存储位置的速度会比访问不那么频繁地被访问的存储位置更快。读取一个不在高速缓存中的字节甚至会导致许多临近的字节也都被缓存起来

就 C++ 而言，这表示一个包含循环处理的代码块的执行速度可能会更快。这是因为组成循环处理的指令会被频繁地执行，而且互相紧挨着，因此更容易留在高速缓存中。一段包含函数调用或是含有 if 语句导致执行发生跳转的代码则会执行得较慢，因为代码中各个独立的部分不会那么频繁地被执行，也不是那么紧邻着。

内存字分为大端和小端

处理器可以一次从内存中读取一字节的数据，但是更多时候都会读取由几个连续的字节组成的一个数字。例如，在微软的 Visual C++ 中，读取 int 值时会读取 4 字节。如果 int 值 0x01234567 存储在地址 1000~1003 中，而且首先存储小端，那么在地址 1000 中存储的是 0x01，在地址 1003 中存储的是 0x67。反之，如果首先存储大端，那么在地址 1000 中存储的是 0x67， 0x01 被存储在地址 1003 中。从首字节地址读取最高有效位的计算机被称为大端计算机， 小端计算机则会首先读取最低有效位。

内存容量是有限的

想让高速缓存更快是非常昂贵的。一台台式计算机或是手机中可能会有数吉字节的主内存，但是只有几百万字节的高速缓存。通常，程序和它们的数据不会被存储在高速缓存中。

高速缓存和虚拟内存带来的一个影响是，由于高速缓存的存在，在进行性能测试时，一个函数运行于整个程序的上下文中时的执行速度可能是运行于测试套件中时的万分之一。当运行于整个程序的上下文中时，函数和它的数据不太可能存储至缓存中，而在测试套件的上下文中，它们则通常会被缓存起来。这个影响放大了减少内存或磁盘使用量带来的优化收益，而减小代码体积的优化收益则没有任何变化。

第二个影响则是，如果一个大程序访问许多离散的内存地址，那么可能没有足够的高速缓存来保存程序刚刚使用的数据。这会导致一种性能衰退，称为页抖动（page thrashing）。

指令执行缓慢

处理器中包含一条指令“流水线”，它支持并发执行指令。指令在流水线中被解码、获取参数、执行计算，最后保存处理结果。处理器的性能越强大，这条流水线就越复杂。它会将指令分解为若干阶段，这样就可以并发地处理更多的指令。如果指令 B 需要指令 A 的计算结果，那么在计算出指令 A 的处理结果前是无法执行指令 B的计算的。这会导致在指令执行过程中发生流水线停滞（pipeline stall）。

计算机难以作决定

跳转指令或跳转子例程指令会将执行地址变为一个新的值。在执行跳转指令一段时间后，执行地址才会被更新。在这之前是无法从内存中读取“下一条”指令并将其放入到流水线中的。新的执行地址中的内存字不太可能会存储在高速缓存中。在更新执行地址和加载新的“下一条”指令到流水线中的过程中，会发生流水线停滞。

在执行了一个条件分支指令后，执行可能会走向两个方向：下一条指令或者分支目标地址中的指令。最终会走向哪个方向取决于之前的某些计算的结果。这时，流水线会发生停滞，直至与这些计算结果相关的全部指令都执行完毕，而且还会继续停滞一段时间，直至决定一下条指令的地址并取得下一条指令为止。

程序执行中的多个流

当许多程序一齐开始运行，互相竞争内存和磁盘时。为了性能调优，如果一个程序必须在启动时执行或是在负载高峰期时执行，那么在测量性能时也必须带上负载。

如果操作系统正在将一个线程切换至同一个程序的另外一个线程，这表示要为即将暂停的线程保存处理器中的寄存器，然后为即将被继续执行的线程加载之前保存过的寄存器。现代处理器中的寄存器包含数百字节的数据。当新线程继续执行时，它的数据可能并不在高速缓存中，所以当加载新的上下文到高速缓存中时，会有一个缓慢的初始化阶段。因此，切换线程上下文的成本很高。

当操作系统从一个程序切换至另外一个程序时，这个过程的开销会更加昂贵。所有脏的高速缓存页面都必须被刷新至物理内存中。所有的处理器寄存器都需要被保存。然后，内存管理器中的“物理地址到虚拟地址”的内存页寄存器也需要被保存。接着，新线程的“物理地址到虚拟地址”的内存页寄存器和处理器寄存器被载入。最后就可以继续执行了。但是这时高速缓存是空的，因此在高速缓存被填充满之前，还有一段缓慢且需要激烈地竞争内存的初始化阶段。

当执行单元写值时，这个值会首先进入高速缓存内存。不过最终，这个值将被写入至主内存中，这样其他所有的执行单元就都可以看见这个值了。但是，这些执行单元在访问主内存时存在着竞争，所以可能在执行单元改变了一个值，然后又执行几百个指令后，主内存中的值才会被更新。

因此，如果一台计算机有多个执行单元，那么一个执行单元可能需要在很长一段时间后才能看见另一个执行单元所写的数据被反映至主内存中，而且主内存发生改变的顺序可能与指令的执行顺序不一样。受到不可预测的时间因素的干扰，执行单元看到的共享内存字中的值可能是旧的，也可能是被更新后的值。这时，必须使用特殊的同步指令来确保运行于不同执行单元间的线程看到的内存中的值是一致的。对优化而言，这意味着访问线程间的
共享数据比访问非共享数据要慢得多。

调用操作系统的开销是昂贵的

操作系统内核需要能够访问所有程序的内存，这样程序就可以通过系统调用访问操作系统。有些操作系统还允许程序发送访问共享内存的请求。许多系统调用的发生方式和共享内存的分布方式是多样和神秘的。对优化而言，这意味着系统调用的开销是昂贵的，是单线程程序中的函数调用开销的数百倍。

C++也会说谎

并非所有语句的性能开销都相同

一个赋值语句，如BigInstance i = OtherObject;会复制整个对象的结构。更值得注意的是，这类赋值语句会调用BigInstance的构造函数，而其中可能隐藏了不确定的复杂性。当一个表达式被传递给一个函数的形参时，也会调用构造函数。当函数返回值时也是一样的。对优化而言，这一点的意义是某些语句隐藏了大量的计算，但从这些语句的外表上看不出它的性能开销会有多大。

语句并非按顺序执行

C++ 程序表现得仿佛它们是按顺序执行的，完全遵守了 C++ 流程控制语句的控制。上句话中的含糊其辞的“仿佛”正是许多编译器进行优化的基础，也是现代计算机硬件的许多技巧的基础。

当然，在底层，编译器能够而且有时也确实会对语句进行重新排序以改善性能。但是编译器知道在测试一个变量或是将其赋值给另外一个变量之前，必须先确定它包含了所有的最新计算结果。现代处理器也可能会选择乱序执行指令，不过它们包含了可以确保在随后读取同一个内存地址之前，一定会先向该地址写入值的逻辑。

并发会让情况变得复杂。C++ 程序在编译时不知道是否会有其他线程并发运行。C++ 编译器不知道哪个变量会在线程间共享。当程序中包含共享数据的并发线程时，编译器对语句的重排序和延迟写入主内存会导致计算结果与按顺序执行语句的计算结果不同。开发人员必须向多线程程序中显式地加入同步代码来确保可预测的行为的一致性。当并发线程共享数据时，同步代码降低了并发量。

小结

  • 在处理器中，访问内存的性能开销远比其他操作的性能开销大。
  • 非对齐访问所需的时间是所有字节都在同一个字中时的两倍。
  • 访问频繁使用的内存地址的速度比访问非频繁使用的内存地址的速度快。
  • 访问相邻地址的内存的速度比访问互相远隔的地址的内存快。
  • 由于高速缓存的存在，一个函数运行于整个程序的上下文中时的执行速度可能比运行于测试套件中时更慢。
  • 访问线程间共享的数据比访问非共享的数据要慢很多。
  • 计算比做决定快。
  • 每个程序都会与其他程序竞争计算机资源。
  • 如果一个程序必须在启动时执行或是在负载高峰期时执行，那么在测量性能时必须加载负载。
  • 每一次赋值、函数参数的初始化和函数返回值都会调用一次构造函数，这个函数可能隐藏了大量的未知代码。
  • 有些语句隐藏了大量的计算。从语句的外表上看不出语句的性能开销会有多大。
  • 当并发线程共享数据时，同步代码降低了并发量。

测量性能

用计算机测量时间

自 Windows 98（可能更早）以来，微软的 C 运行时提供了 ANSI C 函数clock_t clock()。该函数会返回一个有符号形式的时标计数器。常量CLOCKS_PER_SEC指定了每秒钟的时标的次数。返回值为 -1 表示clock()不可用。clock()会基于交流电源的周期性中断记录时标。clock()在 Windows 上的实现方式与 ANSI 所规定的不同。

自奔腾体系结构后，英特尔提供了一个叫作时间戳计数器（Time Stamp Counter， TSC）的硬件寄存器。TSC 是一个从处理器时钟中计算时标数的 64 位寄存器。RDTSC 指令可以非常快地访问该寄存器。

评估代码开销来找出热点代码

评估独立的C++语句的开销

访问内存的时间开销远比执行其他指令的开销大。执行一条指令所花费的时间大致包含从内存中读取指令的每个字节所需要的时间，加上读取指令的输入数据所需的时间，再加上写指令结果的时间。相比之下，隐藏于内存访问时间之下的解码和执行指令的时间就显得微不足道了。读写数据的开销可以近似地看作所有级别的微处理器上的执行指令的相对开销。

有一条有效的规则能够帮助我们评估一条 C++ 语句的开销有多大，那就是计算该语句对内存的读写次数。例如，有一条语句a = b + c;，其中 a、 b 和 c 都是整数， b 和 c 的值必须从内存中读取，而且它们的和必须写入至内存中的位置 a。因此，这条语句的开销是三次内存访问。

再比如，r = *p + a[i];这条语句访问内存的次数如下：一次访问用于读取 i，一次读取a[i]，一次读取 p，一次读取*p所指向的数据，一次将结果写入至r。也就是说总共进行了 5 次访问。

评估循环的开销

由于每条 C++ 语句都只会进行几次内存访问，通常情况下热点代码都不会是一条单独的语句，除非受其他因素的作用，让其频繁地执行。这些因素之一就是该语句出现在了循环中。这样，合计开销就是该语句的开销乘以该语句被执行的次数了。

如果你很幸运，可能会偶然找到这样的代码。分析器可能会指出一条单独的语句被执行了100 万次，或者其他的热点函数包含以下这样的循环：

1
2
3
4
5
6
7
for (int i=1; i<1000000; ++i) {
    do_something_expensive();
    if (mostly_true) {
        do_more_stuff();
        even_more();
    }
}

这个循环中的语句很明显会被执行 100 万次，因此它是热点语句。看起来你需要花点精力去优化。

评估嵌套循环中的循环次数

当一个循环被嵌套在另一个循环里面的时候，代码块的循环次数是内层循环的次数乘以外层循环的次数。例如：

1
2
3
4
5
for (int i=0; i<100; ++i) {
    for (int j=0; j<50; ++j) {
        fiddle(a[i][j]);
    }
}

在这里，代码块的循环次数是 100*50=5000。

嵌套循环可能并非一眼就能看出来。如果一个循环调用了一个函数，而这个函数中又包含了另外一个循环，那么内层循环就是嵌套循环。有时在外层循环中重复地调用函数的开销也是可以消除的。内存循环可能被嵌入在标准库函数中，特别是处理字符串或字符的 I/O 函数。如果这些函数被重复调用的次数非常多，那么可能值得去重新实现标准函数库中的函数来回避调用开销。

评估循环次数为变量的循环的开销

不是所有循环中的循环次数都是很明确的。许多循环处理会不断重复直至满足某个条件为止，比如有些循环会重复地处理字符，直至找到空格为止；还有些循环则会重复地处理数字，直到遇到非数字为止。

识别出隐式循环

响应事件的程序（例如 Windows UI 程序）在最外层都会有一个隐式循环。这个循环甚至在程序中是看不到的，因为它被隐藏在了框架中。如果这个框架以最大速率接收事件的话，那么每当事件处理器取得程序控制权，或是在事件分发前，抑或是在事件分发过程中都会被执行的代码，以及最频繁地被分发的事件中的代码都可能是热点代码。

识别假循环

不是所有的 while 或者 do 语句都是循环语句。我就曾经遇到过使用 do 语句帮助控制流程的代码。下面这个“循环”只会被执行一次。当它遇到while(0)后就会退出：

1
2
3
4
5
6
do {
    if (!operation1())
        break;
    if (!operation2(x,y,z))
        break;
} while(0);

小结

  • 必须测量性能。
  • 做出可测试的预测并记录预测。
  • 记录代码修改。
  • 如果每次都记录了实验内容，那么就可以快速地重复实验。
  • 一个程序会花费 90% 的运行时间去执行 10% 的代码。
  • 只有正确且精确的测量才是准确的测量。
  • 分辨率不是准确性。
  • 只进行有明显效果的性能改善，开发人员就无需担忧方法论的问题。
  • 计算一条 C++ 语句对内存的读写次数，可以估算出一条 C++ 语句的性能开销。

优化字符串的使用：案例研究

为什么字符串很麻烦

字符串是动态分配的

字符串之所以使用起来很方便，是因为它们会为了保存内容而自动增长。为了实现这种灵活性，字符串被设计为动态分配的。相比于 C++ 的大多数其他特性，动态分配内存耗时耗力。因此无论如何，字符串都是性能优化热点。当一个字符串变量超出了其定义范围或是被赋予了一个新的值后，动态分配的存储空间会被自动释放。与下面这段代码展示的需要为动态分配的 C 风格的字符数组手动释放内存相比，这样无疑方便了许多。

1
2
3
4
char* p = (char*) malloc(7);
strcpy(p, "string");
...
free(p);

尽管如此，但字符串内部的字符缓冲区的大小仍然是固定的。任何会使字符串变长的操作，如在字符串后面再添加一个字符或是字符串，都可能会使字符串的长度超出它内部的缓冲区的大小。当发生这种情况时，操作会从内存管理器中获取一块新的缓冲区，并将字符串复制到新的缓冲区中。

有些字符串的实现方式所申请的字符缓冲区的大小是需要存储的字符数的两倍。这样，在下一次申请新的字符缓冲区之前，字符串的容量足够允许它增长一倍。下一次某个操作需要增长字符串时，现有的缓冲区足够存储新的内容，可以避免申请新的缓冲区。

字符串就是值

在赋值语句和表达式中，字符串的行为与值是一样的。可以将一个新值赋予给一个变量，但是改变这个变量并不会改变这个值。例如：

1
2
3
4
int i, j;
i = 3; // i的值是3
j = i; // j的值也是3
i = 5; // i的值现在是5，但是j的值仍然是3

将一个字符串赋值给另一个字符串的工作方式是一样的，就仿佛每个字符串变量都拥有一份它们所保存的内容的私有副本一样：

1
2
3
4
std::string s1, s2;
s1 = "hot"; // s1是"hot"
s2 = s1; // s2是"hot"
s1[0] = 'n'; // s2仍然是"hot"，但s1变为了"not"

由于字符串就是值，因此字符串表达式的结果也是值。如果你使用s1 = s2 + s3 + s4;这条语句连接字符串，那么s2 + s3的结果会被保存在一个新分配的临时字符串中。连接s4后的结果则会被保存在另一个临时字符串中。这个值将会取代s1之前的值。接着，为第一个临时字符串和s1之前的值动态分配的内存将会被释放。这会导致多次调用内存管理器。

字符串会进行大量复制

每个字符串变量必须表现得好像它们拥有一份自己的私有副本一样。实现这种行为的最简单的方式是当创建字符串、赋值或是将其作为参数传递给函数的时候进行一次复制。如果字符串是以这种方式实现的，那么赋值和参数传递的开销将会变得很大，但是变值函数（mutating function）和非
常量引用的开销却很小。

有一种被称为“写时复制”（copy on write）的著名的编程惯用法，它可以让对象与值具有同样的表现，但是会使复制的开销变得非常大。在 C++ 文献中，它被简称为 COW。在 COW 的字符串中，动态分配的内存可以在字符串间共享。每个字符串都可以通过引用计数知道它们是否使用了共享内存。当一个字符串被赋值给另一个字符串时，所进行的处理只有复制指针以及增加引用计数。任何会改变字符串值的操作都会首先检查是否只有一个指针指向该字符串的内存。如果多个字符串都指向该内存空间，所有的变值操作（任何可能会改变字符串值的操作）都会在改变字符串值之前先分配新的内存空间并复制字符串：

1
2
3
4
5
COWstring s1, s2;
s1 = "hot"; // s1是"hot"
s2 = s1; // s2是"hot" （s1和s2指向相同的内存）
s1[0] = 'n';// s1会在改变它的内容之前将当前内存空间中的内容复制一份
// s2仍然是"hot"，但s1变为了"not"

如果以写时复制方式实现字符串，那么赋值和参数传递操作的开销很小，但是一旦字符串被共享了，非常量引用以及任何变值函数的调用都需要昂贵的分配和复制操作。在并发代码中，写时复制字符串的开销同样很大。每次变值函数和非常量引用都要访问引用计数器。当引用计数器被多个线程访问时，每个线程都必须使用一个特殊的指令从主内存中得到引用计数的副本，以确保没有其他线程改变这个值。

第一次尝试优化字符串

假设通过分析一个大型程序揭示出了remove_ctrl()函数的执行时间在程序整体执行时间中所占的比例非常大。这个函数的功能是从一个由 ASCII 字符组成的字符串中移除控制字符。看起来它似乎很无辜，但是出于多种原因，这种写法的函数确实性能非常糟糕。

1
2
3
4
5
6
7
8
std::string remove_ctrl(std::string s) {
    std::string result;
    for (int i=0; i<s.length(); ++i) {
        if(s[i] >= 0x20)
            result = result + s[i];
    }
    return result;
}

remove_ctrl()在循环中对通过参数接收到的字符串 s 的每个字符进行处理。循环中的代码就是导致这个函数成为热点的原因。字符串连接运算符的开销是很大的。它会调用内存管理器去构建一个新的临时字符串对象来保存连接后的字符串。如果传递给remove_ctrl()的参数是一个由可打印的字符组成的字符串，那么remove_ctrl()几乎会为 s 中的每个字符都构建一个临时字符串对象。对于一个由 100 个字符组成的字符串而言，这会调用 100 次内存管理器来为临时字符串分配内存，调用 100 次内存管理器来释放内存。

除了分配临时字符串来保存连接运算的结果外，将字符串连接表达式赋值给 result 时可能还会分配额外的字符串。当然，这取决于字符串是如何实现的。

  • 如果字符串是以写时复制惯用法实现的，那么赋值运算符将会执行一次高效的指针复制并增加引用计数。
  • 如果字符串是以非共享缓冲区的方式实现的，那么赋值运算符必须复制临时字符串的内容。如果实现是原生的，或者 result 的缓冲区没有足够的容量，那么赋值运算符还必须分配一块新的缓冲区用于复制连接结果。这会导致 100 次复制操作和 100 次额外的内存分配。
  • 如果编译器实现了 C++11 风格的右值引用和移动语义，那么连接表达式的结果是一个右值，这表示编译器可以调用 result 的移动构造函数，而无需调用复制构造函数。因此，程序将会执行一次高效的指针复制。

每次执行连接运算时还会将之前处理过的所有字符复制到临时字符串中。如果参数字符串有 n 个字符，那么remove_ctrl()会复制 O(n^2) 个字符。所有这些内存分配和复制都会导致性能变差。

因为remove_ctrl()是一个小且独立的函数，所以我们可以构建一个测试套件，通过反复地调用该函数来测量通过优化到底能将该函数的性能提升多少。

使用复合赋值操作避免临时字符串

我首先通过移除内存分配和复制操作来优化remove_ctrl()。第 5 行中会产生很多临时字符串对象的连接表达式被替换为了复合赋值操作符+=。

1
2
3
4
5
6
7
8
std::string remove_ctrl_mutating(std::string s) {
    std::string result;
    for (int i=0; i<s.length(); ++i) {
        if(s[i] >= 0x20)
            result += s[i];
    }
    return result;
}

这个小的改动却带来了很大的性能提升。这次改善源于移除了所有为了分配临时字符串对象来保存连接结果而对内存管理器的调用，以及相关的复制和删除临时字符串的操作。赋值时的分配和复制操作也可以被移除，不过这取决于字符串的实现方式。

通过预留存储空间减少内存的重新分配

remove_ctrl_mutating()函数仍然会执行一个导致 result 变长的操作。如果std::string是以这种规则实现的，那么对于一个含有 100 个字符的字符串来说，重新分配内存的次数可能会多达 8 次。

假设字符串中绝大多数都是可打印的字符，只有几个是需要被移除的控制字符，那么参数字符串 s 的长度几乎等于结果字符串的最终长度。使用reserve()不仅移除了字符串缓冲区的重新分配，还改善了函数所读取的数据的缓存局部性（cache locality），因此我们从中得到了更好的改善效果。

1
2
3
4
5
6
7
8
9
std::string remove_ctrl_reserve(std::string s) {
    std::string result;
    result.reserve(s.length());
    for (int i=0; i<s.length(); ++i） {
        if (s[i] >= 0x20)
            result += s[i];
    }
    return result;
}

移除了几处内存分配后，程序性能得到了明显的提升。

消除对参数字符串的复制

如果实参是一个变量，那么将会调用形参的构造函数，这会导致一次内存分配和复制。remove_ctrl_ref_args()是改善后的永远不会复制 s 的函数。由于该函数不会修改 s，因此没有理由去复制一份 s。取而代之的是，remove_ctrl_ref_args()会给s 一个常量引用作为参数。这省去了另外一次内存分配。由于内存分配是昂贵的，所以哪怕只是一次内存分配，也值得从程序中移除。

1
2
3
4
5
6
7
8
9
std::string remove_ctrl_ref_args(std::string const& s) {
    std::string result;
    result.reserve(s.length());
    for (int i=0; i<s.length(）; ++i) {
        if (s[i] >= 0x20)
            result += s[i];
    }
    return result;
}

改善后相比remove_ctrl_reserve()性能下降了 8%。这次修改本应该能够省去一次内存分配。原因可能是并没有真正省去这次内存分配，或是将s 从字符串修改为字符串引用后导致其他相关因素抵消了节省内存分配带来的性能提升。引用变量是作为指针实现的。因在，当在remove_ctrl_ref_args()中每次出现 s 时，程序都会解引指针，而在remove_ctrl_reserve()中则不会发生解引。

使用迭代器消除指针解引

解决方法是在字符串上使用迭代器。字符串迭代器是指向字符缓冲区的简单指针。与在循环中不使用迭代器的代码相比，这样可以节省两次解引操作。remove_ctrl_ref_args_it()使用了迭代器。

1
2
3
4
5
6
7
8
9
std::string remove_ctrl_ref_args_it(std::string const& s) {
    std::string result;
    result.reserve(s.length());
    for (auto it=s.begin(),end=s.end(); it != end; ++it) {
        if (*it >= 0x20)
            result += *it;
    }
    return result;
}

在所有这些函数中，使用迭代器都比不使用迭代器要快。在remove_ctrl_ref_args_it()中还包含另一个优化点，那就是用于控制 for 循环的s.end()的值会在循环初始化时被缓存起来。

消除对返回的字符串的复制

remove_ctrl()函数的初始版本是通过值返回处理结果的。C++ 会调用复制构造函数将处理结果设置到调用上下文中。虽然只要可能的话，编译器是可以省去（即简单地移除）调用复制构造函数的，但是如果我们想要确保不会发生复制，那么有几种选择。其中一种选择是将字符串作为输出参数返回，这种方法适用于所有的 C++ 版本以及字符串的所有实现方式。这也是编译器在省去调用复制构造函数时确实会进行的处理。

1
2
3
4
5
6
7
8
9
10
11
void remove_ctrl_ref_result_it (
    std::string& result,
    std::string const& s)
{
    result.clear();
    result.reserve(s.length());
    for (auto it=s.begin(),end=s.end(); it != end; ++it) {
        if (*it >= 0x20)
            result += *it;
    }
}

当程序调用remove_ctrl_ref_result_it()时，一个指向字符串变量的引用会被传递给形参result。如果result引用的字符串变量是空的，那么调用reserve()将分配足够的内存空间用于保存字符。如果程序之前使用过这个字符串变量，例如程序循环地调用了remove_ctrl_ref_result_it()，那么它的缓冲区可能已经足够大了，这种情况下可能无需分配新的内存空间。当函数返回时，调用方的字符串变量将会接收返回值，无需进行复制。

remove_ctrl_ref_result_it()的优点在于多数情况下它都可以移除所有的内存分配。remove_ctrl_ref_result_it()的性能测量结果是每次调用花费 1.02 微秒，比修改之前的版本快了大约 2%。

用字符数组代替字符串

相比std::string， C 风格的字符串函数更难以使用，但是它们却能带来显著的性能提升。在局部存储区（即函数调用栈）中往往有足够的空间可以静态地声明大型临时缓冲区。当函数退出时，这些缓冲区将会被回收，而产生的运行时开销则微不足道。

1
2
3
4
5
6
7
void remove_ctrl_cstrings(char* destp, char const* srcp, size_t size) {
    for (size_t i=0; i<size; ++i) {
        if (srcp[i] >= 0x20)
        *destp++ = srcp[i];
    }
    *destp = 0;
}

第二次尝试优化字符串

使用更好的算法

一种优化选择是尝试改进算法。初始版本的remove_ctrl()使用了一种简单的算法，一次将一个字符复制到结果字符串中。这个不幸的选择导致了最差的内存分配行为。在初始设计的基础上，通过将整个子字符串移动至结果字符串中改善了函数性能。这个改动可以减少内存分配和复制操作的次数。remove_ctrl_block()中展示的另外一种优化选择是缓存参数字符串的长度，以减少外层 for 循环中结束条件语句的性能开销。

1
2
3
4
5
6
7
8
9
10
11
std::string remove_ctrl_block(std::string s) {
    std::string result;
    for (size_t b=0, i=b, e=s.length(); b < e; b = i+1) {
        for (i=b; i<e; ++i) {
            if (s[i] < 0x20)
                break;
        }
        result = result + s.substr(b,i-b);
    }
    return result;
}

这个函数与以前一样，可以通过使用复合赋值运算符替换字符串连接运算符来改善其性能，但是substr()仍然生成临时字符串。由于这个函数将字符添加到了result的末尾，开发人员可以通过重载std::string的append()成员函数来复制子字符串，且无需创建临时字符串。

1
2
3
4
5
6
7
8
9
10
11
std::string remove_ctrl_block_append(std::string s) {
    std::string result;
    result.reserve(s.length());
    for (size_t b=0,i=b; b < s.length(); b = i+1) {
        for (i=b; i<s.length(); ++i) {
            if (s[i] < 0x20) break;
        }
        result.append(s, b, i-b);
    }
    return result;
}

另外一种改善性能的方法是，通过使用std::string的erase()成员函数移除控制字符来改变字符串。

1
2
3
4
5
6
7
std::string remove_ctrl_erase(std::string s) {
    for (size_t i = 0; i < s.length();)
    if (s[i] < 0x20)
        s.erase(i,1);
    else ++i;
    return s;
}

这种算法的优势在于，由于 s 在不断地变短，除了返回值时会发生内存分配外，其他情况下都不会再发生内存分配。

使用更好的字符串库

定义std::string的行为是一种妥协，它是经过很长一段时间以后从各种设计思想中演变出来的。

  • 与其他标准库容器一样，std::string提供了用于访问字符串中单个字符的迭代器。
  • 与 C 风格的字符串一样，std::string提供了类似数组索引的符号，可以使用运算符[]访问它的元素。std::string还提供了一种用于获取指向以空字符结尾的 C 风格字符串的指针的机制。
  • 与 BASIC 字符串类似，std::string有一个连接运算符和可以赋予字符串值语义（value semantics）的返回值的函数。
  • std::string提供的操作非常有限，有些开发人员会感觉受到了限制。

希望std::string与 C 风格的字符数组一样高效，这个需求推动着字符串的实现朝着在紧邻的内存中表现字符串的方向前进。C++ 标准要求迭代器能够随机访问，而且禁止写时复制语义。

使用std::stringstream避免值语义

C++ 已经有几种字符串实现方式了：模板化的、支持迭代器访问的、可变长度的std::string字符串；简单的、基于迭代器的std::vector<char>；老式的、 C 风格的以空字符结尾的、固定长度的字符数组。

C++ 中还有另外一种字符串。std::stringstream之于字符串，就如同std::ostream之于输出文件。std::stringstream类以一种不同的方式封装了一块动态大小的缓冲区（事实上，通常就是一个std::string），数据可以被添加至这个实体中。std::stringstream是一个很好的例子，它展示了如何在类似的实现的顶层使用不同的API 来提高代码性能。

1
2
3
4
5
6
std::stringstream s;
for (int i=0; i<10; ++i) {
    s.clear();
    s << "The square of " << i << " is " << i*i << std::endl;
    log(s.str());
}

这段代码展示了几个优化代码的技巧。由于 s 被修改为了一个实体，这个很长的插入表达式不会创建任何会临时字符串，因此不会发生内存分配和复制操作。另外一个故意的改动是将 s 声明了在循环外。这样， s 内部的缓存将会被复用。第一次循环时，随着字符被添加至对象中，可能会重新分配几次缓冲区，但是在接下来的迭代中就不太可能会重新分配缓冲区了。相比之下，如果将 s 定义在循环内部，每次循环时都会分配一块空的缓冲区，而且当使用插入运算符添加字符时，还有可能重新分配缓冲区。

如果std::stringstream是用std::string实现的，那么它在性能上永远不能胜过std::string。它的优点在于可以防止某些降低程序性能的编程实践。

string_view可以解决std::string的某些问题。它包含一个指向字符串数据的无主指针和一个表示字符串长度的值，所以它可以表示为std::string或字面字符串的子字符串。与std::string的返回值的成员函数相比，它的substring和trim等操作更高效。std::string_view可能会被加入到 C++14 中。有些编译器现在已经实现了std::experimental::string_view。string_view与std::string的接口几乎相同。

std::string的问题在于指针是无主的。程序员必须确保每个string_view的生命周期都不会比它所指向的std::string的生命周期长。

使用更好的内存分配器

每个std::string的内部都是一个动态分配的字符数组。std::string看上去像是下面这样的通用模板的一种特化：

1
2
3
4
5
6
7
namespace std {
    template < class charT,
        class traits = char_traits<charT>,
        class Alloc = allocator<charT>
    > class basic_string;
    typedef basic_string<char> string;
};

第三个模板参数Alloc定义了一个分配器——一个访问 C++ 内存管理器的专用接口。默认情况下，Alloc是std::allocator，它会调用::operator new()和::operator delete()——两个全局的 C++ 内存分配器函数。

::operator new()和::operator delete()以及分配器对象的行为。现在，我只能告诉读者，::operator new()和::operator delete()会做一项非常复杂和困难的工作，为各种动态变量分配存储空间。它们需要为大大小小的对象以及单线程和多线程程序工作。为了实现良好的通用性，它们在设计上做出了一些妥协。有时，选择一种更加特化的分配器可能会更好。因此，我们可以指定默认分配器以外的为std::string定制的分配器作为Alloc。

这是一个极其简单的分配器，来展示可以获得怎样的性能提升。这个分配器可以管理几个固定大小的内存块。首先为使用这种分配器的字符串创建了一个typedef。接着，修改初始的、非常低效的remove_ctrl()来使用这种特殊的字符串。以下使用简单的、管理固定大小内存块的分配器的原始版本的remove_ctrl()

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef std::basic_string<
    char,
    std::char_traits<char>,
    block_allocator<char, 10>> fixed_block_string;

fixed_block_string remove_ctrl_fixed_block(std::string s) {
    fixed_block_string result;
    for (size_t i=0; i<s.length(); ++i) {
        if (s[i] >= 0x20)
            result = result + s[i];
    }
    return result;
}

remove_ctrl_fixed_block()比初始版本快。

消除字符串转换

现代世界的复杂性之一是不止有一种字符串。通常，字符串函数只适用于对相同类型的字符串进行比较、赋值或是作为运算对象和参数，因此，程序员必须将一种类型的字符串转换为另外一种类型。任何时候，涉及复制字符和动态分配内存的转换都是优化性能的机会。转换函数库自身也可以被优化。更重要的是，大型程序的良好设计是可以限制这种转换的。

将C字符串转换为std::string

从以空字符结尾的字符串到std::string的无谓转换，是浪费计算机 CPU 周期的原因之一。例如：

1
2
3
std::string MyClass::Name() const {
    return "MyClass";
}

这个函数必须将字符串常量MyClass转换为一个std::string，分配内存和复制字符到std::string中。C++ 会自动地进行这次转换，因为在std::string中有一个参数为char*的构造函数。

转换为std::string是无谓的。std::string有一个参数为char*的构造函数，因此当Name()的返回值被赋值给一个字符串或是作为参数传递给另外一个函数时，会自动进行转换。上面的函数可以简单地写为：

1
2
3
char const* MyClass::Name() const {
    return "MyClass";
}

这会将返回值的转换推迟至它真正被使用的时候。当它被使用时，通常不需要转换：

1
2
3
char const* p = myInstance->Name(); // 没有转换
std::string s = myInstance->Name(); // 转换为'std::string'
std::cout << myInstance->Name(); // 没有转换

小结

  • 由于字符串是动态分配内存的，因此它们的性能开销非常大。它们在表达式中的行为与值类似，它们的实现方式中需要大量的复制。
  • 将字符串作为对象而非值可以降低内存分配和复制的频率。
  • 为字符串预留内存空间可以减少内存分配的开销。
  • 将指向字符串的常量引用传递给函数与传递值的结果几乎一样，但是更加高效。
  • 将函数的结果通过输出参数作为引用返回给调用方会复用实参的存储空间，这可能比分配新的存储空间更高效。
  • 即使只是有时候会减少内存分配的开销，仍然是一种优化。
  • 有时候，换一种不同的算法会更容易优化或是本身就更高效。
  • 标准库中的类是为通用用途而实现的，它们很简单。它们并不需要特别高效，也没有为某些特殊用途而进行优化。

优化算法

优化模式

本节收集了一些用于改善性能的通用技巧。它们非常实用。

预计算

预计算是一种常用的技巧，通过在程序执行至热点代码之前，先提前进行计算来达到从热点代码中移除计算的目的。预计算有多种不同的形式，既可以将计算从热点代码移至程序中不那么热点的部分，也可以移动至程序链接时、编译时和设计时。通常，越早进行计算越好。以下是预计算的几个例子。

  • C++ 编译器会使用编译器内建的相关性规则和运算符优先级，对常量表达式的值自动地进行预计算。编译器对上例中的 sec_per_day 的值进行预计算是没有问题的。
  • 编译器会在编译时评估调用模板函数时所用到的参数。如果参数是常量的话，编译器会生成高效代码。
  • 当设计人员可以观察到，例如，当在一段程序的上下文中，“周末”的概念总是两天，那么他可以在编写程序的时候预计算这个常量。

延迟计算

延迟计算的目的在于将计算推迟至更接近真正需要进行计算的地方。延迟计算带来了一些好处。如果没有必要在某个函数中的所有执行路径（if-then-else 逻辑的所有分支）上都进行计算，那就只在需要结果的路径上进行计算。以下是延迟计算的例子。

  • 两段构建（two-part construction）
    • 当实例能够被静态地构建时，经常会缺少构建对象所需的信息。在构建对象时，我们并不是一气呵成，而是仅在构造函数中编写建立空对象的最低限度的代码。稍后，程序再调用该对象的初始化成员函数来完成构建。将初始化推迟至有足够的额外数据时，意味着被构建的对象总是高效的、扁平的数据结构。
  • 写时复制
    • 写时复制是指当一个对象被复制时，并不复制它的动态成员变量，而是让两个实例共享动态变量。只在其中某个实例要修改该变量时，才会真正进行复制。

批量处理

批量处理的目标是收集多份工作，然后一起处理它们。批量处理可以用来移除重复的函数调用或是每次只处理一个项目时会发生的其他计算。当有更高效的算法可以处理所有输入数据时，也可以使用批量处理将计算推迟至有更多的计算资源可用时。举例如下。

  • 缓存输出是批量处理的一个典型例子。输出字符会一直被缓存，直至缓存满了或是程序遇到行尾（EOL）符或是文件末尾（EOF）符。相比于为每个字符都调用输出例程，将整个缓存传递给输出例程节省了性能开销。
  • 将一个未排序的数组转换为堆的最优方法是通过批量处理使用更高效算法的一个例子。将 n 个元素一个一个地插入到堆中的时间开销是 O(n log2n)，而一次性构建整个堆的开销则只有 O(n)。
  • 多线程的任务队列是通过批量处理高效地利用计算资源的一个例子。
  • 在后台保存或更新是使用批量处理的一个例子。

缓存

缓存指的是通过保存和复用昂贵计算的结果来减少计算量的方法。这样可以避免在每次需要计算结果时都重新进行计算。举例如下。

  • 就像用于解引数组元素的计算一样，编译器也会缓存短小的、重复的代码块的结果。当编译器发现了像a[i][j] = a[i][j] + c;这样的语句后会保存数组表达式，然后生成一段像这样的代码：auto p = &a[i][j]; *p = *p + c;。
  • 在每次需要知道 C 风格的字符串的长度时，都必须计算字符的数量，而std::string则会缓存字符串的长度，不会在每次需要时都进行计算。
  • 线程池缓存了那些创建开销很大的线程。

特化

特化与泛化相对。特化的目的在于移除在某种情况下不需要执行的昂贵的计算。通过移除那些导致计算变得昂贵的特性可以简化操作或是数据结构，但是在特定情况下，这是没有必要的。可以通过放松问题的限制或是对实现附加限制来实现这一点，例如，使动态变为静态，限制不受限制的条件，等等。举例如下。

  • 模板函数std::swap()的默认实现可能会复制它的参数。不过，开发人员可以基于对数据结构内部的了解提供一种更高效的特化实现。（当参数类型实现了移动构造函数时，C++11 版本的std::swap()会使用移动语义提高效率。）
    -std::string可以动态地改变长度，容纳不定长度字符的字符串。它提供了许多操作来操纵字符串。如果只需要比较固定的字符串，那么使用 C 风格的数组或是指向字面字符串的指针以及一个比较函数会更加高效。

提高处理量

提高处理量的目标是减少重复操作的迭代次数，削减重复操作带来的开销。这些策略如下。

  • 向操作系统请求大量输入数据或是或发送大量输出数据，来减少为少量内存块或是独立的数据项调用内核而产生的开销。
  • 在移动缓存或是清除缓存时，不要以字节为单位，而要以字或是长字为单位。这项优化仅在两块内存对齐至相同大小的边界时才能改善性能。
  • 以字或是长字来比较字符串。这项优化仅适用于大端计算机，不适用于小端的 x86 架构计算机。
  • 在唤醒线程时执行更多的工作。在唤醒线程后，不要只让处理器执行一个工作单元后就放弃它，应当让它处理多个工作单元。这样可以节省重复唤醒线程的开销。
  • 不要在每次循环中都执行维护任务，而应当每循环10次或是100次再执行一次维护任务。

提示

使用提示来减少计算量，可以达到减少单个操作的开销的目的。

例如，std::map中有一个重载的insert()成员函数，它有一个表示最优插入位置的可选参数。最优提示可以使插入操作的时间开销变为 O(1)，而不使用最优提示时的时间开销则是 O(log2n)。

优化期待路径

在有多个 else-if 分支的 if-then-else 代码块中，如果条件语句的编写顺序是随机的，那么每次执行经过 if-then-else 代码块时，都有大约一半的条件语句会被测试。如果有一种情况的发生几率是 95%，而且首先对它进行条件测试，那么在 95% 的情况下都只会执行一次测试。

散列法

大型数据结构或长字符串会被一种算法处理为一个称为散列值的整数值。通过比较两个输入数据的散列值，可以高效地判断出它们是否相等。如果散列值不同，那么这两个数据绝对不相等。如果散列值相等，那么输入数据可能相等。散列法可与双重检查一起使用，以优化条件判断处理的性能。通常，输入数据的散列值都会被缓存起来，这样就无需重复地计算散列值。

双重检查

双重检查是指首先使用一种开销不大的检查来排除部分可能性，然后在必要时再使用一个开销很大的检查来测试剩余的可能性。举例如下。

  • 双重检查常与缓存同时使用。当处理器需要某个值时，首先会去检查该值是否在缓存中，如果不在，则从内存中获取该值或是通过一项开销大的计算来得到该值。
  • 当比较两个字符串是否相等时，通常需要对字符串中的字符逐一进行比较。不过，首先比较这两个字符串的长度可以很快地排除它们不相等的情况。
  • 双重检查可以用于散列法中。首先比较两个输入数据的散列值，可以高效地判断它们是否不相等。如果散列值不同，那么它们肯定不相等。

优化动态分配内存的变量

C++变量回顾

变量的存储期

每个变量都有它的存储期，也称为生命周期。只有在这段时间内，变量所占用的存储空间或者内存字节中的值才是有意义的。为变量分配内存的开销取决于存储期。

具有静态存储期的变量被分配在编译器预留的内存空间中。在程序编译时，编译器会为每个静态变量分配一个固定位置和固定大小的内存空间。静态变量的内存空间在程序的整个生命周期内都会被一直保留。所有的全局静态变量都会在程序执行进入main()前被构建，在退出main()之后被销毁。在函数内声明的静态变量则会在“程序执行第一次进入函数前”被构建，这表示它可能会和全局静态变量同时被构建，也可能直到第一次调用该函数时才会被构建。C++ 为全局静态变量指定了构建和销毁的顺序，因此开发人员可以准确地知道它们的生命周期。

为静态变量创建存储空间是没有运行时开销的。不过，我们无法再利用这段存储空间。因此，静态变量适用于那些在整个程序的生命周期内都会被使用数据。在命名空间作用域内定义的变量以及被声明为 static 或是 extern 的变量具有静态存储期。

自 C++11 开始， 程序可以声明具有线程局部存储期的变量。自 C++11 开始，用thread_local存储类型指示符关键字声明的变量具有线程局部存储期。

具有自动存储期的变量被分配在编译器在函数调用栈上预留的内存空间中。在编译时，编译器会计算出距离栈指针的偏移量，自动变量会以该偏移量为起点，占用一段固定大小的内存，但是自动变量的绝对地址直到程序执行进入变量的作用域内才会确定下来。在程序执行于大括号括起来的代码块内的这段时间，自动变量是一直存在的。当程序运行至声明自动变量的位置时，会构建自动变量；当程序离开大括号括起来的代码块时，自动变量将会被析构。

与静态变量一样，为自动变量分配存储空间不会发生运行时开销。但与静态变量不同的是，自动变量每次可以占用的总的存储空间是有限的。当递归不收敛或是发生深度函数嵌套调用导致自动变量占用的存储空间大小超出这个最大值时，会发生栈溢出，导致程序会突然终止。自动变量适合于那些只在代码块附近被使用的对象。

具有动态存储期的变量被保存在程序请求的内存中。程序会调用内存管理器，即 C++运行时系统函数和代表程序管理内存的数据结构的集合。程序会在 new 表达式中显式地为动态变量请求存储空间并构建动态变量，这可能会发生在程序中的任何一处地方。稍后，程序在 delete 表达式中显式地析构动态变量，并将变量所占用的内存返回给内存管理器。

与静态变量不同的是，动态变量的地址是在运行时确定的。不同于静态变量、线程局部变量和自动变量的是，数组的声明语法被扩展了，这样可以在运行时通过一个（非常量）表达式来指定动态数组变量的最高维度。在 C++ 中，这是唯一一种在编译时变量所占用的内存大小不固定的情况。

变量的所有权

C++ 变量的另一个重要概念是所有权。变量的所有者决定了变量什么时候会被创建，什么时候会被析构。有时，存储期会决定变量什么时候会被创建，什么时候会被析构，但所有权是另外一个单独的概念，而且是对优化动态变量而言非常重要的概念。下面是一些指导原则。

  • 全局所有权
    • 具有静态存储期的变量整体上被程序所有。程序会在进入main()前构建它们，并在从main()返回后销毁它们。
  • 词法作用域所有权
    • 具有自动存储期的变量被一段由大括号括起来的代码块构成的词法作用域所拥有。在程序进入词法作用域时会被构建，在程序退出词法作用域时会被销毁。
  • 成员所有权
    • 类和结构体的成员变量由定义它们的类实例所有。当类的实例被构建时，它们会被类的构造函数构建；当类的实例被销毁时，它们也会随之被销毁。
  • 动态变量所有权
    • 动态变量没有预定义的所有者。取而代之， new 表达式创建动态变量并返回一个必须由程序显式管理的指针。动态变量必须在最后一个指向它的指针被销毁之前，通过delete 表达式返回给内存管理器销毁。

C++动态变量API回顾

使用智能指针实现动态变量所有权的自动化

我们可以设计一个仅仅用于拥有动态变量的简单的类。除了构造和销毁动态变量外，还让这个类实现operator->()运算符和operator*()运算符。这样的类称为智能指针，因为不仅它的行为几乎与 C 风格的指针一样，当它被销毁时还能够销毁它所指向的动态对象。C++ 提供了一个称为std::unique_ptr<T>的智能指针模板来维护 T 类型的动态变量的所有权。相比于自己编写代码实现的智能指针，unique_ptr被编译后产生的代码更加高效。

动态变量所有权的自动化

智能指针会通过耦合动态变量的生命周期与拥有该动态变量的智能指针的生命周期，来实现动态变量所有权的自动化。动态变量将会被正确地销毁，其所占用的内存也会被自动地释放，这些取决于指针的声明。

  • 当程序执行超出智能指针实例所属的作用域时，具有自动存储期的智能指针实例会删除它所拥有的动态变量。
  • 声明为类的成员函数的智能指针实例在类被销毁时会删除它所拥有的动态变量。由于类的析构规则决定了在类的析构函数执行后，所有成员变量都会被销毁，因此没有必要再显式地在析构函数中编写销毁动态变量的代码。智能指针会被 C++ 的内建机制所删除。
  • 当线程正常终止时（通常不包括操作系统终止线程的情况），具有线程局部存储期的智能指针实例会删除它所拥有的动态变量。
  • 当程序结束时，具有静态存储期的智能指针实例会删除它所拥有的动态变量。

在通常情况下维护一个所有者，在特殊情况下使用std::unique_ptr维护所有权，这样可以更加容易地判断一个动态变量是否指向一块有效的内存地址，以及当不再需要它时它是否会被正确地返回给内存管理器。

共享动态变量的所有权的开销更大

C++ 标准库模板std::shared_ptr<T>提供了一个智能指针，可以在所有权被共享时管理被共享的所有权的。shared_ptr的实例包含一个指向动态变量的指针和另一个指向含有引用计数的动态对象的指针。当一个动态变量被赋值给shared_ptr时，赋值运算符会创建引用计数对象并将引用计数设置为 1。当一个shared_ptr被赋值给另一个shared_ptr时，引用计数会增加。当shared_ptr被销毁后，析构函数会减小引用计数；如果此时引用计数变为了 0，还会删除动态变量。

由于在引用计数上会发生性能开销昂贵的原子性的加减运算，因此shared_ptr可以工作于多线程程序中。std::shared_ptr也因此比 C 风格指针和std::unique_ptr的开销更大。

std::auto_ptr与容器类

在 C++11 之前， 有一个称为std::auto_ptr<T>的智能指针，它也能够管理动态变量未共享的所有权。auto_ptr与unique_ptr在许多方面十分相似。C++11 之前的绝大多数标准库容器都会通过复制构造函数将它们的值类型复制到容器内部的存储空间中，因此auto_ptr无法被用作值类型。

减少动态变量的使用

使用静态数据结构

std::string、std::vector、std::map和std::list是 C++ 程序员几乎每天必用的容器。只要使用得当，它们的效率还是比较高的。但它们并非是唯一选择。当向容器中添加新的元素时，std::string和std::vector偶尔会重新分配它们的存储空间。std::map和std::list会为每个新添加的元素分配一个新节点。有时，这种开销非常昂贵。

用std::array替代std::vector

std::vector允许程序定义任意类型的动态大小的数组。如果在编译时能够知道数组的大小，或是最大的大小，那么可以使用与std::vector具有类似接口，但数组大小固定且不会调用内存管理器的std::array。std::array支持复制构造，且提供了标准库风格的随机访问迭代器和下标运算符[]。size()函数会返回数组的固定大小。

在栈上创建大块缓冲区

担心可能会发生局部数组溢出的谨慎的开发人员，可以先检查参数字符串或是数组的长度，如果发现参数长度大于局部数组变量的长度了，那么就使用动态构建的数组。为什么这种复制的速度比使用std::string等动态数据结构要快呢？其中一个原因是变值操作通常会复制输入数据。另一个原因则是，相比于为中间结果分配动态存储空间的开销，在桌面级硬件上复制上千字节的开销更小。

静态地创建链式数据结构

可以使用静态初始化的方式构建具有链式数据结构的数据。在这个例子中，这棵树是一棵二分查找树，节点在一个广度优先（breadth-first）顺序的数组中，其中第一个节点是根节点：

1
2
3
4
5
6
7
8
9
10
11
12
struct treenode {
    char const* name;
    treenode* left;
    treenode* right;
} tree[] = {
    { "D", &tree[1], &tree[2] }
    { "B", &tree[3], &tree[4] },
    { "F", &tree[5], nullptr},
    { "A", nullptr, nullptr},
    { "C", nullptr, nullptr},
    { "E", nullptr, nullptr},
};

这段代码之所以能够正常工作，是因为数组元素的地址是常量表达式。我们可以使用这种标记法定义任何链式结构，但是这种初始化方法难以记住，所以在构建这种结构时很容易出现编码错误。

另外一种静态地创建链式结构的方法是为结构中的每个元素都初始化一个变量。这种方式非常容易记忆，但是它的缺点是必须特别声明前向引用（就像下面示例代码中从第四个节点前向引用到第一个节点这样）。声明这种结构的最自然的方法（第一个节点、第二个节点、第三个节点、第四个节点的顺序）需要将这四个变量都声明为 extern。之所以我在下面的代码片段中反过来定义它们，是因为这样可以使得大多数引用都指向已经定义的变量：

1
2
3
4
5
6
7
8
9
struct cyclenode {
    char const* name;
    cyclenode* next;
}
extern cyclenode first; // 前向引用
cyclenode fourth = { "4", &first );
cyclenode third = { "3", &fourth };
cyclenode second = { "2", &third };
cyclenode first = { "1", &second };

在数组中创建二叉树

在数组中构建二叉树，然后不在节点中保存子节点的链接，而是利用节点的数组索引来计算子节点的数组索引。如果节点的索引是 i，那么它的两个子节点的索引分别是 2i 和 2i+1。这种方法带来的另外一个好处是，能够很快地知道父节点的索引是 i/2。由于这些乘法和除法运算在代码中可以实现为左位移和右位移，因此即使在处理能力非常差的处理器上这些计算也不会太慢。

以数组方式实现的树中的节点需要一种机制来判断它们的左节点和右节点是否有效，或是它们是否等于空指针。如果树是左平衡的，那么用一个整数值保存第一个无效节点的数组索引就足够了。

这些特性——能够计算子节点和父节点的能力以及左平衡树所表现出的高效——使得对于堆数据结构而言，在数组中构建树是一种高效的实现方法。

对于平衡二叉树而言，数组形式的树可能会比链式树低效。有些平衡算法保存一棵有 n 个节点的树可能需要 2n 长度的数组。而且，一次平衡操作需要复制节点到不同的数组位置中，而不仅仅是更新指针。在更加小型的处理器上，对有很多节点的树进行处理时，这种复制操作的开销可能非常大。但是，如果节点的大小小于三个指针时，数组形式的树可能会在性能上领先。

用环形缓冲区替代双端队列

std::deque和std::list经常被用于 FIFO（first-in-first-out，先进先出）缓冲区，以至于在标准库中有一个称为std::queue的容器适配器。其实，还可以在环形缓冲区上实现双端队列。环形缓冲区是一个数组型的数据结构，其中，队列的首尾两端由两个数组索引对数组的长度取模给定。环形缓冲区与双端队列有着相似的特性，包括都有时间开销为常量时间的push_back()和pop_front()以及随机访问迭代器。不过，只要缓冲区消费者跟得上缓冲区生产者，环形缓冲区就无需重新分配内存。

使用std::make_shared替代new表达式

像std::shared_ptr这样的共享指针实际上了包含了两个指针，一个指针指向std::shared_ptr所指向的对象；另一个指针指向一个动态变量，该变量保存了被所有指向该对象的std::shared_ptr所共享的引用计数。因此，下面这条语句：

1
std::shared_ptr<MyClass> p(new MyClass("hello", 123));

会调用两次内存管理器：第一次用于创建MyClass的实例，第二次用于创建被隐藏起来的引用计数对象。

在 C++11 之前，分配引用计数器的开销是添加侵入式引用计数作为 MyClass 的基类，然后创建一个自定义的智能指针使用该侵入式引用计数。

1
custom_shared_ptr<RCClass> p(new RCClass("Goodbye", 999));

C++ 标准库的编写者在了解到了开发人员的这种痛苦后，编写了一个称为std::make_shared()的模板函数，这个函数可以分配一块独立的内存来同时保存引用计数和MyClass的一个实例。std::shared_ptr还有一个删除器函数，它知道被共享的指针是以这两种方式中的哪一种被创建的。make_shared()的使用方法很简单：

1
std::shared_ptr<MyClass> p = std::make_shared<MyClass>("hello", 123);

也可以使用更简单的 C++11 风格的声明：

1
auto p = std::make_shared<MyClass>("hello", 123);

不要无谓地共享所有权

多个std::shared_ptr实例可以共享一个动态变量的所有权。当各个指针的生命周期会不可预测地发生重叠时，shared_ptr非常有用。但它的开销也很昂贵。增加和减少shared_ptr中的引用计数并不是执行一个简单的增量指令，而是使用完整的内存屏障进行一次非常昂贵的原子性增加操作，这样shared_ptr才能工作于多线程程序中。

如果一个shared_ptr的生命周期完全地包含了另一个shared_ptr的生命周期，那么第二个shared_ptr的开销是无谓的。下面的代码描述了一种经常发生的场景：

1
2
3
4
void fiddle(std::shared_ptr<Foo> f);
...
shared_ptr<Foo> myFoo = make_shared<Foo>();
fiddle(myFoo);

myFoo拥有动态变量的实例Foo。当程序调用fiddle()时，会创建第二个指向动态FOO实例的链接，并增加shared_ptr的引用计数。当fiddle()返回时，shared_ptr参数会释放它对动态FOO实例的所有权，但调用方仍然拥有指针。这次调用的最小开销是一次无谓的原子性增加和减小操作，而且这两次操作都带有完整的内存屏障。在一次函数调用过程中，这种开销微不足道。将传递给fiddle()的参数改为一个普通指针可以避免这种开销：

1
2
3
4
5
void fiddle(Foo* f);
...
shared_ptr<Foo> myFoo = make_shared<Foo>();
...
fiddle(myFoo.get());

使用“主指针”拥有动态变量

经常出现的一种情况是，一个单独的数据结构在它的整个生命周期内拥有动态变量。指向动态变量的引用或是指针可能会被传递给函数和被函数返回，或是被赋值给变量，等等。但是在这些引用中，没有哪个的寿命比“主引用”长。如果存在主引用，那么我们可以使用std::unique_ptr高效地实现它。然后，我们可以在函数调用过程中，用普通的 C 风格的指针或是 C++ 引用来引用该对象。如果在程序中贯彻了这种方针，那么普通指针和引用就会被记录为“无主”指针。

减少动态变量的重新分配

预分配动态变量以防止重新分配

随着在std::string或是std::vector上数据的增加，它内部的动态分配的存储空间终究会枯竭。下一个添加操作会导致需要分配更大的存储空间，以及将旧的数据复制到新存储空间中。对内存管理器的调用以及复制操作将会多次访问内存并消耗很多指令。诚然，添加操作的时间开销是 O(1)，但是比例常量（即常量时间是多少毫秒）可能会非常大。

string 和vector都有成员函数reserve(size_t n)，调用该函数会告诉 string 或是vector请确保至少有存储 n 个元素的空间。如果可以事先计算或是预估出这个大小，那么调用reserve()为 string 或是vector预留足够的内部存储空间，可以避免出现它们到达增长极限后需要重新分配存储空间的情况：

1
2
3
4
5
std::string errmsg;
errmsg.reserve(100); // 下面这些字符串连接操作中只会发生一次内存分配
errmsg += "Error 1234: variable ";
errmsg += varname;
errmsg += " was used before set. Undefined behavior.";

调用reserve()如同是对 string 或是vector的一种提示。与分配最差情况下的静态缓存不同的是，即使过小地估计了预留的容量，惩罚也不过是额外的重新分配。而即使过大地估计了预留的容量，只要 string 或是vector会在短暂地使用后被销毁，就都没有问题。在使用reserve()预分配 string 或是vector后，还可以使用std::string或是std::vector的shrink_to_fit()成员函数将未使用的空间返回给内存管理器。

在循环外创建动态变量

在下面这段代码中，循环虽小，问题却大。这段程序会将 namelist 中的每个文件中的每行都添加到std::string类型的变量 config 中，接着再从 config 中抽出一小部分数据。问题出在每次循环中都会创建 config，并且在每次循环内部，随着 config 的不断增大，都会重新分配内存。接着，在循环末尾离开了它的作用域后， config 将会被销毁，它的存储空间会被返回给内存管理器：

1
2
3
4
5
for (auto& filename : namelist) {
    std::string config;
    ReadFileXML(filename, config);
    ProcessXML(config);
}

提高这段循环的性能的一种方法是将 config 的声明移至循环外部。在每次循环中，都先清除该变量。不过，clear()函数并不会释放 config 内部的动态缓冲区，它只是将config 的内容的长度设置为 0。从第二次循环开始，只要接下来的文件没有比第一次循环中使用的文件大很多，就不会重新分配内存：

1
2
3
4
5
6
std::string config;
for (auto& filename : namelist) {
    config.clear();
    ReadFileXML(filename, config);
    ProcessXML(config);
}

移除无谓的复制

在 C++ 中，存在着看似简单，但其实并不高效的赋值语句。如果 a 和 b 都是BigClass类的实例，那么赋值语句a = b;会调用BigClass的赋值运算符成员函数。赋值运算符可以只是简单地将 b 的字段全部复制到 a 中去。但是问题在于这个函数可能会做任何C++ 函数都会做的事情。BigClass可能有很多字段需要复制。如果BigClass中有动态变量，复制它们可能会引发对调用内存管理器的调用。如果BigClass中有一个保存有数百万元素的std::map或是一个保存有数百万字符的字符数组，那么赋值语句的开销会非常大。

在 C++ 中，如果Foo是一个类，初始化声明Foo a = b;可能会调用一个称为复制构造函数的成员函数。复制构造函数和赋值运算符是两个紧密相关的成员函数，它们所做的事情几乎相同：将一个类实例中的字段复制到另一个类实例中去。而且与赋值运算符一样，复制构造函数的开销是没有上限的。

复制可能会发生于以下任何一种情况下：

  • 初始化（调用构造函数）
  • 赋值（调用赋值运算符）
  • 函数参数（每个参数表达式都会被移动构造函数或复制构造函数复制到形参中）
  • 函数返回（调用移动构造函数或复制构造函数，甚至可能会调用两次）
  • 插入一个元素到标准库容器中（会调用移动构造函数或复制构造函数复制元素）
  • 插入一个元素到vector中（如果需要重新为vector分配内存，那么所有的元素都会通过移动构造函数或复制构造函数复制到新的vector中）

在类定义中禁止不希望发生的复制

许多具有实体行为的对象都会有一些状态。如果程序不经意地将实体复制到了一个会检查该实体状态的函数中，虽然在功能上是没有问题的，但是运行时开销会非常大。

如果复制类实例过于昂贵或是不希望这么做，那么一种可以有效地避免发生这种昂贵开销的方法就是禁止复制。将复制构造函数和赋值运算符的可见性声明为 private 可以防止它们被外部调用。既然它们无法被调用，那么也就不需要任何定义，只需要声明就足够了。例如：

1
2
3
4
5
6
7
8
// 在C++11之前禁止复制的方法
class BigClass {
private:
    BigClass(BigClass const&);
    BigClass& operator=(BigClass const&);
public:
...
};

在 C++11 中，我们可以在复制构造函数和赋值运算符后面加上delete关键字来达到这个目的。将带有delete关键字的复制构造函数的可见性设为 public 更好，因为在这种情况下调用复制构造函数的话，编译器会报告出明确的错误消息：

1
2
3
4
5
6
7
// 在C++11中禁止复制的方法
class BigClass {
public:
    BigClass(BigClass const&) = delete;
    BigClass& operator=(BigClass const&) = delete;
...
};

任何企图对以这种方式声明的类的实例赋值——或通过传值方式传递给函数，或通过传值方式返回，或是将它用作标准库容器的值时——都会导致发生编译错误。

但是还可以用指向该类的指针和引用来赋值或初始化变量，或是在函数中传递和返回指向该类实例的引用或指针。从性能优化的角度看，使用指针或引用进行赋值和参数传递，或是返回指针或引用更加高效，因为指针或引用是存储在寄存器中的。

移除函数调用上的复制

当程序调用函数时，会计算每个参数表达式，并以相对应的参数表达式的值作为初始化器创建每个形参。“创建”意味着会调用形参的构造函数。当形参是诸如 int、 double 或是char*等基本类型时，由于基本类型的构造函数是概念上的而非实际的函数，因此程序只会简单地将值复制到形参的存储空间中。

但是当形参是某个类的实例时，程序将调用这个类的复制构造函数之一来初始化实例。通常情况下，复制构造函数都是一个实际的函数。请考虑以下示例代码：

1
2
3
4
5
6
int Sum(std::list<int> v) {
    int sum = 0;
    for (auto it : v)
        sum += *it;
    return sum;
}

当调用这里展示的Sum()函数时，实参是一个链表：例如，int total = Sum(MyList);。形参v也是一个链表。v是通过一个接收链表作为参数的构造函数创建的。它就是复制构造函数。std::list的复制构造函数会为链表中所有的元素创建一份副本。如果MyList总是只有几个元素，那么这个开销尽管没有必要，但是依然可以忍受。但是随着MyList变大，这个开销将会降低程序性能。如果它有 1000 个元素，那么内存管理器会被调用 1000 次。在函数最后，形参v会超出它的作用域，其中的 1000 个元素也会被逐一返回给不会再被使用的链表。

为了避免这种开销，我们可以将形参定义为带有平凡（trivial）构造函数的类型。为了将类实例传递给函数，指针和引用具有普通构造函数。例如，在之前的例子中，我们可以将v定义为std::list<int> const&。接着，该引用会被指向实参的引用初始化，而不会使用复制构造函数初始化类的实例。引用通常被实现为指针。

当一个类和标准库容器一起使用时，通过复制构造函数创建它的实例可能会调用内存管理器来复制它内部的数据，而传递指向类实例的引用可以改善程序性能。通过引用访问实例也会产生开销：每次访问实例时，都必须解引实现该引用的指针。如果函数很大，而且在函数体中多次使用了参数值，那么连续地解引引用的开销会超过所节省下来的复制开销，导致性能改善收益递减。但是对于小型函数，除了特别小的类以外，通过引用传递参数总是能获得更好的性能。

引用参数的行为与值参数并不完全相同。引用参数在函数内部发生改变会导致它所引用的实例也发生改变，但是值参数在函数内部发生改变却不会对函数外的值造成任何影响。将引用参数声明为常量引用可以防止不小心修改所引用的实例。

引用参数还会引入别名，这会导致不曾预料到的影响。也就是说，如果函数签名是：

1
void func(Foo& a, Foo& b);

函数调用func(x,x);引入了一个别名。如果func()更新了 a，那么你会发现 b 突然也被更新了。

移除函数返回上的复制

如果函数返回一个值，那么这个值会被复制构造到一个未命名的与函数返回值类型相同的临时变量中。对于 long、 double 或指针等基本类型会进行默认的复制构造，而当变量是类时，复制构造通常都会发生实际的函数调用。类越大越复杂，复制构造函数的时间开销也越大。下面来看一个例子：

1
2
3
4
5
6
7
std::vector<int> scalar_product(std::vector<int> const& v, int c) {
    std::vector<int> result;
    result.reserve(v.size());
    for (auto val : v)
        result.push_back(val * c);
    return result;
}

在有些情况下，通过返回引用而不是返回已经创建的返回值，可以避免发生复制构造开销。不幸的是，如果在函数内计算出返回值后，将其赋值给了一个具有自动存储期的变量，那么这个技巧将无法适用。当函数返回后，这个变量将超出它的作用域，导致悬挂引用将会指向一块堆内存尾部的未知字节，而且该区域通常都会很快被其他数据覆盖。更糟糕的是，函数计算返回结果是很普遍的情况，所以多数函数都会返回值，而非引用。

就像返回值的复制构造的开销并不算太糟糕，调用方常常会像auto res =scalar_product(argarray, 10);这样将函数返回值赋值给一个变量。因此，除了在函数内部调用复制构造外，在调用方还会调用复制构造函数或赋值运算符。C++ 编译器找到了一种移除额外的复制构造函数调用的方法。这种优化方法被称为复制省略（copy elision）或是返回值优化（return value optimization，RVO）。函数必须返回一个局部对象。编译器必须能够确定在所有的控制路径上返回的都是相同的对象。返回对象的类型必须与所声明的函数返回值的类型相同。最简单的情况是，如果一个函数非常短小，并且只有一条控制路径，那么编译器进行 RVO 的可能性非常大。如果函数比较庞大，或是控制路径有很多分支，那么编译器将难以确定是否可以进行 RVO。当然，各种编译器的分析能力也是不同的。

有一种方法可以移除函数内部的类实例的构造以及从函数返回时发生的两次复制构造（或是等价于复制构造函数的赋值运算符）。这需要开发人员手动编码实现，所以其结果肯定比寄希望于编译器在给定的情况下进行 RVO 要好。这种方法就是不用 return 语句返回值，而是在函数内更新引用参数，然后通过输出参数返回该引用参数：

1
2
3
4
5
6
7
8
9
void scalar_product(
    std::vector<int> const& v,
    int c,
    vector<int>& result) {
        result.clear();
        result.reserve(v.size());
        for (auto val : v)
            result.push_back(val * c);
}

这里，我们在函数参数列表中加入了一个称为 result 的输出参数。这种机制有以下几个优点。

  • 当函数被调用时，该对象已经被构建。有时，该对象必须被清除或是重新初始化，但是这些操作不太可能比构造操作的开销更大。
  • 在函数内被更新的对象无需在 return 语句中被复制到未命名的临时变量中。
  • 由于实际数据通过参数返回了，因此函数的返回类型可以是 void，也可以用来返回状态或是错误信息。
  • 由于在函数中被更新的对象已经与调用方中的某个名字绑定在了一起，因此当函数返回时不再需要复制或是赋值。

当在程序中多次调用一个函数时，许多数据结构（如字符串、矢量和散列表）都有一个可复用的动态分配的骨干数组。有时，函数的结果必须保存在调用方中，但是这种开销永远不会比当函数通过值返回类的实例时调用复制构造函数的开销大。

这种机制会产生额外的运行时开销，例如额外的参数开销吗？其实并不会。编译器在处理返回实例的函数时，会将其转换为一种带有额外参数的形式。这个额外的参数是一个引用，它指向为用于保存函数所返回的未命名的临时变量的未初始化的存储空间。在 C++ 中有一种情况只能通过值返回对象：运算符函数。当开发人员在编写矩阵计算函数时，如果希望使用通用的运算符A = B * C;，就无法使用引用参数。在实现运算符函数时必须格外小心，确保它们会使用 RVO 和移动语义，这样才能实现最高效率。

免复制库

当需要填充的缓冲区、结构体或其他数据结构是函数参数时，传递引用穿越多层库调用的开销很小。这种模式出现在了许多性能需求严格的函数库中。例如， C++ 标准库istream::read()成员函数的签名如下：

1
istream& read(char* s, streamsize n);

这个函数会读取 n 个字节的内容到 s 所指向的存储空间中。这段缓冲区是一个输出参数，因此要读取的数据不会被复制到新分配的存储空间中。由于 s 是一个参数，istream::read()可以将返回值用于其他用途。在本例中，函数将this指针作为引用返回。但是istream::read()自身并不会从操作系统内核获取数据。它会调用另外一个函数。在某些实现方式下，它可能会调用 C 的库函数fread()。fread()的函数签名如下：

1
size_t fread(void* ptr, size_t size, size_t nmemb, FILE* stream);

fread()会读取size*nmemb个字节的数据并将它们存储在ptr所指向的存储空间中。fread()中的ptr参数与read()中的s相同。但是fread()并不是调用链的终点。在 Linux 上，fread()会调用标准 Unix 函数read()；

实现写时复制惯用法

写时复制（copy on write， COW）用于高效地复制那些含有复制开销昂贵的动态变量的类实例。通常来说，当一个带有动态变量的对象被复制时，也必须复制该动态变量。这种复制被称为深复制。通过复制指针，而不是复制指针指向的变量得到包含无主指针的对象的副本，这种复制被称为浅复制。

写时复制的核心思想是，在其中一个副本被修改之前，一个对象的两个副本一直都是相同的。因此，直到其中一个实例或另外一个实例被修改，两个实例能够共享那些指向复制开销昂贵的字段的指针。写时复制首先会进行一次“浅复制”，然后将深复制推迟至对象的某个元素发生改变时。

在现代 C++ 的 COW 的实现方式中，任何引用动态变量的类成员都是用如std::shared_ptr这样的具有共享所有权的智能指针实现的。类的构造函数复制具有共享所有权的指针，将动态变量的一份新的复制的创建延迟到任何一份复制想要修改该动态变量时。作用于类上的任何变值操作都会在真正改变类之前先检查共享指针的引用计数。引用计数值大于 1 表明所有权被共享了，那么这个操作会为对象创建一份新的副本，用指向新副本的共享指针交换之前的共享指针成员，并释放旧的副本和减小引用计数。由于已经确保了动态变量没有被共享，现在可以进行变值操作了。

在 COW 类中使用 std::make_shared() 构建动态变量是非常重要的。否则，使用共享指针会发生额外的调用内存管理器来获取引用计数对象的开销。如果在类中有许多动态变量，那么这个开销与简单地将动态变量复制到新的存储空间中并赋值给一个（非共享的）智能指针的开销无异。因此，除非要复制很多份副本，或者变值运算符通常不会被调用，否则COW 惯用法可能不会发挥什么作用。

切割数据结构

切割（slice）是一种编程惯用法，它指的是一个变量指向另外一个变量的一部分。被切割的对象通常都是小的、容易复制的对象，将其内容复制至子数组或子字符串中而分配存储空间的开销不大。如果被分割的数据结构为被共享的指针所有，那么切割是完全安全的。

实现移动语义

移动语义解决了之前版本的 C++ 中反复出现的问题，例子如下。

  • 将一个对象赋值给一个变量时，会导致其内部的内容被复制。而在这之后，原来的对象立即被销毁了。
  • 开发人员希望将一个实体赋值给一个变量。在这个对象中，赋值语句中的“复制”操作是未定义的，因为这个对象具有唯一的识别符。

以上这两种情况对std::vector等动态容器有很大影响，因为伴随着容器中元素数量的增加，容器内部的存储空间必须被重新分配。第一种情况会导致重新分配容器的开销比实际所需更大。第二种情况则会导致 auto_ptr 等实体无法被存储在容器中。

问题的起因在于，复制构造函数和赋值运算符执行的复制操作对于基本类型和无主指针没有问题，但是对于实体则没有意义。拥有这种类型的成员变量的类可以被保存在 C 风格的数组中，但是无法被保存在std::vector等动态容器中。

移动语义的移动部分

为了实现移动语义， C++ 编译器需要能够识别一个变量在什么时候只是临时值。这样的实例是没有名字的。例如，函数返回的对象或 new 表达式的结果就没有名字。不可能会有其他引用指向该对象。该对象可以被初始化、赋值给一个变量或是作为表达式或函数的参数。但是接下来它会立即被销毁。这样的无名值被称为右值，因为它与赋值语句右侧的表达式的结果类似。相反， 左值是指通过变量命名的值。在语句 y = 2x + 1; 中，表达式2x + 1 的结果是一个右值，它是一个没有名字的临时值。等号左侧的变量是一个左值， y是它的名字。

当一个对象是右值时，它的内容可以被转换为左值。所需做的就是保持右值为有效状态，这样它的析构函数就可以正常工作了。C++ 的类型系统被扩展了，它能够从函数调用上的左值中识别出右值。如果 T 是一个类型，那么声明T&&就是指向 T 的右值引用——也就是说，一个指向类型 T 的右值的引用。函数重载的解析规则也被扩展了，这样当右值是一个实参时，优先右值引用重载；而当左值是实参时，则需要左值引用重载。

代码清单 6-3 是一个包含唯一实体的简单的类。编译器会为这个类自动地生成移动构造函数和移动赋值运算符。如果类的成员定义了移动操作，这些移动运算符就会对这些成员进行一次移动操作；如果没有，则进行一次复制操作。这等同于对每个类成员都执行this->member = std::move(rhs.member)。

1
2
3
4
5
6
7
8
9
10
11
12
class Foo {
std::unique_ptr<int> value_;
public:
...
    Foo(Foo&& rhs) {
        value_ = rhs.release();
    }
    Foo(Foo const& rhs) : value_(nullptr) {
        if (rhs.value_)
            value_ = std::make_unique<int*>(*rhs.value_);
    }
};

实际上，编译器只会在当程序没有指定复制构造函数、赋值运算符或是析构函数，而且父类或是任何类成员都没有禁用移动运算符的简单情况下，才会自动生成移动构造函数和移动赋值运算符。这条规则是有意义的，因为这些特殊的函数定义的出现暗示可能需要一些特殊的东西（而不是“成员逐一移动”）。

移动语义的微妙之处

移动语义并非黑科技。这种特性太重要了，而且标准库的实现人员确实做得很棒，让它在语义上与复制构造函数十分相似。但是我认为，可以说移动语义是非常微妙的。这是 C++中必须谨慎使用的特性之一，如果你对它足够了解，你的程序就可以获得极大的性能提升。

移动实例至std::vector

如果你希望你的对象在std::vector中能够高效地移动，那么仅仅编写移动构造函数和移动赋值运算符是不够的。开发人员必须将移动构造函数和移动赋值运算符声明为noexcept。这很有必要，因为std::vector提供了强异常安全保证（strong exception safety guarantee）：当一个 vetcor 执行某个操作时，如果发生了异常，那么该 vetcor 的状态会与执行操作之前一样。复制构造函数并不会改变源对象。移动构造函数则会销毁它。任何在移动构造函数中发生的异常都会与强异常安全保证相冲突。

如果没有将移动构造函数和移动赋值运算符声明为 noexcept，std::vector会使用比较低效的复制构造函数。当发生这种情况时，编译器可能不会给出警告，代码仍然可以正常运行，不过会变慢。noexcept 是一种强承诺。使用 noexcept 意味着不会调用内存管理器、 I/O 或是其他任何可能会抛出异常的函数。同时，它也意味着必须忍受所有异常，因为没有任何办法报告在程序中发生了异常。

右值引用参数是左值

当一个函数接收一个右值引用作为参数时，它会使用右值引用来构建形参。因为形参是有名字的，所以尽管它构建于一个右值引用，它仍然是一个左值。幸运的是，开发人员可以显式地将左值转换为右值引用。如代码所示，标准库提供了漂亮的<utility>中的模板函数std::move()来完成这项任务。

1
2
3
4
5
6
7
8
9
std::string MoveExample(std::string&& s) {
    std::string tmp(std::move(s));
    // 注意！现在s是空的
    return tmp;
}
...
std::string s1 = "hello";
std::string s2 = "everyone";
std::string s3 = MoveExample(s1 + s2);

在代码中，调用MoveExample(s1 + s2)会导致通过右值引用构建 s，这意味着实参被移动到了 s 中。调用std::move(s)会创建一个指向 s 的内容的右值引用。由于右值引用是std::move()的返回值，因此它没有名字。右值引用会初始化tmp，调用std::string的移动构造函数。此时， s 已经不再指向MoveExample()的实参字符串。它可能是一个空字符串。当返回tmp的时候，从概念上讲，tmp的值会被复制到匿名返回值中，接着 tmp 会被删除。

MoveExample()的匿名返回值会被复制构造到s3中。不过，实际上，在这种情况下编译器能够进行 RVO，这样参数s会被直接移动到s3的存储空间中。通常， RVO 比移动更高效。下面是一个使用了std::move()的移动语义版本的std::swap()：

1
2
3
4
5
6
template <typename T> void std::swap(T& a, T& b) {
{
    T tmp(std::move(a));
    a = std::move(b);
    b = std::move(tmp);
}

只要 T 实现了移动语义，这个函数就会执行三次移动，且不会进重新分配。否则，它会进行复制构造。

不要返回右值引用

移动语义的另外一个微妙之处在于不应当定义函数返回右值引用。直觉上，返回右值引用是合理的。在像x = foo(y)这样的函数调用中，返回右值引用会高效地将返回值从未命名的临时变量中复制到赋值目标 x 中。

但是实际上，返回右值引用会妨碍返回值优化，即允许编译器向函数传递一个指向目标的引用作为隐藏参数，来移除从未命名的临时变量到目标的复制。返回右值引用会执行两次移动操作，而一旦使用了返回值优化，返回一个值则只会执行一次移动操作。因此，只要可以使用 RVO，无论是返回语句中的实参还是函数的返回类型，都不应当使用右值引用。

移动父类和类成员

正如代码所示，要想为一个类实现移动语义，你必须为所有的父类和类成员也实现移动语义。否则，父类和类成员将会被复制，而不会被移动。

1
2
3
4
5
6
7
8
9
10
11
12
class Base {...};
class Derived : Base {
...
    std::unique_ptr<Foo> member_;
    Bar* barmember_;
};
Derived::Derived(Derived&& rhs)
: Base(std::move(rhs)),
member_(std::move(rhs.member_)),
barmember_(nullptr) {
    std::swap(this->barmember_, rhs.barmember_);
}

代码展示了一个编写移动构造函数的微妙之处。假设 Base 有移动构造函数，那么它只有在通过调用std::move()将左值rhs转换为右值引用后才会被调用。同样，只有当rhs.member_被转换为右值引用后才会调用std::unique_ptr的移动构造函数。而对于普通指针barmember_或其他任何没有定义移动构造函数的对象，std::swap()实现了一个类似移动的操作。

在实现移动赋值运算符时，std::swap()可能会引起麻烦。麻烦在于this可能会指向一个已经分配了内存的对象。std::swap()不会销毁那些不再需要的内存。它会将它们保存在rhs中，直至rhs被销毁前这块内存都无法被重新利用。如果在一个类成员中有一个含有100 万个字符的字符串或是包含一张 100 万个元素的表，这可能会是一个潜在的大问题。

在这种情况下，最好先显式地复制barmember_指针，然后在rhs中删除它，以防止rhs的析构函数删除释放它：

1
2
3
4
5
6
void Derived::operator=(Derived&& rhs) {
    Base::operator=(std::move(rhs));
    delete(this->barmember_);
    this->barmember_ = rhs.barmember_;
    rhs.barmember_ = nullptr;
}

扁平数据结构

当一个数据结构中的元素被存储在连续的存储空间中时，我们称这个数据结构为扁平的。相比于通过指针链接在一起的数据结构，扁平数据结构具有显著的性能优势。

  • 相比于通过指针链接在一起的数据结构，创建扁平数据结构实例时调用内存管理器的开销更小。有些数据结构（如 list、 deque、 map、 unordered_map）会创建许多动态变量，而其他数据结构（如 vector）则较少。
  • std::array和std::vector等扁平数据结构所需的内存比 list、 map、 unordered_map 等基于节点的数据结构少，因为在基于节点的数据结构中存在着链接指针的开销。即使所消耗的总字节数没有问题，紧凑的数据结构仍然有助于改善缓存局部性。扁平数据结构在局部缓存性上的优势使得它们更加高效。
  • 以前常常需要用到的技巧，诸如用智能指针组成vector或是 map 来存储不可复制的对象，在 C++11 中的移动语义出现后已经不再需要了。移动语义移除了在分配智能指针和它所指向的对象的存储空间时产生的显著的运行时开销。

小结

  • 在 C++ 程序中，乱用动态分配内存的变量是最大的“性能杀手”。当发生性能问题时，new 不再是你的朋友。
  • 只要知道了如何减少对内存管理器的调用，开发人员就能够成为一个高效的性能优化专家。
  • 通过提供::operator new()运算符和::operator delete()运算符，可以整体地改变程序分配内存的方式。
  • 通过替换malloc()和free()可以整体地改变程序管理内存的方式。
  • 智能指针实现了动态变量所有权的自动化。
  • 共享了所有权的动态变量更加昂贵。
  • 静态地创建类实例。
  • 静态地创建类成员并且在有必要时采用两段初始化。
  • 让主指针来拥有动态变量，使用无主指针替代共享所有权。
  • 编写通过输出参数返回值的免复制函数。
  • 实现移动语义。
  • 扁平数据结构更好。

优化热点语句

循环中的语句开销是语句各自的开销乘以它们被重复执行的次数。热点循环必须由开发人员自己找出来。

频繁被调用的函数：函数的开销是函数自身的开销乘以它被执行的次数。分析器可以直接指出热点函数。

从循环中移除代码

一个循环是由两部分组成的：一段被重复执行的控制语句和一个确定需要进行多少次循环的控制分支。通常情况下，移除 C++ 语句中的计算指的是移除循环中的控制语句的计算。不过在循环中，控制分支也有额外的优化机会，因为从某种意义上说，它产生了额外的开销。

1
2
3
4
5
char s[] = "This string has many space (0x20) chars. ";
...
for (size_t i = 0; i < strlen(s); ++i)
    if (s[i] == ' ')
        s[i] = '*';

这段代码对字符串中的每个字符都会判断循环条件i < strlen(s)是否成立 1。调用strlen()的开销是昂贵的，遍历参数字符串对它的字符计数使得这个算法的开销从O(n)变为了O(n^2)。

缓存循环结束条件值

我们可以通过在进入循环时预计算并缓存循环结束条件值，即调用开销昂贵的strlen()的返回值，来提高程序性能。

1
2
3
for (size_t i = 0, len = strlen(s); i < len; ++i)
    if (s[i] == ' ')
        s[i] = '*';

由于strlen()的开销实在是太大了，因此修改后的效果非常明显。

使用更高效的循环语句

粗略地讲， for 循环会被编译为如下代码：

1
2
3
4
5
6
初始化表达式 ;
L1: if ( ! 循环条件 ) goto L2;
    语句 ;
    继续表达式 ;
    goto L1;
L2:

for 循环必须执行两次 jump 指令：一次是当循环条件为 false 时；另一次则是在计算了继续表达式之后。这些 jump 指令可能会降低执行速度。C++ 还有一种使用不那么广泛的、称为 do 的更简单的循环形式，do 循环会被编译为如下代码：

1
2
L1: 控制语句
if ( 循环条件 ) goto L1;

因此，将一个 for 循环简化为 do 循环通常可以提高循环处理的速度。

用递减替代递增

缓存循环结束条件的另一种方法是用递减替代递增，将循环结束条件缓存在循环索引变量中。许多循环都有一种结束条件判断起来比其他结束条件更高效。例如，循环中，一种结束条件是常量 0，而另外一种则是调用开销昂贵的strlen()函数。

1
2
3
for (int i = (int)strlen(s)-1; i >= 0; --i)
    if (s[i] == ' ')
        s[i] = '*';

归纳变量 i 的类型从无符号的size_t变为了有符号的 int。for 循环的结束条件是i >= 0。如果 i 是无符号的，从定义上说，它总是大于或等于 0，那么循环就永远无法结束。在采用递减方式时，这是一个非常典型的错误。

从循环中移除不变性代码

当代码不依赖于循环的归纳变量时，它就具有循环不变性。现代编译器非常善于找出在循环中被重复计算的具有循环不变性的代码，然后将计算移动至循环外部来改善程序性能。开发人员通常没有必要重写这段代码，因为编译器已经替我们找出了具有循环不变性的代码并重写了循环。

当在循环中有语句调用了函数时，编译器可能无法确定函数的返回值是否依赖于循环中的某些变量。被调用的函数可能很复杂，或是函数体包含在另外一个编译器看不到的编译单元中。这时，开发人员必须自己找出具有循环不变性的函数调用并将它们从循环中移除。

从循环中移除无谓的函数调用

一次函数调用可能会执行大量的指令。如果函数具有循环不变性（loop-invariant），那么将它移除到循环外有助于改善性能。在代码清单 7-1 中，strlen()具有循环不变性，因此可以将它到移动到循环外部。

从循环中移除隐含的函数调用

普通的函数调用很容易识别，它们有函数名，在圆括号中有参数表达式列表。C++ 代码还可能会隐式地调用函数，而没有这种很明显的调用语句。当一个变量是以下类型之一时就可能会发生这种情况：

  • 声明一个类实例（调用构造函数）
  • 初始化一个类实例（调用构造函数）
  • 赋值给一个类实例（调用赋值运算符）
  • 涉及类实例的计算表达式（调用运算符成员函数）
  • 退出作用域（调用在作用域中声明的类实例的析构函数）
  • 函数参数（每个参数表达式都会被复制构造到它的形参中）
  • 函数返回一个类的实例（调用复制构造函数，可能是两次）
  • 向标准库容器中插入元素（元素会被移动构造或复制构造）
  • 向矢量中插入元素（如果矢量重新分配了内存，那么所有的元素都需要被移动构造或是复制构造）

这些函数调用被隐藏起来了。你从表面上看不出带有名字和参数列表的函数调用。它们看起来更像赋值和声明。我们很容易误以为这里没有发生函数调用。

如果将函数签名从通过值传递实参修改为传递指向类的引用或指针，有时候可以在进行隐式函数调用时移除形参构建。如果将函数签名修改为通过输出参数返回指向类实例的引用或指针时，可以在进行隐式函数调用时移除函数返回值的复制。

如果赋值语句和初始化声明具有循环不变性，那么我们可以将它们移动到循环外部。有时，即使需要每次都将变量传递到循环中，你也可以将声明移动到循环外部，并在每次循环中都执行一次开销较小的函数调用。例如，std::string是一个含有动态分配内存的字符数组的类。在以下代码中：

1
2
3
4
5
for (...) {
    std::string s("<p>");
    ...
    s += "</p>";
}

在 for 循环中声明 s 的开销是昂贵的。在循环语句块的反大括号的位置将会调用 s 的析构函数，而析构函数会释放为 s 动态分配的内存，因此当下一次进入循环时，一定会重新分配内存。这段代码可以被优化为：

1
2
3
4
5
6
7
std::string s;
for (...) {
    s.clear();
    s += "<p>";
    ...
    s += "</p>";
}

现在，不会再在每次循环中都调用 s 的析构函数了。这不仅仅是在每次循环中都节省了一次函数调用，同时还带来了其他效果——由于 s 内部的动态数组会被复用，因此当向 s 中添加字符时，可能会移除一次对内存管理器的调用。

将循环放入函数以减少调用开销

如果程序要遍历字符串、数组或是其他数据结构，并会在每次迭代中都调用一个函数，那么可以通过一种称为循环倒置（loop inversion）的技巧来提高程序性能。循环倒置是指将在循环中调用函数变为在函数中进行循环。这需要改变函数的接口，不再接收一条元素作为参数，而是接收整个数据结构作为参数。按照这种方式修改后，如果数据结构中包含 n 条元素，那么可以节省 n-1 次函数调用。我们来看一个非常简单的例子。下面这个函数的功能是用点（“.”）替代非打印字符：

1
2
3
4
5
# include <ctype>
void replace_nonprinting(char& c) {
    if (!isprint(c))
        c = '.';
}

当想替换一个字符串中所有的非打印字符时，可以在程序中循环中调用replace_nonprinting()：

1
2
for (unsigned i = 0, e = str.size(); i < e; ++i)
    replace_nonprinting(str[i]);

如果编译器无法对replace_nonprinting()内联展开，那么当需要处理的字符串是“Ring the carriage bell\x07\x07!!”时，它会调用这个函数 26 次。

库的设计者可以重载replace_nonprinting()函数来处理整个字符串：

1
2
3
4
5
void replace_nonprinting(std::string& str) {
    for (unsigned i = 0, e = str.size(); i < e; ++i)
        if (!isprint(str[i]))
        c = '.';
}

现在，循环在函数内部了，这样可以节省 n-1 次对replace_nonprinting()的调用。请注意，必须将replace_nonprinting()的实现代码复制到新的重载函数中。仅仅在新的重载函数的循环中调用之前的函数是没有效果的。下面的版本实际上只是在循环中调用了之前的函数：

1
2
3
4
void replace_nonprinting(std::string& str) {
    for (unsigned i = 0, e = str.size(); i < e; ++i)
        replace_nonprinting(str[i]);
}

从函数中移除代码

与循环一样，函数也包含两部分：一部分是由一段代码组成的函数体，另一部分是由参数列表和返回值类型组成的函数头。与优化循环一样，这两部分也可以独立优化。尽管执行函数体的开销可能会非常大，但是调用函数的开销与调用大多数 C++ 语句的开销一样，是非常小的。不过，当函数被多次调用时，累积的开销可能会变得巨大，因此减少这种开销非常重要。

函数调用的开销

函数是编程中最古老和最重要的抽象概念。程序员先定义一个函数，接着就可以在代码中的其他地方调用这个函数。每次调用时，计算机都会在执行代码中保存它的位置，将控制权交给函数体，接着会返回到函数调用后的下一条语句，高效地将函数体插入到指令执行流中。

这种便利性可不是免费的。每次程序调用一个函数时，都会发生类似下面这样的处理（依赖于处理器体系结构和优化器设置）。

  1. 执行代码将一个栈帧推入到调用栈中来保存函数的参数和局部变量。
  2. 计算每个参数表达式并复制到栈帧中。
  3. 执行地址被复制到栈帧中并生成返回地址。
  4. 执行代码将执行地址更新为函数体的第一条语句（而不是函数调用后的下一条语句）。
  5. 执行函数体中的指令。
  6. 返回地址被从栈帧中复制到指令地址中，将控制权交给函数调用后的语句。
  7. 栈帧被从栈中弹出。

不过，关于函数开销也有一些好消息。带有函数的程序通常都会比带有被内联展开的大型函数的程序更加紧凑。这有利于提高缓存和虚拟内存的性能。而且，函数调用与非函数调用的其他开销都相同，这使得提高会被频繁地调用的函数的性能成为了一种有效的优化手段。

函数调用的基本开销

有许多细节问题都会降低 C++ 中函数调用的速度，这些问题也构成了函数调用优化的基础。

函数参数：除了计算参数表达式的开销外，复制每个参数的值到栈中也会发生开销。如果只有几个小型的参数，那么可能可以很高效地将它们传递到寄存器中；但是如果有很多参数，那么至少其中一部分需要通过栈传递。

成员函数调用（与函数调用）：每个成员函数都有一个额外的隐藏参数：一个指向 this 类实例的指针，而成员函数正是通过它被调用的。这个指针必须被写入到调用栈上的内存中或是保存在寄存器中。

调用和返回：调用和返回对程序的功能没有任何影响。我们可以通过用函数体替代函数调用来移除这些开销。的确，当函数很小且在函数被调用之前已经定义了函数时，许多编译器都会试图内联函数体。如果不能内联函数，调用和返回就会产生开销。调用函数要求执行地址被写入到栈帧中来生成返回地址。

虚函数的开销

每个带有虚成员函数的实例都有一个无名指针指向一张称为虚函数表（vtable） 的表，这张表指向类中可见的每个虚函数签名所关联的函数体。虚函数表指针通常都是类实例的第一个字段，这样解引时的开销更小。

由于虚函数调用会从多个函数体中选择一个执行，调用虚函数的代码会解引指向类实例的指针，来获得指向虚函数表的指针。这段代码会为虚函数表加上索引（也就是说，代码会在虚函数表上加上一段小的整数偏移量并解引该地址）来得到函数的执行地址。因此，实际上这里会为所有的虚函数调用额外地加载两次非连续的内存，每次都会增加高速缓存未命中的几率和发生流水线停顿的几率。虚函数的另一个问题是编译器难以内联它们。编译器只有在它能同时访问函数体和构造实例的代码（这样编译器才能决定调用虚函数的哪个函数体）时才能内联它们。

继承中的成员函数调用

继承类中定义的虚成员函数如果继承关系最顶端的基类没有虚成员函数，那么代码必须要给 this 类实例指针加上一个偏移量，来得到继承类的虚函数表，接着会遍历虚函数表来获取函数执行地址。这些代码会包含更多的指令字节，而且这些指令通常都比较慢，因为它们会进行额外的计算。这种开销在小型嵌入式处理器上非常显著，但是在桌面级处理器上，指令级别的并发掩盖了大部分这种额外的开销。

为了组成虚多重继承类的实例的指针，代码必须解引类实例中的表，来确定要得到指向虚多重继承类的实例的指针时需要加在类实例指针上的偏移量。如前所述，当被调用的函数是虚函数时，这里也会产生额外的间接开销。

函数指针的开销

C++ 允许在程序中定义指向函数的指针。程序员可以通过函数指针显式地选择一个具有特定签名（由参数列表和返回类型组成）的非成员函数。当函数指针被解引后，这个函数将会在运行时会被调用。通过将一个函数赋值给函数指针，程序可以显式地通过函数指针选择要调用的函数。代码必须解引指针来获取函数的执行地址。编译器也不太可能会内联这些函数。

成员函数指针声明同时指定了函数签名和解释函数调用的上下文中的类。程序通过将函数赋值给函数指针，显式地选择通过成员函数指针调用哪个函数。成员函数指针有多种表现形式，一个成员函数只能有一种表现形式。它必须足够通用才能够在以上列举的各种复杂的场景下调用任意的成员函数。我们有理由认为一个成员函数指针会出现最差情况的性能。

函数调用开销总结

因此， C 风格的不带参数的 void 函数的调用开销是最小的。如果能够内联它的话，就没有开销；即使不能内联，开销也仅仅是两次内存读取加上两次程序执行的非局部转移。

如果基类没有虚函数，而虚函数在多重虚拟继承的继承类中，那么这是最坏的情况。不过幸运的是，这种情况非常罕见。在这种情况下，代码必须解引类实例中的函数表来确定加到类实例指针上的偏移量，构成虚拟多重继承函数的实例的指针，接着解引该实例来获取虚函数表，最后索引虚函数表得到函数执行地址。

简短地声明内联函数

那些函数体在类定义中的函数会被隐式地声明为内联函数。通过将在类定义外部定义的函数声明为存储类内联，也可以明确地将它们声明为内联函数。此外，如果函数定义出现在它们在某个编译单元中第一次被使用之前，那么编译器还可能会自己选择内联较短的函数。

当编译器内联一个函数时，那么它还有可能会改善代码，包括移除调用和返回语句。内联是一种通过在编译时进行计算来移除多余计算的改善性能的手段。

在使用之前定义函数

在第一次调用函数之前定义函数（提供函数体）给了编译器优化函数调用的机会。当编译器编译对某个函数的调用时发现该函数已经被定义了，那么编译器能够自主选择内联这次函数调用。如果编译器能够同时找到函数体，以及实例化那些发生虚函数调用的类变量、指针或是引用的代码，那么这也同样适用于虚函数。

放弃不使用的接口

由于纯虚函数没有函数体，因此 C++ 不允许实例化接口基类。继承类可以通过重写（定义）接口基类中的所有纯虚函来实现接口。C++ 中接口惯用法的优点在于，继承类必须实现接口中声明的所有函数，否则编译器将不会允许程序创建继承类的实例。例如，开发人员可以使用接口类来隔离操作系统依赖性，特别是当设计人员预计需要为多个操作系统实现程序时。我们可以通过下面的接口类 file 来定义读写文件的类。这个file 被称为抽象基类，因为它无法被实例化：

1
2
3
4
5
6
7
8
class File {
public:
    virtual ~File() {}
    virtual bool Open(Path& p) = 0;
    virtual bool Close() = 0;
    virtual int GetChar() = 0;
    virtual unsigned GetErrorCode() = 0;
};

C++11 中的关键字 override 是可选关键字，它告诉编译器当前的声明会重写基类中虚函数的声明。当指定了 override 关键字后，如果在基类中没有虚函数声明，编译器会报出警告消息：

1
2
3
4
5
6
7
8
9
# include "File.h"
class WindowsFile : public File { // C++11风格的声明
public:
    ~File() {}
    bool Open(Path& p) override;
    bool Close() override;
    int GetChar() override;
    unsigned GetErrorCode() override;
};

有时，一个程序虽然定义了接口，但是只提供了一种实现。在这种情况下，通过移除接口，即移除 file.h 类定义中的 virtual 关键字并提供 file 的成员函数的实现，可以节省虚函数调用（特别是频繁地对GetChar()的调用）的开销。

避免使用PIMPL惯用法

PIMPL 是“Pointer to IMPLementation”的缩写，它是一种用作编译防火墙——一种防止修改一个头文件会触发许多源文件被重编译的机制——的编程惯用法。

假设BigClass是一个被其他类广泛使用的类，它有一些内联函数，而且使用了Foo类、Bar类和Baz类。一般情况下，bigclass.h、foo.h、bar.h或是baz.h的任何改动，哪怕只是代码注释中的一个字符发生了变化，都会触发许多引用了bigclass.h的文件被重编译。

1
2
3
4
5
6
7
8
9
10
11
12
# include "foo.h"
# include "bar.h"
# include "baz.h"
class BigClass {
public:
    BigClass();
    void f1(int a) { ... }
    void f2(float f) { ... }
    Foo foo_;
    Bar bar_;
    Baz baz_;
};

要实现 PIMPL，开发人员要定义一个新的类，在本例中，我们将其命名为Impl。bigclass.h的修改如代码所示。

1
2
3
4
5
6
7
8
class Impl;
class BigClass {
public:
    BigClass();
    void f1(int a);
    char f2(float f);
    Impl* impl;
};

C++ 允许声明一个指向未完成类型，即一个还没有定义的对象的指针。在本例中，Impl就是一个未完成类型。这样的代码之所以能够工作，是因为所有指针的大小都是相同的，因此编译器知道如何预留指针的存储空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include "foo.h"
# include "bar.h"
# include "baz.h"
# include "bigclass.h"
class Impl {
    void g1(int a);
    void g2(float f);
    Foo foo_;
    Bar bar_;
    Baz baz_;
};
void Impl::g1(int a) { ... }
char Impl::g2(float f) { ... }
void BigClass::BigClass() { 
    impl_ = new Impl;
}
void BigClass::f1(int a) {
impl_ -> g1(a);
}
char BigClass::f2(float f) {
    return impl_ -> g2(f)
}

实现了 PIMPL 后，在编译时，对foo.h、bar.h或baz.h，或者是对Impl的实现的改动都会导致bigclass.cpp被重编译，但是bigclass.h不会改变，这样就限制了重编译的范围。

在运行时情况就不同了。PIMPL 给程序带来了延迟。之前BigClass中的成员函数可能会被内联，而现在则会发生一次成员函数调用。而且，现在每次成员函数调用都会调用Impl的成员函数。使用了 PIMPL 的工程往往会在很多地方使用它，导致形成了多层嵌套函数调用。更甚者，这些额外的函数调用层次使得调试变得更加困难。

使用静态成员函数取代成员函数

每次对成员函数的调用都有一个额外的隐式参数：指向成员函数被调用的类实例的 this 指针。通过对 this 指针加上偏移量可以获取类成员数据。虚成员函数必须解引 this 指针来获得虚函数表指针。

有时，一个成员函数中的处理仅仅使用了它的参数，而不用访问成员数据，也不用调用其他的虚成员函数。在这种情况下， this 指针没有任何作用。我们应当将这样的成员函数声明为静态函数。静态成员函数不会计算隐式 this 指针，可以通过普通函数指针，而不是开销更加昂贵的成员函数指针找到它们。

将虚析构函数移至基类中

任何有继承类的类的析构函数都应当被声明为虚函数。这是有必要的，这样 delete 表达式将会引用一个指向基类的指针，继承类和基类的析构函数都会被调用。

另外一个在继承层次关系顶端的基类中声明虚函数的理由是：确保在基类中有虚函数表指针。继承层次关系中的基类处于一个特殊的位置。如果在这个基类中有虚成员函数声明，那么虚函数表指针在其他继承类中的偏移量是 0；如果这个基类声明了成员变量且没有声明任何虚成员函数，但是有些继承类却声明了虚成员函数，那么每个虚成员函数调用都会在 this 指针上加上一个偏移量来得到虚函数表指针的地址。确保在这个基类中至少有一个成员函数，可以强制虚函数表指针出现在偏移量为 0 的位置上，这有助于产生更高效的代码。

优化表达式

简化表达式

C++ 会严格地以运算符的优先级和可结合性的顺序来计算表达式。只有像((a*b)+(a*c))这样书写表达式时才会进行a*b+a*c的计算，因为 C++ 的优先级规则规定乘法的优先级高于加法。

C++ 之所以让程序员手动优化表达式，是因为 C++ 的 int 类型的模运算并非是整数的数学运算， C++ 的 float 类型的近似计算也并非真正的数学运算。C++ 必须给予程序员足够的权力来清晰地表达他的意图，否则编译器会对表达式进行重排序，从而导致控制流程发生各种变化。这意味着开发人员必须尽可能使用最少的运算符来书写表达式。

用于计算多项式的霍纳法则（Horner Rule）证明了以一种更高效的形式重写表达式有多么厉害。尽管大多数 C++ 开发人员并不会每天都进行多项式计算，但是我们都很熟悉它。多项式y = ax3 + bx2 + cx + d在 C++ 中可以写为：y = a*x*x*x + b*x*x + c*x + d;。这条语句将会执行 6 次乘法运算和 3 次加法运算。我们可以根据霍纳法则重复地使用分配律来重写这条语句：y = (((a*x + b)*x) + c)*x + d;。这条优化后的语句只会执行 3 次乘法运算和 3 次加法运算。通常，霍纳法则可以将表达式的乘法运算次数从n(n-1)减少为 n，其中 n 是多项式的维数。

将常量组合在一起

我们应当总是用括号将常量表达式组合在一起，或是将它们放在表达式的左端，或者更好的一种的做法是，将它们独立出来初始化给一个常量，或者将它们放在一个常量表达式（constexpr）函数中。这样编译器能够在编译时高效地计算常量表达式。

使用更高效的运算符

整数表达式x*4可以被重编码为更高效的x<<2。任何差不多的编译器都可以优化这个表达式。但是如果表达式是x*y或x*func()会怎样呢？许多情况下，编译器都无法确定y或func()的返回值一定是 2 的幂。这时就需要依靠程序员了。如果其中一个参数可以用指数替换掉 2 的幂，那么开发人员就可以重写表达式，用位移运算替代乘法运算。

另一种优化是用位移运算和加法运算替代乘法。例如，整数表达式x*9可以被重写为x*8+x*1，进而可以重写为(x<<3)+x。当常量运算子中没有许多置为 1 的位时，这种优化最有效，因为每个置为 1 的位都会扩展为一个位移和加法表达式。

使用整数计算替代浮点型计算

浮点型计算的开销是昂贵的。浮点数值内部的表现比较复杂，它带有一个整数型尾数、一个独立的指数以及两个符号。

即使是在具有浮点型计算硬件单元的处理器上，即使对计算结果的整数部分进行了舍入处理，而不是截取处理，计算整数结果仍然能够比计算浮点型结果快至少 10 倍。如果是在没有浮点型计算硬件单元的小型处理器上用函数库进行浮点型计算，那么整数的计算速度会快得更多。但是我们仍然可以看到，有些开发人员在明明可以使用整数计算时，却使用浮点型计算。

双精度类型可能会比浮点型更快

双精度类型的计算速度比浮点类型的计算速度更快。Visual C++ 生成的浮点型指令会引用老式的“x87 FPU coprocessor”寄存器栈。在这种情况下，所有的浮点计算都会以 80 位格式进行。当单精度float 和双精度 double 值被移动到 FPU 寄存器中时，它们都会被加长。对 float 进行转换的时间可能比对 double 进行转换的时间更长。

用闭形式替代迭代计算

有许多特殊情况都需要对置为 1 的位计数，找到最高有效位，确定一个字的奇偶校验位，确定一个字的位是否是 2 的幂，等等。这个问题同样有一种闭形解决方法。如果 x 是 2 的 n 阶幂，那么它只在第 n 位有一个置为1 的位（以最低有效位作为第 0 位）。接着，我们用 x-1 作为当置为 1 的位在第 n-1,…,0 位时的位掩码，那么x& (x-1)等于 0。如果 x 不是 2 的幂，那么它就有不止一个置为 1 的位，那么使用 x-1 作为掩码计算后只会将最低有效位置为 0，x& (x-1)不再等于 0。

优化控制流程惯用法

由于当指令指针必须被更新为非连续地址时在处理器中会发生流水线停顿，因此计算比控制流程更快。

用switch替代if-else if-else

如果测试一个变量的值 n 次，那么需要 n 个 if-then-else if 语句块。如果所有的条件为真的概率都是一样的，那么 if-then-else if 将会进行 O(n) 次判断。switch 语句用 switch 的值与一系列常量进行比较，这样编译器可以进行一系列有效的优化。

一种常见的情况是被测试的常量是一组连续值或是近似一组连续值，这时 switch 语句会被编译为 jump 指令表，其索引是要测试的值或是派生于要测试的值的表达式。switch 语句会执行一次索引操作，然后跳转到表中的地址。无论有多少种要比较的情况，每次比较处理的开销都是 O(1)。我们在程序中不必对各种要比较的情况排序，因为编译器会排序 jump指令表。

如果这些被测试的常量不是连续值，而是互相之间相差很大的数值，那么 jump 指令表会变得异常庞大，难以管理。编译器可能仍然会排序这些要测试的常量并生成执行二分查找的代码。对于一个会与 n 个值进行比较的 switch 语句，这种查找的最差情况的开销是O(log2n)。在任何情况下，编译器编译 switch 语句后产生的代码都不会比编译 if-then 语句后产生的代码的速度慢。

用虚函数替代switch或if

在 C++ 出现之前，如果开发人员想要在程序中引入多态行为，那么他们必须编写一个带有标识变量的结构体或是联合体，然后通过这个标识变量来辨别出当前使用的是哪个结构体或是联合体。程序中应该会有很多类似下面的代码：

1
2
3
4
5
6
7
if (p->animalType == TIGER) {
    tiger_pounce(p->tiger);
}
else if (p->animalType == RABBIT) {
    rabit_hop(p->rabbit);
}
else if (...)

虚函数调用会通过索引虚函数表得到虚函数体的地址。这个操作的开销总是常量时间。因此，基类中的虚成员函数move()会被继承类中表示各种动物的 pounce、 hop 或 swim 等函数重写。

使用无开销的异常处理

异常处理是应当在设计阶段就进行优化的项目之一。错误传播方法的设计会影响程序中的每一行代码，因此改造程序的异常处理的代价可能会非常昂贵。可以说，使用异常处理可以使程序在通常运行时更加快速，在出错时表现得更加优秀。

如果程序不抛出异常，它可能会完全忽略错误码。那么在这种情况下，开发人员就会得到报应了。另外一种情况是，程序必须在各层函数调用之间耐心地、小心地传递错误码，然后在调用库函数的地方将错误码从一种形式转换为另一种形式并相应地释放资源。而且，无论每次运算是成功还是失败，都不能遗漏这些处理。

如果有异常，处理错误的部分开销就被从程序执行的正常路径转移至错误路径上。除此之外，编译器会通过调用在抛出异常和 try/catch 代码块之间的执行路径上的所有自动变量的析构函数，自动地回收资源。这简化了程序执行的正常路径的逻辑，从而提升性能。

在 C++11 中引入了一种新的异常规范，称为 noexcept。声明一个函数为 noexcept 会告诉编译器这个函数不可能抛出任何异常。如果这个函数抛出了异常，那么如同在throw()规范中一样，terminate()将会被调用。不过不同的是，编译器要求将移动构造函数和移动赋值语句声明为 noexcept 来实现移动语义。在这些函数上的 noexcept 规范的作用就像是发表了一份声明，表明对于某些对象而言，移动语义比强异常安全保证更重要。

小结

  • 循环中的语句的性能开销被放大的倍数是循环的次数。
  • 函数中的语句的性能开销被放大的倍数是其在函数中被调用的次数。
  • 被频繁地调用的编程惯用法的性能开销被放大的倍数是其被调用的次数。
  • 有些 C++ 语句（赋值、初始化、函数参数计算）中包含了隐藏的函数调用。
  • 调用操作系统的函数的开销是昂贵的。
  • 一种有效的移除函数调用开销的方法是内联函数。
  • double 计算可能会比 float 计算更快。

使用更好的库

优化标准库的使用

C++ 为以下常用功能提供了一个简洁的标准库。

  • 确定那些依赖于实现的行为，如每种数值类型的最大值和最小值。
  • 最好不要在 C++ 中编写的函数，如strcpy()和memmove()。
  • 易于使用但是编写和验证都很繁琐的可移植的超越函数（transcendental function），如正弦函数和余弦函数、对数函数和幂函数、随机数函数，等等。
  • 除了内存分配外，不依赖于操作系统的可移植的通用数据结构，如字符串、链表和表。
  • 可移植的通用数据查找算法、数据排序算法和数据转换算法。
  • 以一种独立于操作系统的方式与操作系统的基础服务相联系的执行内存分配、操作线程、管理和维护时间以及流 I/O 等任务的函数。考虑到兼容性，这其中包含了一个继承自 C编程语言的函数库。

优化查找和排序

只有少数开发人员知道，在 C++ 标准库中的<algorithm>头文件中包含了几种基于迭代器的查找序列容器的算法。即使在最优情况下，这些算法也并不都具有相同的大 O 性能。

使用std::map和std::string的键值对表

作为一个例子，本节将介绍对一种常用的键值对表进行各种查找和排序的性能。在这个例子中，表的键是一个由 ASCII 字符组成的字符串，我们可以用 C++ 字符串字面量来初始化它，或是将它保存在std::string中。我们通常会使用这样的表来解析初始化配置、命令行、 XML 文件、数据库表以及其他需要有限组键的应用程序。除非有一个非常大的值会影响高速缓存性能，否则值的类型对查找操作的性能不会有影响。

使用std::map构建一个std::string类型的名字与无符号整数值之间的映射关系的表是很容易的。可以如下这样简单地定义一个表：

1
2
3
# include <string>
# include <map>
std::map<std::string, unsigned> table;

如果使用的是支持 C++11 的编译器，开发人员可以如下这样使用初始化列表声明语法轻松地向表中插入数据项：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::map<std::string, unsigned> const table {
{ "alpha", 1 }, { "bravo", 2 },
{ "charlie", 3 }, { "delta", 4 },
{ "echo", 5 }, { "foxtrot", 6 },
{ "golf", 7 }, { "hotel", 8 },
{ "india", 9 }, { "juliet", 10 },
{ "kilo", 11 }, { "lima", 12 },
{ "mike", 13 }, { "november",14 },
{ "oscar", 15 }, { "papa", 16 },
{ "quebec", 17 }, { "romeo", 18 },
{ "sierra", 19 }, { "tango", 20 },
{ "uniform",21 }, { "victor", 22 },
{ "whiskey",23 }, { "x-ray", 24 },
{ "yankee", 25 }, { "zulu", 26 }
};

否则，开发人员必须像下面这样编码来插入每条元素：

1
2
3
4
table["alpha"] = 1;
table["bravo"] = 2;
...
table["zulu"] = 26;

取得或是测试值也非常简单：

1
2
3
4
5
unsigned val = table["echo"];
...
std::string key = "diamond";
if (table.find(key) != table.end())
    std::cout << "table contains " << key << std::endl;

优化std::map的查找

性能优化开发人员可以通过保持表数据结构不变，但改变键的数据结构，当然也包括改变比较键的算法，改善程序性能。

以固定长度的字符数组作为std::map的键

如果开发人员可以使用一种不会动态分配存储空间的数据结构作为键类型，就能够开销减半。而且，如果表使用std::string作为键，而开发人员希望如下这样用 C 风格的字符串字面常量来查找元素，那么每次查找都会将char*的字符串字面常量转换为std::string，其代价是分配更多的内存，而且这些内存紧接着会立即被销毁掉。

1
unsigned val = table["zulu"];

如果键的最大长度不是特别大，那么一种解决方法是使用足以包含最长键的字符数组作为键的类型。不过这里我们无法像下面这样直接使用数组，因为 C++ 数组没有内置的比较运算符。

1
std::map<char[10],unsigned> table

下面是一个名为charbuf的简单的固定长度字符数组模板类的定义：

1
2
3
4
5
6
7
8
9
10
11
template <unsigned N=10, typename T=char> struct charbuf {
    charbuf();
    charbuf(charbuf const& cb);
    charbuf(T const* p);
    charbuf& operator=(charbuf const& rhs);
    charbuf& operator=(T const* rhs);
    bool operator==(charbuf const& that) const;
    bool operator<(charbuf const& that) const;
private:
    T data_[N];
};

charbuf非常简单。我们可以用 C 风格的、以空字符结尾的字符串来对它进行初始化或是赋值，也可以用一个charbuf与另一个charbuf进行比较。由于这里没有明确地定义构造函数charbuf(T const*)，因此我们还可以通过类型转换将charbuf与一个以空字符结尾的字符串进行比较。charbuf的长度是在编译时就确定了的，它不会动态分配内存。

以C风格的字符串组作为键使用std::map

有时，程序会访问那些存储期很长的、 C 风格的、以空字符结尾的字符串，那么我们就可以用这些字符串的char*指针作为std::map的键。例如，当程序使用 C++ 字符串字面常量来构造表时，我们可以直接使用char*来避免构造和销毁std::string的实例的开销。

不过，以char*作为键类型也有一个问题。std::map会在它的内部数据结构中，依据键类型的排序规则对键值对进行排序。默认情况下，它都会计算表达式 key1 < key2 的值。在std::string中定义了一个用于比较字符串的 < 运算符。虽然在char*中也定义了 < 运算符，但它比较的却是指针，而不是指针所指向的字符串。

std::map让开发人员能够通过提供一个非默认的比较算法来解决这个问题。这也是 C++ 允许开发人员对它的标准容器进行精准控制的一个例子。比较算法是通过std::map的第三个模板参数提供的。比较算法的默认值是函数对象std::less<Key>。std::less定义了一个成员函数bool operator()(Key const& k1, Key const& k2)，它会通过返回表达式key1 < key2的结果来比较两个键的大小。

程序还可以创建一个函数对象来封装比较操作。less_for_c_strings是一个类类型的名字，因此它可以用作类型参数，这样就无需使用指针。

1
2
3
4
5
6
7
8
9
struct less_for_c_strings {
    bool operator()(char const* p1, char const* p2) {
        return strcmp(p1,p2)<0;
    }
};
...
std::map<char const*,
    unsigned,
    less_for_c_strings> table;

在 C++11 中，另外一种为std::map提供char*比较函数的方法是，定义一个lambda表达式并将它传递给 map 的构造函数。使用lambda表达式非常便利，因为我们可以在局部定义它们，而且它们的声明语法也非常简洁。

1
2
3
4
5
6
auto comp = [](char const* p1, char const* p2) {
    return strcmp(p1,p2)<0;
};
std::map<char const*,
    unsigned,
    decltype(comp)> table(comp);

请注意，这段示例代码中使用了 C++11 中的decltype关键字。map 的第三个参数是一个类型。名字comp是一个变量，而decltype(comp)则是变量的类型。lambda表达式的类型没有名字，每个lambda表达式的类型都是唯一的，因此decltype是获得lambda表达式的类型的唯一方法。

当键就是值的时候， 使用map的表亲std::set

定义一种数据结构，其中包含一个键以及其他数据作为键所对应的值，有些程序员可能会觉得这是一件再自然不过的事了。事实上，std::map在内部声明了一种像下面这样的可以结合键与值的结构体：

1
2
3
4
5
template <typename KeyType, typename ValueType> struct value_type {
    KeyType const first;
    ValueType second;
    // ……构造函数和赋值运算符
};

如果程序定义了这样一种数据结构，那么无法将它直接用于std::map中。出于一些实际的原因，std::map要求键和值必须分开定义。键必须是常量，因为修改键会导致整个 map 数据结构无效。同样，指定键可以让 map 知道如何访问它。

std::map有一个表亲——std::set。它是一种可以保存它们自己的键的数据结构。这种类型会使用一个比较函数，该比较函数默认使用std::less来比较两个完整元素。因此，要想使用std::set和一种包含自身的键的用户自定义的结构体，开发人员必须为那个用户自定义的结构体实现std::less、指定 < 运算符或是提供一个非默认的比较对象。

使用头文件优化算法

标准库查找算法接收两个迭代器参数：一个指向待查找序列的开始位置，另一个则指向待查找序列的末尾位置（最后一个元素的下一个位置）。所有的算法还都接收一个要查找的键作为参数以及一个可选的比较函数参数。这些算法的区别在于它们的返回值，以及比较函数必须定义键的排序关系还是只是比较是否相等。

以序列容器作为被查找的键值对表

相比于std::map或它的表亲std::set，有几个理由使得选择序列容器实现键值对表更好：序列容器消耗的内存比 map 少，它们的启动开销也更小。标准库算法的一个非常有用的特性是它们能够遍历任意类型的普通数组，因此，它们能够高效地查找静态初始化的结构体的数组。这样可以移除所有启动表的开销和销毁表的开销。

1
2
3
4
struct kv { //（键，值）对
    char const* key;
    unsigned value; // 可以是任何类型
};

由这些键值对构成的静态数组的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
kv names[] = {// 以字母顺序排序
{ "alpha", 1 }, { "bravo", 2 },
{ "charlie", 3 }, { "delta", 4 },
{ "echo", 5 }, { "foxtrot", 6 },
{ "golf", 7 }, { "hotel", 8 },
{ "india", 9 }, { "juliet", 10 },
{ "kilo", 11 }, { "lima", 12 },
{ "mike", 13 }, { "november",14 },
{ "oscar", 15 }, { "papa", 16 },
{ "quebec", 17 }, { "romeo", 18 },
{ "sierra", 19 }, { "tango", 20 },
{ "uniform",21 }, { "victor", 22 },
{ "whiskey",23 }, { "x-ray", 24 },
{ "yankee", 25 }, { "zulu", 26 }
};

names数组的初始化是静态集合初始化。

标准库容器类提供了begin()和end()成员函数，这样程序就能够得到一个指向待查找范围的迭代器。C 风格的数组更加简单，通常没有提供这些函数。不过，我们可以通过用一点模板“魔法”提供类型安全的模板函数来实现这个需求。由于它们接收一个数组类型作为参数，数组并不会像通常那样退化为一个指针：

1
2
3
4
5
6
7
8
9
10
// 得到C风格数组的大小和起始或终止位置
template <typename T, int N> size_t size(T (&a)[N]) {
    return N;
}
template <typename T, int N> T* begin(T (&a)[N]) {
    return &a[0];
}
template <typename T, int N> T* end(T (&a)[N]) {
    return &a[N];
}

std::find()

在标准库<algorithm>头文件中如下定义了一个模板函数find()：

1
template <class It, class T> It find(It first, It last, const T& key)

find()是一个简单的线性查找算法。线性查找是最通用的查找方式。它不需要待查找的数据已经排序完成，只需要能够比较两个键是否相等即可。

find()返回指向序列容器中第一条与待查找的键相等的元素的迭代器。迭代器参数first和last限定了待查找的范围，其中last指向待查找数据的末尾的后一个元素。first和last的类型是通过模板参数It指定的，这取决于find()要遍历的数据结构的类型。

find()的用法示例如代码所示。

1
kv* result=std::find(std::begin(names), std::end(names), key);

在这段示例代码中，names是待查找的数组的名字。key是要查找的关键字，它会与每条kv元素进行比较。要想进行比较操作，必须在find()被实例化的作用域内定义用于比较关键字的函数。该函数会告诉std::find()在进行比较时所需知道的一切信息。C++ 允许为各种类型的一对值重载等号运算符bool operator==(v1,v2)。如果键是一个指向 char 的指针，那么所需的比较关键字的函数就是：

1
2
3
bool operator==(kv const& n1, char const* key) {
    return strcmp(n1.key, key) == 0;
}

find()函数的一种变化形式是find_if()，它接收比较函数作为第四个参数。这里开发人员不用在find()的作用域中定义operator==()，而是可以编写一个lambda表达式作为比较函数。

标准库算法binary_search()返回一个 bool 值，表示键是否存在于有序表中。非常奇怪的是，标准库却没有提供配套的返回匹配的表元素的函数。因此，find()和binary_search()虽然从名字上看都像是我们要找的解决方法，但其实不然。如果程序只是想知道一个元素是否存在于表中，而不是找到它的值，那么我们可以使用binary_search()。

使用std::equal_range()

如果序列容器是有序的，那么开发人员能够从 C++ 标准库提供的零零散散的函数中组合出一个高效的查找函数。不幸的是，这些零零散散的函数的名字都难以使人联想起二分查找。在 C++ 标准库的<algorithm>头文件中有一个模板函数std::equal_range()，它的定义如下：

1
2
3
template <class ForwardIt, class T>
std::pair<ForwardIt,ForwardIt>
equal_range(ForwardIt first, ForwardIt last, const T& value);

equal_range()会返回一对迭代器，它们确定的是范围是有序序列中包含要查找的元素的子序列[first, last)。如果没有找到元素，equal_range()会返回一对指向相等值的迭代器，这表示这个范围是空的。如果返回的两个迭代器不等，表示至少找到了一条元素。

如果找到了元素，就将result设置为指向找到的表元素的迭代器，否则result设置为指向表的末尾的迭代器。

1
2
3
4
auto res = std::equal_range(std::begin(names),
    std::end(names),
    key);
kv* result = (res.first == res.second) ? std::end(names) : res.first;

使用std::lower_bound()

尽管equal_range()所承诺的时间开销是 O(log2n)，但除了表查找以外，它还有其他不必要的功能。equal_range()的一种可能实现方式看起来像下面这样：

1
2
3
4
5
6
template <class It, class T>
std::pair<It,It>
equal_range(It first, It last, const T& value) {
    return std::make_pair(std::lower_bound(first, last, value),
    std::upper_bound(first, last, value));
}

upper_bound()会在表中第二次分而治之来查找要返回的范围的末尾，这是因为equal_range()需要足够通用，能够适用于任何存在一个键对应多个值的有序序列。如代码所示，可以使用lower_bound()和一次额外的比较运算来进行查找就足够了。

1
2
3
4
5
kv* result = std::lower_bound(std::begin(names),
    std::end(names),
    key);
if (result != std::end(names) && key < *result.key)
    result = std::end(names);

在这个例子中，std::lower_bound()返回一个指向表中键大于等于key的第一个元素的迭代器。如果表中所有元素的键都小于key，那么它会返回一个指向表末尾的迭代器。它也可能会返回一条大于key的元素。如果最后一条 if 语句中的所有条件都是 true，那么result会被设置为指向表末尾的迭代器；否则，它会返回键等于key的元素。

使用std::lower_bound()进行查找的性能与使用std::map的最佳实现方式的性能旗鼓相当，而且它还有一个额外的优势，那就是构造或是销毁静态表是没有任何开销的。

自己编写二分查找法

我们将初始表的取值的连续范围值定义为[start, end)。在每一步查找中，函数都会计算取值范围的中间位置，并将键与中间位置的元素进行比较。这种方法可以高效地将表的取值范围分为两部分——[start, mid+1)和[mid+1, stop)。

1
2
3
4
5
6
7
8
9
10
11
12
13
kv* find_binary_lessthan(kv* start, kv* end, char const* key) {
    kv* stop = end;
    while (start < stop) {
        auto mid = start + (stop-start)/2;
        if (*mid < key) {// 查找右半部分[mid+1,stop)
            start = mid + 1;
        }
        else {// 查找左半部分[start,mid)
            stop = mid;
        }
    }
    return (start == end || key < *start) ? end : start;
}

使用strcmp()自己编写二分查找法

如果注意到<运算符可以用strcmp()替换，那么还可以进一步提高性能。与<运算符一样，strcmp()也会对两个键进行比较，但是strcmp()的输出结果包含的信息更多：如果第一个键小于、等于、大于第二个键，那么其返回结果就小于、等于、大于 0。

在 while 循环的每次迭代中，被查找的序列都是[start,stop)。在每一步中，mid都会被设置为被查找序列的中间位置。strcmp()的返回值不是将序列分为两部分，而是分为三部分：[start,mid)、[mid,mid+1)和[mid+1,stop)。如果mid->key大于要查找的键，我们就可以知道键肯定在序列中最左侧的mid之前的部分中。如果mid->key小于要查找的键，那么我们知道键肯定在序列中最右侧的以mid+1开头的部分中。如果mid->key等于要查找的键，循环终止。if/else 逻辑会先进行可能性更大的比较操作来改善性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
kv* find_binary_3(kv* start, kv* end, char const* key) {
    auto stop = end;
    while (start < stop) {
        auto mid = start + (stop-start)/2;
        auto rc = strcmp(mid->key, key);
        if (rc > 0) {
            stop = mid;
        }
        else if (rc < 0) {
            start = mid + 1;
        }
        else {
            return mid;
        }
    }
    return end;
}

优化键值对散列表中的查找

寻找高效的散列函数是实现散列表时的一个复杂环节。一个含有 10 个字符的字符串所包含的位数可能会比一个 32 位整数所包含的位数多。因此，可能存在多个字符串具有相同索引值的情况。我们必须提供一种机制来应对这种冲突。散列表中的每条元素都可能是散列到某个索引值的元素列表中的第一个元素。或者，可以寻找相邻索引值来查找匹配的元素，直到遇到一个空索引为止。

一个糟糕的散列函数或是一组不太走运的键可能会导致许多键散列到相同的索引值上。这样，散列表的性能会降到 O(n)，使得相比于线性查找它没有任何优势。一个优秀的散列函数所计算出的数组索引不会与键的各个位的值紧密相关。

C++ 定义了一个称为std::hash的标准散列函数对象。std::hash是一个模板，为整数、浮点数据、指针和std::string都提供了特化实现。同样适用于指针的未特化的std::hash的定义会将散列类型转换为size_t，然后随机设置它的各个位的值。

使用std::unordered_map

在 C++11 中，标准头文件<unordered_map>提供了一个散列表。使用std::unordered_map创建散列表和插入元素的示例代码如代码。

1
2
3
std::unordered_map<std::string, unsigned> table;
for (auto it = names; it != names+namesize; ++it)
    table[it->key] = it->value;

std::unordered_map使用的默认散列函数是模板函数对象std::hash。由于该模板为std::string提供了特化实现，因此我们无需显式地提供散列函数。当所有元素都被插入到表中后，就可以如下这样进行查找了：

1
auto it = table.find(key);

it是一个迭代器，它要么指向一条匹配元素，要么指向table.end()。以std::string为键的std::unordered_map会使用map模板的所有默认值来实现简单性和可观的性能。

对固定长度字符数组的键进行散列

下面这个模板继承了charbuf，提供了对字符串进行散列的方法以及在发生冲突的情况下可以比较键的==运算符：

1
2
3
4
5
6
7
8
9
10
11
12
template <unsigned N=10, typename T=char> struct charbuf {
    charbuf();
    charbuf(charbuf const& cb);
    charbuf(T const* p);
    charbuf& operator=(charbuf const& rhs);
    charbuf& operator=(T const* rhs);
    operator size_t() const;
    bool operator==(charbuf const& that) const;
    bool operator<(charbuf const& that) const;
private:
    T data_[N];
};

散列函数是运算符size_t()。这有一点不直观，还有一点不纯净。std::hash()的默认特化实现会将参数转换为size_t。对于指针，通常情况下这只会转换指针的各个位，但是如果是charbuf&，那么charbuf的size_t()运算符会被调用，它会返回散列值作为size_t。

当然，由于size_t()运算符被劫持了，它无法再返回charbuf的长度。现在，表达式sizeof(charbuf)返回的是一个容易让人误解的值。使用charbuf的散列表的声明语句如下：

1
std::unordered_map<charbuf<>, unsigned> table;

以空字符结尾的字符串为键进行散列

如果能够用如 C++ 字符串字面常量这样的存储期很长的以空字符结尾的字符串来初始化散列表，那么就可以用指向这些字符串的指针来构造基于散列值的键值对表。以char*为键配合std::unordered_map一起使用是一座值得挖掘的性能金矿。

std::unordered_map 的完整定义是：

1
2
3
4
5
6
7
template<
    typename Key,
    typename Value,
    typename Hash = std::hash<Key>,
    typename KeyEqual = std::equal_to<Key>,
    typename Allocator = std::allocator<std::pair<const Key, Value>>
    > class unordered_map;

Hash是用于计算Key的散列值的函数的函数对象或是函数指针的类型声明。KeyEqual是通过比较两个键的实例是否相等来解决散列冲突的函数的函数对象或是函数指针的类型声明。如果Key是一个指针，那么Hash具有良好的定义。

但程序其实是错误的。std::hash会生成指针的值的散列值，而不是指针所指向的字符串的散列值。如果测试程序是从字符串数组初始化表，然后测试每个字符串是否能被找到，那么指向测试键的指针与指向初始化表的键的指针是同一个指针，因此程序看起来似乎可以正常工作。不过，如果在测试时使用用户另外输入的相同的字符串作为测试键，那么测试结果会是字符串并不在表中，因为指向测试字符串的指针与指向初始化表的键的指针不同。

我们可以通过提供一个非默认的散列函数替代模板的第三个参数的默认值来解决这个问题。就像对于map，这个参数可以是一个函数对象、lambda表达式声明或是非成员函数指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct hash_c_string {
    void hash_combine(size_t& seed, T const& v) {
        seed ^= v + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
    std::size_t operator() (char const* p) const {
        size_t hash = 0;
        for (; *p; ++p)
            hash_combine(hash, *p);
        return hash;
    }
};
// 这种解决方法是不完整的，理由请往下看
std::unordered_map<char const*, unsigned, hash_c_string> table;

这段代码仍然是错误的。问题出在std::unordered_map模板的第四个参数KeyEqual上。这个参数的默认值是std::equal_to，一个使用==比较两个运算对象的函数对象。虽然指针定义了==运算符，但它比较的是指针在计算机内存空间中的顺序，而不是指针所指向的字符串。

当然，解决方式是提供另外一个非默认的函数对象替代KeyEqual模板参数。完整的解决方案代码所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct hash_c_string {
    void hash_combine(size_t& seed, T const& v) {
        seed ^= v + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
    std::size_t operator() (char const* p) const {
        size_t hash = 0;
        for (; *p; ++p)
            hash_combine(hash, *p);
        return hash;
    }
};
struct comp_c_string {
    bool operator()(char const* p1, char const* p2) const {
        return strcmp(p1,p2) == 0;
    }
};
std::unordered_map<
    char const*,
    unsigned,
    hash_c_string,
    comp_c_string
> table;

这个版本的键值对表是以char*为键的std::unordered_map。

用自定义的散列表进行散列

在创建表时，对于给定的一组键不会产生冲突的散列称为完美散列。能够创建出无多余空间的表的散列称为最小散列。当键的数量相当有限时，容易创建完美散列，甚至是完美最小散列。这时，散列函数可以尝试通过首字母（或是前两个字母）、字母和以及键长来计算散列值。

代码展示了一个在实现上与std::unordered_map类似的简单的自定义散列表。

1
2
3
4
5
6
7
8
9
unsigned hash(char const* key) {
    if (key[0] < 'a' || key[0] > 'z')
        return 0;
    return (key[0]-'a');
}
kv* find_hash(kv* first, kv* last, char const* key) {
    unsigned i = hash(key);
    return strcmp(first[i].key, key) ? last : first + i;
}

hash()会将key的首字母映射到 26 条表元素之一，因此对 26 求余。这里采用了一种保守编程方式，以防止当键是“@#$%”这样的字符串时程序会访问未定义的存储空间。

使用C++标准库优化排序

C++ 标准库提供了两种能够高效地对序列容器进行排序的标准算法——std::sort()和std::stable_sort()。C++03 要求std::sort的平均性能达到 O(n log2n)。符合 C++03 标准的实现方式通常都会用快速排序实现std::sort，而且通常都会使用一些技巧来降低快速排序发生最差情况的 O(n^2) 时间开销的几率。C++11 要求最差情况性能为 O(n log2n)。符合 C++11 标准的实现通常都是

std::stable_sort()通常都是归并排序的变种。C++ 标准中的措辞比较奇怪，它指出如果能够分配足够的额外内存，那么std::stable_sort()的时间开销是 O(n log2n)，否则它的时间开销是 O(n (log2n)^2)。如果递归深度不是太深，典型的实现方式是使用归并排序；而如果递归深度太深，那么典型的实现方式是堆排序。

C++ 标准库<algorithm>头文件包含各种排序算法，我们可以使用这些算法为那些具有额外特殊属性的输入数据定制更加复杂的排序。

  • std::heap_sort将一个具有堆属性的范围转换为一个有序范围。heap_sort 不是稳定排序。
  • std::partition会执行快速排序的基本操作。
  • std::merge会执行归并排序的基本操作。
  • 各种序列容器的insert成员函数会执行插入排序的基本操作。

优化数据结构

理解标准库容器

我们有充足的理由喜欢上 C++ 标准库容器，例如统一的命名，以及用于遍历容器的迭代器在概念上的一致性。但是对于性能优化而言，有些特性格外重要，包括：

  • 对于插入和删除操作的性能开销的大 O 标记的性能保证
  • 向序列容器中添加元素具有分摊常时性能开销
  • 具有精准地掌控容器的动态内存分配的能力

序列容器

序列容器std::string、std::vector、std::deque、std::list和std::forward_list中元素的顺序与它们被插入的顺序相同。因此，每个容器都有一头一尾。所有的序列容器都能够插入元素。除了std::forward_list外，所有的序列容器都有一个具有常量时间性能开销的成员函数能够将元素推入至序列容器的末尾。不过，只有std::deque、std::list和std::forward_list能够高效地将元素推入至序列容器的头部。

std::string、std::vector和std::deque中元素的索引是从 0 到 size–1，我们能够通过下标快速地访问这些元素。std::list和std::forward_list则不同，它们没有下标运算符。

std::string、std::vector和std::deque都是基于一个类似数组的内部骨架构建而成的。当一个新元素被插入时，之前被插入的所有元素都会被移动到数组中的下一个位置，因此在非末尾处插入元素的时间开销是 O(n)，其中n是容器中元素的数量。当一个新元素被插入时，这个内部数组可能会被重新分配，导致所有的迭代器和指针失效。相比之下，在std::list和std::forward_list中，只有指向那些从链表中被移除的元素的迭代器和指针才会失效。我们甚至可以在保持迭代器不失效的情况下，拼接或是合并两个std::list或std::forward_list的实例。如果有一个迭代器已经指向插入位置了，那么在std::list和std::forward_list的中间插入元素的时间开销是常量时间。

关联容器

所有的关联容器都会按照元素的某种属性上的顺序关系，而不是按照插入的顺序来保存元素。所有关联容器都提供了高效、具有次线性时间开销的方法来访问存储在它们中的元素。

map和set代表了不同的接口。map能够保存一组独立定义的键与值，因而它提供了一种高效的从键到值的映射。set能够有序地存储唯一值，高效地测试值是否存在于set中的方法。multimaps与map的唯一不同是它允许插入多个相等的元素。

就实现上而言，一共有四种有序关联容器：std::map、std::multimap、std::set和std::multiset。有序关联容器要求必须对键（std::map）或是元素自身（std::set）定义能够对它们进行排序的operator<()等。有序关联容器的实现是平衡二叉树，因此我们无需对有序关联容器进行排序。

在实践中，所有的四种关联容器都是基于相同的平衡二叉树数据结构实现的，不过它们具有独立的“外观”。

std::vector与std::string

这两种数据结构的“产品手册”如下。

  • 序列容器
  • 插入时间：在末尾插入元素的时间开销为 O(1)，在其他位置插入元素的时间开销为 O(n)
  • 索引时间：根据位置进行索引，时间开销为 O(1)
  • 排序时间： O(n log2n)
  • 如果已排序，查找时间开销为 O(log2n)，否则为 O(n)
  • 当内部数组被重新分配时，迭代器和引用失效
  • 迭代器从前向后或是从后向前生成元素
  • 合理控制分配容量，与大小无关

从大 O 标记上看，std::vector的许多操作都是高效的，具有常量时间开销。这些操作包括将一个新元素推入到vector的末尾和获得指向它的第i个元素的引用。得益于vector简单的内部结构，这些操作在绝对意义上也是非常快的。std::vector上的迭代器是随机访问迭代器，这意味着可以在常量时间内计算两个迭代器之间的距离。这个特性使得分而治之的查找算法和排序算法对std::vector非常高效。

重新分配的性能影响

std::vector的size表示当前在vector中有多少个元素；std::vector的capacity则表示存储元素的内部存储空间有多大。当size == capacity时，任何插入操作都会触发一次性能开销昂贵的存储空间扩展：重新分配内部存储空间，将vector中的元素复制到新的存储空间中，并使所有指向旧存储空间的迭代器和引用失效。当发生重新分配时，新的capacity会被设置为新size的若干倍。

高效地使用std::vector的一个秘诀是，通过调用void reserve(size_t n)预留出足够多的capacity，这样可以防止发生不必要的重新分配和复制的开销。高效地使用std::vector的另外一个秘诀是，即使其中的元素被移除了，它也不会自动将内存返回给内存管理器。如果程序将 100 万个元素推入到vector中，接着移除了所有元素，那么vector仍然占用着用于保存那 100 万个元素的存储空间。

std::vector中有几个成员函数会影响它的容量，但标准是笼统的，没有做出任何保证。void clear()会设置容器的大小为 0，但并不一定会重新分配内部存储空间来减小 vector的容量。

要想确保在所有版本的 C++ 中都能释放vector的内存，可以使用以下技巧：

1
2
3
std::vector<Foo> x;
...
vector<Foo>().swap(x);

这段语句会构造一个临时的空的矢量，将它的内容与矢量 x 交换，接着删除这个临时矢量，这样内存管理器会回收所有之前属于 x 的内存。

std::vector中的插入与删除

有多种方法可以向vector中插入数据。我测试了用这些方法构造一个含有 100 000 个kvstruct实例的vector的性能开销，发现其中既有很快的方法，也有很慢的方法。填充vector最快的方式是给它赋值：

1
2
3
std::vector<kvstruct> test_container, random_vector;
...
test_container = random_vector;

赋值操作非常高效，因为它知道要复制的vector的长度，而且只需要调用内存管理器一次来创建被赋值的vector的内部存储空间。

如果数据是在另外一个容器中，使用std::vector::insert()可以将它复制到vector中：

1
2
3
4
5
6
std::vector<kvstruct> test_container, random_vector;
...
test_container.insert(
    test_container.end(),
    random_vector.begin(),
    random_vector.end());

成员函数std::vector::push_back()能够高效地（在常量时间内）将一个新元素插入到vector的尾部。由于这些元素是在另外一个vector中，我们有 3 种方法可以得到它们。

  • 使用vector的迭代器：
1
2
3
4
std::vector<kvstruct> test_container, random_vector;
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it)
    test_container.push_back(*it);
  • 使用std::vector::at()成员函数：
1
2
3
4
std::vector<kvstruct> test_container, random_vector;
...
for (unsigned i = 0; i < nelts; ++i)
    test_container.push_back(random_vector.at(i));
  • 直接使用vector的下标：
1
2
3
4
std::vector<kvstruct> test_container, random_vector;
...
for (unsigned i = 0; i < nelts; ++i)
    test_container.push_back(random_vector[i]);

这段代码更慢的原因是它每次只向vector中插入一个元素。vector 并不知道有多少个元素会被插入，因此它会不断地增大它内部的存储空间。在循环进行插入时，vector内部的空间会发生多次重新分配，并需要将旧空间中的元素复制到新空间中。std::vector确保了在集合中push_back()的性能开销是常量时间，但这不意味着它就没有开销。

开发人员可以通过预先分配一块能存储整个副本的足够大的存储空间，来提高这个循环的效率。下面这段是修改后的使用了迭代器的版本：

1
2
3
4
5
std::vector<kvstruct> test_container, random_vector;
...
test_container.reserve(nelts);
for (auto it=random_vector.begin(); it != random_vector.end(); ++it)
    test_container.push_back(*it);

还有其他方法能够将元素插入到vector中，例如，我们还可以使用另外一个版本的insert()成员函数：

1
2
3
4
std::vector<kvstruct> test_container, random_vector;
...
for (auto it=random_vector.begin(); it != random_vector.end(); ++it)
    test_container.insert(test_container.end(), *it);

看起来它的开销似乎应该与push_back()一样，但其实不然。

最后，我们来看看std::vector的一个超级弱点：在前端插入元素。std::vector并没有提供push_front()成员函数，因为这个操作的时间开销会是 O(n)。在前端插入元素是低效的，因为需要复制vector中的所有元素来为新元素腾出空间，而这确实很低效。下面这个循环所花费的时间几乎是在末尾插入元素的时间的 3000 倍：

1
2
3
4
std::vector<kvstruct> test_container, random_vector;
...
for (auto it=random_vector.begin(); it != random_vector.end(); ++it)
    test_container.insert(test_container.begin(), *it);

因此，想要高效地填充一个vector，请按照赋值、使用迭代器和insert()从另外一个容器插入元素、push_back()和使用insert()在末尾插入元素的优先顺序选择最高效的方法。

遍历std::vector

遍历vector和访问其元素的开销并不大，但就像插入操作一样，不同方法的性能开销差异显著。

有三种方法可以遍历一个vector()：使用迭代器、使用at()成员函数和使用下标。如果循环内部的处理的性能开销很昂贵，那么各种遍历方法之间的性能差异就没有那么明显了。不过，通常开发人员都只会对每个元素进行简单快速的处理。在本例中，循环将会累计值，这个操作所花费的时间微不足道（同时这也可以防止编译器将整个循环优化为无操作）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<kvstruct> test_container;
...
unsigned sum = 0;
for (auto it=test_container.begin(); it!=test_container.end(); ++it)
    sum += it->value;
std::vector<kvstruct> test_container;
...
unsigned sum = 0;
for (unsigned i = 0; i < nelts; ++i)
    sum += test_container.at(i).value;
std::vector<kvstruct> test_container;
...

unsigned sum = 0;
for (unsigned i = 0; i < nelts; ++i)
    sum += test_container[i].value;

开发人员可能会误以为这些循环的性能开销几乎相同，但事实并非如此。使用at()函数的版本性能稍好，下标版本更加高效。

对std::vector排序

在使用二分查找法查找元素前，可以先对vector进行一次高效的排序。C++ 标准库有两种排序算法——std::sort()和std::stable_sort()。如果像std::vector一样，容器的迭代器是随机访问迭代器，那么两种算法的时间开销都是 O(n log2n)，而且它们在有序数据上的排序速度更快。我们可以编写下面这段简短的程序来完成排序：

1
2
3
4
std::vector<kvstruct> sorted_container, random_vector;
...
sorted_container = random_vector;
std::sort(sorted_container.begin(), sorted_container.end());

查找std::vector

下面这段程序会在sorted_container中查找保存在random_vector中的所有键：

1
2
3
4
5
6
7
8
9
10
std::vector<kvstruct> sorted_container, random_vector;
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
    kp = std::lower_bound(
        sorted_container.begin(),
        sorted_container.end(),
        *it);
    if (kp != sorted_container.end() && *it < *kp)
        kp = sorted_container.end();
}

std::deque

deque 的“产品手册”如下。

  • 序列容器
  • 插入时间：在末尾插入元素的时间开销为 O(1)，在其他位置插入元素的时间开销为 O(n)
  • 索引时间：根据位置进行索引，时间开销为 O(1)
  • 排序时间： O(n log2n)
  • 如果已排序，查找时间开销为 O(log2n)，否则为 O(n)
  • 当内部数组被重新分配时，迭代器和引用会失效
  • 迭代器可以从后向前或是从前向后遍历元素

std::deque是一种专门用于创建“先进先出”（FIFO）队列的容器。在队列两端插入和删除元素的开销都是常量时间。下标操作也是常量时间。它的迭代器与std::vector一样，都是随机访问迭代器，因此对std::deque进行排序的时间开销是 O(n log2n)。由于std::deque与std::vector具有相同的性能保证，而且在两端插入元素的时间开销都是常量时间。deque的这些操作的常量比例比vector大。对这些共通操作的性能测量结果表明，deque的操作比vector相同的操作慢 3 到 10 倍。对deque而言，迭代、排序和查找相对来说是三个亮
点，只是比vector慢了大约 30%。

std::deque的典型实现方式是一个数组的数组。获取deque中元素所需的两个间接引用会降低缓存局部性，而且更加频繁地调用内存管理器所产生的性能开销也比vector 的要大。

将一个元素加入到deque的任何一端都会导致最多调用内存分配器两次：一次是为新元素分配另一块存储元素的区域；另一次则可能没那么频繁，那就是扩展deque的内部数组。deque的这种内存分配行为更加复杂，因而比vector的内存分配行为更加难以讨论明白。std::deque没有提供任何类似于std::vector的用于为其内部数据结构预先分配存储空间的reserve()成员函数。另外还有一个称为std::queue的容器适配器模板，而deque就是其默认实现。不过，无法保证这种用法具有优秀的内存分配性能。

std::deque中的插入和删除

std::deque不仅与std::vector具有相同的插入接口，它还有一个成员函数push_front()。下面这段程序会将一个deque赋值给另外一个deque。

1
2
3
4
std::deque<kvstruct> test_container;
std::vector<kvstruct> random_vector;
...
test_container = random_vector;

下面这段代码展示了如何使用一对迭代器将元素插入到deque中。

1
2
3
4
5
6
7
std::deque<kvstruct> test_container;
std::vector<kvstruct> random_vector;
...
test_container.insert(
    test_container.end(),
    random_vector.begin(),
    random_vector.end());

以下是三种使用push_back()将元素从vector复制到deque中的方法：

1
2
3
4
5
6
7
8
9
std::deque<kvstruct> test_container;
std::vector<kvstruct> random_vector;
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it)
    test_container.push_back(*it);
for (unsigned i = 0; i < nelts; ++i)
    test_container.push_back(random_vector.at(i));
for (unsigned i = 0; i < nelts; ++i)
    test_container.push_back(random_vector[i]);

开发人员很容易猜到这三个循环的性能开销大致是一样的。由于at()会进行额外的检查，因此它可能会稍微慢一点点。

使用insert()在末尾和前端插入元素的性能开销分别大约是push_back()和push_front()的性能开销的两倍。

现在让我们来对比一下std::vector和std::deque的性能。对于相同数量的元素，vector的赋值操作的性能是deque的 13 倍，删除操作的性能是deque的 22 倍，基于迭代器的插入操作的性能是deque的 9 倍，push_back()操作的性能是deque的两倍，使用insert()在末尾插入元素的性能则是deque的 3 倍。

std::list

std::list的“产品手册”如下。

  • 序列容器
  • 插入时间：任意位置的插入时间开销都是 O(1)
  • 排序时间： O(n log2n)
  • 查找时间： O(n)
  • 除非元素被移除了，否则迭代器和引用永远不会失效
  • 迭代器能够从后向前或是从前向后访问 list 中的元素

std::list与std::vector和std::deque有许多相同的特性。与vector和deque一样，插入一个元素到list末尾的时间开销是常量时间；与deque一样（但与vector不同），插入一个元素到list前端的时间开销是常量时间。而且，与vector和deque不同的是，通过一个指向插入位置的迭代器插入一个元素到list中间的时间开销是常量时间。与vector和deque一样，我们也可以对list高效地进行排序。但是与vector和deque不同的是，无法高效地查找list。最快的查找list的方法是使用std::find()，它的时间开销是 O(n)。

尽管复制或是创建std::list的开销可能是std::vector的 10 倍，但是与std::deque相比，它还是具有竞争力的。将元素插入到list末尾的开销不足vector的两倍。遍历和排序list的开销只比vector多了 30%。对于我测试过的大部分操作，std::list都比std::deque的效率更高。

std::list的一个优点是在拼接（O(1) 时间开销）和合并时无需复制链表元素。即使是像splice和sort这种操作也不会使std::list的迭代器失效。在list中间插入元素的时间开销是常数时间，因为程序已经知道要在哪里插入元素。因此，如果一个应用程序需要创建元素的集合并对它们进行这些操作，那么使用std::list会比std::vector更高效。std::list能够以一种简单且可预测的方式与内存管理器交互。当有需要时，list中的每个元素会被分别分配存储空间。在list中不存在未使用的额外的存储空间。

list中的每个元素所分配到的存储空间大小是相同的。这有助于提高复杂的内存管理器的工作效率，也降低了出现内存碎片的风险。我们还能够为std::list自定义简单的内存分配器，利用这个特性使其更高效地工作。

std::list中的插入和删除

除了开头的数据结构声明外，通过insert()、push_back()和push_front()将一个list复制到另一个list中的算法与vector和deque的代码清单中的算法是相同的。std::list的结构非常简单，编译器在编译过程中优化代码的余地很小。

在list末尾插入元素是构造list的最快方式；出于某些原因，甚至比=运算符函数更快。

遍历std::list

list没有下标运算符。遍历它的唯一方式是使用迭代器。

对std::list排序

std::list上的迭代器是双向迭代器，不如std::vector的随机访问迭代器功能强大。这些迭代器的一个很特别的特性是，找到两个双向迭代器之间的距离或是元素个数的性能开销是 O(n)。因此，使用std::sort()对std::list排序的时间开销是 O(n^2)。编译器的编译结果仍然是对list调用一次std::sort()，但性能可能远比开发人员所期待的差。
幸运的是，std::list有一种内置的更高效的排序方法，其时间开销是 O(n log2n)。

查找std::list

由于std::list只提供了双向迭代器，对于list，所有的二分查找算法的时间开销都是O(n)。另外， 使用std::find()查找list的时间开销也是 O(n)，其中n是list中元素的数量。因此，std::list不适合替代关联容器。

std::forward_list

std::forward_list的“产品手册”如下。

  • 序列容器
  • 插入时间：任意位置的插入开销都是 O(1)
  • 排序时间： O(n log2n)
  • 查找时间： O(n)
  • 除非元素被移除了，否则迭代器和引用永远不会失效
  • 迭代器从前向后访问元素

std::forward_list是一种性能被优化到极限的序列容器。它有一个指向链表头部节点的指针。它的设计经过了深思熟虑，标准库的设计人员希望使它尽量贴近手动编码实现的单向链表。它没有back()和rbegin()成员函数。

std::forward_list与内存管理器交互的方式非常简单，也是可预测的。当有需要时，前向链表会为每个元素单独分配内存。在前向链表中没有任何未使用的空间。前向链表中的每个元素所分配到的存储空间都是相同的。这有助于提高复杂的内存管理器的工作效率，也降低了出现内存碎片的风险。我们还能够为std::forward_list自定义简单的内存分配器，利用这个特性使其更高效地工作。

顾名思义，前向链表与链表的不同在于它只提供了前向迭代器。我们可以用普通的循环语句来遍历前向链表：

1
2
3
4
5
std::forward_list<kvstruct> flist;
// ...
unsigned sum = 0;
for (auto it = flist.begin(); it != flist.end(); ++it)
    sum += it->value;

不过，插入方法则不同。std::forward_list并没有提供insert()方法，取而代之的是insert_after()方法。std::forward_list没有提供before_begin()这样能够得到指向第一个元素之前的位置的迭代器：

1
2
3
4
5
6
std::forward_list<kvstruct> flist;
std::vector<kvstruct> vect;
// ...
auto place = flist.before_begin();
for (auto it = vvect.begin(); it != vect.end(); ++it)
    place = flist.insert_after(place, *it);

std::forward_list中的插入和删除

只要提供一个指向要插入位置之前的位置的迭代器，std::forward_list就能够以常量时间插入元素。std::forward_list还有一个push_front()。

遍历std::forward_list

std::forward_list没有下标操作符。遍历它的唯一方式是使用迭代器。

对std::forward_list排序

与std::list类似，std::forward_list也有一个时间开销为 O(n log2n) 的内置排序函数。

查找std::forward_list

由于std::forward_list只提供了前向迭代器，因此使用二分查找算法查找前向链表的时间开销是 O(n)。使用更加简单的std::find()进行查找的开销也是 O(n)，其中 n 是前向链表中元素中的数量。这使得前向链表难以替代关联容器。

std::map与std::multimap

std::map与std::multimap的“产品手册”如下。

  • 有序关联容器
  • 插入时间： O(log2n)
  • 索引时间：通过键进行索引的时间开销为 O(log2n)
  • 除非元素被移除，否则迭代器和引用永远不会失效
  • 利用迭代器对元素进行正向排序或是反向排序

std::map可以将键类型的实例映射为某个值类型的实例。std::map与std::list一样，是一种基于节点的数据结构。不过，map会根据键的值对节点排序。map的内部实现是一棵带有便于使用迭代器遍历的额外链接的平衡二叉树

map为每个元素分配的存储空间的大小是相同的。这有助于提高复杂的内存管理器的工作效率，也降低了出现内存碎片的风险。我们还能够为std::map自定义简单的内存分配器，利用这个特性使其更高效地工作。

std::map中的插入和删除

由于需要遍历map的内部树来找到插入位置，因此向map中插入一个元素的时间开销通常是 O(log2n)。std::map提供了另外一个版本的insert()函数，该函数接收一个额外的map迭代器作为参数，利用这个参数提示map在迭代器所指向的位置插入元素会更高效。如果这种提示是最优的，那么插入操作的均摊时间开销会降低为 O(1)。

1
2
3
4
5
6
7
ContainerT test_container;
std::vector<kvstruct> sorted_vector;
...
std::stable_sort(sorted_vector.begin(), sorted_vector.end());
auto hint = test_container.end();
for (auto it = sorted_vector.rbegin(); it != sorted_vector.rend(); ++it)
    hint = test_container.insert(hint, value_type(it->key, it->value));

一种常用的编程惯用法是在程序中先检查某个键是否存在于map中，然后根据结果进行相应的处理。当这些处理涉及插入或是更新键所对应的值时，那么就可能进行性能优化。理解性能优化的关键在于，由于需要先检查键是否存在于map中，然后再找到插入位置，因此map::find()和map::insert()的时间开销都是 O(log2n)。这两种操作都会遍历map的二叉树数据结构中的相同的节点：

1
2
3
4
5
6
7
8
9
iterator it = table.find(key); // O(log n)
if (it != table.end()) {
    // 找到key的分支
    it->second = value;
}
else {
    // 没有找到key的分支
    it = table.insert(key, value); // O(log n)
}

如果程序程序能够得到第一次查找的结果，那么就能够将其作为对insert()的提示，将插入操作的时间开销提高到 O(1)。取决于程序的需求，有两种方法能够实现这个惯用法。如果只要知道是否找到了键即可，那么可以使用返回pair的版本的insert()。在被返回的pair中保存的是一个指向找到或是插入的元素的迭代器以及一个布尔型变量，当这个布尔型变量为 true 时表示该元素被找到了，而当这个布尔型变量为 false 时表示该元素是被插入的。当程序在检查元素是否存在于map之前知道如何初始化元素，或是更新值的性能开销并不大时，这种方法非常有效：

1
2
3
4
5
6
7
std::pair<value_t, bool> result = table.insert(key, value);
if (result.second) {
// k找到key的分支
}
else {
// 没有找到key的分支
}

对std::map排序

map本来就是有序的。使用迭代器遍历一个map会按照键和查找谓词的顺序访问元素。请注意，只有将所有的元素都从一个map中复制到另一个map中，才能对map重排序。

std::set与std::multiset

std::set与std::multiset的“产品手册”如下。

  • 有序关联容器
  • 插入时间： O(log2n)
  • 索引时间：通过键进行索引，时间开销为 (log2n)
  • 除非移除元素，否则迭代器和引用永远不会失效
  • 迭代器能够按照正序或反序遍历元素

std::map与std::set之间的一个不同点是查找方法返回的元素是 const 的。这其实并不是什么大问题。如果你真的想使用set，可以将与排序关系无关的值类型的字段声明为mutable，指定它们不参与排序。

std::unordered_map与std::unordered_multimap

std::unordered_map与std::unordered_multimap的“产品手册”如下。

  • 无序关联容器。
  • 插入时间：平均时间开销为 O(1)，最差情况时间开销为 O(n)。
  • 索引时间：通过键索引的平均时间开销为 O(1)，最差情况时间开销为 O(n)。
  • 再计算散列值时迭代器会失效；只有在移除元素后引用才会失效。
  • 可以独立于大小（size）扩大或是缩小它们的容量（capacity）。

std::unordered_map能够将键类型的实例映射到某个值类型的实例上。这种方式与std::map相似。不过，映射的完成过程不同。std::unordered_map被实现为了一个散列表。键会被转换为一个整数散列值，使用这个散列值能够以分摊平均常量时间的性能开销从unordered_map中查找到值。

与std::string一样， C++ 标准也限制了std::unordered_map的实现。因此，尽管有多种方式能够实现散列表，但是只有采用了动态分配内存的骨干数组，然后在其中保存指向动态分配内存的节点组成的链表的桶的设计，才有可能符合标准定义。

unordered_map的构造是昂贵的。它包含了为表中所有元素动态分配的节点，另外还有一个会随着表的增长定期重新分配的动态可变大小的桶数组。因此，要想改善它的查找性能，需要消耗相当多的内存。每次桶数组重新分配时，迭代器都会失效。不过，只有在删除元素时，指向元素节点的引用才会失效。

unordered_map中元素的数量就是它的大小。计算出的size / buckets比例称为负载系数（load factor）。负载系数大于 1.0 表示有些桶有一条多个元素链接而成的元素链，降低了查询这些键的性能。在实际的散列表中，即使负载系数小于1.0，键之间的冲突也会导致形成元素链。负载系数小于 1.0 表示存在着未被使用，但却在unordered_map的骨干数组中占用了存储空间的桶（换言之，非最小散列）。当负载系数小于 1.0 时， (1 – 负载系数 ) 的值是空桶数量的下界，但是由于散列函数可能非完美，因此未使用的存储空间通常更多。

负载系数在unordered_map中是一个因变数。我们能够在程序中观察到它的值，但是无法在重新分配内存后直接设置或是预测它的值。当一条元素被插入到unordered_map中后，如果负载系数超过了程序指定的最大负载系数值，那么桶数组会被重新分配，所有的元素都被会重新计算散列值，这个值会被保存在新数组的桶中。由于桶数量的增长总是因负载系数大于 1 而引起的，因此插入操作的均摊时间开销 O(1)。当最大负载系数大于 1.0 这个默认值时，插入操作和查找操作的性能会显著降低。通过将最大负载系数降低到 1.0 以下能够适度地提高程序性能。

调用reserve(size_t n)可以确保在重新分配骨干数组之前预留出足够的空间来保存n条元素。这等价于调用rehash(ceil(n/max_load_factor()))。

调用unordered_map的clear()成员函数会清除所有的元素，并将所有存储空间返回给内存管理器。这与vector或是string的clear()成员函数相比是一种更有力的承诺。

std::unordered_map中的插入与删除

与std::map类似，std::unordered_map也提供了两种插入方法：带插入提示的和不带插入提示的。但与map不同的是，unordered_map并不使用插入提示。这只是一种接口兼容性。

遍历std::unordered_map

代码是一段遍历std::unordered_map的代码。

1
2
3
4
5
for (auto it = test_container.begin();
    it != test_container.end();
    ++it) {
    sum += it->second;
}

顾名思义，unordered_map无法被排序，使用迭代器遍历unordered_map中元素的顺序也是无规则的。

小结

  • 斯特潘诺夫的标准模板库是第一个可复用的高效容器和算法库。
  • 各容器类的大 O 标记性能并不能反映真实情况。有些容器比其他容器快许多倍。
  • 在进行插入、删除、遍历和排序操作时std::vector都是最快的容器。
  • 使用 std::lower_bound查找有序 std::vector的速度可以与查找 std::map的速度相匹敌。
  • std::deque 只比 std::list 稍快一点。
  • std::forward_list 并不比 std::list 更快。
  • 散列表 std::unordered_map 比std::map更快，但是相比所受到的开发人员的器重程度，
    它并没有比std::map快上一个数量级。
  • 互联网上有丰富的类似标注库容器的容器资源。

优化I/O

读取文件的秘诀

代码是一个将文件读取到字符串中的简单函数，在解析 XML 或是 JSON 前经常会出现这样的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::string file_reader(char const* fname) {
    std::ifstream f;
    f.open(fname);
    if (!f) {
        std::cout << "Can't open " << fname
        << " for reading" << std::endl;
        return "";
    }
    std::stringstream s;
    std::copy(std::istreambuf_iterator<char>(f.rdbuf()),
    std::istreambuf_iterator<char>(),
    std::ostreambuf_iterator<char>(s) );
    return s.str();
}

fname是文件名。如果打不开文件，file_reader()会打印一条错误信息到标准输出中并返回空字符串。否则，std::copy()会将f的流缓冲区复制到std::stringstream s的流缓冲区中。

创建一个吝啬的函数签名

从库设计的角度看，file_reader()是可以改善的。它做了几件不同的事情：打开文件；进行错误处理（以报告打开文件出错的形式）；读取已打开且有效的流到字符串中。作为一个库函数，这几种职责混合在一起使得调用方难以使用file_reader()函数。

file_reader()同样还会分配一块新的内存并返回它，这里存在一个潜在的问题，因为这会导致返回值在调用链中传递的时候发生多次复制。如果文件无法打开，file_reader()会返回空字符串。如果文件能够打开，但是其中一个字符都没有，那么它也会返回一个空字符串。

代码：带有吝啬函数签名的stream_read_streambuf_stringstream()

1
2
3
4
5
6
7
8
9
void stream_read_streambuf_stringstream(
    std::istream& f,
    std::string& result) {
    std::stringstream s;
    std::copy(std::istreambuf_iterator<char>(f.rdbuf()),
    std::istreambuf_iterator<char>(),
    std::ostreambuf_iterator<char>(s) );
    std::swap(result, s.str());
}

stream_read_streambuf_stringstream()的最后一行将result的动态存储空间与s.str()的动态存储空间进行了交换。std::swap()对许多标准库类的特化实现都是调用它们的swap()成员函数。该成员函数会交换指针，这远比内存分配和复制操作的开销小。吝啬的回报是f变成了std::istream，而不是std::ifstream。

客户端代码可以如下这样调用stream_read_streambuf_stringstream()：

1
2
3
4
5
6
7
8
9
10
std::string s;
std::ifstream f;
f.open(fname);
if (!f) {
    std::cerr << "Can't open " << fname
    << " for reading" << std::endl;
}
else {
    stream_read_streambuf_stringstream(f, s);
}

更大的吞吐量——使用更大的输入缓冲区

C++ 流包含一个继承自std::streambuf的类，用于改善从操作系统底层以更大块的数据单位读取文件时的性能。数据会被读取到streambuf的缓冲区中。

1
2
3
4
std::ifstream in8k;
in8k.open(filename);
char buf[8192];
in8k.rdbuf()->pubsetbuf(buf, sizeof(buf));

更大的吞吐量——一次读取一行

我们有理由猜测使用逐行读取文件的函数能够减少函数调用次数，最好是在内部使用逐行读取或是填充缓冲区的接口。除此之外，如果不会频繁地更新结果字符串，那么复制和重新分配存储空间的次数也会较少。确实，在标准库中就有一个叫作getline()的函数。

1
2
3
4
5
6
void stream_read_getline(std::istream& f, std::string& result) {
    std::string line;
    result.clear();
    while (getline(f, line))
        (result += line) += "\n";
}

stream_read_getline()会将读取的字符串添加到result中。result的内容必须在最开始被清空，因为当它被传递给这个函数时，函数并不要求它里面没有保存任何内容。clear()不会将字符串的动态缓冲区返回给内存管理器，它只是设置字符串的长度为 0。根据在函数调用之前使用这个字符串参数的情况，可能它已经有一个大块的动态缓冲区了，这样能够减小分配存储空间的性能开销。

优化并发

复习并发

并发是多线程控制的同步（或近似同步）执行。并发的目标并不是减少指令执行的次数或是每秒访问数据的次数。相反，它是通过提高计算资源的使用率来减少程序运行的时间的。

并发通过在其他程序活动等待事件发生或是资源变为可用状态时，允许某些程序活动向前执行来提高程序性能。这样能够增加计算资源的使用时间。C++ 为共享内存的基于线程的并发提供了一个库。

并发概述

最著名的几种并发形式如下。

时间分割（time slicing）：这是操作系统中的一个调度函数。操作系统是依赖于处理器和硬件的。它会使用计时器和周期性的中断来调整处理器的调度。C++ 程序并不知道它被时间分割了。

虚拟化（Virtualization）：一种常见的虚拟化技术是让一个称为“hypervisor”的轻量级操作系统将处理器的时间块分配给客户虚拟机。当 hypervisor 运行客户虚拟机后，某些处理器指令和对内存区域的某些访问会产生 Trap（陷入），并将它下传给hypervisor，这将允许 hypervisor 竞争 I/O 设备和其他硬件资源。

虚拟化技术的优点如下。

  • 客户虚拟机是在运行时被打包为磁盘文件的，因此我们能够对客户虚拟机设置检查点（checkpoint），保存客户虚拟机，加载和继续执行客户虚拟机，以及在多台主机上运行客户虚拟机。
  • 只要资源允许，我们能够并发地运行多台客户虚拟机。hypervisor 会与计算机虚拟内存保护硬件共同协作，隔离这些客户虚拟机。
  • 我们能够配置客户虚拟机使用主机的一部分资源（物理内存、处理器核心）。计算资源能够根据每台客户虚拟机上正在运行的程序的需求“量体裁衣”，确保并发地在同一硬件上运行的多台虚拟机保持性能稳定，并防止它们之间意外地发生交互。

容器化（containerization）：容器化与虚拟化的相似之处在于，容器中也有一个包含了程序在检查点的状态的文件系统镜像和内存镜像；不同之处在于容器主机是一个操作系统，这样能够直接地提供 I/O和系统资源，而不必通过 hypervisor 去较低效地竞争资源。

对称式多处理（symmetric multiprocessing）：对称式多处理器（symmetric multiprocessor）是一种包含若干执行相同机器代码并访问相同物理内存的执行单元的计算机。现代多核处理器都是对称式多处理器。当前正在执行的程序和系统任务能够运行于任何可用的执行单元上，尽管选择执行单元可能会给性能带来影响。

对称式多处理器使用真正的硬件并发执行多线程控制。如果对称式多处理器有 n 个执行单元，那么一个计算密集型程序的执行时间最多可以被缩短为 1/n。

同步多线程（simultaneous multithreading）：有些处理器的硬件核心有两个（或多个）寄存器集，可以相应地执行两条或多条指令流。当一条指令流停顿时（如需要访问主内存），处理器核心能够执行另外一条指令流上的指令。具有这种特性的处理器核心的行为就像是有两个（或多个）核心一样，这样一个“四核处理器”就能够真正地处理八个硬件线程。

多进程：进程是并发的执行流，这些执行流有它们自己的受保护的虚拟内存空间。进程之间通过管道、队列、网络 I/O 或是其他不共享的机制进行通信。线程使用同步原语或是通过等待输入（即发生阻塞直至输入变为可用状态）来进行同步。

复习C++并发方式

线程

<thread>头文件提供了std::thread模板类，它允许程序创建线程对象作为操作系统自身的线程工具的包装器。std::thread的构造函数接收一个可调用对象（函数指针、函数对象、lambda或是绑定表达式）作为参数，并会在新的软件线程上下文中执行这个对象。C++ 使用可变模板参数转发“魔法”调用带有可变参数列表的函数，而底层操作系统的线程调用通常接收一个指向带有void*参数的void函数的指针作为参数。

std::thread是一个用于管理操作系统线程的 RAII（资源获取即初始化）类。它有一个返回操作系统原生线程处理句柄的get()成员函数，程序可以使用该处理句柄访问操作系统中更丰富的作用于线程上的函数集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
void f1(int n) {
    std::cout << "thread " << n << std::endl;
}
void thread_example() {
    std::thread t1; // 线程变量，不是一个线程
    t1 = std::thread(f1, 1); // 将一个线程赋值给线程变量
    t1.join(); // 等待线程结束
    std::thread t2(f1, 2);
    std::thread t3(std::move(t2));
    std::thread t4([]() { return; });// 也可以与lambda表达式配合使用
    t4.detach();
    t3.join();
}

线程t1会被初始化为一个空线程。由于每个线程都有一个唯一的指向底层资源的句柄，因此线程无法被复制，但是我们能够使用移动赋值运算符将一个右值赋值给空线程。t1可以拥有任何一个执行接收一个整数参数的函数的线程。std::thread的构造函数接收一个指向f1的函数指针和一个整数作为参数。第二个参数会被转发给在std::thread的构造函数中启动的可调用对象（f1）。

线程t2是用同一个函数但是不同参数启动的。线程t3是一个移动构造函数的示例。在被移动构造后，t3运行的是作为t2启动的线程，t2变为了空线程。线程t4展示了如何使用lambda表达式作为线程的可调用对象启动线程。

std::thread代表的操作系统线程必须在std::thread被销毁之前被销毁掉。我们可以像t3.join()这样加入线程，这表示当前线程会等待被加入的线程执行完毕。我们可以像t4.detach()这样将操作系统线程从std::thread对象中分离出来。在这种情况下，线程会继续执行，但对启动它的线程来说变成了不可见的。当被分离线程的可调用对象返回时它就会结束。如果可调用对象不会返回，那么就会发生资源泄露，被分离的线程会继续消耗资源，直到整个程序结束。

如果在std::thread被销毁前既没有调用过join()也没有调用过detach()，它的析构函数会调用terminate()，整个程序会突然停止。尽管我们能够直接使用std::thread，但是使用基于它编写出更加优秀的工具的话，可能有助于提高生产率。函数对象返回的任何值都会被忽略。函数对象抛出的异常会导致terminate()被调用，使程序无条件地突然停止。

promise和future

C++ 中的std::promise模板类和std::future分别是一个线程向另外一个线程发送和接收消息的模板类。promise和future允许线程异步地计算值和抛出异常。promise和future共享一个称为共享状态（shared state）的动态分配内存的变量，这个变量能够保存一个已定义类型的值，或是在标准包装器中封装的任意类型的异常。一个执行线程能够在future上被挂起，因此future也扮演着同步设备的角色。

C++<future>头文件中包含promise和future的功能。std::promise模板的实例允许线程将共享状态设置为一个指定类型的值或是一个异常。发送线程并不会等待共享状态变为可读状态，它能够立即继续执行。

promise的共享状态直到被设置为一个值或是一个异常后才就绪。共享状态必须且只能被设置一次，否则会发生以下情况。

  • 如果某个线程多次试图将共享状态设置为一个值或是一个异常，那么共享状态将会被设置为std::future_error异常，错误代码是promise_already_satisfied，而且共享状态变为就绪状态，为释放所有在promise上等待的future做好准备。
  • 如果某个线程从来没有将共享状态设置为一个值或是一个异常，那么在promise被销毁时，它的析构函数会将共享状态设置为std::future_error异常，错误代码是broken_promise，而且共享状态变为就绪状态，为释放所有在promise上等待的future做好准备。

要想获得这个有用的错误提示，我们必须在线程的可调用对象中销毁promise。

std::future允许线程接收保存在promise的共享状态中的值或是异常。future是一个同步原语，接收线程会在对future的get()成员函数的调用中挂起，直到相应的promise设置了共享状态的值或是异常，变为就绪状态为止。

在被构造出来或是通过promise赋值后，future才是有效的。在future无效时，接收线程是无法在future上挂起的。future必须在发送线程被执行之前通过promise构造出来。否则，接收线程会试图在future变为有效之前在它上面挂起。

promise和future无法被复制。它们是代表特定通信集结点的实体。我们能构造和移动构造它们，可以将一个promise赋值给一个future。理想情况下，promise是在发送线程中被创建的，而future则是在接收线程中被创建的。有一种编程惯用法是在发送线程中创建promise，然后使用std::move(promise)将其作为右值引用传递给接收线程，这样它的内容就会被移动到属于接收线程的promise中。开发人员可以使用std::async()来做到这一点。

1
2
3
4
5
6
7
8
9
void promise_future_example() {
    auto meaning = [](std::promise<int>& prom) {
        prom.set_value(42); // 计算"meaning of life"
    };
    std::promise<int> prom;
    std::thread(meaning, std::ref(prom)).detach();
    std::future<int> result = prom.get_future();
    std::cout << "the meaning of life: " << result.get() << "\n";
}

promise的prom在std::thread被调用之前被创建出来了。这种写法并不完美，因此它没有考虑broken_promise的情况。尽管如此，但这是有必要的，因为如果没有在线程开始之前构造出prom，就无法确保在调用result.get()之前future的result是有效的。程序接着构造出一个匿名std::thread。它有两个参数，一个是lambda表达式meaning，它是待执行的可调用对象；另一个是promise类型的变量prom，它是传给meaning使用的参数。请注意，由于prom是一个引用参数，因此必须将其包装在std::ref()中才能使参数转发正常工作。调用detach()函数会从被销毁的匿名std::thread中分离出正在运行的线程。

现在正在发生两件事情：一件是操作系统正在为执行meaning做准备，另一件是程序正在创建future类型的result。程序可能会在线程开始运行之前执行prom.get_future()。这就是在构造出线程之前先创建prom的原因——这样future是有效的，程序会挂起等待线程。

程序会在result.get()中挂起，等待线程设置prom的共享状态。线程调用prom.set_value(42)，让共享状态就绪并释放程序。程序在输出” the meaning of life:42”后结束。

异步任务

C++ 标准库任务模板类在 try 语句块中封装了一个可调用对象，并将返回值或是抛出的异常保存在promise中。任务允许线程异步地调用可调用对象。C++ 标准库中的基于任务的并发只是一个半成品。C++11 提供了将可调用对象包装为任务，并在可复用的线程上调用它的async()模板函数。async()有点像“上帝函数”，它隐藏了线程池和任务队列的许多细节。

在 C++ 标准库<future>头文件中定义了任务。std::packaged_task模板类能够包装任意的可调用对象，使其能够被异步调用。packaged_task自身也是一个可调用对象，它可以作为可调用对象参数传递给std::thread。与其他可调用对象相比，任务的最大优点是一个任务能够在不突然终止程序的情况下抛出异常或返回值。任务的返回值或抛出的异常会被存储在一个可以通过std::future对象访问的共享状态中。

1
2
3
4
5
6
7
8
void promise_future_example_2() {
    auto meaning = std::packaged_task<int(int)>(
    [](int n) { return n; });
    auto result = meaning.get_future();
    auto t = std::thread(std::move(meaning), 42);
    std::cout << "the meaning of life: " << result.get() << "\n";
    t.join();
}

packaged_task类型的变量meaning包含一个可调用对象和一个std::promise。这解决了在线程的上下文中调用promise的析构函数的问题。请注意meaning中的lambda表达式只是简单的返回参数，设定promise的部分被优雅地隐藏起来了。

在本例中，程序加入（join）了线程，而不是分离（detach）它。尽管在这个例子中并没有体现得特别明显，但是在主程序得到future的值后，主程序和线程都能继续并发地执行。<async>库提供了一个基于任务的工具——std::async()。模板函数std::async()执行一个可调用对象参数，这个可调用参数可能是在新线程的上下文中被执行的。不过，std::async()返回的是一个std::future，它既能够保存一个返回值，也能够保存可调用对象抛出的异常。而且，有些实现方式可能会为了改善性能而选择在线程池外部分配std::async()线程。

1
2
3
4
5
void promise_future_example_3() {
    auto meaning = [](int n) { return n; };
    auto result = std::async(std::move(meaning), 42);
    std::cout << "the meaning of life: " << result.get() << "\n";
}

这里定义了lambda表达式meaning，并且将lambda表达式的参数传递给了std::async()。这里使用了类型推导来决定std::async()的模板参数。std::async()返回一个能够得到一个整数值或是一个异常的future，它会被移动到result中。result.get()的调用会挂起，直到std::async()调用的线程通过返回它的整数型参数设置它的promise。线程终止是由std::async()负责的，它可能会将线程保留在线程池中。

互斥量

<mutex>头文件包含了四种互斥量模板。

  • std::mutex一种简单且相对高效的互斥量。
  • std::recursive_mutex：一种线程能够递归获取的互斥量，就像函数的嵌套调用一样。由于该类需要对它被获取的次数计数，因此可能稍微低效。
  • std::timed_mutex：允许在一定时间内尝试获取互斥量。要想在一定时间内尝试获取互斥量，通常需要操作系统的介入，导致与std::mutex相比，这类互斥量的延迟显著地增大了。
  • std::recursive_timed_mutex：一种能够在一定时间内递归地获取的互斥量。这类互斥量很“美味”，但是开销也非常昂贵。

锁

获取互斥量也被称为锁住互斥量，释放互斥量也被称为解锁互斥量。在 C++ 中，互斥量的获取互斥量的成员函数的名字叫作lock()。C++ 标准库提供了一种简单的用于获得单个互斥量的锁，还提供了一种更加通用的用于获得多个互斥量的锁。后者实现了一种避免死锁的算法。在<mutex>头文件中有两个锁模板。

  • std::lock_guard：一种简单的 RAII 锁。在这个类的构造过程中，程序会等待直到获得锁；而在析构过程中则会释放锁。这个类的预标准实现通常被称为scope_guard。
  • std::unique_lock：一个通用的互斥量所有权类，提供了 RAII 锁、延迟锁、定时锁、互斥量所有权的转移和条件变量的使用。

在 C++14 的<shared_mutex>头文件中加入了共享互斥量的锁。

  • std::shared_lock：共享（reader/writer）互斥量的一个互斥量所有权类。它提供了std::unique_lock的所有复杂特性，另外还有共享互斥量的控制权。一个单独的线程能够以排他模式锁住一个共享互斥量来原子性地更新数据结构。多个线程能够以共享模式锁住一个共享互斥量来原子性地读取数据结构，但是在所有的读取者都释放互斥量之前无法以排他模式锁住它。

条件变量

一个监视器在多线程之间共享一个数据结构。当一个线程成功地进入监视器后，它就拥有一个允许它更新共享数据结构的互斥量。线程可能会在更新共享数据结构后退出监视器，放弃它的排他访问权限。它也可能会阻塞在一个条件变量上，暂时地放弃排他访问权限直到这个条件变量变为特定的值。

一个监视器可以有一个或多个条件变量。每个条件变量都表示数据结构中一个概念上的状态改变事件。当运行于监视器中的一个线程更新数据结构时，它必须通知所有会受到这次更新影响的条件变量，它们所表示的事件发生了。

C++ 在<condition_variable>头文件中提供了条件变量的两种实现方式。它们之间的区别在于所接收的参数锁的一般性。

  • std::condition_variable：最高效的条件变量，它需要使用std::unique_lock来锁住互斥量。
  • std::condition_variable_any：一种能够使用任何BasicLockable锁（即任何具有lock()和unlock()成员函数的锁）的条件变量。该条件变量可能会比std::condition_variable低效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void cv_example() {
    std::mutex m;
    std::condition_variable cv;
    bool terminate = false;
    int shared_data = 0;
    int counter = 0;
    auto consumer = [&]() {
        std::unique_lock<std::mutex> lk(m);
        do {
            while (!(terminate || shared_data != 0))
                cv.wait(lk);
            if (terminate)
                break;
            std::cout << "consuming " << shared_data << std::endl;
            shared_data = 0;
            cv.notify_one();
        } while (true);
};
    auto producer = [&]() {
        std::unique_lock<std::mutex> lk(m);
        for (counter = 1; true; ++counter) {
            cv.wait(lk,[&]() {return terminate || shared_data == 0;});
            if (terminate)
                break;
            shared_data = counter;
            std::cout << "producing " << shared_data << std::endl;
            cv.notify_one();
        }
    };
    auto p = std::thread(producer);
    auto c = std::thread(consumer);
    std::this_thread::sleep_for(std::chrono::milliseconds(1000));
    {
        std::lock_guard<std::mutex> l(m);
        terminate = true;
    }
    std::cout << "total items consumed " << counter << std::endl;
    cv.notify_all();
    p.join();
    c.join();
    exit(0);
}

生产者通过将一个名为shared_data的整数变量设为非零值来进行“生产”。消费者通过将其重新设置为零来“消费”shared_data。主程序线程会启动生产者和消费者，接着打一个 1000 毫秒的盹。当主线程醒来后，它会锁住互斥量m短暂地进入监视器，接着设置terminate标识位，这会使生产者线程和消费者线程都退出执行。主程序通知条件变量terminate的状态发生了改变，加入两个线程并退出。

消费者通过锁住互斥量m进入监视器。消费者是一个挂起在名为cv的条件变量上的单层循环。当它挂起在cv上时，消费者不在监视器内，互斥量m是可用的。当没有东西可以消费时，cv会收到通知。消费者会醒来，重新锁住互斥量m并从它对cv.wait()的调用中返回，在概念上重新进入监视器。

消费者通常等待的更新是shared_data != 0，但它也需要在terminate == true时醒来。这是对同步原语的合理使用。另外一种类似的情况是使用一个条件变量唤醒消费者，使用另一个条件变量唤醒生产者。消费者在一个循环中调用cv.wait()，每次醒来时都会检查是否满足了合适的条件。这是因为有些实现能够在不合适的时候假装意外地唤醒等待条件变量变为合适值的线程。如果条件满足了，那么退出while循环。如果唤醒消费者的条件是terminate == true，那么消费者会退出外层循环并返回。否则，条件就是shared_data != 0。消费者会打印出一条消息，接着通过设置shared_data为 0 表示它已经消费了数据并通知cv共享数据发生了变化。在这时，消费者仍然在监视器内，持有加在互斥量m上的锁，但它会继续循环，再次进入cv.wait()，释放互斥量并在概念上退出监视器。

生产者也是类似的。它会挂起，直到它看到了加在互斥量m上的锁，然后它会进入到外层循环中，直到它看到了terminate == true。生产者会等待cv状态发生改变。在本例中，生产者使用了一个接收谓词（predicate）作为参数的版本的wait()，这会导致一直循环直至判断式为 false。因此谓词就是在通知条件变量中隐藏的条件。

共享变量上的原子操作

C++ 标准库<atomic>头文件提供了用于构建多线程同步原语的底层工具：内存栅栏和原子性的加载与存储。std::atomic提供了一种更新任意数据结构的标准机制，前提条件是这种数据结构有可用的复制构造函数或是移动构造函数。std::atomic的任何特化实现都必须为任意类型T提
供以下函数。

  • std::atomic<T>提供了成员函数T load(memory_order)，它可以原子性地复制T对象到std::atomic<T>外部。
  • std::atomic<T>提供了成员函数store(T, memory_order)，它可以原子性地复制T对象到std::atomic<T>内部。
  • is_lock_free()：如果在这个类型上定义的所有的操作的实现都没有使用互斥，is_lock_free()返回true，就如同是使用一条单独的读 - 改 - 写机器指令进行操作一样。

std::atomic为整数和指针类型提供了特化实现。只要处理器支持，这些特化不调用操作系统的同步原语就能够同步内存。这些特化实现提供了一组能够在现代硬件上实现的原子性操作。

std::atomic的性能取决于编译代码的处理器。

  • Intel 架构的 PC 具有丰富的读 - 改 - 写指令，原子性访问的性能开销取决于内存栅栏，其中部分栅栏完全没有性能开销。
  • 在有读 - 改 - 写指令的单核心处理器上，std::atomic可能根本不会生成任何额外代码。
  • 在没有原子性的读 - 改 - 写指令的处理器上，std::atomic可能是用昂贵的互斥实现的。

std::atomic的许多成员函数都会接收一个可选参数memory_order，它会选择一个围绕在操作上下的栅栏。如果没有提供memory_order参数，它的默认值是memory_order_acq_rel。

内存栅栏通过多个硬件线程的高速缓存来同步主内存。通常，在一个线程与另一个线程同步时，这两个线程上都会加上内存栅栏。在 C++ 中能够使用以下内存栅栏。

  • memory_order_acquire：你可以将memory_order_acquire理解为“通过其他线程完成所有工作”的意思。它确保随后的加载不会被移动到当前的加载或是前面的加载之前。自相矛盾的是，它是通过等待在处理器和主内存之间的当前的存储操作完成来实现这一点的。如果没有栅栏，当一次存储还处于处理器和主内存之间，它的线程就在相同的地址进行了一次加载时，该线程会得到旧的数据，仿佛这次在程序中加载被移动到了存储之前。memory_order_acquire可能会比默认的完全栅栏高效。例如，在原子性地读取在繁忙等待while循环中的标识位时，可以使用memory_order_acquire。
  • memory_order_release：你可以将memory_order_release理解为“通过这个线程将所有工作释放到这个位置”的意思。它确保这个线程完成的之前的加载和存储不会被移动到当前的存储之后。它是通过等待这个线程内部的当前存储操作完成来实现这一点的。memory_order_release可能会比默认的完全栅栏高效。例如，在自定义的互斥量的尾部设置标识位时，可以使用memory_order_release。
  • memory_order_acq_rel：这会结合之前的两种“确保”，创建一个完全栅栏。
  • memory_order_consume：memory_order_consume是memory_order_acquire的一种弱化（但更快）的形式，它只要求当前的加载发生在其他依赖这次加载数据的操作之前。例如，当一个指针的加载被标记为memory_order_consume时，紧接着的解引这个指针的操作就不会被移动它之前。
  • memory_order_relaxed：使用这个值意味着允许所有的重新排序。

优化多线程C++程序

用std::async替代std::thread

从性能优化的角度看，std::thread有一个非常严重的问题，那就是每次调用都会启动一个新的软件线程。启动线程时，直接开销和间接开销都会使得这个操作非常昂贵。

  • 直接开销包括调用操作系统为线程在操作系统的表中分配空间的开销、为线程的栈分配内存的开销、初始化线程寄存器组的开销和调度线程运行的开销。如果线程得到了一份新的调度量子（scheduling quantum），在它开始执行之前会有一段延迟。如果它得到了其他正在被调用线程的调度量子，那么在存储正在被调用线程的寄存器时会发生延迟。
  • 创建线程的间接开销是增加了所使用的内存总量。每个线程都必须为它自己的函数调用栈预留存储空间。如果频繁地启动和停止大量线程，那么在计算机上执行的线程会竞争访问有限的高速缓存资源，导致高速缓存发生抖动。
  • 当软件线程的数量比硬件线程的数量多时会带来另外一种间接开销。由于需要操作系统进行调度，因此所有线程的速度都会变慢。

thread内部的空函数会立即返回。这是可能的最短的函数。调用join()会让主线程等待thread结束，导致线程调用变为了“端到端”，没有任何并发。如果不是为了测量线程的启动开销而有意为之，那么它就是一个糟糕的并发设计。

1
2
3
std::thread t;
t = std::thread([]() { return; });
t.join();

尽管切换线程的有些开销（保存和恢复寄存器并刷新和重新填充高速缓存）是相同的，但可以移除或减少为线程分配内存以及操作系统调度线程等其他开销。模板函数std::async()会运行线程上下文中的可调用对象，但是它的实现方式允许复用线程。从 C++ 标准来看，std::async()可能是使用线程池的方式实现的。

1
std::async(std::launch::async, []() { return; });

async()会返回一个std::future，在这种情况下它是一个匿名临时变量。只要std::async()一返回，程序就会立即调用这个匿名std::future的析构函数。析构函数会等待该future变为就绪状态，因此它可以抛出所有会发生的异常。这里不需要显式地调用join()或是detach()。

实现任务队列和线程池

在面向任务的编程中，程序是一组可运行任务（runnable task）对象的集合，这些任务由线程池中的线程负责执行。当一个线程变为可用状态后，它会从任务队列中取得一个任务并执行。执行完任务后，线程并不会终止，而是要么继续做下一个任务，要么挂起，等待新任务的到来。面向任务的编程有以下几个优点。

  • 面向任务的编程能够通过非阻塞 I/O 调用高效地处理 I/O 完成事件，提高处理器的利用率。
  • 使用线程池和任务队列能够移除为短周期任务启动线程的间接开销。
  • 面向任务的编程将异步处理集中在一组数据结构中，因此容易限制使用中的线程的数量。

面向任务的编程的一个缺点是控制返转（inversion of control）。控制流不再由程序指定，而是变为事件消息接收的顺序。

在单独的线程中执行I/O

磁盘转速和网络连接距离等物理现实问题造成在程序请求数据和数据变为可用状态之间存在着延迟。因此， I/O 是适用并发的绝佳位置。另外一个典型的 I/O 问题是，程序在写数据之前或是读数据之后必须对它进行转换。

优化内存管理

复习C++内存管理器API

动态变量的生命周期

动态变量有五个唯一的生命阶段。最常见的 new 表达式的各种重载形式执行分配和放置生命阶段。在使用阶段后， delete 表达式会执行销毁和释放阶段。C++ 提供了单独管理每个阶段的方法。

  • 分配：程序要求内存管理器返回一个指向至少包含指定数量未类型化的内存字节的连续内存地址的指针。如果没有足够的可用内存，那么分配将会失败。
  • 放置：程序创建动态变量的初始值，将值放置到被分配的内存中。如果变量是一个类的实例，那么它的构造函数之一将会被调用。如果变量是一个简单类型，那么它可能会被初始化。如果构造函数抛出异常，那么放置会失败，需要将被分配的存储空间返回给内存管理器。new 表达式参与这个阶段。
  • 使用：程序从动态变量中读取值，调用动态变量的成员函数并将值写入到动态变量中。
  • 销毁：如果变量是一个类实例，那么程序会调用它的析构函数对动态变量执行最后的操作。析构对动态变量而言是一次机会，它可以趁机返回持有的所有系统资源，完成所有清理工作。如果析构函数抛出一个在析构函数体内不会处理的异常，析构会失败。若发生了这种情况，程序会无条件终止。
  • 释放：程序将属于被销毁的动态变量的存储空间返回给内存管理器。

内存管理函数分配和释放内存

C++ 提供了一组内存管理函数，而不是 C 中简单的malloc()和free()。重载new()运算符能够为任意类型的单实例分配存储空间。重载new[]()运算符能够为任意类型的数组分配空间。当数组版本和非数组版本的函数以相同的方式进行处理时，我将它们统一称为new()运算符，表示还包括一个相同的new[]()运算符。

new表达式会调用new()运算符的若干版本之一来获得动态变量的内存，或是调用new[]()运算符获得动态数组的内存。C++ 提供了这些运算符的默认实现。它还隐式地声明了这些运算符，这样程序无需包含<new>头文件即可调用它们。

new()运算符对于性能优化非常重要，因为默认内存管理器的开销是昂贵的。在有些情况下，通过实现专门的运算符能够让程序非常高效地分配内存。

C++ 定义了new()运算符的几种重载形式。

1
void* ::operator new(size_t)

默认情况下，所有动态分配的变量的内存都是通过调用new()运算符的带有指定要分配内存的最小字节数参数的重载形式分配的。当没有足够多的内存能够满足请求时，这种重载形式的标准库实现会抛出std::bad_alloc异常。

new()运算符的所有其他重载形式的标准库实现都会调用这个重载形式。通过在任意编译单元中提供一个::operator new(size_t)的定义，程序能够全局地改变内存的分配方式。

尽管 C++ 标准并没有规定这是必需的，但是标准库中的这个重载版本的实现通常都会调用malloc()。

1
void* ::operator new[](size_t)

程序用new()运算符的这个重载版本为数组分配内存。在标准库中，该版本的实现会调用::operator new(size_t)。

1
2
void* ::operator new(size_t, const std::nothrow_tag&)
Foo* p = new(std::nothrow) Foo(123);

这样的new表达式会调用new()运算符的不抛出异常的重载形式。如果没有可用内存，该版本会返回nullptr，而不会抛出std::bad_alloc异常。在标准库中，该版本的实现会调用new(size_t)运算符并捕捉所有可能会抛出的异常。

1
void* ::operator new[](size_t, const std::nothrow_tag&)

这是new()运算符的无异常抛出版本的数组版本。

new表达式能够调用第一个参数是size_t类型的、具有任意函数签名的new()运算符。所有这些new()运算符的重载形式都被称为定位放置new()运算符。new表达式通过将定位放置new()运算符的参数类型与可用的new()运算符函数签名进行匹配，来确定使用哪个函数。

标准库提供并隐式声明了定位放置new()运算符的两种重载版本。它们不会分配内存（动态变量生命周期的第一阶段），取而代之的是接收一个额外的参数，这个参数是一个指向程序所分配的内存的指针。两种重载版本如下。

1
void* ::operator new(size_t, void*)

这是用于单个变量的定位放置new()运算符。它接收一个指向内存的指针作为它的第二个参数，并简单地返回该指针。

1
void* ::operator new[](size_t, void*)

这是数组版本的定位放置new()运算符。它接收一个指向内存的指针作为它的第二个参数并返回该指针。

这两个定位放置new()运算符的重载会被定位放置new表达式new(p)类型调用，其中p是指向有效存储空间的指针。根据 C++ 标准，这些重载是不能被替换为开发人员自己的代码的。

delete表达式会调用delete()运算符，将分配给动态变量的内存返回给运行时系统，调用delete[]()运算符将分配给动态数组的内存返回给运行时系统。

new运算符和delete运算符共同工作，分配和释放内存。如果一个程序定义了new()运算符来从一个特殊的内存池中或是以一种特别的方式分配内存，它也必须在相同的作用域内相应地定义一个delete()运算符，将所分配的内存返回给内存池，否则delete()运算符的行为就是未定义的。

为了确保与 C 程序的兼容性， C++ 提供了 C 语言库函数malloc()、calloc()和realloc()来分配内存，以及free()函数来返回不再需要的内存。

  • void* malloc(size_t size)实现了一个动态变量生命周期的分配阶段，它会返回一个指向可以存储size字节大小的存储空间的指针，如果没有可用存储空间则会返回nullptr。
  • void free(void* p)实现了一个动态变量生命周期的释放阶段，它会将p所指向的存储空间返回给内存管理器。
  • void* calloc(size_t count, size_t size)实现了一个动态数组生命周期的分配阶段。它会执行一个简单的计算来算出含有count个大小为size的元素的数组的字节长度，并使用这个值调用malloc()。
  • void* realloc(void* p, size_t size)可以改变一块内存的大小，如果有需要会将内存块移动到一个新的存储空间中去。旧的内存块中的内容将会被复制到新的存储块中，被复制的内容的大小是新旧两块内存块大小中的较小值。必须谨慎使用realloc()。有时它会移动参数所指向的内存块并删除旧的内存块。如果它这么做了，指向旧内存块的指针将变为无效。有时它会重用现有的内存块，而这个内存块可能会比所请求的大小大。

根据 C++ 标准，malloc()和free()作用于一块称为“堆”（heap）的内存区域上，而new()运算符和delete()运算符的重载版本则作用于称为“自由存储区”（free store）的内存区域上。C++ 标准中这种严谨的定义能够让库开发人员实现两套不同的函数。也就是说，在 C 和 C++ 中内存管理的需求是相似的。只是对于一个编译器来说，有两套并行但不同的实现是不合理的。在我所知道的所有标准库实现中，new()运算符都会调用malloc()来进行实际的内存分配。通过替换malloc()和free()函数，一个程序能够全局地改变管理内存的方式。

new表达式构造动态变量

C++ 程序使用new表达式请求创建一个动态变量或是动态数组。new表达式包含关键字new，紧接着是一个类型，一个指向new表达式返回的地址的指针。new表达式还有一个用于初始化变量值或是每个数组元素的初始化列表。new表达式会返回一个指向被完全初始化的 C++ 变量或数组的有类型指针，而不是指向 C++new()运算符或是 C 语言中内存管理函数返回的未初始化的存储空间的简单空指针。new 表达式返回一个指向动态变量或是动态数组的第一个元素的右值指针。

如果 placement-params 中包含有关键字std::nothrow，那么new表达式不会抛出std::bad_alloc。它不会尝试构造对象，而是直接返回nullptr。

通常认为异常处理会降低效率，因此不抛出异常的 new 表达式应该会更快。不过，现代C++ 编译器实现的异常处理仅在异常被抛出后才会发生非常小的运行时开销，因此这条常理的真相可能取决于编译器。

如果 placement-params 是一个指向已经存在的有效存储空间的指针，那么 new 表达式不会调用内存管理器，而只是简单地将 type 放置在指针所指向的内存地址，而且这块内存必须能够容下 type。定位放置 new 表达式的用法如下：

1
2
3
char mem[1000];
class Foo {...};
Foo* foo_p = new (mem) Foo(123);

在这段示例代码中，Foo类的一个实例被放置在了数组mem的顶部。定位放置new表达式调用类的构造函数对类的实例进行初始化。对于基本类型，定位放置new表达式会执行初始化，而不是调用构造函数。

由于定位放置new表达式并不分配存储空间，因此它没有相应的定位放置delete表达式。当mem超出作用域后，被定位放置new表达式放置在mem顶部的Foo的实例不会被自动地销毁。开发人员需要显式地调用类的析构函数来销毁定位放置new表达式创建的实例。事实上，如果Foo的实例被放在了为Bar的实例所分配的存储空间中，那么Bar的析构函数将会被调用，这会带来未定义的灾难性的结果。因此，必须在new()运算符返回的内存或是char或其他基本数据类型的数组占用的内存上使用定位放置new表达式。

new表达式在要创建的类型范围中查找new()运算符。因此，一个类能够通过提供这些运算的实现来精准地掌握对它自己的内存分配。如果在类中没有定义类专用new()运算符，那么全局new()运算符将会被使用。要想使用全局new()运算符替代类专用new()运算符，程序员需要如下这样在new表达式中指定全局作用域运算符::

1
Foo* foo_p = ::new Foo(123);

只有为定义了这种运算符的类实例分配存储空间时，类专用new()运算符才会被调用。当在类的成员函数中用new表达式生成其他类的实例时，如果有为其他类定义的new()运算符，那么就会使用该运算符，否则就会调用默认的全局new()运算符。

类专用new()运算符是高效的，因为它为大小固定的对象分配内存。因此，第一个未使用的内存块总是可用的。如果类没有被用在多线程中，那么类专用new()运算符就可以免去确保类的内部数据结构是线程安全的这项开销。

类专用new()运算符需要定义为类的静态成员函数。这是有原因的，因为new()运算符会为每个实例分配存储空间。如果一个类实现了自定义定位放置new()运算符，那么它必须实现相应的delete()运算符，否则全局delete()运算符就会被调用。

高性能内存管理器

默认情况下，所有申请存储空间的请求都会经过::operator new()，释放存储空间的请求都会经过::operator delete()。这些函数形成了 C++ 的默认内存管理器。默认的 C++ 内存管理器必须满足许多需求。

  • 它必须足够高效，因此它非常有可能成为热点代码。
  • 它必须能够在多线程程序中正常工作。访问默认内存管理器中的数据结构必须被序列化。
  • 它必须能够高效地分配许多相同大小的对象（例如链表节点）。
  • 它必须能够高效地分配许多不同大小的对象（例如字符串）。
  • 它必须既能够分配非常大的数据结构（I/O 缓冲区，含有数百万个整数值的数组）， 也能够分配非常小的数据结构（例如一个指针）。
  • 为了使性能最大化，它必须至少知道较大内存块的指针的对齐边界、缓存行和虚拟内存页。
  • 它的运行时性能不能随着时间而降低。
  • 它必须能够高效地复用返回给它的内存。

提供类专用内存管理器

即使是最先进的malloc()也是对创建优化机会的妥协。我们还能够在类级别重写new()运算符。当动态创建类实例的代码被确定为热点代码时，通过提供类专用内存管理器能够改善程序性能。

如果一个类实现了new()运算符，那么当为该类申请内存时就不会调用全局new()运算符，而是调用这个new()运算符。相比于默认版本的new()运算符，我们可以利用对对象的了解在类专用内存管理器中编写更多有利于提升性能的处理。所有为某个类的实例申请分配内存的请求都会申请相同的字节大小。编写高效地处理分配相同大小内存的请求的内存管理器是很容易的，原因如下。

  • 分配固定大小内存的内存管理器能够高效地复用被返回的内存。它们不必担心碎片，因为所有的请求都申请相同大小的内存。
  • 能够以很少甚至零内存间接开销的方式实现分配固定大小内存的内存管理器。
  • 分配固定大小内存的内存管理器能够确保所消耗内存总量的上限。
  • 在分配固定大小内存的内存管理器中，分配和释放内存的函数都非常简单，因此它们会被高效地内联，而默认 C++ 内存分配器中的函数则无法被内联。它们必须是函数调用，这样才能够被开发人员定义的重写版本所替代。出于同样的原因， C 语言中的内存管理函数malloc()和free()也必须都是普通函数。
  • 分配固定大小内存的内存管理器具有优秀的高速缓存行为。最后一个被释放的节点可以是下一个被分配的节点。

分配固定大小内存的内存管理器

代码定义了一个简单的分配固定大小内存块的内存管理器，它会从一个名为“分配区”（arena）的单独的、静态声明的存储空间块中分配内存块。作为从自由存储区分配内存的一种方式。

fixed_block_memory_manager非常简单：一个单独的未使用内存块的链表。这种简单的设计将会在本章中多处被用到，因此我们来详细地看看它。代码分配固定大小内存块的内存管理器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class Arena> struct fixed_block_memory_manager {
    template <int N>
    fixed_block_memory_manager(char(&a)[N]);
    fixed_block_memory_manager(fixed_block_memory_manager&) = delete;
    ~fixed_block_memory_manager() = default;
    void operator=(fixed_block_memory_manager&) = delete;
    void* allocate(size_t);
    size_t block_size() const;
    size_t capacity() const;
    void clear();
    void deallocate(void*);
    bool empty() const;
private:
    struct free_block {
        free_block* next;
    };
    free_block* free_ptr_;
    size_t block_size_;
    Arena arena_;
};
# include "block_mgr.inl"

在代码中定义的构造函数接收一个 C 风格的字符数组作为它的参数。这个数组形成了分配内存块的分配区。它的构造函数是一个以数组大小作为模板参数的模板函数。

1
2
3
4
5
6
7
template <class Arena>
template <int N>
inline fixed_block_memory_manager<Arena>
::fixed_block_memory_manager(char(&a)[N]) :
arena_(a), free_ptr_(nullptr), block_size_(0) {
    /* empty */
}

当函数定义出现在模板类外部时，我们需要使用一种更冗长的语法来帮助编译器连接函数定义与模板类体中的声明。在上一个例子中，第一行template <class Arena>声明了类的模板参数。第二行template <int N>适用于构造函数自身，它是一个模板函数。当成员函数定义出现在模板类体的外部时，必须明确写明关键字 inline，否则只有当函数定义出现在类的内部时才会进行内联。

代码中的成员函数allocate()会在有可用内存块时，将一个内存块弹出未使用内存块的链表并返回它。如果未使用内存块的链表是空的，allocate()会试图从分配区管理器中获得一个新的未使用内存块的链表，我会在后面讲解这一点。如果分配区管理器没有可分配的内存，它会返回nullptr，而allocate()则会抛出std::bad_alloc。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class Arena>
inline void* fixed_block_memory_manager<Arena>
::allocate(size_t size) {
    if (empty()) {
        free_ptr_ = reinterpret_cast<free_block*>
        (arena_.allocate(size));
        block_size_ = size;
        if (empty())
            throw std::bad_alloc();
    }
    if (size != block_size_)
        throw std::bad_alloc();
    auto p = free_ptr_;
    free_ptr_ = free_ptr_->next;
    return p;
}

deallocate()成员函数非常简单。它会将一个内存块推入到未使用内存块的链表中：

1
2
3
4
5
6
7
8
9
template <class Arena>
inline void fixed_block_memory_manager<Arena>
::deallocate(void* p) {
    if (p == nullptr)
        return;
    auto fp = reinterpret_cast<free_block*>(p);
    fp->next = free_ptr_;
    free_ptr_ = fp;
}

下面是其他成员函数的定义。我们使用 C++11 语法在类定义中禁用了内存管理器的复制和赋值。

1
2
3
4
5
6
7
8
9
10
template <class Arena>
inline size_t fixed_block_memory_manager<Arena>
::capacity() const {
    return arena_.capacity();
}
template <class Arena>
inline void fixed_block_memory_manager<Arena>::clear() {
    free_ptr_ = nullptr;
    arena_.clear();
}

内存块分配区

fixed_block_memory_manager中唯一的复杂点在于未使用内存块的链表是如何被初始化的。这种复杂性被考虑在单独的模板类内部。这里要展示的实现方式称为fixed_arena_controller。正如这里所用到的一样，arena表示一个发生某些活动的封闭空间。block_arena是一个能够被block_manager分配的固定大小的内存池。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct fixed_arena_controller {
    template <int N>
    fixed_arena_controller(char(&a)[N]);

    fixed_arena_controller(fixed_arena_controller&) = delete;
    ~fixed_arena_controller() = default;
    void operator=(fixed_arena_controller&) = delete;
    void* allocate(size_t);
    size_t block_size() const;
    size_t capacity() const;
    void clear();
    bool empty() const;
    private:
    void* arena_;
    size_t arena_size_;
    size_t block_size_;
};

fixed_arena_controller类的目的是创建一个内存块链表，其中所有的内存块的大小都是相同的。这个大小是在第一次调用allocate()时设置的。链表中的每个内存块都必须足够大，能够满足请求的字节数，同时还必须能够存储一个指针，当该内存块在未使用内存块的链表中时这个指针会被使用。

构造函数模板函数接收来自fixed_block_memory_manager的分配区数组，保存数组大小和一个指向数组起始位置的指针：

1
2
3
4
5
template <int N>
inline fixed_arena_controller
::fixed_arena_controller(char (&a)[N]) :
arena_(a), arena_size_(N), block_size_(0) { /*空*/
}

allocate()成员函数是发生分配操作的地方。当未使用内存块的链表为空时，它会被fixed_block_memory_manager的成员函数allocate()调用，这会在第一次分配请求到来时发生。

fixed_arena_controller有一个内存块可分配。如果这个内存块已经被使用了，allocate()会再次被调用并且必须返回一个错误提示。在这种情况下错误提示是nullptr。其他种类的分配区控制器可能会通过调用::operator new()等将它们所得到的大内存块分解为小块。对于其他分配区控制器，多次调用allocate()是没有问题的。

当allocate()初次被调用时，它会设置内存块大小和容量。实际创建未使用内存块的链表是将未类型化的内存字节重新解释为类型化指针的过程。字符数组被解释为一组端到端的内存块。每个内存块的第一个字节都是一个指向下一个内存块的指针。最后一个内存块的指针是nullptr。fixed_arena_controller无法控制分配区数组的大小。可能在尾部会有数个未使用的字节永远不会被分配。设置未使用内存块指针的代码并不优雅。它需要继续将一种指针重新解释为另外一种指针，退出 C++ 类型系统，进入到实现定义（implementation-defined）行为的“国度”。不过，这是内存管理器都存在的不可避免的问题。

fixed_arena_controller中的分配和释放代码很简单：在提供给构造函数的存储空间上分配未使用节点的链表，返回一个指向链表第一个元素的指针。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void* fixed_arena_controller ::allocate(size_t size) {
    if (!empty())
        return nullptr; // arena已经被分配了
    block_size_ = std::max(size, sizeof(void*));
    size_t count = capacity();
    if (count == 0)
        return nullptr; // arena太小了，甚至容不下一个元素
    char* p;
    for (p = (char*)arena_; count > 1; --count, p += size) {
        *reinterpret_cast<char**>(p) = p + size;
    }
    *reinterpret_cast<char**>(p) = nullptr;
    return arena_;
}

下面是fixed_arena_controller的其他部分：

1
2
3
4
5
6
7
8
9
10
11
12
inline size_t fixed_arena_controller::block_size() const {
    return block_size_;
}
inline size_t fixed_arena_controller::capacity() const {
    return block_size_ ? (arena_size_ / block_size_) : 0;
}
inline void fixed_arena_controller::clear() {
    block_size_ = 0;
}
inline bool fixed_arena_controller::empty() const {
    return block_size_ == 0;
}

添加一个类专用new()运算符

代码是一个具有类专用new()运算符和delete()运算符的非常简单的类。其中还有一个静态成员变量mgr_。new()运算符和delete()运算符都是内联函数，它们会将请求转发给mgr_的成员函数allocate()和deallocate()。

1
2
3
4
5
6
7
8
9
10
11
12
class MemMgrTester {
    int contents_;
public:
    MemMgrTester(int c) : contents_(c) {}
    static void* operator new(size_t s) {
        return mgr_.allocate(s);
    }
    static void operator delete(void* p) {
        mgr_.deallocate(p);
    }
    static fixed_block_memory_manager<fixed_arena_controller> mgr_;
};

mgr_被声明为public，这样我能够通过调用mrg_.clear()重新初始化未使用内存块的链表，以方便编写性能测试。如果mgr_只在程序启动时被初始化一次，之后永远无需重新初始化，那么最好将其声明为private成员变量。

能够像这样被重置的内存管理器被称作内存池管理器（pool memory manager）， 它所控制的分配区则被称为内存池（memory pool）。内存池管理器非常适用于数据结构被构造、使用然后被销毁的情况。如果能够快速地重新初始化整个内存池，那么程序就能够避免逐节点地释放数据结构。

mgr_是BlockTester类的一个静态成员变量。在程序中的某个地方，也必须如代码这样定义静态成员。这段代码定义了一个内存分配区以及mgr_，mgr_的构造函数接收这个分配区作为参数。

1
2
3
char arena[4004];
fixed_block_memory_manager<fixed_arena_controller>
MemMgrTester::mgr_(arena);

这段代码没有定义类专用new[]()运算符来分配数组的存储空间。分配固定大小内存块的内存管理器无法工作于根据定义可能会有不同数量元素的数组之上。如果程序试图分配一个MemMgrTester数组，那么new表达式会使用全局new[]()运算符，因为没有定义类专用的运算符。也就是说，程序会使用分配固定大小内存块的内存管理器来为单独的类实例分配存储空间，使用malloc()为数组分配存储空间。

自定义标准库分配器

在std::list<T>中动态分配的变量不是用户提供的类型T。它们是像listitem<T>这样的无形类型，不但包含有效载荷类型T，还包含指向前向节点和后向节点的指针。在std::map<K,V>中动态分配的变量是另外一种像treenode<std::pair<const K, V>>这样的隐藏类型。这些模板类藏在编译器提供的头文件中。我们无法修改这些类，在其中加入类专用new()运算符和delete()运算符。

标准库容器可以接收一个Allocator参数，它具有与类专用new()运算符相同的自定义内存管理器的能力。Allocator是一个管理内存的模板类。作为被扩展的基础，一个分配器会做三件事情：从内存管理器中获取存储空间，返回存储空间给内存管理器，以及从相关联的分配器中复制构造出它自己。

分配器的实现可以非常简单，也可以复杂到让人头脑发麻。默认分配器std::allocator<T>是::operator new()的一个简单的包装器。分配器有两种基本类型。最简单的分配器是无状态的，也就是说一种没有非静态状态的分配器类型。默认分配器std::allocator<T>对于标准库容器是无状态的。

  • 无状态分配器能够被默认构造，无需显式地创建一个无状态分配器的实例，然后将它传递给容器类的构造函数。语句std::list<myClass, myAlloc> my_list;会构造一个由无状态分配器myAlloc分配的myClass的实例所组成的链表。
  • 一个无状态分配器不会在容器实例中占用任何空间。大多数标准库容器类都继承自它们的分配器，会利用空基类的优化生成一个零字节的基类。

无状态分配器my_allocator<T>的两个实例是难以区分的。这意味着一个无状态分配器分配的对象能够被另外一个分配器释放。这使得像std::list的splice()成员函数的操作变为可能。像AllocX<T>和AllocX<U>这样的不同类型的两个无状态分配器有时会相等，但并非总是相等。确实是这样的，std::allocator就是一个例子。

相等还意味着可以高效地进行移动赋值和std::swap()操作。如果两个分配器不等，那么必须使用目标容器类的分配器来深复制原来容器中的内容。请注意，尽管像AllocX<T>和AllocX<U>这样两个完全无关的分配器类型的实例可能会碰巧相等，但是这种特性是没有价值的。容器的类型包括分配器的类型。你无法将一个std::list<T,AllocX>拼接到std::list<T,AllocY>上，就像你不能将std::list<int>拼接到std::list<string>上一样。

创建和使用带有内部状态的分配器更加复杂，原因如下。

  • 在大多数情况下，一个带有局部状态的分配器是无法被默认构造出来的。这个分配器必须被手动地构造出来，然后传递给容器的构造函数。
1
2
3
char arena[10000];
MyAlloc<Foo> alloc(arena);
std::list<Foo, MyAlloc<Foo>> foolist(alloc);
  • 分配器的状态必须被存储在所有变量中，这会增大它们的大小。这对于像std::list和std::map这样的创建许多节点的容器是非常痛苦的，但也是容器编程人员最希望自定义的。
  • 两个相同类型的分配器在进行比较时可能会不相等，因为它们具有不同的内部状态，使得使用该分配器类型在容器上进行的某些操作变为不可用或是非常低效。

不过带状态的分配器具有一个很重要的优点，那就是当所有的分配请求无需通过一个单独的全局内存管理器时，为多种不同用途创建多种类型的内存分配区也更容易了。

最小C++11分配器

如果开发人员足够幸运，有一个完全符合 C++11 标准的编译器和标准库，那么他就可以提供一个只需要极少定义的最小分配器。代码展示了一个类似于std::allocator的分配器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T> struct my_allocator {
    using value_type = T;
    my_allocator() = default;
    
    template <class U> my_allocator(const my_allocator<U>&) {}
    T* allocate(std::size_t n, void const* = 0) {
        return reinterpret_cast<T*>(::operator new(n*sizeof(T)));
    }
    void deallocate(T* ptr, size_t) {
        ::operator delete(ptr);
    }
};
template <typename T, typename U>
inline bool operator==(const my_allocator<T>&, const my_allocator<U>&) {
    return true;
}
template <typename T, typename U>
inline bool operator!=(const my_allocator<T>& a, const my_allocator<U>& b) {
    return !(a == b);
}

在该最小分配器中只有以下这些函数。

  • allocator()：这是默认构造函数。如果分配器有一个默认构造函数，开发人员就无需显式地创建一个实例，然后将其传递给容器的构造函数。在无状态分配器的构造函数中，默认构造函数通常都是空函数，在具有非静态状态的分配器中则通常不存在默认构造函数。
  • template <typename U> allocator(U&)：这个复制构造函数使得将一个allocator<T>转换为如allocator<treenode<T>>这样的一个私有类的关联分配器成为可能。这非常重要，因为在大多数容器中，类型T的节点都不会被分配。

在无状态分配器中，复制构造函数通常都是空函数，但在具有非静态状态的分配器中，复制构造函数中则必须复制或克隆状态。

1
T* allocate(size_type n, const void* hint = 0)

该函数允许分配器分配足够存储 n 字节的存储空间，并返回一个指向这块存储空间的指针，或是在没有足够的内存空间时抛出std::bad_alloc。

1
void deallocate(T* p, size_t n)

该函数用于将之前allocate()分配的指针p所指向的占用n字节的存储空间返回给内存管理器。n必须与调用allocate()时的参数相等，p则指向allocate()所分配的存储空间。

1
2
bool operator==(allocator const& a) const
bool operator!=(allocator const& a) const

这一对函数用于比较两个相同类型的分配器的实例是否相等。如果两个实例的比较结果是相等，那么由一个实例分配的对象就可以安全地被另外一个实例释放。这意味着两个实例从相同的存储区域中分配对象。

C++98分配器的其他定义

在 C++11 之前，每个分配器包含了最小分配器中的所有函数，另外再加上以下这些。

  • value_type：待分配的对象的类型。
  • size_type：一个足以保存这个分配器能够分配的最大字节数的整数类型。对于用作标准库容器模板的参数的分配器，这个定义需要定义别名typedef size_t size_type;。

  • difference_type：一个足以保存两个指针之间的最大差值的整数类型。对于用作标准库容器模板的参数的分配器，这个定义需要定义别名typedef ptrdiff_t difference_type;。

  • pointer/const_pointer：一个指向(const) T的指针类型。对于用作标准库容器模板的参数的分配器，这个定义需要定义别名：

1
2
typedef T* pointer;
typedef T const* const_pointer;

对于其他分配器，指针可能会是一个实现了用于解引指针的operator*()的类指针类。

  • reference/const_reference：一个指向(const) T的引用类型。对于用作标准库容器模板的参数的分配器，这个定义需要定义别名：
1
2
typedef T& reference;
typedef T const& const_reference;
  • pointer address(reference)/const_pointer address(const_reference)：分别是用于返回一个指向(const) T的指针的函数和返回一个指向(const) T的引用的函数。

对于用作标准库容器模板的参数的分配器，这两个函数需要定义为：

1
2
pointer address(reference r) { return &r; }
const_pointer address(const_reference r) { return &r; }

这些函数原本是用于抽象内存模型的。不幸的是，它们需要与标准库容器兼容，这要求pointer必须是T*，因此线性随机访问迭代器和二分查找能够高效地进行工作。尽管这些定义对于标准库容器的分配器有固定值，但是定义还是需要的，因为 C++98 中的容器代码使用了它们。例如：

1
typedef size_type allocator::size_type;