2 C++ 标准库
2.1 C++ 标准库概述

上图概述了 C++ 标准库 (SL) 的一些组件，包括算法、迭代器、原子操作、范围、协程、输入/输出、线程支持和容器。需要注意的是，大多数组件由 C++ 17 标准提供，其中两个由 C++ 20 标准提供。为简单起见，我们省略了 C++ 17 标准的信息。此外，我们仅展示了本书将要使用的组件。首先，容器组件 1 提供以下数据结构：无序关联容器、关联容器和序列容器。在当前版本的 SL 中，映射和集合作为关联容器提供。作为无序关联容器，本书提供了无序集合和无序映射。本书最重要的容器是序列容器，例如向量、列表和数组。iterator组件提供了六个迭代器，用于处理值序列，例如列表或任何容器。根据对值序列的操作，定义了以下操作：读或写访问、随机访问、递增或递减。在 C++ 标准中，迭代器组件将通过基于概念的迭代器进行扩展，这些迭代器与 C++ 17 迭代器不同。此外，ranges组件将成为现有 C++ 迭代器的扩展和泛化。然而，我们还没有使用ranges，因为并非所有主流 C++ 编译器都支持它们。作用于容器的第二个组件是算法。我们精心挑选了本书将使用的算法：

排序：按值序列的顺序对其进行排序。
搜索：在值序列中搜索特定值。
数值算法：例如，计算值序列中所有值的和。
最小/最大运算：查找值序列中的最小值或最大值。
通用迭代：迭代值序列，而不是使用例如 for 循环。
请注意，还有更多可用的算法，并且所有这些算法都适用于所有容器。协程是在 C++ 20 标准中引入的，它们是无栈函数，它们的执行可以暂停并稍后重新启动。为了避免竞争条件和死锁引入了并发支持。我们认为，从介绍中最重要的一点是：查看 SL，如果找不到所需的容器或算法，您应该问问自己是否真的需要它。

3.2 容器
在本节中，我们将通过一个示例来展示容器存储数据的必要性。假设我们要计算元素 n 的平均值 a：

在第 20 页的清单 3.1 中，平均值计算的实现使用了 C++ 标准库 (SL) 的头文件 #include 。此头文件提供了从标准流中写入和读取的功能。

%%cling

include

include

//—————————————————————–
double sum = 0;
size_t count = 0;
std::vector vals = {1, 3, 7, 2.2, 1.8};

for (auto x : vals) {
sum += x;
++count;
}

std::cout << “Average: ” << sum / count << std::endl;
注意，计算平均值时我们不必存储用户的输入。但是，为了计算中位数，我们需要存储用户的输入。中位数是排序列表的中间值。为了实现此计算，我们需要一个向量来存储列表，以及一个rt 算法。在研究 3.3 节中的算法之前，我们先来了解一下三个常用的容器。

