标准库算法：C++ 17中的更改和添加

今天我们有一个来自 格雷瓜尔 2007年起担任尼康计量公司和微软MVP的软件架构师。

C++ 14标准已经包含了丰富的不同种类的算法。C++ 17添加了更多的算法并更新了一些现有算法。本文解释了什么是新的，以及在C++ 17标准库中发生了什么变化。

新算法

取样

C++ 17包括以下新的采样算法：

• sample(first, last, out, n, gen)

它使用给定的随机数生成器( gen )挑选 n 给定范围内的随机元素[ first , last )并将它们写入给定的输出迭代器( out ).

下面是一段简单的代码，它构造一个包含整数1到20的向量，然后建立一个随机数生成器，最后生成10个5个值的序列，其中每个值从 data 矢量：

using namespace std;

vector<int> data(20);
iota(begin(data), end(data), 1);
copy(cbegin(data), cend(data), ostream_iterator<int>(cout, " "));
cout << '';

random_device seeder;
const auto seed = seeder.entropy() ? seeder() : time(nullptr);
default_random_engine generator(
       static_cast<default_random_engine::result_type>(seed));

const size_t numberOfSamples = 5;
vector<int> sampledData(numberOfSamples);

for (size_t i = 0; i < 10; ++i)
{
    sample(cbegin(data), cend(data), begin(sampledData),
           numberOfSamples, generator);
    copy(cbegin(sampledData), cend(sampledData),
         ostream_iterator<int>(cout, " "));
    cout << '';
}

Here is an example of a possible output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4 8 9 17 19
4 7 12 13 18
5 7 8 14 18
1 4 5 10 20
2 4 8 13 17
2 3 4 5 20
4 7 8 9 13
1 7 8 10 15
4 5 8 12 13
1 3 8 10 19

迭代

C++标准库已经包含 for_each() 处理给定范围内的每个元素。C++ 17添加了 for_each_n(first, n, func) 算法。它调用给定的函数对象( func )对于第一个迭代器给定范围内的每个元素( first )还有很多元素( n ). 因此，它与 for_each() ，但是 for_each_n() 只处理第一个 n 范围的元素。

下面是一个简单的例子，它生成一个包含20个值的向量，然后使用 for_each_n() 要将前5个值打印到控制台：

using namespace std;

vector<int> data(20);
iota(begin(data), end(data), 1);

for_each_n(begin(data), 5,
           [](const auto& value) { cout << value << ''; });

搜索

C++ 17包括一对专门的搜索器，它们都定义在 <functional> :

• default_searcher
• boyer_moore_searcher
• boyer_moore_horspool_searcher

Boyer-Moore搜索器通常用于在一大块文本中查找一段文本，通常比默认的搜索器效率更高。实际上，两个Boyer-Moore搜索者可以跳过某些字符，而不必对每个字符进行比较。这给了这些算法一个次线性的复杂性，使得它们比默认的搜索程序快得多。看到了吗 维基百科文章 有关算法的详细信息。

要使用这些专用搜索器，您需要创建其中一个的实例，并将该实例作为最后一个参数传递给 std::search() ，例如：

using namespace std;

const string haystack = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.";
const string needle = "consectetur";

const auto result = search(cbegin(haystack), cend(haystack),
       boyer_moore_searcher(cbegin(needle), cend(needle)));

if (result != cend(haystack))
    cout << "Found it.";
else
    cout << "Not found.";

如果要在同一范围内执行多个搜索，可以构造的单个实例 std::boyer_moore_searcher 并重用它，而不是为每一个都创建一个新的 std::search() 打电话。

广义和算法

扫描

下面的广义和算法已经被添加到C++ 17标准库：

• exclusive_scan(first, last, out, init[, bin_op])
• inclusive_scan(first, last, out[, bin_op[, init]])
• transform_exclusive_scan(first, last, out, init, bin_op, un_op)
• transform_inclusive_scan(first, last, out, bin_op, un_op[, init])

