move in accumulateアルゴリズム

C++20標準ヘッダ<numeric>のstd::accumulateアルゴリズム内部実装では、T型のアキュムレータ変数(acc)への累積操作時にstd::move関数適用（右辺値への変換）が規定される。

// C++20仕様の累積演算（1要素あたり）
acc = std::move(acc) + *iterator;
//    ^^^^^^^^^^^^^^
//    右辺値

// C++17仕様の累積演算（1要素あたり）
acc = acc + *iterator;
//    ^^^
//    左辺値

C++17以前の標準ライブラリ仕様では左辺値に対する演算となっていたが、右辺値に変更されたことで（代入右辺の）accオブジェクトに対する破壊的操作が可能となり、より効率的な実装が選択される可能性が広がる。

本ライブラリ仕様変更の提案文書P0616R0では、事前メモリ確保した文字列型に対する累積（連結）操作において大幅な性能改善を報告している。*1

1 Motivation
(snip)
A very simple measurement program showing the difference of using accumulate with strings with or without move show a significant improvement for that case (150 to over 200 times faster with concatenating 10000 short strings, with the additional potential of pre-allocating the whole string size up front when using move). (snip)

同様の改善はinner_product, partial_sum, adjacent_differenceアルゴリズムに対しても適用される。

C++20

C++20 25.10.2/p2より引用（下線部は強調）。

template <class InputIterator, class T>
  constexpr T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
  constexpr T accumulate(InputIterator first, InputIterator last, T init, 
                         BinaryOperation binary_op);
Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = std::move(acc) + *i or acc = binary_op(std::move(acc), *i) for every iterator i in the range [first, last) in order.

C++17以前

C++17 29.8.2/p2より引用。

template <class InputIterator, class T>
  T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
  T accumulate(InputIterator first, InputIterator last, T init, 
               BinaryOperation binary_op);
Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first, last) in order.

yohhoyの日記

技術的メモをしていきたい日記

move in accumulateアルゴリズム

C++20

C++17以前