C++ STLアルゴリズムの進化：並列化からレンジ拡張まで

# C++ STLアルゴリズムの進化

C++標準ライブラリの[ヘッダ`<algorithm>`][algorithm]は、操作対象の型を限定しないジェネリックな「アルゴリズム」を提供します。かつては [STL(Standard Template Library)][stl] と呼ばれていたことから、C++標準ライブラリの一部となった現在でも STL として言及されることがあります。

この記事では最もシンプルな[検索アルゴリズム`find`][find]を題材に、C++標準ライブラリの進化を見ていきましょう。

[algorithm]: https://cpprefjp.github.io/reference/algorithm.html
[stl]: https://ja.wikipedia.org/wiki/Standard_Template_Library
[find]: https://cpprefjp.github.io/reference/algorithm/find.html


## C++14以前： STL 1.0

C++言語がC++98として標準化されてからC++14までの17年間（1998年～2014年）は、古き良き STL 1.0 時代の[`std::find`アルゴリズム][cpp11-find]のみが提供されました。

```cpp
// #1 基本の find
template<class InputIterator, class T>
  InputIterator find(InputIterator first, InputIterator last,
                     const T& value);
```

検索対象コンテナのイテレータ・ペアで表現される範囲`[first, last)`から、値`value`と一致する要素のイテレータを返します。それだけです。

```cpp
#include <vector>
#include <algorithm>

std::vector<int> vec = { 0, 1, 2, 3, 4, 5 };

// vec全体 から 要素値3 の位置を探す
auto it = std::find(vec.begin(), vec.end(), 3);

assert(it != vec.end() && *it == 3);
```

[cpp11-find]: https://timsong-cpp.github.io/cppwp/n3337/alg.find


## C++17： Parallel STL

C++11で初めて[マルチスレッド処理が正式に導入][thread]されましたが、C++17標準ライブラリでようやく[`std::find`アルゴリズム][cpp17-find]も並列処理に対応しました。並列化された STL という意味で Parallel STL とも呼ばれます。

```cpp
// #1 基本の find （C++14以前と同じ）
template<class InputIterator, class T>
  InputIterator find(InputIterator first, InputIterator last,
                     const T& value);

// #2 並列実行ポリシー指定 find
template<class ExecutionPolicy, class ForwardIterator, class T>
  ForwardIterator find(ExecutionPolicy&& exec,
                       ForwardIterator first, ForwardIterator last,
                       const T& value);
```

