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

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

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

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

C++14以前： STL 1.0

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

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

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

#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);

C++17： Parallel STL

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

// #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アルゴリズムをマルチスレッドで並列処理でき、従来のシングルスレッド処理よりも高速に要素を見つけられる可能性があります。

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

C++20： STL 2.0

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

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

// #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 = {});

（C++17知識で読めるよう変形した簡略宣言）

// #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 = {});

名前空間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 ...が記載されていますが、とりあえずは無視して解釈しても大丈夫です。

#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, ...)のようにすっきり記述できます。これは単にタイピング数が減ってうれしいだけでなく、正しいイテレータ・ペアの組み合わせを意識する必要がなくなるため、イテレータ操作のバグ混入リスクが減ると期待されます。

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)” は、C++20で追加される多くのレンジ拡張アルゴリズムでサポートされます。

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対応、つまりコンパイル時処理に対応します。これまで以上にコンパイル時処理がはかどること請け合いですね。

(C++23以降～)

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

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