Skip to content

Latest commit

 

History

History
563 lines (455 loc) · 20.1 KB

ch23.md

File metadata and controls

563 lines (455 loc) · 20.1 KB
Raw

Chapter23 新的STL算法详解

C++17引入了一些新的STL算法。主要目的是为了支持并行化， 不过你也可以顺序地使用这些算法。

23.1 std::for_each_n()

作为并行STL算法的一部分，原本的for_each_n()又有了一个新的并行版本。 类似于copy_n()、fill_n()、generate_n()，这个算法需要 一个整数参数指出要对范围内多少个元素进行操作。

InputIterator
for_each_n (ExecutionPolicy&& pol,  // 可选的
            InputIterator beg,
            Size count,
            UnaryProc op)
  • 对以 beg 为起点的范围中前 count 个元素调用 op(elem) 。
  • 返回最后一个调用了 op ()的元素的下一个位置。
  • 调用者必须保证以 beg 为起点的范围内包含足够多的元素。
  • op 返回的任何值都会被忽略。
  • 如果没有传递执行策略，for_each_n()保证传入的可调用对象按照顺序对每个元素进行调用。
  • 如果传入了第一个可选的执行策略参数：
    • 对所有元素调用 op 的顺序没有任何保证。
    • 调用者要保证并行操作不会产生数据竞争。
    • 迭代器必须至少是前向迭代器。
  • 复杂度：线性（op ()会调用 count 次）

例如：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>    // for for_each_n()

int main()
{
    // 初始化10,000个string的vector：
    std::vector<std::string> coll;
    for (int i = 0; i < 10000; ++i) {
        coll.push_back(std::to_string(i));
    }

    // 修改前5个元素：
    for_each_n(coll.begin(), 5,
               [] (auto& elem) {
                   elem = "value" + elem;
               });

    // 打印前10个元素：
    for_each_n(coll.begin(), 10,
               [] (const auto& elem) {
                   std::cout << elem << '\n';
               });
}

我们首先用足够数量的string初始化了一个vector，之后我们先是修改了前5个string：

for_each_n(coll.begin(), 5,
           [] (auto& elem) {
               elem = "value" + elem;
           });

然后又打印出前10个string：

for_each_n(coll.begin(), 10,
           [] (const auto& elem) {
               std::cout << elem << '\n';
           });

因此，程序将会有如下输出：

value0
value1
value2
value3
value4
5
6
7
8
9

23.2 新的STL数值算法

这一节中列出了定义在头文件<numeric>中的新STL算法。 注意这些新算法的动机之前就已经讨论过。

23.2.1 std::reduce()

typename iterator_traits<InputIterator>::value_type
reduce (ExecutionPolicy&& pol,   // 可选的
        InputIterator beg, InputIterator end)

T
reduce (ExecutionPolicy&& pol,   // 可选的
        InputIterator beg, InputIterator end,
        T initVal)

T
reduce (ExecutionPolicy&& opl,   // 可选的
        InputIterator beg, InputIterator end,
        T initVal,
        BinaryOp op)

  • 前两个形式返回范围[beg, end)内所有元素和初始值之和。 因此，在如下初始化后：

    result = initVal

    将会对每个元素调用如下语句：

    result = result + elem

  • 对于第一种形式，初始值是元素类型的“默认值”（默认构造函数构造出的值或者是 0、0.0、false、nullptr等。

  • 对于第二种形式，初始值是 initVal 。

  • 因此，对于值

    a1 a2 a3 a4 ...

    前两种形式会计算并返回：

    initVal + a1 + a2 + a3 + ...

  • 第三种形式计算并返回对 initVal 和范围[beg, end)内 所有元素调用 op 的结果。它会对每一个元素进行如下调用：

    result = op(result, elem)

    因此，对于值

    a1 a2 a3 a4 ...

    这种形式会计算并返回：

    initVal op a1 op a2 op a3 op ...

  • 如果范围为空（ beg==end ），所有形式都返回初始值。

  • op 不能修改传入的参数。

  • 复杂度：线性（运算符+或者 op ()调用 numElems 次）。

  • 对于并行版本的std::accumulate()。如果传递了第一个可选的执行策略参数：

    • 调用 op 的顺序并没有任何保证，所以 op 必须是可交换可结合的。
    • 调用者需要保证并行进行操作不会导致数据竞争。
    • 迭代器必须至少是前向迭代器。