在哪里？ bin_op 是一个二进制运算符( std::plus<>() 默认情况下），而unop是一元运算符。

所有这些算法都计算给定范围内元素和的序列[ first , last )，表示为[e ₀ ，电子 _n ). 计算出的总和写入[ out , out + (last-first) )，表示为[s ₀ ，秒 _n ). 进一步假设我们表示二进制运算符( bin_op )作为⊕. 这个 exclusive_scan() 然后，算法计算以下求和序列：

s0 = init 
s1 = init ⊕ e0
s2 = init ⊕ e0 ⊕ e1 
...
sn-1 = init ⊕ e0 ⊕ e1 ⊕ ... ⊕ en−2

而 inclusive_scan() 计算以下总和：

s0 = init ⊕ e0 
s1 = init ⊕ e0 ⊕ e1 
... 
sn-1 = init ⊕ e0 ⊕ e1 ⊕ ... ⊕ en−1

唯一的区别是 inclusive_scan() 包括i ^第 i中的元素 ^第 求和，而 exclusive_scan() 不包括i ^第 i中的元素 ^第 总和。

exclusive_scan() 和 inclusive_scan() 类似于 partial_sum() . 然而， partial_sum() 从左到右评估所有内容，而 exclusive_scan() 和 inclusive_scan() 以不确定的顺序评估一切。这意味着，如果所使用的二元运算符不是相联的，则这些结果将是不确定的。由于顺序的不确定性，可以通过指定并行执行策略来并行执行这些算法，请参见下文。

计算的总和 inclusive_scan() 具有 init 等于0和关联二元运算符与 partial_sum() .

transform_exclusive_scan() 和 transform_inclusive_scan() 它们非常相似。唯一的区别是它们在计算和之前应用给定的一元运算符。假设一元运算符表示为函数调用 f (). 这个 transform_exclusive_scan() 然后，算法计算以下和序列：

s0 = init
s1 = init ⊕ f(e0)
s2 = init ⊕ f(e0) ⊕ f(e1)
...
sn-1 = init ⊕ f(e0) ⊕ f(e1) ⊕ ... ⊕ f(en−2)

transform_inclusive_scan（）算法计算以下总和：

s0 = init ⊕ f(e0)
s1 = init ⊕ f(e0) ⊕ f(e1)
...
sn-1 = init ⊕ f(e0) ⊕ f(e1) ⊕ ... ⊕ f(en−1)

减少

此外，还添加了以下两种reduce算法：

• reduce(first, last[, init[, bin_op]])
• transform_reduce(first, last, init, bin_op, un_op)

在哪里？ bin_op 是一个二进制运算符， std::plus<>() 默认情况下。这些算法产生一个值，类似于 accumulate() .

再假设范围[ first , last )表示为[e ₀ ，电子 _n ). reduce() 然后计算以下总和：

init ⊕ e0 ⊕ e1 ⊕ ... ⊕ en−1

当transform_reduce（）产生以下和时，假设一元运算符表示为函数调用 f ():

init ⊕ f(e0) ⊕ f(e1) ⊕ ... ⊕ f(en−1)

不像 accumulate() , reduce() 支持并行执行。这个 accumulate() 算法总是从左到右确定地计算每件事物，而对每件事物的计算顺序是不确定的 reduce() . 结果是 reduce() 如果二元运算符不是结合的或不是交换的，则将是不确定的。

计算的总和 reduce() 具有 init 等于0与调用的结果完全相同 accumulate() 只要使用的二元运算符是结合的和交换的。

最后，还有一组 transform_reduce() :

• transform_reduce(first1, last1, first2, init[, bin_op1, bin_op2])

它需要两个范围：一个范围[ first1 , last1 )，表示为[a ₀ ，一个 _n )，以及从 first2 ，表示为[b ₀ ，乙 _n ). 假设 bin_op1 ( std::plus<>() 默认情况下）表示为⊕, 和 bin_op2 ( std::multiplies<>() 默认情况下）表示为⊖, 然后计算以下总和：

init ⊕ (a0 ⊖ b0) ⊕ (a1 ⊖ b1) ⊕ ... ⊕ (an-1 ⊖ bn-1)

并行算法

C++ 17标准库的主要补充是支持并行执行60以上的算法，例如 sort() , all_of() , find() , transform() , …

如果标准库算法支持并行执行，则它接受执行策略作为其第一个参数。此策略确定算法可并行化或矢量化其执行的程度。当前，在中定义了以下策略类型和实例 std::execution 中的命名空间 <execution> 标题：

执行策略类型	全局实例	说明
顺序的u策略	seq	不允许并行执行。
平行保险单	par	允许并行执行。
并行u非顺序u策略	par_unseq	允许并行和矢量化执行。执行也可以在不同的线程之间切换。

这个 parallel_unsequenced_policy 对允许算法的函数回调执行的操作施加了很多限制。使用该策略，对回调的调用是不连续的。因此，它的回调不允许执行内存分配/释放、获取互斥等等。其他策略没有这样的限制，事实上保证它们的回调调用是按顺序排列的，当然它们可以按不确定的顺序排列。在任何情况下，您都有责任防止数据争用和死锁。

使用这些并行策略非常简单。下面是一个生成 vector 然后使用 std::transform() 并行计算每个值的平方根的算法：

using namespace std;

vector<double> data(1'000'000'000);
iota(begin(data), end(data), 1);

transform(execution::par_unseq, begin(data), end(data), begin(data),
          [](const auto& value) { return sqrt(value); });

如果在8核机器上运行这段代码，CPU负载如下所示。您在所有八个内核上看到的峰值是对 std::transform() .

效用函数

C++ 17还包括一些实用的函数，它们不是真正的算法，但仍然有用。

夹紧（）

std::clamp(value, low, high) 定义在 <algorithm> 标题。它确保给定的值在给定的范围内[ low , high ]. 呼叫的结果 clamp() 是：

• 引用 low 如果 value < low
• 引用 high 如果 value > high
• 否则，引用 value

一个用例是将音频样本钳制到16位范围：

using namespace std;
const int low = -32'768;
const int high = 32'767;
cout << clamp(12'000, low, high) << '';
cout << clamp(-36'000, low, high) << '';
cout << clamp(40'000, low, high) << '';

此代码段的输出如下：

12000
-32768
32767

gcd（）和lcm（）

std::gcd() 返回两个整数类型的最大公约数，而 lcm() 返回两个整数类型的最小公倍数。这两种算法在 <numeric> 标题。

使用这些算法很简单，例如：

cout << gcd(24, 44) << '';
cout << lcm(24, 44) << '';

输出如下：

4
264

删除的算法

C++ 17已经删除了一个算法：STD:：RealthySuffle（）。这个算法以前已经被C++ 14所标记，你应该使用。 std::shuffle() 相反。

进一步阅读材料

看看我的书，” 专业C++ 4 ^第 版本 由威利/WROX发布，用于对C++ 17标准库提供的所有功能进行更深入的概述。它还包括了C++ 17所添加的所有语言特征的描述。

此外，您还可以阅读更多关于我的某些C++ 17特性。 C++ 17博客系列文章 .