3.2.1 Vector(向量）

从数学角度来看，头文件 #include 提供的 std::vector 与向量的数学定义类似。

C++ 中的容器是同构数据结构，只能包含相同类型的元素。关于向量的用法，我们来看看平均值的计算。

%%cling

include

include

include

//—————————————————————–
size_t count = 0;
std::vector values = {1.1, 2.3, 5.4, 3.2};

double sum = std::accumulate(values.begin(), values.end(), 0.0f);
std::cout << “Average: ” << sum / values.size() << std::endl;

3.2.2 List（列表）

另一个动态大小的容器是 std::list，由头文件 #include 提供。从 API 的角度来看，向量和列表在大多数情况下是相同的，只需在代码中将 std::vector 替换为 std::list 即可。因此，我们不会重复计算列表平均值的示例。但是，我们将创建一个新的计算中位数的示例，因为我们发现这里存在一些差异。

%%cling

include

include

include

typedefstd::list::size_type list_size;
//—————————————————————–
std::list values = {2, 7.7, 3, 9.2, 1.4};
double x = 0;

values.sort();
list_size mid_index = values.size() / 2;
auto mid = values.begin();
std::advance(mid, mid_index);

double median = 0;

if (values.size() % 2 == 0) {
auto mid_one = values.begin();
std::advance(mid_one, mid_index + 1);
median = 0.5 * (*mid + *mid_one);
} else
median = *mid;

std::cout << “Median: ” << median << std::endl;

std::sort 需要随机访问迭代器，因此无法正常工作。因此，我们使用成员函数 std::list::sort。我们使用 values.size() 计算列表中间元素的索引，这与 std::vector 的操作相同。对于标准向量，我们可以使用访问运算符 values[i] 访问索引 i 处的元素，然而，我们缺少了随机迭代器的关键属性，我们使用 values.begin() 获取指向列表第一个元素的迭代器, 使用 std::advance13 将迭代器推进到列表中间的元素, 使用解引用运算符 *mid 访问中间元素的值。

3.2.3 列表 vs. 向量

在这里，我们将仔细研究向量和列表用法上的差异。选择使用其中一种会对性能产生很大的影响。在选择列表或向量时，需要考虑以下几点：

对于相同数量的元素，向量需要的内存更少，因为向量只存储元素。而列表则必须为每个数据元素存储两个指针。
列表在任意位置插入元素所需的时间更少。
向量的随机数据访问速度更快，因为元素在内存中是顺序存储的。而列表只能按顺序遍历内存。
为了研究这两种数据结构的计算时间差异，下图结果是在单个节点上使用 gcc 12 获得的，并绘制了每种元素数量 10 次运行的平均值。对于所有，列表或向量中的元素数量从 10、102、103 到 10^9 不等。

3.2.4 数组

%%cling

include

//—————————————————————–
// Define the length of the array
constsize_t size = 6;

// Generate the array
double a[size];

// Fill the a
for (size_t i = 0; i < size; i++) {
a[i] = i;
}

// Print the a
for (size_t i = 0; i < size; i++) {
a[i] = i;
}
std::cout << “last element: ” << a[size – 1] << std::endl;
对于存储固定数量的元素（需要在编译时确定），C++ 提供了两种方案。首先，可以使用语言特性，例如 int* array = double[5];。

使用容器 std::array和作为语言特性非常相似，主要区别在于算法的使用。

%%cling

include

include

include

include

//—————————————————————–
// Define the length of the array
std::array a;

// Fill the array
std::iota(a.begin(), a.end(), 0);

// Print the array
std::for_each(a.begin(), a.end(), [](double value) {
std::cout << value << ” “;
});
std::cout << std::endl;
3.2.5 迭代器

C++ 标准库 (SL) 使用头文件 #include提供迭代器。主要有五种迭代器类型：

(1) 输出迭代器类型使用增量运算符 ++ 在容器上向前迭代，并且只能使用解引用运算符 * 写入元素一次；(2) 输入迭代器类型是只读的，使用增量运算符 ++ 在容器上向前迭代，并且可以使用解引用运算符 * 多次访问元素；(3) 前向迭代器类型结合了输入和输出迭代器类型；(4) 双向迭代器类型类似于前向迭代器类型，但它添加了 — 减运算符，可以在两个方向上对容器进行迭代； (5) 随机访问迭代器类型通过允许程序员添加整数，扩展了双向迭代器类型的随机访问能力。注意，C++ 指针类型是随机访问迭代器。

现在，我们来看一下迭代器的用法：使用迭代器打印 std::list 元素的示例：Listing_3_6.cpp

include

include

//—————————————————————–
intmain() {
std::list values = {2, 7, 3, 9, 1};

// Accessing the iterator to the first element
std::list::iterator it = std::begin(values);

for (; it != std::end(values); it++)
// Accessing the element using the dereference operator *
std::cout << *it << std::endl;

std::cout << “——” << std::endl;

for (constint value : values) {
std::cout << value << std::endl;
}

std::cout << “——” << std::endl;

for (int index = 0; constint value : values) {
std::cout << “Index=” << index << ” Value= ” << value
<< std::endl;
}
}
编译执行：

g++ -std=c++20 -I . -o Listing_3_6 Listing_3_6.cpp -lpthread

./Listing_3_6

2
7
3
9

1

2
7
3
9

1

Index=0 Value= 2
Index=0 Value= 7
Index=0 Value= 3
Index=0 Value= 9
Index=0 Value= 1

迭代器的类型对我们访问容器元素的方式有很大影响。例如，对于 std::vector 或 std::array，下标运算符 [] 可用于通过索引访问元素，而对于 std::list 则不能。

参考资料

软件测试精品书籍文档下载持续更新 https://github.com/china-testing/python-testing-examples 请点赞，谢谢！
本文涉及的python测试开发库 谢谢点赞！ https://github.com/china-testing/python_cn_resouce
python精品书籍下载 https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
Linux精品书籍下载 https://www.cnblogs.com/testing-/p/17438558.html
python八字排盘 https://github.com/china-testing/bazi
联系方式：钉ding或V信: pythontesting
3.3 算法
在本节中，我们将研究 C++ 标准库提供的算法，因为这些算法是并行算法的基础。我们将遵循 Sean Parent 在 2013 年 CppCon 大会上的演讲（值得一看），他在演讲中建议不要使用“原始循环”。使用标准库中的算法，您可以创建更短、更易于推理和维护的代码，并且可能更高效。此外，它还可以帮助程序员养成重用代码的习惯，而不是自己从头开始编写所有内容。

例如，Sean 使用了 slide 函数。Slide 函数接收由前两个参数指定的元素范围，并将它们移动到由第三个参数指定的位置。您可能想通过从起始位置移除元素，然后将其插入到终止位置来实现此算法。

%%cling

include

template
std::pair slide1(V &v, T b, T e, T p) {
auto n = e – b;
typedef typename std::iterator_traits::value_type e_type;
std::vector v2;
for (auto i = 0; i != n; ++i) {
v2.push_back(*b);
v.erase(b);
}
T p2 = p;
for (auto i = 0; i != n; ++i) {
v.insert(p, v2.back());
v2.pop_back();
p2++;
}
return {p, p2};
}
这段代码的问题不在于它错了（它本身并没有错）。如果使用 std::list 对象，它甚至可能相当高效。然而，对于 std::vector 来说，它的效率非常低。更糟糕的是，它没有提供并行性的机会。

另一方面，如果意识到滑动操作只是旋转值范围的子集，那么可以使用 std::rotate算法重写滑动函数，而无需使用循环。

%%cling

include

//—————————————————————–
template
std::pair slide2(T first, T last, T pos) {
if (pos < first) {
return {pos, std::rotate(pos, first, last)};
} else {
T hi = pos + (last – first);
return {std::rotate(first, last, hi), hi};
}
}
新版本代码缩短了大约 50%，不需要传递容器，并且无需分配向量。事实证明，旋转容器元素的算法很难高效实现，更不用说并行化了。通过重写 slide 函数以使用算法库，我们也能获得这些好处。

经验教训是，程序员应该熟悉 C++ 标准库中可用的算法，并尽可能地使用它们。

第二个示例是计算自然对数 ln 的泰勒级数。自然算法的麦克劳林级数为：

%%cling

include

include

include

include

include

include

include

//—————————————————————–
conststd::size_t n = 10;
constdouble x = .372;
std::vector parts(n);
std::iota(parts.begin(), parts.end(), 1);

std::for_each(parts.begin(), parts.end(), [](double &e) {
e = std::pow(-1.0, e + 1) * std::pow(x, e) / (e);
});

double result = std::accumulate(parts.begin(), parts.end(), 0.);

在本例中，我们再次避免使用原始的 for 循环，以便更容易地使用第 1 章中的并行算法编写并行代码。