例如，下面的程序：

#include <array>
#include <iostream>
#include <numeric>

int main()
{
    std::array coll{3, 1, 7, 5, 4, 1, 6, 3};

    // 计算元素之和
    std::cout << "sum: "
              << std::reduce(coll.cbegin(), coll.cend())    // 范围
              << '\n';

    // 指定初始值计算元素之和
    std::cout << "sum: "
              << std::reduce(coll.cbegin(), cool.cend()),   // 范围
                             0)                             // 初始值
              << '\n';

    // 计算所有元素的积
    std::cout << "product: "
              << std::reduce(coll.cbegin(), coll.cend(),    // 范围
                             1LL,                           // 初始值
                             std::multiplies{})             // 操作数
              << '\n';

    // 计算所有元素的积（0作为初始值）
    std::cout << "product: "
              << std::reduce(coll.cbegin(), coll.cend(),    // 范围
                             0,                             // 初始值
                             std::multiplies{})             // 操作数
              << '\n';
}

将会有如下输出：

sum: 30
sum: 30
product: 7560
product: 0

参见并行算法的动机小节来了解关于这个算法的更详细的动机。

23.2.2 std::transform_reduce()

std::transform_reduce()有两种变体：

单范围的std::transform_reduce()

T
transform_reduce (ExecutionPolicy&& pol,    // 可选的
                  InputIterator beg, InputIterator end,
                  T initVal,
                  BinaryOp op2, UnaryOp op1)

  • 计算并返回范围[beg, end)内所有元素变换之后再和初始值一起进行结合/累积之后的结果。

  • 因此，对于值

    a1 a2 a3 a4 ...

    它会计算并返回

    initVal op2 op1(a1) op2 op1(a2) op2 op1(a3) op2 ...

  • 如果范围是空的（ beg==end ），它会返回 initVal 。

  • op1 和 op2 不能修改传入的参数。

  • 复杂度：线性（ op1 和 op2 调用 numElems 次）。

  • 对于并行版本的std::accumulate()。如果传递了第一个可选的执行策略参数：

    • 调用 op2 的顺序并没有任何保证，所以 op2 必须是可交换可结合的。
    • 调用者需要保证并行进行操作不会导致数据竞争。
    • 迭代器必须至少是前向迭代器。

例如，下面的程序：

#include <array>
#include <iostream>
#include <numeric>

int main()
{
    std::array coll{3, 1, 7, 5, 4, 1, 6, 3};

    auto twice = [] (int v) { return v*2; };

    // 计算每个元素的两倍的和：
    std::cout << "sum of doubles: "
              << std::transform_reduce(coll.cbegin(), coll.cend(),  // 范围
                                       0, std::plus{}, twice)
              << '\n';

    // 计算每个元素的平方的和：
    std::cout << "sum of squared: "
              << std::transform_reduce(coll.cbegin(), coll.cend(),  // 范围
                                       0L, std::plus{},
                                       [] (auto v) {
                                           return v * v;
                                       })
              << '\n';
}

会有如下输出：

sum of doubles: 60
sum of squared: 146

参见并行算法的动机小节来了解关于这个算法的更详细的动机 和一些其他的例子。

双范围的std::transform_reduce()

T
transform_reduce (ExecutionPolicy&& pol,    // 可选的
                  InputIterator1 beg1, InputIterator1 end1,
                  InputIterator2 beg2,
                  T initVal)

