执行策略（C++17）

std::execution::seq
std::execution::par
std::execution::par_unseq
std::execution::unseq (C++20)

它们分别属于以下类型，但是使用的时候不要自己创建类型，应该直接使用标准库中提供的执行策略对象。

std::execution::sequenced_policy
std::execution::parallel_policy
std::execution::parallel_unsequenced_policy
std::execution::unsequenced_policy (C++20)

其中的并行策略仅仅是允许算法这样做，但不能强制算法按要求做。

Note that this is permission, not a requirement—the library may still execute the code on a single thread if it wishes.

如果指定了执行策略，那么抛出的异常将不会传播到当前线程，程序将会因为 std::terminate 的调用而终止。以下例子展示了为标准库算法模板指定 std::execution::seq 之后，抛出的异常就不再传播： https://godbolt.org/z/dTaKM4h6r 。这是指定 std::execution::seq 和不指定执行策略的一个显著的区别。打印结果中线程 ID 没有变化，说明这只是标准库为了满足标准做了专门处理，并不是为序列任务创建了一个新线程。

不同执行策略的比较

除了书上的内容，还可以参考网页 execution_policy_tag_t 。

std::execution::seq

序列化运行。

1. 这也是一种执行策略，所以根据标准规定，异常不会传播到调用者。
2. 保证操作按照某种顺序进行，但是这个顺序是未指定的（unspecified），而且在函数的不同次调用中可能操作顺序不同。

std::vector<int> v(1000);
int count = 0;
std::for_each(std::execution::seq, v.begin(), v.end(), [&](int& x) {
    x = ++count;
});

以上代码保证了执行按照某顺序进行，但是不保证按照从前到后的顺序访问 v 中的元素。这句话是书里面的说法，但是我看网上都说的是默认的执行策略是 std::execution::seq，我感觉可能是网上的不严谨？参考网页 execution_policy_tag_t，基本上也是这个意思：

The invocations of element access functions in parallel algorithms invoked with this policy (usually specified as std::execution::seq) are indeterminately sequenced in the calling thread.

std::execution::par

并行，要注意防止数据竞争。可以通过同步措施来访问数据。

execution_policy_tag_t 里说这个 tag 表示操作可以并行。如果 std::thread 或 std::jthread 创建的线程的执行提供 concurrent parallel execution（这个条件基本上都是满足的），那么由库创建的线程的执行提供 parallel forward progress。Parallel forward progress 的含义是：如果线程执行了一步，那么它最终会再前进一步，这样线程就能使用同步操作安全访问临界区。

std::execution::par_unseq

并行，且顺序未指定，不可以在线程之间施加同步措施。

execution_policy_tag_t 里说这个 tag 表示操作可以并行、向量化、在线程之间迁移（比如工作窃取）。每个元素访问函数不能使用 vectorization-unsafe 操作。如果 std::thread 或 std::jthread 创建的线程的执行提供 concurrent parallel execution，那么由库创建的线程的执行提供 weakly parallel forward progress。Weakly parallel forward progress 的含义是：执行线程中已经前进了一步的某一个线程最终会再前进一步。这禁止了线程访问临界区或者获取锁。因为持有锁的线程可能在尝试获取锁的线程执行完成之前都不再得到调度。

参考 https://stackoverflow.com/a/47706880/ ，在 par_unseq 这个策略下，同一个线程可以并发执行多个元素访问函数。比如：

// 安全
int sum = 0;
std::mutex m;
std::for_each(std::execution::par, std::begin(v), std::end(v), [&](int i) {
  std::lock_guard<std::mutex> lock{m};
  sum += i*i;
});

改成 par_unseq 策略就变得不安全：

 m.lock();    // iteration 1 (constructor of std::lock_guard)
 m.lock();    // iteration 2 <== 会在这里阻塞住，导致后面的代码无法运行
 sum += ...;  // iteration 1
 sum += ...;  // iteration 2
 m.unlock();  // iteration 1 (destructor of std::lock_guard)
 m.unlock();  // iteration 2

std::execution::unseq

execution_policy_tag_t 里说这个 tag 表示操作可以向量化。

标准库对迭代器的约定

例子：合并网站访问量

书上给了个合并网站访问量的例子，代码使用了 std::transform_reduce 函数。该函数首先用 transform 操作将一行字符串转换成一个记录结构，再用 reduce 操作将记录合并在一起。

Reduce 操作是比较麻烦的，因为我们必须考虑规约后的类型和规约前的类型不同的问题。为此我们可能需要使用提供多种参数类型重载的函数对象作为 reduce 函数，具体可见 https://godbolt.org/z/7jd854Ec9 。书上是使用了 4 个重载，libstdc++ 只用到其中 3 个，但是最好还是全部提供。