C++ - std::for_each_n() が導入された理由について

Question

C++17 で追加された「先頭から n 個の範囲に関数を適用する」という処理を行う std::for_each_n() は、これまであった std::for_each() で std::for_each(begin, begin + n) と指定すれば同じことができると思うのですが、なぜ別の関数として追加されたのでしょうか。
これら2つはどのように使い分ければいいのでしょうか。

よろしくおねがいします。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5};

    // for_each
    std::for_each(v.begin(), v.begin() + 3, [](int x) { std::cout << x << " "; });
    std::cout << std::endl;

    // for_each_n
    std::for_each_n(v.begin(), 3, [](int x) { std::cout << x << " "; });
    std::cout << std::endl;

    // 上記2つの違いがわからない
}

Answer 1

これら2つはどのように使い分ければいいのでしょうか。

通常のシングルスレッド逐次処理では、使い分けについて気にする必要はありません。その文脈において自然な方（イテレータペア指定 or 個数指定）を使えばよいでしょう。

第1引数に 実行ポリシーExecutionPolicy をとるマルチスレッド並列処理に非ランダムアクセスイテレータ（前方向イテレータや双方向イテレータ）を指定するケースでは、std::for_each関数 よりも std::for_each_n関数 の方が効率的に処理を実行できる可能性があります。

std::for_each走査対象範囲を複数スレッドにチャンク分割するとき、「要素総数の計算」が ランダムアクセスイテレータでは計算量 O(1) で済みますが、非ランダムアクセスイテレータでは計算量 O(N) を必要とします。std::for_each_nならばこの計算が必要ありません。

---

なぜ別の関数として追加されたのでしょうか。

std::for_each_nは、C++17標準ライブラリに追加された「並列アルゴリズム」の一部として追加されました。

並列アルゴリズムは Thrustライブラリ として標準化を目指して検討されてきた経緯があり、当時からthrust::for_eachとthrust::for_each_nの2種類が存在しました。

2012年頃のC++標準化提案文書 N3408 Parallelizing the Standard Algorithms Library には下記言及があります。要素数を指定する他の並列アルゴリズム（thrust::generate_nなど）の、実装を補助する道具としての側面があったようです。

5.1 std::for_each versus thrust::for_each and thrust::for_each_n
std::for_each assumes the function object it receives contains state which will be mutated inside a serial loop. It returns a copy of this state as a result. std::for_each_n does not exist.

By contrast, thrust::for_each and thrust::for_each_n instantiate many copies of their function object parameter in parallel. In such a setting, shared mutable state within the function object is a performance hazard at best. At worst, it is impossible for some parallel substrates to achieve. Instead, thrust::for_each and thrust::for_each_n exist exclusively for the sake of the side effects they may induce on the elements of their input ranges.

For consistency with other higher-level algorithms, thrust::for_each and thrust::for_each_n return the end of their input range. This simplifies the implementation of algorithms such as thrust::generate_n which can be lowered onto thrust::for_each_n in a straightforward manner.

Comments

[tiitoi]

std::for_each_n の使い所及び導入された経緯について、解説してくださりありがとうございます。ランダムアクセスでないイテレータのときは for_each_n のほうを使ってみますね。ExecutionPolicy もデフォルト以外試したことなかったので、使ってみたいと思います。

[episteme]

あーなるほど、Thrust由来か。納得。

[yohhoy]

回答中では for_each_n が有利になるケースを説明していますが、実際問題としては「非ランダムアクセスイテレータ（を提供するコンテナ）＋要素数は既知」という条件を満たすケースは稀かと思います。
C++標準アルゴリズムはイテレータ・ペアに対する操作がキホンですから、通常は for_each だけ覚えておけば十分な気はします。
P.S. C++20からは従来イテレータ・ペアに加えて、範囲(Range)サポートが追加されます。

Answer 2

イテレータは様々なコンテナを想定します。 ランダムアクセスが可能とは限りません。 (イテレータに足し算が可能であるとは限りません。)

配列や std::array std::vector std::string といったように要素が隣接することが保証されるデータ型では質問者が考えるような足し算で問題ありませんが、そうでない構造を持つ場合にはイテレータのインクリメントを一定回数繰り返す (std::advance) という形で進めるしかありません。 非効率ですので、上限を数値で指定できる方法があれば効率的に出来る可能性があります。

要素が隣接することが保証されないコンテナを途中まで辿るときには std::for_each_n が必要だということになります。

Comments

[tiitoi]

ランダムアクセスできないイテレータにも適用できるようにするという意図でしたか。
理解できました。迅速な回答ありがとうございます。

[episteme]

for_each( c.eagin(), next(c.begin(), n) ... ) って書けるんだから、
for_each「だけ」が _n 付きのが追加された理由としては弱い気がする。

[kazuma-s]

> for_each( c.eagin(), next(c.begin(), n) ... ) って書けるんだから、

c が list の場合、next でリンクを n 回たどって終了位置のイテレータを取得します。
そして、for_each でもう一度 list の先頭からリンクを n回たどります。二度リンクをたどります。
for_each_n なら、list のリンクをたどるのは一度で済みます。

[episteme]

フォローありがとです。
そうであったにせよ、for_each「だけ」が _n 付きのが追加された理由としては弱いんちゃうかしら、