T
transform_reduce (ExecutionPolicy&& pol,    // 可选的
                  InputIterator1 beg1, InputIterator1 end1,
                  InputIterator2 beg2,
                  T initVal,
                  BinaryOp1 op1, BinaryOp2 op2)

  • 第一个形式计算范围[beg1, end1)和 以 beg2 开头的范围内元素的内积再加上 initVal 。 特别地，它对每两个相应的元素进行如下操作：

    initVal = initVal + elem1 * elem2

  • 第二个形式首先对范围[beg1, end1)和 以 beg2 开头的范围内每两个相应的元素调用 op2 ， 再对 initVal 和所有上一步的结果调用 op1 。 特别地，它对每两个相应的元素进行如下操作：

    initVal = op1(initVal, op2(elem1, elem2))

  • 因此，对于值

    a1 a2 a3 ...

    b1 b2 b3 ...

    这个形式会计算并返回

    initVal + (a1 * b1) + (a2 * b2) + (a3 * b3) + ...*

    或者

    initVal op1 (a1 op2 b1) op1 (a2 op2 b2) op1 (a3 op2 b3) op1 ...

  • 如果范围为空（ beg1==end1 ），所有形式都会返回 initVal 。

  • 调用者必须保证以 beg2 开头的范围含有足够数量的元素（至少要和 范围[beg1, end1)的元素数量一样多）。

  • op1 和 op2 不能修改传入的参数。

  • 复杂度：线性（ op1 和 op2 调用 numElems 次）。

  • 对于并行版本的std::inner_product()。 如果传递了第一个可选的执行策略参数：

    • 调用 op1 的顺序并没有任何保证，所以 op1 必须是可交换可结合的。
    • 调用者需要保证并行进行操作不会导致数据竞争。
    • 迭代器必须至少是前向迭代器。

例如，下面的程序：

#include <array>
#include <iostream>
#include <numeric>
#include <string>

int main()
{
    std::array coll1{3, 1, 7, 5, 4, 1, 6, 3};
    std::array coll2{1, 2, 3, 4, 5, 6, 7, 8};

    // 计算每个元素的平方的和：
    std::cout << "sum of squared:         "
              << std::transform_reduce(coll1.cbegin(), coll1.cend(),    // 第一个范围
                                       coll1.cbegin(),                  // 第二个范围
                                       0L)
              << '\n';

    // 计算每两个相应元素的差的乘积：
    std::cout << "product of differences: "
              << std::transform_reduce(coll1.cbegin(), coll1.cend(),    // 第一个范围
                                       coll2.cbegin(),                  // 第二个范围
                                       1L,
                                       std::multiplies{}, std::minus{})
              << '\n';

    // 先把两个相应元素转换成的字符串连接起来，再连接所有上一步生成的字符串：
    std::cout << "sum of combined digits: "
              << std::transform_reduce(coll1.cbegin(), coll1.cend(),    // 第一个范围
                                       coll2.cbegin(),                  // 第二个范围
                                       std::string{}, std::plus{},
                                       [] (auto x, auto y) {
                                           return std::to_string(x) + std::to_string(y) + " ";
                                       })
              << '\n';
}

将会有如下输出：

sum of squared:         146
product of differences: -200
sum of combined digits: 31 12 73 54 45 16 67 38

23.2.3 std::inclusive_scan()和std::exclusive_scan()

OutputIterator
inclusive_scan (ExcutionPolicy&& pol,   // 可选的
                InputIterator inBeg, InputIterator inEnd,
                OutputIterator outBeg,
                BinaryOp op,            // 可选的
                T initVal)              // 可选的