C++14以前からある`find`関数テンプレート(#1)に加えて、C++17では並列実行ポリシー`ExecutionPolicy`をとるオーバーロード(#2)が追加されました。第一引数に実行ポリシー`std::execution::par`を指定すると`find`アルゴリズムをマルチスレッドで並列処理でき、従来のシングルスレッド処理よりも高速に要素を見つけられる可能性があります。

```cpp
#include <vector>
#include <algorithm>
#include <execution>  // std::execution::par

std::vector<int> vec = { /*1万要素のデータ*/ };

// vec全体 から 要素値42 の位置をマルチスレッド並列処理で探す
auto it = std::find(std::execution::par, vec.begin(), vec.end(), 42);
```

※ C++に限らず マルチスレッド並列処理 == 常に高速動作する 保証はありません！たまに過度に期待される方がいますので念のため。

[thread]: https://cpprefjp.github.io/reference/thread.html
[cpp17-find]: https://timsong-cpp.github.io/cppwp/n4659/alg.find


## C++20： STL 2.0

きたるC++20では言語仕様に[コンセプト(Concepts)][concepts]が導入され、コンセプト機能を活用した[レンジ・ライブラリ(Ranges Library)][ranges]の名前空間`std::ranges`以下に[`find`アルゴリズム][cpp20-find]をはじめ拡張された関数テンプレートが追加されます。これらの追加ライブラリは STL 2.0 と言えるほどの機能拡張が行われます。

* イテレータ版／レンジ版アルゴリズムの両提供
* 要素比較時の射影(Projection)対応
* コンパイル時アルゴリズム処理（`constexpr`対応）

```cpp
// #1 基本の find （constepr対応）
template<class InputIterator, class T>
  constexpr InputIterator find(InputIterator first, InputIterator last,
                               const T& value);

// #2 並列実行ポリシー指定 find
template<class ExecutionPolicy, class ForwardIterator, class T>
  ForwardIterator find(ExecutionPolicy&& exec,
                       ForwardIterator first, ForwardIterator last,
                       const T& value);

// #3 イテレータ版 ranges::find
template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
  requires indirect_relation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});

// #4 レンジ版 ranges::find
template<input_range R, class T, class Proj = identity>
  requires indirect_relation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  constexpr safe_iterator_t<R>
    ranges::find(R&& r, const T& value, Proj proj = {});
```

<details><summary>（C++17知識で読めるよう変形した簡略宣言）</summary><div>

```cpp
// #3 イテレータ版 ranges::find の簡略宣言
template<class I, class S, class T, class Proj = identity>
  constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});

// #4 レンジ版 ranges::find の簡略宣言
template<class R, class T, class Proj = identity>
  constexpr safe_iterator_t<R>  // レンジRのイテレータ型
    ranges::find(R&& r, const T& value, Proj proj = {});
```
</div></details>

名前空間`std::ranges`以下には、従来アルゴリズム`std::find(first, last, value)`(#1)と良く似たイテレータ版`std::ranges::find(first, last, value)`(#3)と、全く新しいレンジ版`std::ranges::find(r, value)`(#4)の関数テンプレート2種類が追加されます。関数テンプレート宣言に見なれないパラメータ`Proj proj = {}`や`requires ...`が記載されていますが、とりあえずは無視して解釈しても大丈夫です。

```cpp
#include <vector>
#include <algorithm>

std::vector<int> vec = /*...*/;

// vec全体 から 要素値42 の位置を探す（イテレータ版 #3）
auto it = std::ranges::find(vec.begin(), vec.end(), 42);

// vec全体 から 要素値42 の位置を探す（レンジ版 #4）
auto it = std::ranges::find(vec, 42);
```

従来からあるイテレータ版の関数呼出し`find(vec.begin(), vec.end(), ...)`に比べると、レンジ版アルゴリズムでは`find(vec, ...)`のようにすっきり記述できます。これは単にタイピング数が減ってうれしいだけでなく、正しいイテレータ・ペアの組み合わせを意識する必要がなくなるため、イテレータ操作のバグ混入リスクが減ると期待されます。

```cpp
std::vector<int> vec1 = /*...*/;
std::vector<int> vec2 = /*...*/;

// NG: イテレータ・ペアが同一コンテナに属さないため、未定義動作となる
auto it = std::ranges::find(vec1.begin(), vec2.end(), 42);

// OK: コンテナvec1から検索する
auto it = std::ranges::find(vec1, 42);
```

さらに前掲コード例では省略していた引数`proj`を活用すると、例えば構造体の特定メンバ(`Item::id`)をキーとした検索処理をシンプルに記述できます。このような “コンテナ要素(`Item`)から比較対象(`int`)への[射影(Projection)][projection]” は、C++20で追加される多くのレンジ拡張アルゴリズムでサポートされます。

```cpp
struct Item {
  int          id;
  std::string  name;
};
std::vector<Item> items = /*...*/;
int pivot = 100;

// items全体 から id==100要素 の位置を探す（イテレータ版 #3）
auto it = std::ranges::find(items.begin(), items.end(), pivot, &Item::id);

// items全体 から id==100要素 の位置を探す（レンジ版 #4）
auto it = std::ranges::find(items, pivot, &Item::id);

// C++17以前は find_if アルゴリズムが必要
auto it = std::find_if(items.begin(), items.end(),
                       [pivot](const Item& e){ return e.id == pivot; });
```

またC++20標準ライブラリでは、ほとんど全てのアルゴリズム（名前区間`std`, `std::ranges`の両方）と、`std::vector<T>`や`std::array<T,N>`などの一部標準コンテナが`constexpr`対応、つまりコンパイル時処理に対応します。これまで以上にコンパイル時処理がはかどること請け合いですね。

[concepts]: https://cpprefjp.github.io/lang/cpp20/concepts.html
[ranges]: http://eel.is/c++draft/ranges
[cpp20-find]: http://eel.is/c++draft/alg.find
[projection]: http://eel.is/c++draft/defns.projection


## (C++23以降～)

C++20時点ではヘッダ`<algorithm>`配下の汎用アルゴリズムのみがレンジ拡張される予定です。[ヘッダ`<numeric>`][numeric]で提供される数値シーケンスアルゴリズムのレンジ拡張はC++23以降をターゲットに[検討][p1813]が進んでいるようです。

2019年10月現在、残念ながらC++標準ライブラリへのレンジ拡張を実装したC++コンパイラはまだ存在しません。しかし、C++20標準ライブラリにその大部分が採用された [Range-v3ライブラリ][range-v3] は今すぐお試し可能です（そのままC++20正式採用さるわけではないためご注意を）。

[numeric]: https://cpprefjp.github.io/reference/numeric.html
[p1813]: https://wg21.link/p1813
[range-v3]: https://github.com/ericniebler/range-v3