cppreference.com -> C++ アルゴリズム

C++ アルゴリズム

この項目はStandard Template Library プログラミング on the Webより引用しています。引用を快く許可してくれたεπιστημηさんに感謝します。
STLの中心的存在がアルゴリズムです。
コンテナ、イテレータ、関数オブジェクト
はどれもアルゴリズムを機能させるために
用意されたと言ってもいいでしょう。

アルゴリズムはコンテナに対する汎用的な操作を提供します。コンテナ(データ構造)とアルゴリズムはイテレータ(コンテナ内の要素にアクセスするためのオブジェクト)を介して結び付けられます。

STLのほとんどのアルゴリズムには入力となる要素の集合を2つのイテレータで指定します。ひとつは集合の先頭を指すイテレータfirst、もうひとつは集合の末尾の次を指すイテレータlastです。すなわちアルゴリズムはfirstから始まりlastに達しない範囲(first以上last未満)にある要素を入力とします。

末尾位置を指定するのに"末尾の次"を使うのは、

です。 アルゴリズムはおおまかに以下の４種類のカテゴリに分類されます。

表の読み方
略記号 イテレータ種別(下にあるものは上のイテレータの機能も持つ)
I input_iterator
O output_iterator
F forward_iterator
B bidirectional_iterator
R random_iterator
T イテレータ以外の型

(I, I)というのは、一つの配列で、先頭と終端を表すinput_iteratorを引数に持つ。(I, I), Iは二組配列を示す。後者の配列はoutput_iterator以外の場合には前者と同じか、大きい要素数を持っている必要がある。(F, F), (F, F)は二組の配列の先頭と終端を表すforward_iteratorを二組、計４個引数にとるということを表している。配列のサイズは同じである必要はない。(F, F, F)のように３個のイテレータが指定されているものは、一つの配列を真ん中のイテレータを境に前半と後半に分けて２つの配列として扱うアルゴリズムである。