OutputIterator
exclusive_scan (ExcutionPolicy&& pol,   // 可选的
                InputIterator inBeg, InputIterator inEnd,
                OutputIterator outBeg,
                T initVal,              // 必须的
                BinaryOp op)            // 可选的

  • 所有的形式都计算范围[inBeg, inEnd)内每个 元素和之前所有元素组合之后的值并写入以 outBeg 开头的目标范围。

  • inclusive_scan()和exclusive_scan()的区别在 于exclusive_scan()的结果以初始值开始并排除输入的最后一个元素。 注意两种形式函数参数和初始值参数的顺序不同。另外exclusive_scan()中初始值参数是必须的。

  • 因此，对于值

    a1 a2 a3 ... aN

    inclusive_scan()会计算

    initVal op a1, initVal op a1 op a2, initVal op a1 op a2 op a3, ... aN

    exclusive_scan()会计算

    initVal, initVal op a1, initVal op a1 op a2, ... op aN-1

    这意味着对于inclusive_scan()来说， initVal 充当每个输出值的偏移量， 而对于exclusive_scan()来说，它充当第一个输出的值（尽管如果输入区间为空时它并不会被写入到输出区间）。

  • 所有的形式都返回最后一个被写入的位置的下一个位置（第一个还未被写入的位置）。

  • 如果没有传递 op ，将会使用std::plus，因此会计算所有元素的和。

  • 如果没有传递 initVal （只有inclusive_scan()会出现这种情况）， 将不会添加初始值。因此，第一个输出的值将直接是第一个输入的值。

  • 如果范围为空（ inBeg==inEnd ），所有形式都不会写入任何值。

  • 调用者必须保证以 outBeg 开头的区间有足够数量的元素可以写入（事实上， 至少要和输入区间里的元素一样多），或者直接使用插入迭代器。

  • op 不能修改传入的参数。

  • 复杂度：线性（ op 会调用 numElems 次）。

  • 对于并行版本的std::partial_sum()。如果传递了第一个可选的执行策略参数：

    • 调用 op 的顺序并没有任何保证，所以 op 必须是可交换可结合的。
    • 调用者需要保证并行进行操作不会导致数据竞争。
    • 迭代器必须至少是前向迭代器。

例如，如下程序：

#include <numeric>
#include <iostream>
#include <iterator>
#include <array>

int main()
{
    std::array coll{3, 1, 7, 0, 4, 1, 6, 3};

    std::cout << " inclusive_scan():   ";
    std::inclusive_scan(coll.begin(), coll.end(),
                        std::ostream_iterator<int>(std::cout, " "));

    std::cout << "\n exclusive_scan(): ";
    std::exclusive_scan(coll.begin(), coll.end(),
                        std::ostream_iterator<int>(std::cout, " "),
                        0);     // 必须的

    std::cout << "\n exclusive_scan(): ";
    std::exclusive_scan(coll.begin(), coll.end(),
                        std::ostream_iterator<int>(std::cout, " "),
                        100);   // 必须的

    std::cout << "\n inclusive_scan():     ";
    std::inclusive_scan(coll.begin(), coll.end(),
                        std::ostream_iterator<int>(std::cout, " "),
                        std::plus{}, 100);

    std::cout << "\n exclusive_scan(): ";
    std::exclusive_scan(coll.begin(), coll.end(),
                        std::ostream_iterator<int>(std::cout, " "),
                        100, std::plus{});  // 注意：参数顺序不同
}

将会有如下输出：

inclusive_scan():   3 4 11 11 15 16 22 25
exclusive_scan(): 0 3 4 11 11 15 16 22
exclusive_scan(): 100 103 104 111 111 115 116 122
inclusive_scan():     103 104 111 111 115 116 122 125
exclusive_scan(): 100 103 104 111 111 115 116 122

注意两个算法输出的值的数量都和输入区间内的元素数量相同。然而，当使用inclusive_scan()时， 我们以第一个元素开始，以所有元素组合的结果结尾（加上传递的初始值作为偏移量）， 当使用exclusive_scan()时，我们以初始值开始，以除了最后一个元素之外的所有元素的组合结果结尾。

23.2.4 std::transform_inclusive_scan()和std::transform_exclusive_scan()

OutputIterator
transform_inclusive_scan (ExcutionPolicy&& pol,     // 可选的
                          InputIterator inBeg, InputIterator inEnd,
                          OutputIterator outBeg,
                          BinaryOp op2,             // 必须的
                          UnaryOp op1,              // 必须的
                          T initVal)                // 可选的

