|
其他库工具
ratio 库
可通过 ratio 库精确地表示任何可在编译时使用的有限有理数。ratio 对象在 std::chrono::duration 类中使用。与有理数相关的所有内容都在头文件中定义，并且都在 std 名称空间中。有理数的分子和分母通过类型为 std::intmax_t 的编译时常量表示，这是一种有符号的整数类型，其最大宽度由编译器指定。由于这些有理数编译时的特性，它们在使用时看上去比较复杂，不同寻常。ratio 对象的定义方式和普通对象的定义方式不同， 而且不能调用 ratio 对象的方法。需要使用类型别名。例如，下面这行代码定义了一个表示 1/60 的有理数编译时常量:
using r1 = ratio<1,60>;
rl 有理数的分子和分母是编译时常量，可通过以下方式访问:
intmax_t num = r1::num;intmax_t den = r1::den;
记住 ratio 是一个编译时常量，也就是说，分子和分母需要在编译时确定。下面的代码会产生编译错误;
intmax_t n = 1;intmax_t d = 60;using r1 = ratio<n,d>;
将n和d 定义为常量就不会有编译错误了:
const intmax_t n = 1;
const intmax_t d = 60;
using r1 = ratio<n,d>;
有理数总是化简的。对于有理数 ratio<n, d>，计算最大公约数 gcd、分子 num 和分母 den 的定义如下:
num = sign(n)*sign(d)*abs(n)/gcb;
den = abs(d)/gcb;
ratio 库支持有理数的加法、减法、乘法和除法运算。由于所有这些操作都是在编译时进行的，因此不能使用标准的算术运算符，而应使用特定的模板和类型别名组合。可用的算术 ratio 模板包括 ratio_ add、ratio_subtract ratio_multiply 和 ratio_divide。 这些模板将结果计算为新的 ratio 类型。这种类型可通过名为 type的内嵌类型别名访问。例如, 下面的代码首先定义了两个 ratio 对象, 一个表示 1/60, 另一个表示 1/30。ratio_add模板将两个有理数相加，得到的 result 有理数应该是化简之后的 1/20。
using r1 = ratio<1,60>;
using r2 = ratio<1,30>;
using result = ratio_add<r1,r2>::type;
C++标准还定义了一些 ratio 比较模板: ratio_equal、ratio_not_ equal、ratio_less、ratio_less_equal、ratio_greater和 ratio_greater_equal。与算术 ratio 模板一样，ratio 比较模板也是在编译时求值的。这些比较模板创建了一种新类型 std::bool_constant 来表示结果。bool_constant 也是 std::integral_constant，即 struct 模板，里面保存了一种类型和一个编译时常量值。例如，integral_constant<int 15>保存了一个值为 15 的整型值。bool_constant 还是布尔类型的 integral_constant。 例如, bool_constant是 integral_constant<bool, true>, 存储值为 true 的布尔值。ratio比较模板的结果要么是 bool constant<bool， true>，要么是 bool_constant<bool，false> 。与 bool constant 或integral_constant 关联的值可通过 value 数据成员访问。下面的代码演示了 ratio_less 的使用。第 13 章讨论了如何使用 boolalpha 以 true 或 false 的形式输出布尔值:
using r1 = ratio<1,60>;
using r2 = ratio<1,30>;
using res = ratio_less<r2,r1>;
cout<<boolalpha<<res::value<< endl;
下面的例子整合了所有内容。注意，由于 ratio 是编译时常量，因此不能编写像 cout << rl 这样的代码，而是需要获得分子和分母并分别进行打印。
using r1 = ratio<1,60>;
cout<<"1) "<<r1::num<<"/"<<r1::den<<endl;
intmax_t num = r1::num;
intmax_t den = r1::den;
cout<<"2) "<<num<<"/"<<den<<endl;
using r2 = ratio<1,30>;
cout<<"3) "<<r2::num<<"/"<<r2::den<<endl;
using res = ratio_less<r2,r1>;
cout<<"5) "<<boolalpha<<res::value<<endl;
输出
xz@xiaqiu:~/study/test/test$ ./test1) 1/602) 1/603) 1/305) false
为方便起见，ratio 库还提供了一些 SI(国际单位制)的类型别名，如下所示:
using yocto = ratio<1, 1'000'000'000'000'000'000'000'000>;
using zepto = ratio<1, 1'000'000'000'000'000'000'000>;
using atto = ratio<1, 1'000'000'000'000'000'000>;
using femto = ratio<1, 1'000'000'000'000'000>;
using pico = ratio<1, 1'000'000'000'000>;
using nano = ratio<1, 1'000'000'000>;
using micro = ratio<1, 1'000'000>;
using milli = ratio<1, 1'000>;
using centi = ratio<1, 100>;
using deci = ratio<1, 10>;
using deca = ratio<10, 1>;
using hecto = ratio<100, 1>;
using kilo = ratio<1'000, 1>;
using mega = ratio<1'000'000, 1>;
using giga = ratio<1'000'000'000, 1>;
using tera = ratio<1'000'000'000'000, 1>;
using peta = ratio<1'000'000'000'000'000, 1>;
using exa = ratio<1'000'000'000'000'000'000, 1>;
using zetta = ratio<1'000'000'000'000'000'000'000, 1>;
using yotta = ratio<1'000'000'000'000'000'000'000'000, 1>;
只有在编译器能表示类型别名为 intmax t 的常量分子和分母值时, 才会定义结尾处标了星号的 SI 单位。本章后面讨论 duration 时会给出这些预定义 SI 单位的使用示例。
chrono 库
chrono 库是一组操作时间的库。这个库包含以下组件;
持续时间
时钟
时点
所有组件都在 std::chrono 名称空间中定义，而且需要包含头文件。下面讲解每个组件。
持续时间
持续时间(duration)表示的是两个时间点之间的间隔时间，通过模板化的 duration 类来表示。duration 类保存了滴答数和滴答周期(tick period)。滴答周期指的是两个滴答之间的秒数，是一个编译时 ratio 常量，也就是说可以是 1 秒的分数。duration 模板接收两个模板参数，定义如下所示:
template<class Rep,class Period = ratio<1>> class duration{...}
第一个模板参数 Rep 表示保存滴答数的变量类型，应该是一种算术类型，例如 long 和 double 等。第二个模板参数 Period 是表示滴答周期的有理数常量。如果不指定滴答周期，那么会使用默认值 ratio<1>，也就是说默认滴答周期为 1 秒。
duration 类提供了 3 个构造函数: 一个是默认构造函数，另一个构造函数接收一个表示滴答数的值作为参数; 第三个构造函数接收另一个 duration 作为参数。后者可用于将一个 duration 转换为另一个 duration，例如将分钟转换为秒。本节后面会列举一个示例。
duration 支持算术运算，例如+、-、*、/、%、++、–、+=、-=、*=、/=和%=，还支持比较运算符。duration类包含多个方法，如表 20-1 所示。
| 方法 | 说明 |
|---|
| Rep count() const | 以滴答数返回 duration 值，返回类型是 duration 模板中指定的类型参数 | | static duration zero() | 返回持续时间值等于 0 的 duration | | static duration min() static duration max() | 返回 duration 模板指定的类型参数表示的最小值/最大值持续时间的 duration 值 |
C++17 添加了用于持续时间的 foor()、ceil()、round()和 abs()操作，行为与用于数值数据时类似。下面看一下如何在实际代码中使用 duration。每一个滴答周期为 1 秒的 duration 定义如下所示:
duration<long> d1;
由于 ratio<1>是默认的滴答周期，因此这行代码等同于:
duration<long,ratio<1>> d1;
下面的代码指定了滴答周期为 1 分钟的 duration(滴答周期为 60 秒):
duration<double,ratio<60>> d2;
下面的代码定义了每个滴答周期为 1/60 秒的 duration;
duration<double,ration<1,60>> d3;
根据本章前面的描述，头文件定义了一些 SI 有理数常量。这些预定义的常量在定义滴答周期时非常方便。例如，下面这行代码定义了每个滴答周期为 1 毫秒的 duration:
duration<long long,milli> d4;
下面的例子展示了 duration 的几个方面。它展示了如何定义 duration，如何对 duration 执行算术操作，以及如何将一个 duration 转换为另一个滴答周期不同的 duration:
#include <iostream>
#include <string>
#include <regex>
#include <algorithm>
#include <ratio>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main()
{
duration<long,ratio<60>> d1(123);
cout<<d1.count()<<endl;
duration<double> d2;
d2 = d2.max();
cout<<d2.count()<<endl;
duration<long,ratio<60>> d3(10);
duration<long,ratio<1>> d4(14);
if(d3 > d4)
cout<<"d3 > d4"<<endl;
else
cout<<"d3 <= d4"<<endl;
++d4;
d4 *= 2;
duration<double,ratio<60>> d5 = d3 + d4;
duration<long,ratio<1>> d6 = d3 + d4;
cout << d3.count() << " minutes + " << d4.count() << " seconds = "
<< d5.count() << " minutes or "
<< d6.count() << " seconds" << endl;
duration<long> d7(30);
duration<double,ratio<60>> d8(d7);
cout<<d7.count()<<" seconds = "<<d8.count() <<" minutes"<<endl;
return 0;
}
输出
xz@xiaqiu:~/study/test/test$ ./test1231.79769e+308d3 > d410 minutes + 30 seconds = 10.5 minutes or 630 seconds30 seconds = 0.5 minutesxz@xiaqiu:~/study/test/test$
注意
上面输出中的第二行表示类型 double 能表示的最大 duration。具体的值因编译器而异。特别注意下面两行;
duration<double,ratio<60>> d5 = d3 + d4;duration<long,ratio<1>> d6 = d3 + d4;
这两行都计算了 d3+d4，但第一行将结果保存在表示分钟的浮点值中，第二行将结果保存在表示秘的整数中。分钟到秒的转换(或秒到分钟的转换)自动进行。上例中的下面两行展示了如何在不同时间单位问进行显式转换，
duration<long> d7(30);
第一行定义了一个滴答周期为 30 秒的 duration。第二行将这 30 秒转换为 0.5 分钟。使用这个方向的转换可能会得到非整数值，因此要求使用浮点数类型表示的 duration，否则会得到一些很诡异的编译错误。例如，下面的代码不能成功编译，因为 d8 使用了 long 类型而不是浮点类型:
duration<long>d7(30);
但可以使用 duration_cast()进行强制转换,
duration<long> d7(30);
此处，d8 的滴答周期为 0 分钟，因为整数除法用于将 30 秒转换为分钟数。在另一个方向的转换中，如果源数据是整数类型，那么不要求转换至浮点类型。因为如果从整数值开始转换，那么得到的总是整数值。例如，下面的代码将 10 分钟转换为秒数，两者都用整数类型 long 表示，
duration<long,ratio<60>> d9(10);
chrono 库还提供了以下标准的 duration 类型，它们位于 std::chrono 名称空间中:
using nanoseconds = duration<X 64 bits, nano>;using microseconds = duration<X 55 bits, micro>;using milliseconds = duration<X 45 bits, milli>;using seconds = duration<X 35 bits>;using minutes = duration<X 29 bits, ratio<60>>;using hours = duration<X 23 bits, ratio<3600>>;
区的具体类型取决于编译器，但 C++标准要求蕊的类型为至少指定大小的整数类型。上面列出的类型别名使用了本章前面描述的预定义的 SI ratio 类型别名。使用这些预定义的类型，不是编写:
duration<long,ratio<60>> d9(10);
而是编写;
minutes d9(10);
下面是一个讲解如何使用这些预定义 duration 的例子。这段代码首先定义了一个变量t，这个变量保存的是1 小时+23 分钟+45 秒的结果。这里使用了 auto 关键字，让编译器自动推导出 t 的准确类型。第二行使用了预定义的 seconds duration 构造函数，将t 的值转换为秒数，并将结果输出到控制台:
auto t = hours(1) + minutes(23)+seconds(45);cout<<seconds(t).count()<<" seconds"<<endl;
由于 C++标准要求预定义的 duration 使用整数类型，因此如果转换后得到非整数的值，那么会出现编译错误。尽管整数除法通常都会截断，但在使用通过 ratio 类型实现的 duration 时，编译器会将所有可能导致非零余数的计算声明为编译时错误。例如，下面的代码无法编译，因为转换 90 秒后得到的是 1.5 分钟:
seconds s(90);minutes m(s);
下面的代码也无法成功编译，即使 60 秒刚好为 1 分钟也是如此。这段代码也会产生编译错误，因为从秒到分钟的转换可能会产生非整数值:
seconds s(60);minutes m(s);
另一个方向的转换可正常完成，因为 minutes duration 是整数值，将它转换为 seconds 总能得到整数值;
minutes m(2);seconds s(m);
可使用标准的用户自定义字面量“h”“min”“s”“ms”“us”和“ns”来创建 duration。从技术角度看，这些定义在 std::literals::chrono_literals 名称空间中, 但也可通过 using namespace std::chrono 来访问。下面是一个示例:
using namespace std::chrono;
时钟
clock 类由time_point 和 duration 组成。 time_point 类在 20.2.3 节中详细讨论，不过理解 clock 的工作方式并不需要这些细节。但由于 time_point 本身依赖于 clock，因此应该首先详细了解 clock 的工作方式。C++标准定义了 3 个 clock。第一个称为 system_clock，表示来自系统实时时钟的真实时间。第二个称为steady_clock，是一个能保证其 time_point 绝不递减的时钟。system_clock 无法做出这种保证，因为系统时钟可以随时调整。第三个称为high_resolution_clock，这个时钟的滴答周期达到了最小值。high_resolution_clock 可能就是 stead_clock 或 system_clock 的别名，具体取决于编译器。每个 clock 都有一个静态的 now()方法，用于把当前时间用作 time_point。system_clock 定义了两个静态辅助函数，用于 time_point 和 C 风格的时间表示方法 time_t之间的相互转换。第一个辅助函数为to_time_t()，它将给定 time_point 转换为 time_t，第二个辅助函数为 from_time_t()，它返回用给定 time_t 初始化的 time_ point。time_t 类型在<ctime.h>头文件中定义。
下例展示了一个完整程序, 它从系统获得当前时间, 然后将这个时间以可供用户读取的格式输出到控制台。localtime()函数将 time_t 转换为用 tm 表示的本地时间，定义在头文件中。C++的 put_time()流操作算子定义在头文件中，详见第 13 章的讨论。
如果想要将时间转换为字符串，可使用 std::stringstream 或 C 风格的 strfime()函数，这些定义在中。
system_clock::time_point tpoint = system_clock::now();
time_t tt = system_clock::to_time_t(tpoint);
tm* t = localtime(&tt);
char buffer[80] = {0};
strftime(buffer,sizeof(buffer),"%H:%M:%S",t);
cout<<buffer<<endl;
通过 chrono 库还可计算一段代码执行所消耗的时间。下例展示了这个过程。变量 start 和 end 的实际类型为system_clock::time_point，diff企的实际类型为 duration:
auto start = high_resolution_clock::now();
double d = 0;
for(int i = 0;i < 1000000; ++i)
{
d+=sqrt(sin(i) * cos(i));
}
auto end = high_resolution_clock::now();
auto diff = end - start;
cout<<duration<double,milli>(diff).count()<<"ms"<<endl;
输出
xz@xiaqiu:~/study/test/test$ ./test88.7702msxz@xiaqiu:~/study/test/test$ ./test90.009msxz@xiaqiu:~/study/test/test$ ./test93.3066msxz@xiaqiu:~/study/test/test$ ./test88.8442msxz@xiaqiu:~/study/test/test$ ./test88.889msxz@xiaqiu:~/study/test/test$
这个例子中的循环执行一些算术操作，例如 sqrt()、sin()和 cos()，确保循环不会太快结束。如果在系统上获得非常小的毫秒差值，那么这些值不会很准确，应该增加循环的友代次数，使循环执行时间更长。小的计时值不会很准确，因为尽管定时器的精度为毫秒级，但在大多数操作系统上，这个定时器的更新频率不高，例如每10 毫秒或 15 毫秒更新一次。这会导致一种称为门限错误(gating erron)的现象，也就是说，任何持续时间小于1个定时器滴答的事件只花了 0 个时间单位，任何持续时间在 1 个和 2 个定时器滴答之间的事件花了 1 个时间单位。例如, 在一个定时器更新频率为 15 毫秒的系统上,运行了 44 毫秒的循环看上去只花了 30 毫秒。当使用这类定时器确定计算所用的时间时, 一定要确保整个计算消耗了大量的基本定时器滴答单位， 这样误差才能最小化。
时点
time_point 类表示的是时间中的某个时点，存储为相对于纪元(epoch)的 duration。time_ point 总是和特定的clock 关联，纪元就是所关联 clock 的原点。例如，经典 UNIX/Linux 的时间纪元是 1970年 1月 1 日，duration用秒来度量。Windows 的纪元是 1601 年 1月 1 日，duration 用 100 纳秒作为单位来度量。其他操作系统还有不同的纪元日期和 duration 单位。time_point 类包含 time_ since_epoch()函数, 它返回的 duration 表示所关联 clock 的纪元和保存的时间点之间的时间。C++支持合理的 time_point 和 duration 算术运算。下面列出这些运算。tp 代表 time point，d 代表 duration。
tp + d = tp tp – d = tpd + tp = tp tp – tp = dtp += d tp -= d
C++不支持的操作示例是 tp+tp。C++支持使用比较运算符来比较两个时间点，提供了两个静态方法: min()返回最小的时间点，而 max()返回最大的时间点。time_point 类有 3 个构造函数。e time_point(): 构造一个time_point, 通过 duration::zero()进行初始化。得到的 time_point 表示所关联 clock的纪元。
time_point(const duration&c ): 构造一个 time_point，通过给定的 duration 进行初始化。得到的 time_point 表示纪元+d。template time_point(const time_point<clock, Duration2>& b: 构造一个 time_point，通过time_since_epoch()进行初始化。每个 time_point 都关联一个 clock。创建 time_point 时，指定 clock 作为模板参数:
time_point<steady_clock> tp1;
每个 clock 都知道各自的 time_point 类型，因此可编写以下代码;
steady_clock::time_point tp1;
输出
xz@xiaqiu:~/study/test/test$ ./test600 secondxz@xiaqiu:~/study/test/test$ ./test600 secondxz@xiaqiu:~/study/test/test$ ./test600 secondxz@xiaqiu:~/study/test/test$
可通过隐式方法或显式方法转换 time_point，这与 duration 转换类似。下面是一个隐式转换示例，输出是42000 ms。
time_point<steady_clock,seconds> tpSeconds(42s);
生成随机数
在软件中生成符合需求的随机数是一个复杂主题。 在 C++11 之前, 生成随机数的唯一方法是使用 C 风格的srand()和 rand()函数。srand()函数需要在应用程序中调用一次，这个函数初始化随机数生成器，也称为设置种子(seeding)。通常应该使用当前系统时间作为种子。
警告;
在基于软件的随机数生成器中, 一定要使用高质量的种子。如果每次都用同一个种子初始化随机数生成器，那么每次生成的随机数序列都是一样的。这也是为什么通常要采用当前系统时间作为种子的原因。
? 初始化随机数生成器后,通过 rand()生成随机数。下例展示了如何使用 srand()和 rand()。time(nullpt)调用返
srand(static_cast<unsigned int>(time(nullptr)));
cout<<rand()<<endl;
可通过以下函数生成特定范围内的随机数:
旧式的 C 风格 rand()函数生成的随机数在 0 到RAND_MAX 之间，根据标准，RAND_MAX 至少应该为32767。但rand()的低位通常不是非常随机，也就是说，通过上面的 getRandom()生成的随机数范围较小(例如 1和6之间)，并且得到的随机性并不是非常好。
注意:
基于软件的随机数生成器永远都不可能生成真正的随机数，而是根据数学公式生成随机的效果，因此称为伪随机数生成器。
旧式的 srand()和 rand()函数没有提供太多灵活性。例如，无法改变生成的随机数的分布。C++11 添加了一个非常强大的库，能根据不同的算法和分布生成随机数。这个库定义在头文件中。这个库有 3 个主要组件: 随机数引擎(engine)、随机数引擎适配器(engine adapte)和分布(distribution)。随机数引擎负责生成实际的随机数， 并将生成后续随机数需要的状态保存起来。分布判断生成随机数的范围以及随机数在这个范围内的数学分布情况。随机数引擎适配器修改相关联的随机数引擎生成的结果。强烈建议不再使用 srand()和 rand()，而使用中的类。
随机数引擎
以下随机数引擎可供使用:
random_device
linear_congruential_engine
mersenne_twister_engine
Subtract_with_carry_engine
random_device 引擎不是基于软件的随机数生成器; 这是一种特殊引擎，要求计算机连接能真正生成不确定随机数的硬件，例如通过物理原理来生成。一种经典的机制是通过计算每个时间间隔内的 alpha 粒子数或类似的方法来测量放射性同位素的衰变，但还有很多其他类型的基于物理原理的生成器，包括测量反向偏压二极管“噪声”的方法(不必担心计算机内有放射源)。由于篇幅受限，本书不讲解这些机制的细节。根据 random_device 的规范，如果计算机没有连接此类硬件设备，这个库可选用一种软件算法。算法的选择取决于库的设计者。
随机数生成器的质量由随机数的熵(entropy)决定。 如果 random_device 类使用的是基于软件的伪随机数生成器，那么这个类的 entropy()方法返回的值为 0.0; 如果连接了硬件设备，则返回非零值。这个非零值是对连接设备的熵的估计。random_device 引擎的使用非常简单;
random_device rnd;
cout<<"Entropy: "<<rnd.entropy()<<endl;
cout<<"Min value: "<<rnd.min()
<<", Max value: "<<rnd.max()<<endl;
cout<<"Random number: "<<rnd()<<endl;
这个程序的输出如下所示;
xz@xiaqiu:~/study/test/test$ ./test
Entropy: 0
Min value: 0, Max value: 4294967295
Random number: 3393511293
random_ device 的速度通常比伪随机数引擎更慢。因此，如果需要生成大量的随机数，建议使用伪随机数引擎，使用 random_device 为随机数引擎生成种子。除了 random_device 随机数引擎之外，还有 3 个伪随机数引擎线性同余引擎(linear congruential engine)保存状态所需的内存量最少。状态是一个包含上一次生成的随机数的整数，如果尚未生成随机数，则保存的是初始种子。这个引擎的周期取决于算法的参数，最高可达 2“，但是通常不会这么高。因此，如果需要使用高质量的随机数序列，那么不应该使用线性同余引擎。
在这 3 个伪随机数引擎中，梅森旋转算法生成的随机数质量最高。梅森旋转算法的周期取决于算法参数，但比线性同余引擎的周期要长得多。梅森旋转算法保存状态所需的内存量也取决于算法参数，但是比线性同余引擎的整数状态高得多。例如，预定义的梅森旋转算法 mt19937 的周期为 2^19937 - 1，状态包含 625 个整数，约为 2.5SKB。它是最快的随机数引擎之一。带进位减法(subtract with carry)引擎要求保存大约 100 字节的状态。不过，这个随机数引擎生成的随机数质量不如梅森旋转算法。这些随机数引擎的数学原理超出了本书的讨论范围，而且对随机数质量的定义需要一定的数学背景。如果要更深入地了解这个主题的内容，可以参阅附录 B 的“随机数”部分列出的参考文献。random_device 随机数引擎易于使用，不需要任何参数。然而，创建这 3 个伪随机数生成器的实例时需要指定一些数学参数，这些参数可能会很复杂。参数的选择会极大地影响生成的随机数的质量。例如，mersenne_twister_engine 类的定义如下所示:
template<class UIntType, size_t w, size_t n, size_t m, size_t r,UIntType a, size_t u, UIntType d, size_t s,UIntType b, size_t t, UIntType c, size_t l, UIntType f>class mersenne_twister_engine {...}
这个定义需要 14 个参数。linear_congruential_engine 类和 subtract_ with_carry_engine 类也需要一些这样的数学参数。因此，C++标准定义了一些预定义的随机数引擎，比如 mt19937 梅森旋转算法，定义如下:
using mt19937 = mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,0x9908b0df, 11, 0xffffffff, 7, 0x9d2c5680, 15, 0xefc60000, 18,1812433253>;
除非理解梅森旋转算法的细节，和否则会觉得这些参数都是魔幻数。一般情况下不需要修改任何参数，除非你是伪随机数生成器方面的数学专家。强烈建议使用这些预定义的类型别名，例如 mt19937。20.3.2 节将完整列出所有预定义的随机数引擎。
随机数引擎适配器修改相关联的随机数引擎生成的结果，关联的随机数引擎称为基引擎base engine)。这是适配器模式的一个实例。C++定义了以下 3 个适配器模板:
template<class Engine, size_t p, size_t r> class
discard_block_engine {...}
template<class Engine, size_t w, class UIntType> class
independent_bits_engine {...}
template<class Engine, size_t k> class
shuffle_order_engine {...}
discard_block_engine 适配器丢弃基引擎生成的一些值，以生成随机数。这个适配器模板需要 3 个参数: 要适配的引擎、块大小p 以及使用的块大小 r。 基引擎用于生成p 个随机数。适配器丢弃其中 p - r个数，返回剩下的r个数。
independent_bits_engine 适配器组合由基引擎生成的一些随机数，以生成具有给定位数 w 的随机数。
shuflle_order_engine 适配器生成的随机数和基引擎生成的随机数一致，但顺序不同。这些适配器的具体工作原理与数学知识相关，超出了本书的讨论范围。C++标准中包含一些预定义的随机数引擎适配器。20.3.3 节列出了预定义的随机数引擎和引擎适配器。20.3.3 ”预定义的随机数引擎和引擎适配器
预定义的随机数引擎和引擎适配器
如前所述，建议不要自行指定伪随机数引擎和引擎适配器的参数，而是使用那些标准的随机数引擎。C++定义了表 20-2 所示的预定义引擎和引擎适配器，它们都定义在头文件中。它们都有复杂的模板参数不过，即使不理解这些参数，也可以使用它们。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aCwg1K6W-1633182167484)(/home/xz/图片/选区_999(119)].png)
default_random_engine 与编译器相关。20.3.4 节将列举一个使用这些预定义引擎的例子。
生成随机数
在生成随机数前，首先要创建一个引擎实例。如果使用一个基于软件的引擎，那么还需要定义分布。分布是一个描述数字在特定范围内分布方式的数学公式。创建引擎的推荐方式是使用前面讨论的预定义引擎。下面的例子使用了名为 mt19937 的预定义的梅森旋转算法。这是一个基于软件的生成器。与旧式的 rand()生成器一样，基于软件的引擎也需要使用种子进行初始化。srand()的种子常常是当前时间。在现代 C++中，建议不使用任何基于时间的种子(random_device 不拥有类)，而使用 random_device 生成种子:
random_device seeder;const auto seed = seeder.entropy()?seeder():time(nullptr);
接下来定义了分布。这个例子使用均匀整数分布，在范围 1~99 内分布。在这个例子中，均匀分布很容易使用:
uniform_int_distribution<int> dist(1,99);
定义了引擎和分布后，通过调用分布的函数调用运算符，并将引擎作为参数传入，就可以生成随机数了。在这个例子中写为 dist(eng):
cout<<dis(eng)<<endl;
从这个例子中可以看出,为通过基于软件的引擎生成随机数，总是需要指定引擎和分布。使用第 18 章介绍的定义在头文件中的 std::bind()实用工具，可以避免在生成随机数时指定分布和引擎。下面的例子和前面的例子一样，使用 mt19937 引擎和均匀分布。这个例子通过 std::bind()将 eng 绑定至 dist()的第一个参数，从而定义了 gen()。通过这种方式，调用 gen()生成新的随机数时不需要提供任何参数。然后这个例子演示了如何结合使用 gen()和 generate()算法，为一个 10 元素的 vector 填充随机数。第 18 章讨论了 generate()算法，这个.算法在中定义。
random_device seeder;const auto_seed = seeder.entropy()?seeder():time(nullptr);mt1993 eng(static_cast<mt19937::restulty_type>(seed));uniform_int_distribution<int> dist(1,99);auto gen = std::bind(dist,eng);vector<int> vec(10);generate(begin(vec),end(vec),gen);for(auto i : vec){cout<<i<<" ";}
注意;
记住 generate()算法改写现有的元素，不会插入新的元素。这意味着首先需要将 vector 设置为足够大，以保存所需数目的元素，然后调用 generate()算法。前一个例子将 vector 的大小指定为构造孙数的参数。尽管不知道 gen()的具体类型是什么，但仍可将 gen()传入另一个需要使用生成器的函数。你有两个选项:使用 std::function<int(>类型的参数，或者使用函数模板。上一个例子可改为在 fllVector()函数中生成随机数。下面是使用 std::function 的实现:
void fillVector(vector<int>& vec,const std::function<int()>& generator){ generate(begin(vec),end(vec),generator);}
下面是函数模板版本:
template<typename T>void fillVector(vector<int>& vec,const T& generator){ generate(begin(vec),end(vec),generator);}
按如下方式使用该函数:
#include <iostream>#include <random>#include <ctime>#include <functional>#include <algorithm>using namespace std;template<typename T>void fillVector(vector<int>& vec,const T& generator){ generate(begin(vec),end(vec),generator);}int main(){ random_device seeder; const auto seed = seeder.entropy()?seeder():time(nullptr); mt19937 eng(static_cast<mt19937::result_type>(seed)); uniform_int_distribution<int> dist(1,99); auto gen = std::bind(dist,eng); vector<int> vec(10); fillVector(vec, gen); for(auto i : vec) { cout<<i<<" ";} return 0;}
输出
xz@xiaqiu:~/study/test/test$ ./test9 76 95 64 57 41 29 43 6 53 x
随机数分布
分布是一个描述数字在特定范围内分布的数学公式。随机数生成器库带有的分布可与伪随机数引擎结合使用，从而定义生成的随机数的分布。这是一种压缩的表示形式。每个分布的第一行是类的名称和类模板参数(如果有的话)。接下来的行是这个分布的构造函数。每个分布只列出了一个构造函数，以帮助读者理解这个类。标准库参考资源(见附录 B)列出了每个分布的所有构造函数和方法。
均匀分布
template<class IntType = int> class uniform_int_distribution
uniform_int_distribution(IntType a = 0,IntType b = numeric_limits<IntType>::max());
template<class RealType = double> class uniform_real_distribution
uniform_real_distribution(RealType a = 0.0, RealType b = 1.0);
伯努利分布:
class bernoulli_distributionbernoulli_distribution(double p = 0.5);template<class IntType = int> class binomial_distributionbinomial_distribution(IntType t = 1, double p = 0.5);template<class IntType = int> class geometric_distributiongeometric_distribution(double p = 0.5);template<class IntType = int> class negative_binomial_distributionnegative_binomial_distribution(IntType k = 1, double p = 0.5);
泊松分布
template<class IntType = int> class poisson_distributionpoisson_distribution(double mean = 1.0);template<class RealType = double> class exponential_distributionexponential_distribution(RealType lambda = 1.0);template<class RealType = double> class gamma_distributiongamma_distribution(RealType alpha = 1.0, RealType beta = 1.0);template<class RealType = double> class weibull_distributionweibull_distribution(RealType a = 1.0, RealType b = 1.0);template<class RealType = double> class extreme_value_distributionextreme_value_distribution(RealType a = 0.0, RealType b = 1.0);
正态分布;
template<class RealType = double> class normal_distributionnormal_distribution(RealType mean = 0.0, RealType stddev = 1.0);template<class RealType = double> class lognormal_distributionlognormal_distribution(RealType m = 0.0, RealType s = 1.0);template<class RealType = double> class chi_squared_distributionchi_squared_distribution(RealType n = 1);template<class RealType = double> class cauchy_distributioncauchy_distribution(RealType a = 0.0, RealType b = 1.0);template<class RealType = double> class fisher_f_distributionfisher_f_distribution(RealType m = 1, RealType n = 1);template<class RealType = double> class student_t_distributionstudent_t_distribution(RealType n = 1);
采样分布
template<class IntType = int> class discrete_distributiondiscrete_distribution(initializer_list<double> wl);template<class RealType = double> class piecewise_constant_distributiontemplate<class UnaryOperation>piecewise_constant_distribution(initializer_list<RealType> bl,UnaryOperation fw);template<class RealType = double> class piecewise_linear_distributiontemplate<class UnaryOperation>piecewise_linear_distribution(initializer_list<RealType> bl,UnaryOperation fw);
每个分布都需要一组参数。对这些数学参数的详细解释超出了本书的范围，本节剩余部分将列举一些例子来解释分布对生成的随机数造成的影响。观察图形是理解分布的最简便方法。例如，下面的代码生成 100 万个介于 1 和 99 之间的随机数，然后计算1 和 99 之间的某个数字被随机选择的次数。将结果保存在一个 map 中, 这个 map 的键是介于 1 到 99 之间的数，与键关联的值是这个键被随机选择的次数。在循环之后，将结果写入一个 CSV(喜号分隔值)文件，然后可在电子表格应用程序中打开这个文件
const unsigned int kStart = 1;const unsigned int kEnd = 99;const unsigned int kIteration = 1'000'000;
optional
std::optional 在中定义，用于保存特定类型的值，或什么都不保存。如果希望值是可选的，可将其用作函数的参数。如果函数可以返回一些值，或什么都不返回，通常也可将其用作函数的返回类型。这样，就不必从函数返回特殊值，如 nullptr、end()、- 1 和 EOF 等。这样，也不必使编写的函数返回布尔值，同时在引用输出参数中存储实际值，如 bool getData(T& dataOub)。在下面的示例中，函数返回 optional;
optiona<int> getData(bool giveIt){ if(giveIt) { return 42; } return nullopt;
可采用如下方式调用该函数:
auto data1 = getData(true);auto data2 = getData(false);
要确定 optional 是否具有值，可使用 has_value()方法，或在 让语句中使用 optional;
cout<<"data1.has_value = "<<data1.has_value()<<endl;if(data2){ cout<<"data2 has a value."<<endl;}
如果 optional 具有值，可使用 value()接收它，或使用以下反引用运算符，
cout<<"data1.value = "<<data1.value()<<endl;cout<<"data1.value = "<<*data1<<endl;
如果在空的 optional 上调用 value()，将抛出 bad_optional_ access 异常。
可使用 value_or()返回 optional 值，或在 optional 为空时返回另一个值:
cout<<"data2.value = "<<data2.value_or(0)<<endl;
注意，不能在 optional 中存储引用，因此 optional<T&>不可行。相反，应当使用 optional<T*>、optional<reference_ wrapper>或optional<reference_ wrapper>。第17章曾讲过, 可使用std::ref()或 cref()分别创建 std::reference_wrapper或 reference_ wrapper 。
variant
std::variant 在 中定义，可用于保存给定类型集合的一个值。定义 variant 时，必须指定它可能包含的类型。例如，以下代码定义 variant 一次可以包含整数、字符串或浮点值;
variant<int,string,float>v;
这里，这个默认构造的 variant 包含第一个类型(此处是 int)的默认构造值。要默认构造 variant，务必确保variant 的第一个类型是默认可构造的。例如，下面的代码无法编译，因为 Foo 不是默认可构造的。
class Foo{public:Foo() = delete;F(int){}};
class Bar{public:Bar() = delete;Bar(int){}};
事实上，Foo 和 Bar 都不是默认可构造的。如果仍需要默认构造 variant，可使用 std::monostate(一个空的替代)作为 variant 的第一个类型:
variant<monostate,Foo,Bar> v;
可使用赋值运算符，在 variant 中存储内容:
variant<int,string,float> v;v = 12;v = 12.5f;v = "An std::string"s;
variant 在任何给定时间只能包含一个值。因此，对于这三行代码，首先将整数 12 存储在 variant 中，然后将 variant 改为包含浮点值，最后将 variant 改为包含字符串。定 variant 当前是否包含特定类型的值:
cout<<"Type index: "<<v.index()<<endl;cout<<"Contains an int: "<<holds_alternative<int>(v)<<endl;
输出如下所示:
Type index: 1Contains an int: 0
使用 std::get()或 std::get()从 variant 检索值。如果使用类型的索引，或使用与 variant 的当前值不匹配的类型，这些函数抛出 bad_variant_access 异常:
cout<<std::get<string>(v)<<endl;
try
{
cout<<std::get<0>(v)<<endl;
}
catch(const bad_variant_access& ex)
{
cout<<"Exception: "<<ex.what()<<endl;
}
输出如下
An std::string
Exception: bad variant access
为避免异常，可使用 std::get_if()或 std::get_if()辅助函数。这些函数接收指向 variant 的指针，返回指向请求值的指针，如果遇到错误，则返回 nullptr。
string* theString = std::get_if<string>(&v);int* theInt = std::get_if<int>(&v);cout<<"retrieved string: "<<(theString?*theString:"null")<<endl;cout<<"retrieved int: "<<(theInt?*theInt:0)<<endl;
输出如下
retrieved string: An std::stringretrieved string: 0
可使用 std::visit()辅助函数，将 visitor 模式应用于 variant。假设以下类定义了多个重载的函数调用运算符，variant 中的每个可能类型对应一个:
class MyVisitor{ public: void operator()(int i){cout<<"int "<<i<<endl;} void operator()(const string& s){cout<<"string "<<s<<endl;} void operator()(float f){cout<<"float "<<f<<endl;}};
可将其与 std::visit()一起使用，如下所示:
visit(MyVisitor(),v);
这样就会根据 variant 中当前存储的值，调用适当的重载的函数调用运算符。这个示例的输出如下:
string An std::string
与 optional 一样，不能在 variant 中存储引用。可以存储指针、reference_ wrapper或 reference_wrapper的实例。
any
std::any 在 中定义，是一个可包含任意类型值的类。一旦构建，可确认 any 实例中是否包含值，以及所包含值的类型。要访问包含的值，需要使用 any_cast()，如果失败，会抛出 bad_any_cast 类型的异常。下面是一个示例，
any empty;
any anInt(3);
any aString("An std::string "s);
cout<<"empty.has_value = "<<empty.has_value()<<endl;
cout<<"anInt.has_value = "<<anInt.has_value()<<endl<<endl;
cout<<"anInt wrapped type = "<<anInt.type().name()<<endl;
cout<<"aString wapped type = "<<aString.type().name()<<endl<<endl;
int theInt = any_cast<int>(anInt);
cout<<theInt<<endl;
try
{
int test = any_cast<int>(aString);
cout<<test<<endl;
}
catch(const bad_any_cast& ex)
{
cout<<"Exception: "<<ex.what()<<endl;
}
输出如下所示。注意，aString 的包装类型与编译器相关。
ampty.has_value = 0;anInt.has_value = 1;anInt wrapped type = int;aString wrapped type = class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char>> 3 Exception: Bad any_cast
可将新值赋给 any 实例，甚至是不同类型的新值
any something(3);
any 的实例可存储在标准库容器中。这样就可在单个容器中存放异构数据。这么做的唯一缺点在于，只能通过显式执行 any_cast 来检索特定值，如下所示:
vector<any> v;v.push_back(any(42));v.push_back(any("An std::string"s));cout<<any_cast<string>(v[1])<<endl;
与 optional 和 variant 一样，无法存储 any 实例的引用。可存储指针，也可存储 reference_ wrapper或 reference_wrapper的实例。
元组
第 17 章介绍的且在中定义的 std::pair 类可保存两个值，每个值都有特定的类型。每个值的类型都应该在编译时确定。下面是一个简单的例子，
pair<int,string> p1(16,"Hello world");pair<bool,float> p2(true,0.1234f);cout << "p1 = (" << p1.first << ", " << p1.second << ")" << endl;cout << "p2 = (" << p2.first << ", " << p2.second << ")" << endl;
输出如下所示
p1 = (16,Hello world)p2 = (1,0.124)
还有 std::tuple 类，这个类定义在头文件中。tuple(元组)是 pair 的泛化，允许存储任意数量的值，每个值都有自己特定的类型。和 pair 一样，tuple 的大小和值类型都是编译时确定的，都是固定的。
tuple 可通过 tuple 构造函数创建，需要指定模板类型和实际值。例如，下面的代码创建了一个tuple，其第一个元素是一个整数，第二个元素是一个字符串，最后一个元素是一个布尔值:
using MyTuple = tuple<int,string,bool>;MyTuple t1(16,"Test",true);
std::get()从 tuple 中获得第 i 个元素，i 是从 0 开始的索引;， 因此<0>表示 tuple 的第一个元素，<1>表示tuple 的第二个元素，依此类推。返回值的类型是 tuple 中那个索引位置的正确类型
cout<<"t1 = (" <<get<0>(t1)<<","<<get<1>(t1)<<", "<<get<2>(t1)<<")"<<endl;
可通过头文件中的 typeid()检查 get()是否返回了正确的类型。下面这段代码的输出表明，get<1>(t1)返回的值确实是 std::string:
const <<"Type of get<1>(t1) = "<<typeid(get<1>(t1)).name()<<endl;
typeid()返回的准确字符串与编译器相关。上面例子中的输出来自 Visual C++ 2017。也可根据类型使用 std::get()从 tuple 中提取元素, 其中了是要提取的元素(而不是索引)的类型.如果 tuple有几个所需类型的元素，编译器会生成错误。例如，可从tl 中提取字符串元素:
cout<<"String = "<<get<string>(t1)<<endl;
遗憾的是，迭代tuple 的值并不简单。无法编写简单循环或调用 get(mytuple)等，因为i 的值在编译时必须是已知的。一种可能的解决方案是使用模板元编程，详见第 22 章，其中举了一个打印 tuple 值的示例。
cout<<"Tuple size = "<<tuple_size<decltype(t1)>::value<<endl;
在 C++17 中，提供了构造函数的模板参数推导规则。在构造 tuple 时，可忽略模板类型形参，让编译器根据传递给构造函数的实参类型，自动进行推导。例如，下面定义同样的世 元组，它包含一个整数、一个字符串和一个布尔值。注意，必须指定"Tests，以确保它是 std::string。
std::tuple t1(16,"Test"s,true);
缘于类型的自动推导，不能通过&来指定引用。如果需要通过构造函数的模板参数推导方式，生成一个包含引用或常量引用的 tuple, 那么需要分别使用 ref()和 cref()。 ref()和 cref()辅助函数在头文件中定义。例如，下面的构造会生成一个类型为 tuple<int double&,const double&, string&>的 tuple:
double d = 3.14;
string str1 = "Test";
std::tuple t2(16,ref(d),ref(str1));
为测试元组 包 中的 double 引用，下面的代码首先将 double 变量的值写入控制台。然后调用 get<1>(t2)，这个函数实际上返回的是对 d 的引用，因为第二个 tuple(索引 1)元素使用了ref(d)。第二行修改引用的变量的值，最后一行展示了 d 的值的确通过保存在 tuple 中的引用修改了。 注意，第三行未能编译，因为 cref()用于第三个tuple 元素，也就是说，它是 d 的常量引用。
cout<<"d = "<<d<<endl;
get<1>(t2) *= 2;
cout<<"d = "<<d<<endl;
如果不使用构造函数的模板参数推导方法，可以使用 std:make_tuple()工具函数创建一个 tuple。利用这个辅助函数模板，只需要指定实际值，即可创建一个 tuple。在编译时自动推导类型，例如
auto t2 = std::make_tuple(16,ref(d),cref(d),ref(str1));
分解元组
可采用两种方法，将一个元组分解为单独的元素:结构化绑定(C++17)以及 std::tie()。
1， 结构化绑定
C++17 引入了结构化绑定，人允许方便地将一个元组分解为多个变量。例如，下面的代码定义了一个tuple，这个tuple包括一个整数、一个字符串和一个布尔值，此后，使用结构化绑定，将这个 tuple 分解为三个独立的变量:
tuple t1(16,"Test"s,true);auto[i,str,b] = t1;cout<<"Decomposed: i= " <<i<<",str = \""<<str<<"\",b= "<<b<<endl;
使用结构化绑定，无法在分解时忽略特定元素。如果 tuple 包含三个元素，则结构化绑定需要三个变量。如果想忽略元素，则必须使用 tie()。tie()的结果。由于 tie()的结果是一个引用 tuple，赋值实际上更改了三个独立变量中的值。
tuple<int,string,bool> t1(16,"Test",true);int i = 0;string str;bool b = false;cout<<"Before: i = "<<i<<",str = \""<<str<<"\",b= "<<b<<endl;tie(i,str,b) = t1;cout<<"After: i= "<<i<<",str = \""str<<"\",b= "<<b<<endl;
结果如下
Before: i = 0,str = "",b = 0After: i = 16,str = "Test",b = 1
有了 tie()，可忽略一些不想分解的元素。并非使用分解值的变量名，而使用特殊的 std::ignore 值。对于前面的例子，这里在调用 tie()时忽略了 tuple 的字符串元素:
tuple<int,string,bool> t1(16,"Test",true);int i = 0;bool b = false;cout<<"Before: i = "<<i<<", b = "<<b<<endl;
下面是新的输出;
Before: i = 0, b = 0After: i = 16,b = 1
串联
通过 std::tuple_cat()可将两个 tuple 串联为一个 tuple。在下面的例子中，t 的类型为 tuple<int，string，bool，double, string>
tuple<int,string,bool>t1(16,"Test",true);tuple<double,string>t2(3.14,"string 2");auto t3 = tuple_cat(t1,t2);auto [i,str,b,d,s] = t3;cout<<i<<" "<<str<<" "<<b<<" "<<d<<" "<<s<<endl;
输出
xz@xiaqiu:~/study/test/test$ ./test16 Test 1 3.14 string 2xz@xiaqiu:~/study/test/test$
比较
tuple 还支持以下比较运算符: ==、!=、<、>、<=和>=。为了能使用这些比较运算符，tuple 中存储的元素类型也应该支持这些操作。例如:
tuple<int,string> t1(123,"def");tuple<int,string> t2(123,"abc");if(t1 < t2){ cout<<"t1 < t2"<<endl;}else{ cout<<"t1 > t2"<<endl;}
输出如下所示;
t1 >= t2
对于包含多个数据成员的自定义类型，tuple 比较可用于方便地实现这些类型的按词典比较运算符。例如，如下简单结构包含三个数据成员:
struct Foo{ int mInt; string mStr; bool mBool;};
当然,在生产环境级别的代码中，私有数据成员应当具有公有 getter 方法和可能的公有 setter 方法。为保持代码简单，抓住要点，本例使用公有的 struct。实现 Foo 的正确 operator<并非易事! 但是，使用 std::tie()和元组比较，则可简单地完成;
bool operator<(const Foo& f1,const Foo& f2){ return tie(f1.mInt,f1.mStr,f1.mBool)<tie(f2.mInt,f2.mStr,f2.mBool);}
下面是一个使用示例;
Foo f1(42,"Hello",0);Foo f2(32,"World",0);cout<<(f1 < f2)<<endl;cout<<(f2 < f1)<<endl;
make_from_tuple()
使用 std::make_from_tuple()可构建一个工类型的对象，将给定 tuple 的元素作为参数传递给 T 的构造函数。例如，假设具有以下类:
class Foo{ public: Foo(string str,int i):mStr(str),mInt(i){} private: string mStr; int mInt;};
可按如下方式使用 make_from_tuple():
auto myTuple = make_tuple("Hello world ",42);auto foo = make_from_tuple<Foo>(myTuple);
提供给 make_from_tuple()的实参未必是一个 tuple，但必须支持 std::get<>和 std::tuple_size。std::array 和std::pair 也满足这些要求。在日常工作中，该函数并不实用， 不过，如果要编写使用模板的泛型代码，或进行模板元编程，那么这个函数可提供便利。
apply()
std::apply()调用给定的函数、lambda 表达式和函数对象等，将给定 tuple 的元素作为实参传递。下面是一个例子:
int add(int a,int b){ return a + b;}...cout<<apply(add,std::make_tuple(39,3))<<endl;
与 make_from_tuple()一样，在日常工作中，该函数并不实用， 不过，如果要编写使用模板的泛型代码，或进行模板元编程，那么这个函数可提供便利。
文件系统支持库
C++17 引入了文件系统支持库，它们全部定义在头文件中，位于 std::filesystem 名称空间。它允许你编写可移植的用于文件系统的代码。使用它，可以区分是目录还是文件，迭代目录的内容，操纵路径，检索文件信息(如大小、扩展名和创建时间等)。下面介绍这个库最重要的两个方面: path(路径)和directory_entry(目录项)。
path
这个库的基本组件是 path。path 可以是绝对路径，也可以是相对路径，可包含文件名，也可不包含文件名。例如，以下代码定义了一些路径，注意使用了原始字符串字面量来避免对反斜线进行转义。
path p1(LR"(D:\Foo\Bar)");
path p2(L"D:/Foo/Bar");
path p3(L"D:/Foo/Bar/MyFile.txt");
path p4(LR"(..\SomeFolder)");
path p5(L"/usr/lib/X11");
将 path 转换为字符串(如使用 c_str()方法)或插入流时，会将其转换为运行代码的系统中的本地格式。例如:
#include <tuple>#include <iostream>#include <filesystem>using namespace std;int main(){ filesystem::path p1(LR"(D:\Foo\Bar)"); filesystem::path p2(L"D:/Foo/Bar"); cout << p1 << endl; cout << p2 << endl; return 0;}
输出如下所示
xz@xiaqiu:~/study/test/test$ ./test"D:\\Foo\\Bar""D:/Foo/Bar"xz@xiaqiu:~/study/test/test$
可使用 append()方法或 operator=，将组件追加到路径。路径会自动添加分隔符。例如:
path p(L"D:\\Foo");p.append("Bar");p /= "Bar";cout<<p<<endl;
输出
"D:\\Foo/Bar/Bar"
可使用 concat(方法或 operatort=，将字符串与现有路径相连。此时路径不会添加分隔符。例如:
path p(L"D:\\Foo");p.concat("Bar");p+="Bar";cout<<p<<endl;
输出
xz@xiaqiu:~/study/test/test$ ./test"D:\\FooBarBar"xz@xiaqiu:~/study/test/test$
警告：
append()和 operator/=自动添加路径分隔符，而 concat()和 operator+=不会自动添加。
path 支持使用迭代器帮代不同的组件，下面是一个示例:
#include <iostream>#include <filesystem>using namespace std;int main(){ filesystem::path p(LR"(./Foo/Bar)"); for(const auto& component : p) { cout<<component<<endl; } return 0;}
输出如下:
xz@xiaqiu:~/study/test/test$ ./test".""Foo""Bar"xz@xiaqiu:~/study/test/test$
path 接口支持 remove_filename() 、replace_filename()、replace_extension() 、root_name()、parent_path()、extension()、has_extension()、is_absolute()和 is_relative()等操作。可参阅标准库参考资源(见附录 B)来查看所有可用功能的完整列表。
directory_entry
path 只表示文件系统的目录或文件。path 可能指不存在的目录或文件。如果想要查询文件系统中的实际目录或文件，需要从 path 构建一个 directory_entry。如果给定目录或文件不存在，该结构会失败。directory_entry接口支持 is_directory()、is_regular_file()、is_socket()、is_symlink()、file_size()和 last_write_time()等操作 。
下例从 path 构建 directory_entry，以查询文件大小:
#include <tuple>#include <iostream>#include <filesystem>using namespace std;int main(){ filesystem::path myPath(L"/home/xz/tool/test"); filesystem::directory_entry dirEntry(myPath); if(dirEntry.exists() && dirEntry.is_regular_file()) { cout<<"File size: "<<dirEntry.file_size()<<endl; } return 0;}
输出
xz@xiaqiu:~/study/test/test$ ./testFile size: 8xz@xiaqiu:~/study/test/test$
辅助函数
有一组完整的辅助函数可供使用。例如，可使用 copy()复制文件或目录，使用 create_directory()在文件系统中创建新目录, 使用 exists()查询给定目录或文件是否存在,使用 file_size()获取文件大小, 使用 last_write_time()获取文件最近一次的修改时间，使用 remove()删除文件，使用 temp_directory_path()获取适于保存临时文件的目录，使用 space()查询文件系统中的可用空间，等等。可参阅标准库参考资源(见附录 B)来查看完整列表。
下面的示例打印文件系统的容量以及当前的可用空间:
#include <tuple>#include <iostream>#include <filesystem>using namespace std;int main(){ filesystem::space_info s = filesystem::space("/home/xz/"); cout<<"Capacity: "<<s.capacity<<endl; cout<<"Free: "<<s.free<<endl; return 0;}
输出
xz@xiaqiu:~/study/test/test$ ./testCapacity: 489639649280Free: 317362716672xz@xiaqiu:~/study/test/test$
目录和迭代
如果想要递归地和迭代给定目录中的所有文件和子目录，可使用如下 recursive _directory iterator:
void processPath(const path& p){ if(!exists(p)) return; auto begin = recursive_directory_iterator(p); auto end recursive_directory_iterator(); for(auto iter = begin;iter!=end;++iter) { const string spacer(iter.depth()*2,' '); auto& entry = *iter; if(is_regular_file(entry)) { cout<<spacer<<"File: "<<entry; cout<<" ("<<file_size(entry) <<" bytes)"<<endl; } else { std::cout<<spacer<<"Dir: "<<entry<<endl; } }}
可按如下方式调用该函数
path p(LR"(/home/xz/study/test/test)");processPath(p);
输出
xz@xiaqiu:~/study/test/test$ ./test
File: "/home/xz/study/test/test/res.csv" (866 bytes)
File: "/home/xz/study/test/test/test.go" (1935 bytes)
File: "/home/xz/study/test/test/test2.cpp" (46 bytes)
File: "/home/xz/study/test/test/test.cpp" (775 bytes)
File: "/home/xz/study/test/test/test1.cpp" (101 bytes)
File: "/home/xz/study/test/test/CMakeLists.txt" (916 bytes)
File: "/home/xz/study/test/test/test" (68096 bytes)
Dir: "/home/xz/study/test/test/build"
也可使用 directory_iterator和欠代目录的内容, 并自行实现递归。下例与上例的作用相同,但用 directory_iterator替代了 recursive _directory_iterator:
void processPath(const path& p, size_t level = 0)
{
if (!exists(p))
{
return;
}
const string spacer(level * 2, ' ');
if (is_regular_file(p))
{
cout << spacer << "File: " << p;
cout << " (" << file_size(p) << " bytes)" << endl;
}
else if (is_directory(p))
{
std::cout << spacer << "Dir: " << p << endl;
for (auto& entry : directory_iterator(p))
{
processPath(entry, level + 1);
}
}
}
掌握 C++的高级特性
第 16-18 章提到，标准库是功能强大的通用容器和算法的集合。你目前了解的信息应该足以满足大部分应用程序的需要。然而，前面的章节只介绍了库的基本功能。可根据需要的方式任意自定义和扩展标准库。例如，可将迭代器应用于输入流和输出流，可编写自己的容器、算法和迭代器;甚至可指定容器使用自定义的内存分配方案。这一章通过容器 hash_map 的开发过程，讲解这些高级特性。
警告;
很少需要自定义和扩展标准库。如果对前面章节讲解的基本标准库容器和算法不其明了，可跳过这一章。不过，如果想理解标准库，而不只满足于使用标准库， 那么本章值得阅读。 你应该很熟悉第 15 章讲解的运算符重载内容，由于这一章大量使用了模板,因此在继续阅读本章之前还应该熟悉第 12 章讲解的模板。
分配器
每个标准库容器都接收 Allocator 类型作为模板参数，大部分情况下默认值就足够了。例如，vector 模板的定义如下所示;
template <class T, class Allocator = allocator<T>> class vector;
容器构造函数还允许指定 Allocator 类型的对象。通过这些额外参数可自定义容器分配内存的方式。容器执行的每一次内存分配都是通过调用 Allocator 对象的 allocate()方法进行的。相反，每一次内存释放都是通过调用Allocator 对象的 deallocate()方法进行的。标准库提供了一个默认的 Allocator 类，名为 allocator，这个类通过对operator new 和 operator delete 进行包装实现了这些方法。如果程序中的容器需要使用自定义的内存分配和释放方案,那么可编写自己的 Allocator 类。有几种原因需要使用自定义的分配器。例如，如果底层分配器的性能无法接受，但可构建蔡换的分配器;或者如果内存碎片问题(大量不同的分配和释放操作导致内存中出现很多不可用的小空洞)严重，那么可以创建某种类型的“对象池” 这种方式称为内存池。如果必须给操作系统特定的功能分配空间，例如共享内存段，那么通过自定义分配器允许在共享内存段内使用标准库容器。自定义分配器的使用很复杂，如果不小心，可能产生很多问题，因此不应该草率地使用自定义分配器。任何提供了 allocate()、deallocate()和其他需要的方法和类型别名的类都可蔡换默认的 allocator 类。C++17 引入了多态内存分配器的概念。对于指定为模板类型参数的容器的分配器，问题在于两个十分相似但具有不同分配器类型的容器区别很大。例如，有具有不同分配器模板类型参数的两个 vector容器是不同的，因此不能将其中一个赋给另一个。std::pmr 名称空间的中定义的多态内存分配器有助于解决这个问题。std::pmr::polymorphicallocator 是适当的分配器类，因为它满足各种要求，如具有 allocate()和 deallocate()方法。polymorphic_allocator的分配行为取决于构建期间的 memory_resource，而非取决于模板类型参数。因此，在分配和释放内存时，虽然具有相同的类型，但不同 polymorphic_allocator 的行为角异。C++标准提供了一些内置的内存资源，可供初始化多态内存分配器: synchronized_pool_resource、unsynchronized_pool_resource 和 monotonic_buffer_resource。然而，根据经验，这些自定义分配器和多态内存分配器相当高级，很少使用。因此本书略去了这些细节。要了解详情，请参阅附录B中列出的C++标准库的相关书籍。
流适配器
标准库提供了 4个流适配器(stream iteraton)。它们是类似于迭代器的类模板，允许将输入流和输出流视为输入迭代器和输出迭代器。通过这些迭代器可对输入流和输出流进行适配，将它们在不同的标准库算法中分别当成来源和目标。下面列出可用的流迭代器:
ostream _ iterator 是一个输出流和途代器
istream_iterator 是一个输入流和从代器
还有 ostreambuf_iterator 和 istreambuf_iterator，但这些都很少使用，此处不详细讨论。
输出流和迭代器
ostream_iterator 是一个输出流和迭代器，是一个类模板，接收元素类型作为类型参数。这个类的构造函数接收的参数包括一个输出流以及要在写入每个元素之后写入流的分隔符字符串。ostream_iterator 通过 operator<<运算符写入元素。例如,可利用 ostream_iterator 和 copy()算法用一行代码打印出容器中的所有元素。copy()的第一个参数是要复制的范围的首迭代器，第二个参数是这个范围的尾和迭代器，第三个参数是目标迭代器。
#include <iostream>#include <iterator>#include <vector>#include <numeric>using namespace std;int main(){ vector<int> myVector(10); iota(begin(myVector),end(myVector),1);
输出
xz@xiaqiu:~/study/test/test$ ./test1 2 3 4 5 6 7 8 9 10
输入流迭代器
还可使用输入流和迭代器 istream_iterator 通过迭代器抽象从输入流中读取值。这是类模板，将元素类型作为类型参数，通过 operator>>运算符读取元素。istream_iterator 可用作算法和容器方法的来源。例如，下面的代码段从控制台读取整数，直到流的末尾。在 Windows 中，按下 Ctrl+Z 和回车键，就会到达流的末尾。 在 Linux 中, 按下 Ctrl+D 和回车键,就会到达流的末尾。accumulate()算法用于计算所有整数之和。注意，可使用 istream_iterator 的默认构造函数创建一个尾迭代器。
cout<<"Enter numbers seperated by white space."<<endl;cout<<"Press Ctr+Z followed by Enter to stop "<<endl;istream_iterator<int> numbersIter(cin);istream_iterator<int> endIter;int sum = accumulate(numbersIter,endIter,0);cout<<"Sum: "<<sum<<endl;
考虑一下这些代码。如果删除所有的输出语句和变量声明，剩下的就是 accumulate()调用。由于使用了算法和输入流先代器，不使用任何显式循环，这行代码会从控制台读取任意数量的整数，并把它们加在一起。
迭代器适配器
标准库提供了 3 个迭代器适配器(iterator adapter)，它们是基于其他迭代器构建的特殊迭代器。这 3 个和迭代器适配器都在头文件中定义。也可以编写自己的迭代器适配器，但本书不讨论这些内容。更多细节可以参考附录 B 中列出的标准库的相关书籍。
反向迭代器
标准库提供了std::reverse_iterator类模板，以反向遍历双向迭代器或随机访问和迭代器。标准库中所有可反向迭代的容器(C++标准中每个容器都是，但forward_list和无序关联容器除外)都提供了类型别名 reverse_iterator以及rbegin0和rend()方法。这些reverse_iterator类型别名的类型是std::reverse_iterator，T等于容器的iterator类型别名。rbegin()方法返回指向容器中最后一个元素的reverse_iterator，rend()方法也返回一个reverse_iterator，这个迭代器指向容器中第一个元素之前的元素。对reverse_iterator应用operator++运算符，会对底层容器友代器调用operator–运算符，反之亦然。例如，可通过以下方式从头到尾遍历一个集合:
for(auto iter = begin(collection);iter != end(collection);++iter){}
要从尾到头遍历这个集合的元素,可调用 rbegin()和 rend()来使用 reverse_iterator。 注意,这里仍使用++iter:
for(auto iter = rbegin(collection);iter != end(collection);++iter){}
std::reverse_iterator 主要用在标准库中没有等价算法能够反向运行的情况。例如，基本的 find()算法搜索序列中的第一个元素。如果想要搜索序列中的最后一个元素，可以改用 reverse_iterator。注意，通过 reverse_iterator调用 find()之类的算法时，算法返回的也是一个 reverse_iterator。通过调用 reverse_iterator 的 base()方法总能得到这个reverse_iterator 中的底层迭代器。不过，考虑到 reverse_iterator 的具体实现，base()返回的迭代器总是引用被调用的 reverse_iterator 引用的元素的后一个元素。为了获取同一元素，必须减去 1。下面是一个结合使用 find()和 reverse_iterator 的例子:
#include <iostream>
#include <iterator>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
template<typename Container>
void populateContainer(Container& cont)
{
int num;
while(true)
{
cout<<"Enter a number (0 to quit):";
cin>>num;
if(num == 0)
{
break;
}
cont.push_back(num);
}
}
int main()
{
vector<int> myVector;
populateContainer(myVector);
int num;
cout << "Enter a number to find: ";
cin >> num;
auto it1 = find(begin(myVector), end(myVector), num);
auto it2 = find(rbegin(myVector), rend(myVector), num);
if (it1 != end(myVector))
{
cout << "Found " << num << " at position " << it1 - begin(myVector) << " going forward " << endl;
cout << "Found " << num << " at position " << it2.base() - 1 - begin(myVector) << " going backward " << endl;
}
else
{
cout << "Failed to find " << num << endl;
}
return 0;
}
輸出
xz@xiaqiu:~/study/test/test$ ./test
Enter a number (0 to quit):1
Enter a number (0 to quit):2
Enter a number (0 to quit):3
Enter a number (0 to quit):3
Enter a number (0 to quit):3
Enter a number (0 to quit):3
Enter a number (0 to quit):3
Enter a number (0 to quit):4
Enter a number (0 to quit):4
Enter a number (0 to quit):4
Enter a number (0 to quit):0
Enter a number to find: 3
Found 3 at position 2 going forward
Found 3 at position 6 going backward
xz@xiaqiu:~/study/test/test$
插入迭代器
根据第 18 章的描述，copy()这类算法并不会将元素插入容器，只是将某个范围内的旧元素替换为新元素。为了让 copy()这类算法的用途更广泛，标准库提供了 3 个插入迭代器以真正将元素插入容器: insert_iterator、back_insert_iterator 和 front_insert_iterator。插入和迭代器根据容器类型模板化, 在构造函数中接收实际的容器引用。通过提供必要的迭代器接口，这些适配器可用作 copy()这类算法的目标迭代器。这些适配器不会替換容器中的元素，而通过调用容器真正插入新元素。基本的 insert_iterator 调用容器的 insert(position，element)方法，back_insert_iterator 调用 push_back(element)方法，front_insert_iterator 调用 push_front(element)方法。例如，结合 back_insert_iterator 和 copy_if()算法能为 vectorTwo 填充来自 vectorOne 的不等于 100 的所有元素:
#include <iostream>
#include <iterator>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
template<typename Container>
void populateContainer(Container& cont)
{
int num;
while(true)
{
cout<<"Enter a number (0 to quit):";
cin>>num;
if(num == 0)
{
break;
}
cont.push_back(num);
}
}
int main()
{
vector<int> vectorOne, vectorTwo;
populateContainer(vectorOne);
back_insert_iterator<vector<int>> inserter(vectorTwo);
copy_if(cbegin(vectorOne), cend(vectorOne), inserter,
[](int i){ return i != 100; });
copy(cbegin(vectorTwo), cend(vectorTwo), ostream_iterator<int>(cout, " "));
return 0;
}
輸出
xz@xiaqiu:~/study/test/test$ ./test
Enter a number (0 to quit):10
Enter a number (0 to quit):1
Enter a number (0 to quit):1
Enter a number (0 to quit):1
Enter a number (0 to quit):1
Enter a number (0 to quit):20
Enter a number (0 to quit):20
Enter a number (0 to quit):20
Enter a number (0 to quit):20
Enter a number (0 to quit):100
Enter a number (0 to quit):100
Enter a number (0 to quit):1001
Enter a number (0 to quit):100
Enter a number (0 to quit):100
Enter a number (0 to quit):0
10 1 1 1 1 20 20 20 20 1001
从这段代码可看出，在使用插入迭代器时，不需要事先调整目标容器的大小。也可通过 std::back_inserter()具函数创建一个 back_insert_iteritor。例如，在前一个例子中，可删除定义inserter 变量的那一行代码，然后将 copy_if()调用改写为以下代码。结果和之前的实现完全相同:
copy_if(cbegin(vectorOne), cend(vectorOne), back_inserter(vectorTwo), [](int i){ return i != 100; });
使用 C++17 的构造函数模板参数推导，可改写成以下形式:
copy_if(cbegin(vectorOne), cend(vectorOne),
back_insert_iterator(vectorTwo), [](int i) { return i != 100; });
front_insert_iterator 和 insert_iterator 的工作方式类似, 区别在于 insert_iterator 在构造函数中还接收初始的迭代器位置作为参数，并将这个位置传入第一次 insert(position, element)调用。后续的迭代器位置提示通过每一次insert()调用的返回值生成。使用 insert_iterator 的一个巨大好处是可将关联容器用作修改类算法的目标。第 18 章讲解了关联容器的问题，就是不允许修改迭代的元素。通过 insert_iterator 则可插入元素。关联容器实际上支持将接收迭代器位置作为参数的 insert)，并将这个位置用作“提示”，但这个位置可忽略。在关联容器上使用 insert_iterator 时，可传入容器的 begin()或 end()和迭代器用作提示。insert_iterator 在每次调用 insert()后修改传输给 insert()的欠代器提示，使其成为刚插入元素之后的那个位置。下面是前一个例子的修改版本，在这个版本中目标容器是 set 而不是 vector:
vector<int> vectorOne;set<int> setOne;populateContainer(vectorOne);insert_iterator<set<int>> inserter(setOne, begin(setOne));copy_if(cbegin(vectorOne), cend(vectorOne), inserter, [](int i){ return i != 100; });copy(cbegin(setOne), cend(setOne), ostream_iterator<int>(cout, " "));
与back_insert_iterator 示例类似，可使用 std::inserter()工具函数来创建 insert_iterator:
copy_if(cbegin(vectorOne), cend(vectorOne),inserter(setOne, begin(setOne)),[](int i){ return i != 100; });
也可使用 C++17 的构造函数模板参数推导
copy_if(cbegin(vectorOne), cend(vectorOne),insert_iterator(setOne, begin(setOne)),[](int i) { return i != 100; });
移动迭代器
第 9 章讨论了移动语义，假设源对象会在赋值构造或复制构造后销毁，那么使用这种语义可以避免不必要的复制。和迭代适配器 std::move_iterator 的解除引用运算符会自动将值转换为 rvalue 引用，也就是说，这个值可移动到新的目的地, 而不会有复制开销。在使用移动语义前, 需要保证对象支持移动语义。 下面的 MoveableClass支持移动语义。更多细节请参阅第9 章。
class MoveableClass{ public: MoveableClass() { cout<<"Default constructor"<<endl; } MoveableClass(const MoveableClass& src) { cout<<"Copy constructor"<<endl; } Moveableclass(MoveableClass&& src) noexcept { cout<<"Move contructor"<<endl; } MoveableClass& operator=(const MoveableClass& rhs) { cout<<"Copy assigment operator"<<endl; return *this; } MoveableClass& operator=(MoveableClass&& rhs) noexcept { cout<<"Move assignment operator "<<endl; return *this; }};
这里的构造函数和赋值运算符没有做实际事情，只是打印出一条信息，以说明调用的内容。现在有了这个类之后，可定义一个 vector，并保存一些 MoveableClass 实例，如下所示;
int main(){ vector<MoveableClass> vecSource; MoveableClass mc; vecSource.push_back(mc); vecSource.push_back(mc); return 0;}
輸出如下
xz@xiaqiu:~/study/test/test$ ./testDefault constructor [1]Copy constructor [2]Copy constructor [3]Move contructor [4]xz@xiaqiu:~/study/test/test$
这段代码的第二行通过默认构造函数([1])创建一个 MoveableClass 实例。第一个 push_back()调用触发了复制构造函数，将 mc 复制至这个 vector ([2])。执行该操作后，这个 vector 就有了一个元素的空间，即 mc 的第一份副本。注意上述讨论基于 Microsoft Visual C++ 2017 实现的 vector 初始大小和空间增长策略。C++标准没有指定 vector 的初始容量和空间增长策略，所以输出随编译器而异。第二个 push_back()调用触发这个 vector 调整自身大小，为第二个元素分配空间。这个调整大小的操作会调用移动构造函数，将旧 vector 中的每个元素移动到新的调整大小后的 vector 中([4])。之后，再触发复制构造函数，再次将 mc 复制到这个 vector 中([3])。移动和复制顺序未定义，因此可以交换[3]和[4]的顺序。
可创建一个名为 vecOne 的新 vector，其中包含 vecSource 中的所有元素，代码如下所示:
int main()
{
vector<MoveableClass> vecSource;
MoveableClass mc;
vecSource.push_back(mc);
vecSource.push_back(mc);
std::cout<<"------------------------------"<<std::endl;
vector<MoveableClass> vecOne(cbegin(vecSource),cend(vecSource));
return 0;
}
如果不使用 move_iterator，这段代码会触发两次复制构造函数，为 vecSource 中的每个元素触发一次:
xz@xiaqiu:~/study/test/test$ ./testDefault constructorCopy constructorCopy constructorMove contructor------------------------------Copy constructorCopy constructorxz@xiaqiu:~/study/test/test$
通过 std::make_move_iterator()函数创建 move_iterator, 调用的是 MoveableClass 的移动构造函数而不是复制构造函数:
int main(){ vector<MoveableClass> vecSource; MoveableClass mc; vecSource.push_back(mc); vecSource.push_back(mc); std::cout<<"------------------------------"<<std::endl; vector<MoveableClass> vecTwo(make_move_iterator(begin(vecSource)), make_move_iterator(end(vecSource))); return 0;}
輸出
xz@xiaqiu:~/study/test/test$ ./testDefault constructorCopy constructorCopy constructorMove contructor------------------------------Move contructorMove contructorxz@xiaqiu:~/study/test/test$
也可以使用 C++17 的构造函数模板参数推导;
vector<MoveableClass> vecTwo(move_iterator(begin(vecSource)), move_iterator(end(vecSource)));
扩展标准库
标准库包含很多有用的容器、算法和迭代器，可在应用程序中使用这些工具。然而，任何库都不可能包含所有潜在客户可能需要的所有工具。因此，库最好具有可扩展性; 允许客户基于基本功能进行适配和添加功能，从而得到客户需要的准确功能。标准库本质上就是可扩展的，因为标准库的基础结构将数据和操作数据的算法分开了。提供符合标准库标准的迭代器，就可以自行编写能够用于标准库算法的容器。类似地，还可编写能操纵标准容器迭代器的算法。注意不能把自己的容器和算法放在 std 名称空间中。
扩展标准库的原因
准备用 C++编写算法或容器时，可遵循或不遵循标准库的约定。对于简单的容器和算法来说，可能不值得为遵循标准库规范而付出额外的努力。然而，对于打算重用的重要代码，这些努力是值得的。首先，代码更容易被其他 C++程序员理解，因为代码遵从构建良好的接口规范。其次，可将自己的容器和算法与标准库中的其他部分(算法或容器)结合使用，而不需要提供特别的修改版或适配器。最后，可强迫遵循开发稳固代码所需的严格规范。
編写标准库算法
第 18 章描述了标准库中的一组有用算法,但有时需要在自己的程序中使用新算法。这种情况下，编写和标准算法一样能操纵标准库迭代器的算法并不难。
- find_all()
假设需要在指定范围内找到满足某个谓词的所有元素。find()和 find_if()是最符合条件的备选算法，但这些算法返回的都是仅引用一个元素的迭代器。可使用 copy_if()找出所有满足谓词的元素，但会用所找到元素的副本填充输出。如果想要避免复制，可使用 copy_if()和 back insert_iterator(在 vector<reference_wrapper>中)，但这不能给出所找到元素的位置。事实上，无法利用任何一种标准算法找到满足谓词的所有元素的迭代器，但可自行编写能提供这个功能的版本，称为 find_all()。
第一个任务是定义函数原型。可遵循 copy_if()采用的模型。 这应该是一个带有 3 个类型参数的模板化函数:输入迭代器类型、输出迭代器类型和谓词类型。这个函数的参数为输入序列的首尾迭代器、输出序列的首迭代器以及谓词对象。与 copy_if()一样，该算法给输出序列返回一个迭代器，指向输出序列中存储的最后一个元素后面的那个元素。下面是算法原型:
template <typename InputIterator,typename OutputIterator, typename Predicate>OutputIterator find_all(InputIterator first,InputIterator last, OutputIterator dest,Predicate pred);
另一种可选方案是忽略输出迭代器，给输入序列返回一个迭代器，遍历输入序列中所有匹配的元素，但是这种方案要求编写自定义的迭代器类，见稍后的讨论。下一项任务是编写算法的实现。find_all()算法遍历输入序列中的所有元素，给每个元素调用谓词，把匹配元素的迭代器存储在输出序列中。下面是算法的实现
template <typename InputIterator, typename OutputIterator,
typename Predicate>
OutputIterator find_all(InputIterator first, InputIterator last,
OutputIterator dest, Predicate pred)
{
while (first != last)
{
if (pred(*first))
{
*dest = first;
++dest;
}
++first;
}
return dest;
}
与 copy_if()类似，该算法也只覆盖输出序列中的已有元素，所以确保输出序列足够大，以存储结果，或者使用迭代适配器，例如下面代码中的 back_insert_iterator。找到引用所有匹配的元素后，代码计算找到的元素个
int main()
{
vector<int> vec{3, 4, 5, 4, 5, 6, 5, 8};
vector<vector<int>::iterator> matches;
find_all(begin(vec),end(vec),back_inserter(matches),
[](int i){ return i == 5;});
cout<<"Found "<<matches.size()<<" matching elements:"<<endl;
for(const auto& it : matches)
{
cout<<*it<<" at position "<<(it - cbegin(vec))<<endl;
}
return 0;
}
输出
xz@xiaqiu:~/study/test/test$ ./testFound 3 matching elements:5 at position 25 at position 45 at position 6xz@xiaqiu:~/study/test/test$
2.iterator_traits
一些算法的实现需要迭代器的额外信息。例如，为保存临时值，算法可能需要知道迭代器引用的元素的类型，还可能需要知道迭代器是双向访问的还是随机访问的。C++提供了一个名为iterator_traits 的类模板, 以找到这些信息。通过要使用的迭代器类型实例化iterator_traits类模板，然后可访问以下 5 个类型别名: value_type、difference_type、iterator_category、pointer 和 reference。例如,下面的模板函数声明了一个临时变量, 其类型是 IteratorType 类型的友代器引用的类型。注意,在 iterator_traits这行前面要使用 typename 关键字。访问基于一个或多个模板参数的类型时，必须显式地指定 typename。在这个例子中，模板参数 IteratorType 用于访问 value_type 类型;
#include <iterator>template <typename IteratorType>void iteratorTraitsTest(IteratorType it){ typename std::iterator_traits<IteratorType>::value_type temp; temp = *it; cout<<temp<<endl;}
可通过以下代码测试这个函数:
int main(){ vector<int> v{ 5 }; iteratorTraitsTest(cbegin(v)); return 0;}
输出
xz@xiaqiu:~/study/test/test$ ./test
5
xz@xiaqiu:~/study/test/test$
在这段代码中，iteratorTraitsTest()函数中 temp 变量的类型为int。输出是 5。在这个例子中，通过 auto 关键字可简化上述代码，但这样无法说明如何使用 iterator_traits 类模板。
编写标准库容器
C++标准包含要把容器作为标准库容器应该满足的要求列表。此外，如果想要一个容器为顺序容器(例如 vector)、有序关联容器(例如 map)或无序关联容器(例如unordered_map)，那么这个容器还必须满足额外的要求。我们对编写新容器的建议是: 首先编写遵循一般标准库规则的基本容器，例如编写类模板，不用太关心遵循标准库的细节。开发基本实现后，可添加迭代器和方法，使容器能配合标准库框架工作。本章采用这种方式开发了一个hash_map。
注意:
建议使用标准 C++的无序关联容器(也称为哈希表)，而不是自己实现一个。第 17 章讲解的这些无序关联容器包括 unordered_map、unordered_multimap、unordered_set 和 unordered_multiset。 本章中的 hash_map 用于演示如何编写标准库容器。
- 基本的 hash_map
C++11 开始支持哈希表，见第 17 章的讨论。然而，之前版本的 C++并不支持哈希表。标准库中的 map 和 set 提供对数时间复杂度的插入、查找和删除操作，而哈希表与此不同，它提供一般情况下常量时间复杂度的插入、查找和操作，以及最坏情况下线性时间复杂度的相应操作。哈希表不将元素以有序方式保存，而是将每个元素哈希(或称为映射)到某个哈希桶中。只要保存的元素数量不显著多于桶的数目，而且哈希函数能将元素均匀地分布在所有的桶中，那么插入、删除和查找操作都能以常量时间执行。
注意:
本节假定你热悉哈希数据结构。如果还不熟悉，请参阅第 17 章，其中包含对哈希表的讨论，还可以参阅附录B 中列出的任何标准数据结构文献。
本节实现一个简单却功能全面的 hash_map。和 map 一样，hash_map 保存的是键值对。事实上，hash_map提供的操作几乎等同于 map 提供的操作，只不过性能不同。这个 hash_map 实现使用了链式哈希(chained hashing，也称为开放哈希)，但是没有提供重新哈希这种高级功能。17.5 节“无序关联容器/哈希表”讲解了链式哈希的概念。
哈希函数
编写 hash_map 需要做的第一个决策是如何处理哈希函数。有个说法: 好的抽象应该让简单的情况简单处理，还能处理复杂的情况，好的 hash_map 接口允许客户指定自己的哈希函数和哈希桶的数目，以自定义哈希行为，满足特定的工作负载。另外，不需要自定义或没有能力编写好的哈希函数以及选择哈希桶数目的那些客户，应该能够在使用容器时不考虑这些。一种解决方案是允许客户在 hash_map 构造函数中提供哈希函数和哈希桶的数目，还要提供默认值。在这种实现中，哈希函数是一个简单的函数对象，只包含一个函数调用运算符。函数对象在要哈希的键类型上模板化，以支持模板化的 hash_map 容器。模板特例可用于给某些类型编写自定义的哈希函数。基本的函数对象如下所示:
template <typename T>class hash{ public: size_t operator()(const T& key) const;};
注意，hash_map 实现的所有内容都放在 ProCpp 名称空间中，这样名称就不会与已有的名称冲突。hash 函数调用运算符的实现比较复杂，原因是它必须能应用于任意类型的键。下面的实现把键作为一系列字节，计算一个整数的哈希值;
遗城的是，对字符串应用上述哈希方法时，这个函数会计算整个字符串对象的哈希，而不是实际文本的哈希。实际文本可能在堆上，字符串对象只包含长度和指向堆上文本的指针。指针是不同的，即使指向的文本相同。这样的结果就是两个文本相同的字符串对象会生成不同的哈希值。因此，最好专门为字符串提供哈希模板的特殊版本，为包含动态分配内存的任何类提供泛型模板。第 12 章更深入地讨论了模板特化。
如果要将其他指针类型或对象用作键，那么必须为这些类型编写自定义的哈希特化。
警告
这一节中的哈希函数是基本 hash_map 实现的示例。这些哈希函数不能保证对所有的键均匀哈希。如果需要编写数学上更严庶的哈希函数，或者根本不知道什么是“均匀哈希"，那么请参考附录 B 中列出的算法参考。
hash_map 接口
hash_map 支持三类基本操作: 插入、删除和查找。hash_map 也是可交换的。当然，它还提供了构造函数。复制和移动构造函数被显式设置为默认，并提供复制和移动赋值运算符。下面是 hash_map 类模板中的公共部分:
template <typename Key, typename T,
typename KeyEqual = std::equal_to<>,
typename Hash = hash<Key>>
class hash_map
{
public:
using key_type = Key;
using mapped_type = T;
using value_type = std::pair<const Key, T>;
virtual ~hash_map() = default;
explicit hash_map(const KeyEqual &equal = KeyEqual(),
size_t numBuckets = 101,
const Hash &hash = Hash());
hash_map(const hash_map<Key, T, KeyEqual, Hash> &src) = default;
hash_map(hash_map<Key, T, KeyEqual, Hash> &&src) noexcept = default;
hash_map<Key, T, KeyEqual, Hash> &operator=(
const hash_map<Key, T, KeyEqual, Hash> &rhs);
hash_map<Key, T, KeyEqual, Hash> &operator=(
hash_map<Key, T, KeyEqual, Hash> &&rhs) noexcept;
void insert(const value_type &x);
void erase(const key_type &k);
void clear() noexcept;
value_type *find(const key_type &k);
const value_type *find(const key_type &k) const;
T &operator[](const key_type &k);
void swap(hash_map<Key, T, KeyEqual, Hash> &other) noexcept;
private:
using ListType = std::list<value_type>;
std::pair<typename ListType::iterator, size_t> findElement(const key_type& k);
std::vector<ListType>mBuckets;
size_t mSize = 0;
KeyEqual mEqual;
Hash mHash;
};
从中可以看出，和标准库的 map 一样，键和值的类型都是模板参数。hash_map 在容器中保存的实际元素是 pair<const Key, T>。insert()、erase()、find()和 operator[]方法都很简单。然而，这个接口还有几处需要详细解释。
模板参数 KeyEqual
与 map、set 以及其他标准容器一样，hash_map 允许客户在模板参数中指定比较类型，并在构造函数中传入相应类型的特定比较对象。和 map 及 set 的不同之处在于，hash_map 不会根据键对元素排序，但是仍然需要比较键是否相等。因此，hash_map 没有使用 less 作为默认的比较类型，而是使用 equal_ to。比较对象的唯一目的是检测是否向容器插入重复的键。
模板参数
应能修改哈希函数，以更好地适应要存储在 hash_map 中的元素类型。因此，hash_map 模板接收 4 个模板参数: 键类型、值类型、比较类型和哈希类型。
类型别名
hash_map 类模板定义了 3 个类型别名:
using key_type = Key;using mapped_type = T;using value_type = std::pair<const Key,T>;
value_type 用于引用复杂的 pair<const Key, T>类型。你在后面会了解到，这些类型别名也是 C++标准对标准库容器的要求。
实现
确定好 hash_map 接口后，需要选择实现模型。基本的哈希表数据结构通常由固定数目的哈希桶组成，每个哈希桶可存储一个或多个元素。哈希桶应该可通过 bucket_id(对键进行哈希的结果)以常量时间访问。因此，vector 是保存哈希桶最合适的容器。每个桶都必须保存一个元素列表，因此可将标准库 list 用作桶的类型。最终结构为: pair<const Key, T>元素的链表 vector。下面是 hash_map 类中的 private 成员:
private: using ListType = std::list<value_type>; std::vector<ListType>mBuckets; size_t mSize = 0; KeyEqual mEqual; Hash mHash;
如果没有 value_type 和 ListType 的类型别名，声明 mBuckets 的那一行可写为:
std::vector<std::list<std::pair<const Key,T>>>mBuckets;
mComp 和 mHash 成员分别保存比较对象和哈希对象，mSize 保存容器中当前的元素个数。
构造函数
构造函数初始化所有字段，并给哈希桶指定正确的大小。遗城的是，模板语法比较复杂。如果对语法感到迷惑不解，请参阅第 12 章，以了解编写类模板的详细信息。
这个实现要求至少一个桶，因此构造函数强制实现了这个限制。
查找元素
hash_map 的三个主要操作(查找、插入和删除)都要求代码根据给定键查找元素。因此，最好实现一个能执行这项任务的 private 辅助方法。findElement()首先通过哈希对象计算键的哈希，并对计算的值取模，将计算出的哈希值限制为哈希桶的数目。然后，在这个桶中查找匹配给定键的元素。元素保存在键值对中，因此实际的比较操作必须针对元素的第一个字段。通过构造函数指定的比较函数对象执行比较操作。
template<typename Key, typename T, typename KeyEqual, typename Hash>std::pair<typename hash_map<Key, T, KeyEqual, Hash>::ListType::iterator, size_t>hash_map<Key, T, KeyEqual, Hash>::findElement(const key_type &k){
注意，findElement()返回 pair，其中包含迭代器和桶索引。桶索引是给定键映射到的桶的索引，与给定键是和否在容器中无关。返回的迭代器指向桶list 中的元素，list 表示键映射到的桶。如果找到元素，人迭代器指向相应的元素，和否则，就是 list 的尾迭代器。
该方法的函数头中的语法较难理解，特别是使用 typename 关键字的部分。使用和模板参数相关的类型时，必须使用 typename 关键字。确切地讲，ListType::iterator 类型就是 list<pair<const Key, T>>::iterator 类型，它与模板参数 Key 和T相关。find()方法可实现为 fndElement()的简单包装:
template<typename Key, typename T, typename KeyEqual, typename Hash>typename hash_map<Key, T, KeyEqual, Hash>::value_type *hash_map<Key, T, KeyEqual, Hash>::find(const key_type &k){
find()的 const 版本使用 const_cast，将请求传递给非 const 版本， 以避免代码重复:
template<typename Key, typename T, typename KeyEqual, typename Hash>const typename hash_map<Key, T, KeyEqual, Hash>::value_type *hash_map<Key, T, KeyEqual, Hash>::find(const key_type &k) const{ return const_cast<hash_map<Key, T, KeyEqual, Hash>*>(this)->find(k);}
operator[]实现使用了 findElement()方法，如果没有找到元素，则插入元素:
template <typename Key, typename T, typename KeyEqual, typename Hash>T &hash_map<Key, T, KeyEqual, Hash>::operator[](const key_type &k){
插入元素
insert()必须首先检查带有该键的元素是否已经在 hash_map 中。如果不在，将元素添加到对应桶的list 中。注意，findElement()通过引用返回那个键哈希到的桶，即使没有找到那个键对应的元素也是如此:
template<typename Key, typename T, typename KeyEqual, typename Hash>void hash_map<Key, T, KeyEqual, Hash>::insert(const value_type &x){
注意 insert()的实现返回 void，因此调用者不知道元素已经插入还是相应的元素已经在 hash_map 中。本章后面为 hash_map 实现和迭代器时，将分析如何克服这个缺点。
删除元素
erase()和insert(采用相同的模式: 首先调用findElement()来搜索元素。如果元素存在，就将元素从对应桶的list中删除。和否则，什么也不做。
template<typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::erase(const key_type &k)
{
auto[it, bucket] = findElement(k);
if (it != end(mBuckets[bucket]))
{
mBuckets[bucket].erase(it);
mSize--;
}
}
交换
swap()方法使用 std::swap()交换所有数据成员:
void hash_map<Key, T, KeyEqual, Hash>::swap(
hash_map<Key, T, KeyEqual, Hash> &other) noexcept
{
using std::swap;
swap(mBuckets, other.mBuckets);
swap(mSize, other.mSize);
swap(mEqual, other.mEqual);
swap(mHash, other.mHash);
}
C++还提供下面独立的 swap()版本，它只是转发给 swap()方法:
template <typename Key, typename T, typename KeyEqual, typename Hash>void swap(hash_map<Key, T, KeyEqual, Hash> &first, hash_map<Key, T, KeyEqual, Hash> &second) noexcept{ first.swap(second);}
赋值运算符
下面是复制和移动赋值运算符的实现。可参见第 9 章讨论的“复制和交换”惯用语法。
template <typename Key, typename T, typename KeyEqual, typename Hash>hash_map<Key, T, KeyEqual, Hash>& hash_map<Key, T, KeyEqual, Hash>::operator=( const hash_map<Key, T, KeyEqual, Hash> &rhs){
使用基本的 hash_map
下面是一个简单的测试程序，演示了如何使用基本的 hash_map 类模板:
hash_map<int,int>myHash;
myHash.insert(make_pair(4,40));
myHash.insert(make_pair(6,60));
auto x2 = myHash.find(4);
if(x2 != nullptr)
{
cout<<"4 maps to "<<x2->second<<endl;
}
else
{
cout<<"cannot find 4 in map"<<endl;
}
myHash[4] = 35;
myHash[4] = 60;
auto x3 = myHash.find(4);
if(x3 != nullptr)
{
cout<<"4 maps to"<<x3->second<<endl;
}
else
{
cout<<"cannot find 4 in map"<<endl;
}
hash_map<int,int> other(std::equal_to<>(),11);
swap(other,myHash);
hash_map<int,int> myHash2(other);
hash_map<int,int> myHash3;
myHash3 = myHash2;
hash_map<int,int>myHash4 (std::move(myHash3));
hash_map<int,int>myHash5;
myHash5 = std::move(myHash4);
代码
#include <iostream>
#include <iterator>
#include <vector>
#include <numeric>
#include <list>
#include <utility>
#include <string>
#include <algorithm>
using namespace std;
namespace ProCpp
{
template <typename T>
class hash
{
public:
size_t operator()(const T &key) const;
};
template <typename T>
size_t hash<T>::operator()(const T &key) const
{
const size_t bytes = sizeof(key);
size_t sum = 0;
for (size_t i = 0; i < bytes; ++i)
{
unsigned char b = *(reinterpret_cast<const unsigned char *>(&key) + i);
sum += b;
}
return sum;
}
template<>
class hash<std::string>
{
public:
size_t operator()(const std::string &key) const;
};
size_t hash<std::string>::operator()(const std::string &key) const
{
size_t sum = 0;
for (auto c : key)
{
sum += static_cast<unsigned char>(c);
}
return sum;
}
template <typename Key, typename T,
typename KeyEqual = std::equal_to<>,
typename Hash = hash<Key>>
class hash_map
{
public:
using key_type = Key;
using mapped_type = T;
using value_type = std::pair<const Key, T>;
virtual ~hash_map() = default;
explicit hash_map(const KeyEqual &equal = KeyEqual(),
size_t numBuckets = 101,
const Hash &hash = Hash());
hash_map(const hash_map<Key, T, KeyEqual, Hash> &src) = default;
hash_map(hash_map<Key, T, KeyEqual, Hash> &&src) noexcept = default;
hash_map<Key, T, KeyEqual, Hash> &operator=(
const hash_map<Key, T, KeyEqual, Hash> &rhs);
hash_map<Key, T, KeyEqual, Hash> &operator=(
hash_map<Key, T, KeyEqual, Hash> &&rhs) noexcept;
void insert(const value_type &x);
void erase(const key_type &k);
void clear() noexcept;
value_type *find(const key_type &k);
const value_type *find(const key_type &k) const;
T &operator[](const key_type &k);
void swap(hash_map<Key, T, KeyEqual, Hash> &other) noexcept;
private:
using ListType = std::list<value_type>;
std::pair<typename ListType::iterator, size_t> findElement(const key_type &k);
std::vector<ListType>mBuckets;
size_t mSize = 0;
KeyEqual mEqual;
Hash mHash;
};
template<typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>::hash_map(
const KeyEqual &equal, size_t numBuckets,
const Hash &hash)
: mBuckets(numBuckets), mEqual(equal), mHash(hash)
{
if (numBuckets == 0)
{
throw std::invalid_argument("Number of buckets must be positive ");
}
}
template<typename Key, typename T, typename KeyEqual, typename Hash>
std::pair<typename hash_map<Key, T, KeyEqual, Hash>::ListType::iterator, size_t>
hash_map<Key, T, KeyEqual, Hash>::findElement(const key_type &k)
{
size_t bucket = mHash(k) % mBuckets.size();
auto iter = find_if(begin(mBuckets[bucket]), end(mBuckets[bucket]),
[this, &k](const auto & element)
{
return mEqual(element.first, k);
});
return std::make_pair(iter, bucket);
}
template<typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::value_type *
hash_map<Key, T, KeyEqual, Hash>::find(const key_type &k)
{
auto[it, bucket] = findElement(k);
if (it == end(mBuckets[bucket]))
{
return nullptr;
}
return &(*it);
}
template<typename Key, typename T, typename KeyEqual, typename Hash>
const typename hash_map<Key, T, KeyEqual, Hash>::value_type *
hash_map<Key, T, KeyEqual, Hash>::find(const key_type &k) const
{
return const_cast<hash_map<Key, T, KeyEqual, Hash>*>(this)->find(k);
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
T &hash_map<Key, T, KeyEqual, Hash>::operator[](const key_type &k)
{
auto[it, bucket] = findElement(k);
if (it == end(mBuckets[bucket]))
{
mSize++;
mBuckets[bucket].push_back(std::make_pair(k, T()));
return mBuckets[bucket].back().second;
}
else
{
return it->second;
}
}
template<typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::insert(const value_type &x)
{
auto[it, bucket] = findElement(x.first);
if (it != end(mBuckets[bucket]))
{
return;
}
else
{
mSize++;
mBuckets[bucket].push_back(x);
}
}
template<typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::erase(const key_type &k)
{
auto[it, bucket] = findElement(k);
if (it != end(mBuckets[bucket]))
{
mBuckets[bucket].erase(it);
mSize--;
}
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::swap(
hash_map<Key, T, KeyEqual, Hash> &other) noexcept
{
using std::swap;
swap(mBuckets, other.mBuckets);
swap(mSize, other.mSize);
swap(mEqual, other.mEqual);
swap(mHash, other.mHash);
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
void swap(hash_map<Key, T, KeyEqual, Hash> &first, hash_map<Key, T, KeyEqual, Hash> &second) noexcept
{
first.swap(second);
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash> &
hash_map<Key, T, KeyEqual, Hash>::operator=(
const hash_map<Key, T, KeyEqual, Hash> &rhs)
{
if (this == &rhs)
{
return *this;
}
auto copy = rhs;
swap(copy);
return *this;
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash> &
hash_map<Key, T, KeyEqual, Hash>::operator=
(hash_map<Key, T, KeyEqual, Hash> &&rhs) noexcept
{
swap(rhs);
return *this;
}
}
int main()
{
ProCpp::hash_map<int, int>myHash;
myHash.insert(make_pair(4, 40));
myHash.insert(make_pair(6, 60));
auto x2 = myHash.find(4);
if (x2 != nullptr)
{
cout << "4 maps to " << x2->second << endl;
}
else
{
cout << "cannot find 4 in map" << endl;
}
myHash[4] = 35;
myHash[4] = 60;
auto x3 = myHash.find(4);
if (x3 != nullptr)
{
cout << "4 maps to " << x3->second << endl;
}
else
{
cout << "cannot find 4 in map" << endl;
}
ProCpp::hash_map<int, int> other(std::equal_to<>(), 11);
swap(other, myHash);
ProCpp::hash_map<int, int> myHash2(other);
ProCpp::hash_map<int, int> myHash3;
myHash3 = myHash2;
ProCpp::hash_map<int, int>myHash4 (std::move(myHash3));
ProCpp::hash_map<int, int>myHash5;
myHash5 = std::move(myHash4);
return 0;
}
输出
xz@xiaqiu:~/study/test/test$ ./test4 maps to 404 maps to 60xz@xiaqiu:~/study/test/test$
- 将 hash_map 实现为标准库容器
前面讨论的基本 hash_map 遵循标准库的思想，但没有遵循详细的规范。在大部分场合中，上面的实现已经足够好了。然而，如果想在 hash_map 上使用标准库算法，还需要多做一些工作。C++标准指定了数据结构作为标准库容器必须提供的方法和类型别名。需要的类型别名
C++标准指定每个标准库容器都要有表 21-1 所示的 public 类型别名。
| 类型名称 | 说明 |
|---|
| value_type | 容器中保存的元素类型 | | reference | 容器中保存的元素类型的引用 | | const_reference | 容器中保存的元素类型的 const 引用 | | iterator | 遍历容器中元素的类型 | | const_iterator | 另一个版本的 iterator，遍历容器中的 const 元素 | | size_type | 表示容器中元素个数的类型，通常为 size_t(来自) | | difference_ type | 表示用于容器的两个 iterator 间差值的类型，通常为 ptrdiff t(来自) |
下面是 hash_map 实现这些类型别名的类模板定义，除了 iterator 和 const_iterator。后面将详细讲解迭代器的编写方式。注意 value_type(再加上后面要讨论的 key_type 和 mapped_type)在旧版本的 hash_map 中就已经定义了。这个实现还添加了类型别名 hash_map_type，用于给 hash_map 的特定模板实例指定短名:
template<typename Key, typename T,typename KeyEqual = std::equal_to<>,typename Hash = hash<Key>>class hash_map{ public: using key_type = Key; using mapped_type = T; using reference = value_type&; using const_reference = const value_type&; using size_type = size_t; using difference_type = ptrdiff_t; using hash_map_type = hash_map<Key, T, KeyEqual, Hash>;
要求容器提供的方法
除类型别名外，每个容器必须提供表 21-2 所示的方法。
| 方法 | 说 明 | 最坏情况下的复杂度 |
|---|
| 默认构造函数 | 构造一个空容器 | 常量时间复杂度 | | 复制构造函数 | 执行容器的深复制 | 线性时间复杂度 | | 移动构造函数 | 执行移动构造操作 | 常量时间复杂度 | | 复制赋值运算符 | 执行容器的深度复制 | 线性时间复杂度 | | 移动赋值运算符 | 执行移动赋值操作 | 常量时间复杂度 | | 析构函数 | 销毁动态分配的内存，对容器中剩余的所有元素调用析构函数 | 线性时间复杂度 | | iterator begin(); const_iterator begin() const; | 返回引用容器中第一个元素的迭代器 | 常量时间复杂度 | | iterator end(); const_terator end() const; | 返回引用容器中最后一个元素后面那个位置的迭代器 | 常量时间复杂度 | | const_iterator cbegin() const; | 返回引用容器中第一个const迭代器 | 常量时间复杂度 | | const_iterator cend() const; | 返回引用容器中最后一个元素后面那个位置的const迭代器 | 常量时间复杂度 | | operator== operator!= | 逐元素比较两个容器的比较运算符 | 线性时间复杂度 | | void swap(Container&) noexcept | 对作为参数传入这个方法的容器中的内容, 以及在其中调用这个 | 常量时间复杂度 | | size_type size() const | 返回容器中元素的个数 | 常量时间复杂度 | | size_type max_size() const; | 返回容器可以保存的最大元素数目 | 常量时间复杂度 | | bool empty() const; | 指定容器是否包含任何元素 | 常量时间复杂度 |
注意:
在这个 hash map 示例中，忽略了比较运算符。实现这些运算符对读者来说是很好的练习，但首先必须考虑两个 hash_map 的相等语义。一种可能是，只有当两个 hash_ map 的桶数量完全相同，而且桶的内容相同时，它们才是相等的。与此类似，必须考虑一个 hash_map 小于另一个 hash_map 的含义。一种选择是将它们定义为元素的成对比较。
下面的代码片段展示了剩余所有方法的声明，除了 begin()、end()、cbegin()和 cend()。这些方法稍后讨论。
template<typename Key,typename T,typename KeyEqual = std::equal_to<>,typename Hash = hash<Key>>class hash_map{ public:
size()和empty()的实现很简单, 因为hash_map 的实现在 mSize 数据成员中维护了自己的大小。注意,size_type是这个类中定义的一个类型别名。由于是类的成员，因此这样的返回类型在实现中必须带有全名 typename hash_map<Key,T,KeyEqual,Hash>
template<typename Key, typename T, typename KeyEqual, typename Hash>bool hash_map<Key, T, KeyEqual, Hash>::empty() const{ return mSize == 0;}template <typename Key, typename T, typename KeyEqual, typename Hash>typename hash_map<Key, T, KeyEqual, Hash>::size_type hash_map<Key,T,KeyEqual,Hash>::size() const{ return mSize;}
max_size()的实现稍微麻烦一些。一开始，你可能认为这个 hash_map 容器的最大大小为所有 list 的最大大小的总和。然而，在最坏情况下，所有元素都哈希到同一个桶。因此，hash_map 可声明支持的最大大小应该是单个 list 的最大大小:
template <typename Key, typename T, typename KeyEqual, typename Hash>typename hash_map<Key, T, KeyEqual, Hash>::size_type hash_map<Key,T,KeyEqual,Hash>::max_size() const{ return mBuckets[0].max_size(); }
编写迭代器
容器最重要的要求是实现迭代器。为了能用于泛型算法，每个容器都必须提供一个能够访问容器中元素的迭代器。和迭代器一般应该提供重载的 operator*和 operator->运算符，再加上其他一些取决于特定行为的操作。只要迭代器提供基本的迭代操作，就不会出现问题。有关迭代器需要做的第一个决策是选择迭代器的类型: 正向访问、双向访问或随机访问迭代器。随机访问迭代器对关联容器来说没有什么意义，因此 hash_map 迭代器从逻辑上看应该是双向访问和迭代器。这意味着必须提供 operator++、operator–、operator==和 operatorI=。有关不同迭代器的具体要求，请参阅第 17 章。第二个决策是如何对容器的元素排序。hash_map 是无序的，因此执行有序迭代可能有点难。实际情况是可以遍历所有的桶，从第一个桶开始遍历元素，直到最后一个桶。从客户的角度看，这个顺序是随机的，但具有-一致性和可重复性。第三个决策是选择迭代器的内部表示形式。这个实现通常和容器的内部实现紧密相关。迭代器的最主要作用是引用容器中的元素。在 hash_map 中，每个元素都在标准库 list 中，因此 hash_map 迭代器可以是引用相关元素的 list 迭代器的包装。然而，双向访问迭代器还有一个作用，就是允许客户从当前元素前进到下一个元素或回退到前一个元素。为了从一个桶前进到下一个桶，还需要跟踪当前的桶，以及迭代器引用的 hash_map对象。一旦选择好实现方式，就必须为尾和迭代器决定一致的表示方式。回顾一下，尾迭代器实际上应该是“越过最后一个元素”的标记，也就是对容器中最后一个元素的迭代器应用++运算符后得到的迭代器。hash_map 迭代器可将 hash_map 中最后一个桶链表的尾迭代器用作 hash_map 的尾迭代器。容器需要提供 const 迭代器和非 const 迭代器。非 const 迭代器必须能转换为 const 迭代器。这个实现用派生的 hash_map_iterator 定义了const_hash_map_iterator。
const_hash_map_iterator 类
根据前面做出的决策，下面开始定义 const_hash_map_iterator 类。首先要注意的是，每个 const_hash_map_iterator 对象都是 hash_map 类的某个实例的迭代器。为提供这种一对一映射， const_hash_map_iterator 也必须是一个类模板，并把 hash_map 类型作为模板参数，称为 HashMap。
这个类定义中的主要问题在于如何满足双向访问迭代器的要求。任何行为上像迭代器的对象都是迭代器。自定义的类不需要是另一个类的子类，也能满足双向访问迭代器的要求。然而，如果想让迭代器能适用于泛型算法的函数，就必须指定 iterator_traits。本章前面已经解释了 iterator traits 是一个类模板，它为每种迭代器类型定义了5个类型别名: value_type、difference_type、 iterator_category、pointer 和 reference。 如有必要, iterator_traits类模板可部分特例化以满足新的迭代器类型。另外，iterator_traits 类模板的默认实现从 iterator 类本身获取了 5个类型别名。因此，可在自己的 iterator 类中直接定义这些类型别名。const_hash_map_iterator 是一个双向访问和迭代器，因此将 bidirectional_iterator_tag 指定为迭代器类别。其他合法的迭代器类别是 input_iterator_tag、output_iterator_tag、 forward_iterator_tag 和random_access_iterator_tag，对于 const_hash_map_iterator，元素类型是 typename_HashMap::value_type。
下面是基本的const_hash_map_iterator类定义
template <typename HashMap>
class const_hash_map_iterator
{
public:
using value_type = typename HashMap::value_type;
using difference_type = ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;
using pointer = value_type*;
using reference = value_type&;
using list_iterator_type = typename HashMap::ListType::const_iterator;
const_hash_map_iterator() = default;
const_hash_map_iterator(size_t bucket, list_iterator_type listIt, const HashMap* hashmap);
const value_type& operator*() const;
const value_type* operator->() const;
const_hash_map_iterator<HashMap>& operator++();
const_hash_map_iterator<HashMap> operator++(int);
const_hash_map_iterator<HashMap>& operator--();
const_hash_map_iterator<HashMap> operator--(int);
bool operator==(const const_hash_map_iterator<HashMap>& rhs) const;
bool operator!=(const const_hash_map_iterator<HashMap>& rhs) const;
protected:
size_t mBucketIndex = 0;
list_iterator_type mListIterator;
const HashMap* mHashmap = nullptr;
void increment();
void decrement();
};
如果感觉重载运算符的定义和实现难以理解，请参阅第 15 章关于运算符重载的详细内容。
const_hash_map_iterator 的方法实现
const_hash_map_iterator 构造函数初始化了 3 个成员变量:
template<typename HashMap>const_hash_map_iterator<HashMap>::const_hash_map_iterator(size_t bucket,list_iterator_type listIt,const HashMap* hashmap) :mBucketIndex(bucket),mListIterator(listIt),mHashmap(hashmap) { }
默认构造函数的唯一目的是允许客户声明未初始化的 const_hash_map_iterator 变量。通过默认构造函数构的迭代器可以不引用任何值，而对这个迭代器进行任何操作都可以产生为定义行为
解除引用运算符的实现十分简洁，但也难以理解。第 15 章讲到 operator*和 operator->运算符是不对称的;operator*运算符返回的是对底层实际值的引用，在这个例子中即迭代器引用的元素; 而 operator->运算符返回的是某个可以再次应用箭头运算符的对象。因此，返回的是指向元素的指针。编译器对这个指针应用->运算符，从而访问元素中的字段:
递增运算符和递减运算符的实现如下所示，这两个实现将实际的递增和递减操作推给了私有的 increment()和 decrement()辅助方法:
递增 const_hash_map_iterator 表示让这个迭代器引用容器中的“下一个”元素。这种方法首先递增list 迭代器，然后检查是否到达这个桶的尾部。如果到达，则寻找 hash_map 中的下一个非空椭，并将 list 迭代器设置为等于那个桶中的第一个元素。注意，不能简单地移到下一个桶，因为下一个桶中可能没有元素。如果没有更多的非空桶，则根据这个例子选用的约定，将 mListIterator 设置为 hash_map 中最后一个桶的尾从代器，这个迭代器是 const_hash_map iterator 的特殊“结尾”位置。并不要求欠代器比普通指针更安全，因此不需要对“递增已经是尾友代器的友代器”这类操作执行错误检查。
template<typename HashMap>
void const_hash_map_iterator<HashMap>::increment()
{
++mListIterator;
auto& buckets = mHashmap->mBuckets;
if(mListIterator == end(buckets(mBucketIndex)))
{
for(size_t i = mBucketIndex + 1; i < buckets.size();i++)
{
if(!buckets[i].empty())
{
mListIterator = begin(buckets[i]);
mBucketIndex = i;
return;
}
mBucketIndex = buckets.size() -1;
mListIterator = end(buckets[mBucketIndex]);
}
}
}
递减是与递增相反的过程: 使迭代器引用容器中的“前一个”元素。然而，递减和递增存在非对称性，因为起始位置和结束位置的表示方式不同: 起始位置表示第一个元素，而结束位置表示最后一个元素的“后一个位置”>。 用于递减的算法是首先检查底层的 list 迭代器是否在当前桶中的起始位置。如果不在这个位置，则直接进行递减操作。和否则，代码需要查找当前桶之前的第一个非空桶。如果找到一个，那么必须将 list 迭代器设置为引用那个桶中的最后一个元素，也就是将那个桶的尾迭代器减 1。如果找不到非空桶，那么递减操作是无效的，代码可以做任何处理(行为未定义)。注意 for 循环需要使用带符号的整数类型作为循环变量，而不是不带符号的类型，例如 size_t，因为循环使用了–i;
template<typename HashMap>
void const_hash_map_iterator<HashMap>::decrement()
{
auto& buckets = mHashmap->mBuckets;
if(mListIterator == begin(buckets(mBucketIndex)))
{
for(int i = mBucketIndex - 1;i >= 0;--i)
{
if(!buckets[i].empty())
{
mListIterator = --end(buckets[i]);
mBucketIndex = -1;
return;
}
}
mBucketIndex = buckets.size() - 1;
mListIterator = end(buckets[mBucketIndex]);
}
else
{
--mListIterator;
}
}
注意，increment()和 decrement()都访问 hash_map 类的 private 成员。因此，hash_map 类必须将 const_hash_map_iterator 声明为友元类。定义完 increment()和 decrement()后，operator==和 operator!=的定义就相对简单了。这些运算符只需要比较对象的 3 个数据成员:
template<typename HashMap>
bool const_hash_map_iterator<HashMap>::operator==(const const_hash_map_iterator<HashMap>& rhs) const
{
return(mHashmap == rhs.mHashmap&&
mBucketIndex == rhs.mBucketIndex&&
mListIterator == rhs.mListIterator);
}
template<typename HashMap>
bool const_hash_map_iterator<HashMap>::operator!=(const const_hash_map_iterator<HashMap>& rhs) const
{
return !(*this == rhs);
}
hash_map_iterator 类
hash_map_iterator 类派生于 const_hash_map_iterator，并且不需要重写 operator==、operator!=、increment()和 decrement()，因为基类版本就足够了 :
template<typename HashMap>
class hash_map_iterator : public const_hash_map_iterator<HashMap>
{
public:
using value_type = typename const_hash_map_iterator<HashMap>::value_type;
using difference_type = ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;
using pointer = value_type*;
using reference = value_type&;
using list_iterator_type = typename HashMap::ListType::iterator;
hash_map_iterator() = default;
hash_map_iterator(size_t bucket,list_iterator_type listIt,HashMap* hashmap);
value_type& operator*();
value_type* operator->();
hash_map_iterator<HashMap>& operator++();
hash_map_iterator<HashMap> operator++(int);
hash_map_iterator<HashMap>& operator--();
hash_map_iterator<HashMap> operator--(int);
};
hash_map_iterator 方法的实现
hash_map_iterator 方法的实现相当简单。 构造函数仅调用基类构造函数，operator*和 operator->使用 const_cast返回非 const 类型，operator+和 operator-只使用基类的 increment()和 decrement()，但返回 hash_map_iterator 而不是 const_hash_map_iterator。C++名称查找规则要求显式使用 this 指针指向基类模板中的数据成员和方法:
template<typename HashMap>
hash_map_iterator<HashMap>::hash_map_iterator(
size_t bucket,list_iterator_type listIt,HashMap* hashmap)
{
}
template<typename HashMap>
typename hash_map_iterator<HashMap>::value_type&
hash_map_iterator<HashMap>::operator*()
{
return const_cast<value_type&>(*this->mListIterator);
}
template<typename HashMap>
typename hash_map_iterator<HashMap>::value_type*
hash_map_iterator<HashMap>::operator->()
{
return const_cast<value_type*>(&(*this->mListIterator));
}
template <typename HashMap>
hash_map_iterator<HashMap>& hash_map_iterator<HashMap>::operator++()
{
this->increment();
return *this;
}
template<typename HashMap>
hash_map_iterator<HashMap> hash_map_iterator<HashMap>::operator++(int)
{
auto oldIt = *this;
this->increment();
return oldIt;
}
template<typename HashMap>
hash_map_iterator<HashMap>& hash_map_iterator<HashMap>::operator--()
{
this->decrement();
return *this;
}
template<typename HashMap>
hash_map_iterator<HashMap> hash_map_iterator<HashMap>::operator--(int)
{
auto oldIt = *this;
this->decrement();
return oldIt;
}
和迭代器类型别名和访问方法
hash_map 提供迭代器支持的最后一部分内容是在 hash_map 类模板中提供必要的类型别名, 并编写 begin()、end()、cbegin()和 cend()方法。类型别名和方法原型如下所示:
template<typename Key,typename T, typename KeyEqual = std::equal_to<>,typename Hash = hash<Key>>class hash_map{ public:
begin()的实现包含优化，换言之，若 hash _map 中没有元素，将返回尾欠代器。代码如下:
template<typename Key,typename T,typename KeyEqual,typename Hash>
typename hash_map<Key,T,KeyEqual,Hash>::iterator
hash_map<Key,T,KeyEqual,Hash>::begin()
{
if(mSize == 0)
{
return end();
}
for(size_t i = 0;i < mBuckets.size();++i)
{
if(!mBuckets[i].empty())
{
return hash_map_iterator<hash_map_type>(i,
std::begin(mBuckets[i]), this);
}
}
return end();
}
end()创建的 hash_map_iterator 引用最后一个桶中的尾迭代器:
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
hash_map<Key, T, KeyEqual, Hash>::end()
{
size_t bucket = mBuckets.size() - 1;
return hash_map_iterator<hash_map_type>(bucket,
std::end(mBuckets[bucket]), this);
}
const 版本的 begin()和 end()实现使用 const_cast 调用对应的非 const 版本。这些非 const 版本返回 hash_map_iterator，它可以转换为 const_hash_map_iterator。
template<typename Key,typename T,typename KeyEqual, typename Hash>
typename hash_map<Key,T,KeyEqual,Hash>::const_iterator
hash_map<Key,T,KeyEqual,Hash>::begin() const
{
return const_cast<hash_map_type*>(this)->begin();
}
template<typename Key,typename T,typename KeyEqual,typename Hash>
typename hash_map<Key,T,KeyEqual,Hash>::const_iterator
hash_map<Key, T, KeyEqual, Hash>::end() const
{
return const_cast<hash_map_type*>(this)->end();
}
cbegin() 和 cend()方法把请求传囊给 begin()和 end()的 const 版本:
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::const_iterator
hash_map<Key, T, KeyEqual, Hash>::cbegin() const
{
return begin();
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::const_iterator
hash_map<Key, T, KeyEqual, Hash>::cend() const
{
return end();
}
使用 hash_map_iterator
” 现在 hash_map 支持迭代，下面可以像迭代任何标准库容器一样迭代 hash_map 的元素了，并可将 hash_map的欠代器传给方法和函数。下面是一些示例:
hash_map<string, int> myHash;
myHash.insert(make_pair("KeyOne", 100));
myHash.insert(make_pair("KeyTwo", 200));
myHash.insert(make_pair("KeyThree", 300));
for (auto it = myHash.cbegin(); it != myHash.cend(); ++it)
{
cout << it->first << " maps to " << (*it).second << endl;
}
for (auto& p : myHash)
{
cout << p.first << " maps to " << p.second << endl;
}
for (auto&[key, value] : myHash)
{
cout << key << " maps to " << value << endl;
}
map<string, int> myMap(cbegin(myHash), cend(myHash));
for (auto& p : myMap)
{
cout << p.first << " maps to " << p.second << endl;
}
这段代码还说明，std::cbegin()和 std::cend()等非成员函数正如预期那样工作。
- 有关分配器的补充说明
根据本章前面的描述，所有标准库容器都允许指定自定义的内存分配器。hash_map 的实现也应该一样。但是，由于这些已经偏离了本章的主线，而且自定义分配器极少使用，因此略去不讲。
- 有关可反向容器的补充说明
如果容器提供了双向访问或随机访问迭代器, 那么可认为这个容器是可反向的.可反向容器应该提供表21-3所示的两个额外的类型别名。
| 类型名称 | 说明 |
|---|
| reverse_iterator | 反向遍历容器中元素的类型 | | const_reverse_iterator | 另一个版本的 reverse_iterator，反向遍历容器中的 const 元素 |
此外，容器还应提供与 begin()和 end()对应的 rbegin()和 rend(); 还应该提供 crbegin()和 crend()，这两个和cbegin()与 cend()对应。一般的实现使用本章前面描述的 std::reverse_iterator 适配器即可。这些实现留给读者作为练习。
- 将 hash_map 实现为无序关联容器
除了已经展示的基本容器要求外，还可让容器满足有序关联容器、无序关联容器或顺序容器的要求。本节将修改 hash_map 类模板，以满足另外一些无序关联容器的要求。
无序关联容器的类型别名要求
无序关联容器需要表 21-4 所示的类型别名。
| 类型名称 | 说明 |
|---|
| key_type | 容器实例化时选择的键类型 | | mapped_type | 容器实例化时使用的元素类型 | | value_type | pair<const Key, T> | | hasher | 容器实例化时使用的哈希类型 | | key_equal | 容器实例化时使用的 equality 谓词 | | local_iterator | 选代单个桶时使用的迭代器类型，不能跨桶迭代 | | const_local_iterator | 和迭代单个桶时使用的 const 迭代器类型，不能跨桶和欠代 | | node_type | 表示节点的类型。本节不再详细讨论，可参见第 17 章对节点的讨论 |
下面是更新了类型别名集合的hash_map定义。注意，已经移动了ListType的定义，因为本地迭代器的定义需要ListType。
template<typename Key,typename T,typename KeyEqual = std::equal_to<>,typename Hash = hash<Key>>
class hash_map
{
public:
using key_type = Key;
using mapped_type = T;
using value_type = std::pair<const Key, T>;
using hasher = Hash;
using key_equal = KeyEqual;
private:
using ListType = std::list<value_type>;
public:
using local_iterator = typename ListType::iterator;
using const_local_iterator = typename ListType::const_iterator;
}
无序关联容器的方法要求C++标准规定了无序关联容器需要实现的一些额外方法，如表 21-5 所示。最后一列中的兽是容器中元素的
| 方法 | 说明 | 复杂度 |
|---|
| 接收一个迭代器范围作为参数的构造函数 | 构造容器，并插入迭代器范围内的元素。不要求先代器范围引用同一类型的其他容器 注意，所有无序关联容器的构造函数都必须接收一个 equality 谓词。构造函数应该提供一个默认构造的对象作为默认值 | 平均复杂度，O(n)最糟情况复杂度: O(n^2) | | 接收 initializer_list<value -type>作为参数的构造函数 | 将容器中的所有元素蔡换为初始化列表中的元素 | 平均复杂度: O(n)最糟情况复杂度: O(n^2) | | 右侧为 initializer list 的赋值运算符 | 将容器中的所有元素蔡换为初始化列表中的元素 | 平均复杂度: O(n)最糟情况复杂度: O(n^2) | | hasher hash_function() const； | 返回哈希函数 | 常量时间复杂度 | | key_equal key_eq() const; | 返回比较键的 equality 谓词 | 常量时间复杂度 | | pair<iterator, bool> insert(value_type&c);iterator insert(const_iterator hint, value_type&); | 两种不同形式的 insert() hint 可由实现忽略 允许重复键的容器在第一种形式中只返回 iterator,因为 insert()始终都会成功 | 平均复杂度: O(1)糟情况复杂度: O(n) | | void insert(Inputterator start, Inputlterator end); | 插入元素范围，范围未必来自相同类型的容器 | 平均复杂度:(m)m是插入的元素数量最灶情况复杂度: O(m*n+m) | | void insert(initializer_list<value_type>); | 将元素从初始化列表插入容器 | 平均复杂度:(m)m是插入的元素数量最灶情况复杂度: O(m*n+m) | | pair<iterator,bool> emplace(Args&&…);iterator emplace_hint(const_iterator hint,Args&&…); | 实现了放置操作,就地构造对象 | 平均复杂度: O(1) 最粳情况复杂度: O(n) | | size_type erase(key_type&); iterator erase(iterator position);iterator erase (iterator start, iterator end); | 3 种不同形式的 erase()第一种形式返回删除值的个数(在不允许重复键的容器中返回0或 1)。第二种形式和第三种形式删除位于 position 的元素或删除从 start 到 end 范围内的元素，返回的迭代器指向最后被删除的元素后面的那个元素 | 最粳情况复杂度: O(n) | | void clear() | 除所有元素 | O(n) | | Iterator find(key_type&); const_iterator find(key_type&) | 查找匹配指定键的元素 | 平均复杂度: O(1)最粳情况复杂度: O(n) | | size_type count(key_type&) const; | 返回匹配指定键的元素的个数(在不允许重复键的 容器中返回0或1) | 平均复杂度: O(1)最粳情况复杂度: O(n) | | pair<iterator,iterator>equal_range(key_type&); pair<const_iterator, const_iterator>equal_range(key_type&) const; | 返回引用匹配指定键的第一个元素的迭代器，以及匹配指定键的最后一个元素后面那个位置的迭代器 | 最粳情况复杂度: O(n) |
注意，hash_map 不允许有重复的键，所以 equal_range()总是返回一对相同的迭代器。C++17在需求列表中添加了 extract()和 merge()方法。这两个方法与处理节点相关(见第 17 章), 这个hash_map实现会将其忽略。下面是完整的 hash_map 类定义。insert()、erase()和 find()的原型相比之前的版本稍有变动，因为原始版本不符合无序关联容器对返回类型的要求;
template <typename Key, typename T, typename KeyEqual = std::equal_to<>,
typename Hash = hash<Key>>
class hash_map
{
public:
using key_type = Key;
using mapped_type = T;
using value_type = std::pair<const Key, T>;
using hasher = Hash;
using key_equal = KeyEqual;
using reference = value_type&;
using const_reference = const value_type&;
using size_type = size_t;
using difference_type = ptrdiff_t;
using hash_map_type = hash_map<Key, T, KeyEqual, Hash>;
using iterator = hash_map_iterator<hash_map_type>;
using const_iterator = const_hash_map_iterator<hash_map_type>;
private:
using ListType = std::list<value_type>;
public:
using local_iterator = typename ListType::iterator;
using const_local_iterator = typename ListType::const_iterator;
friend class hash_map_iterator<hash_map_type>;
friend class const_hash_map_iterator<hash_map_type>;
virtual ~hash_map() = default;
explicit hash_map(const KeyEqual& equal = KeyEqual(),
size_type numBuckets = 101, const Hash& hash = Hash());
template <typename InputIterator>
hash_map(InputIterator first, InputIterator last,
const KeyEqual& equal = KeyEqual(),
size_type numBuckets = 101, const Hash& hash = Hash());
explicit hash_map(std::initializer_list<value_type> il,
const KeyEqual& equal = KeyEqual(), size_type numBuckets = 101,
const Hash& hash = Hash());
hash_map(const hash_map_type& src) = default;
hash_map(hash_map_type&& src) noexcept = default;
hash_map_type& operator=(const hash_map_type& rhs);
hash_map_type& operator=(hash_map_type&& rhs) noexcept;
hash_map_type& operator=(std::initializer_list<value_type> il);
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
const_iterator cbegin() const;
const_iterator cend() const;
bool empty() const;
size_type size() const;
size_type max_size() const;
T& operator[](const key_type& k);
std::pair<iterator, bool> insert(const value_type& x);
iterator insert(const_iterator hint, const value_type& x);
template <typename InputIterator>
void insert(InputIterator first, InputIterator last);
void insert(std::initializer_list<value_type> il);
size_type erase(const key_type& k);
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void swap(hash_map_type& other) noexcept;
void clear() noexcept;
key_equal key_eq() const;
hasher hash_function() const;
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
std::pair<iterator, iterator> equal_range(const key_type& k);
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
size_type count(const key_type& k) const;
private:
std::pair<typename ListType::iterator, size_t> findElement(
const key_type& k);
std::vector<ListType> mBuckets;
size_type mSize = 0;
KeyEqual mEqual;
Hash mHash;
};
hash_map 迭代器范围构造函数
接收迭代器范围的构造函数是一个方法模板，这个方法模板可接收来自任何容器的迭代器范围，而不仅仅来自其他 hash_map 的迭代器范围。如果这不是一个方法模板，那么需要将 Inputterator 类型显式地指定为hash_map_iterator，将其限制为只能接收来自 hash_map 的欠代器。不管这种语法有多么复杂，实现都不难: 它将构造委托给显式的构造函数，以初始化所有数据成员，然后调用 insert()以插入指定范围内的所有元素。
template <typename Key, typename T, typename KeyEqual, typename Hash>
template <typename InputIterator>
hash_map<Key, T, KeyEqual, Hash>::hash_map(
InputIterator first, InputIterator last, const KeyEqual& equal,
size_type numBuckets, const Hash& hash)
: hash_map(equal, numBuckets, hash)
{
insert(first, last);
}
hash_map 初始化列表构造函数
第 1 章讨论了初始化列表。下面是接收一个初始化列表作为参数的 hash_map 构造函数的实现，它非常类似于接收迭代器范围的构造函数的实现:
template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>::hash_map(
std::initializer_list<value_type> il,
const KeyEqual& equal, size_type numBuckets, const Hash& hash)
: hash_map(equal, numBuckets, hash)
{
insert(std::begin(il), std::end(il));
}
有了这个初始化列表构造函数，可按以下方式构造 hash_map:
hash_map<string, int> myHash {
{ "KeyOne", 100 },
{ "KeyTwo", 200 },
{ "KeyThree", 300 } };
hash_map 初始化列表赋值运算符
赋值运算符也可在右侧接收一个初始化列表。下面是 hash_map 初始化列表赋值运算符的实现。它使用类以于“复制和交换”惯用语法的算法来确保实现强大的异常安全。
template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>&
hash_map<Key, T, KeyEqual, Hash>::operator=(std::initializer_list<value_type> il)
{
hash_map_type newHashMap(il, mEqual, mBuckets.size(), mHash);
swap(newHashMap);
return *this;
}
有了这个赋值运算符，就可以编写下面的代码
myHash = {{ "KeyOne", 100 },{ "KeyTwo", 200 },{ "KeyThree", 300 } };
hash_map 插入操作
在本章前面讨论基本 hash_map 的部分，提供了一个简单的 insert()方法。在这个版本中，提供了 4 个具有额外功能的 insert()版本:简单的 insert()操作返回一个 pair<iterator, bool>，表明元素插入的位置以及是否新创建了元素。接收一个 hint 作为参数的 insert()版本在 hash_map 中没有作用，但为了和其他类型的集合对称，也需要提供。这个 hint 被忽略了，然后只是调用第一个版本。第三种形式的 insert()是一个方法模板，因此可用于在 hash_map 中插入任何容器的元素范围。最后一种形式的 insert()接收一个 initializer_list<value_type>。注意从技术角度看，也可提供以下 insert()版本，它们接收右值引用。
std::pair<iterator, bool> insert(value_type&& x);iterator insert(const_iterator hint, value_type&& x);
hash_map 没有提供这些。另外，还有两个与处理节点相关的 insert()版本。第 17 章讨论了节点。hash_map前两种形式的 insert()方法的实现代码如下:
template <typename Key, typename T, typename KeyEqual, typename Hash>
std::pair<typename hash_map<Key, T, KeyEqual, Hash>::iterator, bool>
hash_map<Key, T, KeyEqual, Hash>::insert(const value_type &x)
{
auto[it, bucket] = findElement(x.first);
bool inserted = false;
if (it == std::end(mBuckets[bucket]))
{
it = mBuckets[bucket].insert(it, x);
inserted = true;
mSize++;
}
return std::make_pair(hash_map_iterator<hash_map_type>(bucket, it, this), inserted);
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
hash_map<Key, T, KeyEqual, Hash>::insert(const_iterator ,
const value_type &x)
{
return insert(x).first;
}
第三种形式的 insert()是一个方法模板，原因和之前展示的构造函数一致: 应能使用来自任何类型的容器的和迭代器插入元素。实际的实现使用了一个 insert_iterator，参见本章前面的讨论;
template <typename Key, typename T, typename KeyEqual, typename Hash>template <typename InputIterator>void hash_map<Key, T, KeyEqual, Hash>::insert(InputIterator first, InputIterator last){
最后一种形式的 insert0接收初始化列表，hash_map 的这个实现只是将工作转交给接收一个迭代器范围的insert()方法。
template <typename Key, typename T, typename KeyEqual, typename Hash>void hash_map<Key, T, KeyEqual, Hash>::insert(std::initializer_list<value_type> il){ insert(std::begin(il), std::end(il));}
有了这个 insert()方法，就可以编写下面的代码:
myHash.insert({{ "KeyFour", 400 },{ "KeyFive", 500 } });
hash_map 放置操作
使用放置操作可以就地构造对象，第 17 章讨论了放置操作。hash_map 的放置方法如下所示:
template <typename... Args>std::pair<iterator, bool> emplace(Args&&... args);template <typename... Args>iterator emplace_hint(const_iterator hint, Args&&... args);
这些代码行中的“…”并非输入错误。它们是所谓的可变参数模板(variadic template)，即模板具有的模板类型参数以及函数参数数量是可变的。第 22 章将讨论可变参数模板。hash_map 实现忽略了放置操作。
hash_map 删除操作
本章前面讨论基本 hash_map 时提到的 erase()版本不符合标准库的要求。需要实现以下版本的 erase():
一个版本接收 key_type 类型的参数，并返回一个 size_type 值，表示从集合中删除的元素个数(对于hash_map，只有两个可能的返回值: (0 和 1))。
另一个版本删除处于指定的迭代器位置的元素，返回一个指向被删除元素后面那个元素的迭代器。
第三个版本删除由两个迭代器指定的范围内的元素，返回一个指向最后被删除元素后面那个元素的迭代器
第一个版本的 erase()的实现如下所示:
template<typename Key, typename T, typename KeyEqual,typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
hash_map<Key,T,KeyEqual,Hash>::erase(const key_type & k)
{
auto[it, bucket] = findElement(k);
if(it != std::end(mBuckets[bucket]))
{
mBuckets[bucket].erase(it);
mSize--;
return 1;
}
else
{
return 0;
}
}
第二个版本的 erase()必须删除用于指定的迭代器位置的元素。给定的迭代器当然是一个 hash_map_iterator。因此，hash_map 应该有某种能力通过 hash_map_iterator 获得底层的桶以及 list 迭代器。我们采取的方法是将hash_map 类定义为 hash_map_iterator 的友元(前面的类定义中没有表现出来)。下面是这个 erase()版本的实现:
template<typename Key,typename T,typename KeyEqual,typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
hash_map<Key, T, KeyEqual, Hash>::erase(iterator position)
{
iterator next = position;
++next;
mBuckets[position.mBucketIndex].erase(position.mListIterator);
mSize--;
return next;
}
最后一个版本的 erase()删除某个范围内的元素。从 first 迭代至 last，对每个元素调用 erase0)，让 erase()的前一个版本完成所有工作:
template <typename Key, typename T, typename KeyEqual, typename Hash>typename hash_map<Key, T, KeyEqual, Hash>::iteratorhash_map<Key, T, KeyEqual, Hash>::erase(iterator first, iterator last){
hash_map 访问器操作
C++标准要求使用 key_eq()和 hash_function()方法分别检索 equality 谓词和哈希函数:
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::key_equal
hash_map<Key, T, KeyEqual, Hash>::key_eq() const
{
return mEqual;
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::hasher
hash_map<Key, T, KeyEqual, Hash>::hash_function() const
{
return mHash;
}
这个 fnd()方法和前面基本 hash_map 的 find()方法相似，只是返回代码不同。这个 find()版本返回的不是指向元素的指针，而是构造了一个引用这个元素的 hash_map_iterator:
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::iterator
hash_map<Key, T, KeyEqual, Hash>::find(const key_type& k)
{
auto[it, bucket] = findElement(k);
if (it == std::end(mBuckets[bucket]))
{
return end();
}
return hash_map_iterator<hash_map_type>(bucket, it, this);
}
const版本的find()返回const_hash_map_iterator，并使用const_cast调用find()的非const版本，以避免代码重复.注意，非const版本的find()返回hash_map_iterator，hash_map_iterator则被转换为const_hash_map_iterator。
template <typename Key, typename T, typename KeyEqual, typename Hash>typename hash_map<Key, T, KeyEqual, Hash>::const_iteratorhash_map<Key, T, KeyEqual, Hash>::find(const key_type& k) const{ return const_cast<hash_map_type*>(this)->find(k);}
这两个版本的 equal range()实现是相同的，但其中一个返回一对 hash_map_iterator，另一个返回一对const_hash_map_iterator。 它们都只是把请求传递给 find()。 hash_map 不能包含带有重复键的元素, 所以 hash map的.equal_ range()实现总是返回一对相同的迭代器。
template <typename Key, typename T, typename KeyEqual, typename Hash>
std::pair<
typename hash_map<Key, T, KeyEqual, Hash>::iterator,
typename hash_map<Key, T, KeyEqual, Hash>::iterator>
hash_map<Key, T, KeyEqual, Hash>::equal_range(const key_type& k)
{
auto it = find(k);
return std::make_pair(it, it);
}
hash_map 不允许重复键，count()只能返回 1 或 0: 如果找到元素，就返回 1，和否则返回 0。实现只是包装find()调用。如果 find()方法没有找到元素，则返回尾欠代器。count()调用 end()，获得尾迭代器，用于比较。
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
hash_map<Key, T, KeyEqual, Hash>::count(const key_type& k) const
{
if (find(k) == end())
{
return 0;
}
else
{
return 1;
}
}
最后一个方法是 operator[]，C++标准没有要求实现这个方法，但这个方法可以给程序员提供便利，而且和std::map 的这个方法对应。这个方法的原型和实现等同于标准库::map 中的 operator[]。以下代码中的注释解释了可能难以理解的单行实现代码
template <typename Key, typename T, typename KeyEqual, typename Hash>
T& hash_map<Key, T, KeyEqual, Hash>::operator[] (const key_type& k)
{
return ((insert(std::make_pair(k, T()))).first)->second;
}
hash_map 桶操作
无序关联容器也提供多个与桶相关的方法:
bucket_count()返回容器中桶的数量。
max_bucket_count()返回支持的最大桶数量。
bucket(key)返回给定的键映射到的桶的索引。
bucket_size(n)返回具有给定索引的桶中的元素数量。
begin(n)、end(n)、cbegin(m)和 cend(m)返回具有给定索引的桶的本地首尾欠代器。下面是 hash_map 的实现:
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
hash_map<Key, T, KeyEqual, Hash>::bucket_count() const
{
return mBuckets.size();
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
hash_map<Key, T, KeyEqual, Hash>::max_bucket_count() const
{
return mBuckets.max_size();
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
hash_map<Key, T, KeyEqual, Hash>::bucket(const Key& k) const
{
return const_cast<hash_map_type*>(this)->findElement(k).second;
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::size_type
hash_map<Key, T, KeyEqual, Hash>::bucket_size(size_type n) const
{
return mBuckets[n].size();
}
template <typename Key, typename T, typename KeyEqual, typename Hash>
typename hash_map<Key, T, KeyEqual, Hash>::local_iterator
hash_map<Key, T, KeyEqual, Hash>::begin(size_type n)
{
return mBuckets[n].begin();
}
其他 begin(m)、end(n)、cbegin()和 cend()方法的实现是类似的。它们只是基于给定的索引，将调用转发给正确的桶列表。最后，无序关联容器应当提供 load 和包ctor()、max_load_factor()、rehash()和 reserve()方法。hash_map 忽略了这些方法。
- 有关顺序容器的补充说明
前面开发的 hash_map 是一个无序关联容器。当然，还可编写顺序容器或有序关联容器，只不过要遵循不同的要求。这里没有列出这些要求，更简单的方法是指出 deque 容器几乎完美符合所规定的顺序容器的要求。唯一的区别在于 deque 提供了额外的 resize()方法(C++标准没有要求实现这个方法)。有序关联容器的一个例子是 map，可在 map 的基础上构建自己的有序关联容器。
|