OutputIterator
transform_exclusive_scan (ExcutionPolicy&& pol,     // 可选的
                          InputIterator inBeg, InputIterator inEnd,
                          OutputIterator outBeg,
                          T initVal,                // 必须的
                          BinaryOp op2,             // 必须的
                          UnaryOp op1)              // 必须的

  • 所有的形式都先对范围[inBeg, inEnd)内每个 元素进行变换，再把每个元素变换后的值和之前所有元素变换后的值组合之后的值写入以 outBeg 开头的目标范围。

  • transform_inclusive_scan()和transform_exclusive_scan()的区别在于 后者以初始值开始并且会排除最后一个输入元素。注意这两个函数最后几个参数的顺序不同，另外exclusive_scan()的 初始值参数是必须的。

  • 因此，对于值

    a1 a2 a3 ... aN

    transform_inclusive_scan()会计算

    initVal op2 op1(a1), initVal op2 op1(a1) op2 op1(a2), ... op2 op1(aN)

    transform_exclusive_scan()会计算

    initVal, initVal op2 op1(a1), initVal op2 op1(a1) op2 op1(a2), ... op2 op1(aN-1)

    这意味着对于transform_inclusive_scan()， initVal 作为每一个输出值的偏移量，而对于transform_ exclusive_scan()，它将作为第一个输出的值（尽管如果输入区间为空时不会输出任何值）。

  • 所有的形式都返回最后一个被写入的位置的下一个位置（第一个还未被写入的位置）。

  • 如果没有传递initVal（只有transform_inclusive_scan()会出现这种情况）， 将不会添加初始值。因此，第一个输出的值将直接是第一个输入元素变换后的值。

  • 如果输入范围为空（ inBeg==inEnd ），所有形式都不会写入任何值。

  • 调用者必须保证以 outBeg 开头的区间有足够数量的元素可以写入（事实上， 至少要和输入区间里的元素一样多），或者直接使用插入迭代器。

  • op1 和 op2 不能修改传入的参数。

  • 复杂度：线性（ op1 和 op2 会调用 numElems 次）。

  • 如果传递了第一个可选的执行策略参数：

    • 调用 op2 的顺序并没有任何保证，所以 op2 必须是可交换可结合的。
    • 调用者需要保证并行进行操作不会导致数据竞争。
    • 迭代器必须至少是前向迭代器。

例如，下面的程序：

#include <numeric>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <array>

int main()
{
    std::array coll{3, 1, 7, 0, 4, 1, 6, 3};

    auto twice = [] (int v) { return v*2; };

    std::cout << " source:                      ";
    std::copy(coll.begin(), coll.end(),
              std::ostream_iterator<int>(std::cout, " "));

    std::cout << "\n transform_inclusive_scan():      ";
    std::transform_inclusive_scan(coll.begin(), coll.end(),
                                  std::ostream_iterator<int>(std::cout, " "),
                                  std::plus{}, twice);

    std::cout << "\n transform_inclusive_scan():      ";
    std::transform_inclusive_scan(coll.begin(), coll.end(),
                                  std::ostream_iterator<int>(std::cout, " "),
                                  std::plus{}, twice, 100);

    std::cout << "\n transform_exclusive_scan():  ";
    std::transform_exclusive_scan(coll.begin(), coll.end(),
                                  std::ostream_iterator<int>(std::cout, " "),
                                  100, std::plus{}, twice); // 注意参数顺序
}

将会有如下输出：

source:                      3 1 7 0 4 1 6 3
transform_inclusive_scan():      6 8 22 22 30 32 44 50
transform_inclusive_scan():      106 108 122 122 130 132 144 150
transform_exclusive_scan():  100 106 108 122 122 130 132 144

注意两个算法输出的值的数量都和输入区间内的元素数量相同。然而，当使用transform_inclusive_ scan()时，我们以第一个元素变换后的值开始，以所有元素变换后的值的组合结尾（加上传入的初始值作为偏移量）， 而当使用transform_exclusive_scan()时，我们以初始值开始，以除了最后一个元素 之外的所有元素变换后的值的组合结尾。