2.2 さまざまな反復子

表 3 に示すように、標準 C++ ライブラリで使用される反復子には 5 つの基本形式があります。

表 3 -- 標準 C++ ライブラリの反復子の形式

反復子のカテゴリは階層的です。順方向反復子は、入力反復子または出力反復子が要求される場合にいつでも使用することができます。双方向反復子は、順方向反復子の代わりに使用することができ、ランダムアクセス反復子は、双方向性が要求される状況で使用することができます。

反復子の第 2 の特性は、関連性のあるコンテナに保持される値の変更に使用できるかどうかということです。定数反復子はアクセスだけに使用できる反復子で、変更には使用できません。出力反復子が定数となることはなく、入力反復子は常に定数です。その他の反復子が定数となるかどうかは、作成方法によって異なります。定数と非定数の両方の双方向反復子や、定数と非定数の両方のランダムアクセス反復子などがあります。

表 4 に、標準 C++ ライブラリのコンテナでさまざまなカテゴリの反復子を生成する方法を示します。

表 4 -- 標準 C++ ライブラリで生成される反復子

以下の節では、各形式の反復子の機能と構造について説明します。

入力反復子は、最も単純な形式の反復子です。この機能を理解するために、プログラム例を示します。

template <class InputIterator, class T>
InputIterator 
   find (InputIterator first, InputIterator last, const T& value)
{
   while (first != last && *first != value) 
      ++first;
   return first;
}

このプログラムでは、find() 汎用アルゴリズム (13.3.1 節) が単純な線形探索を実行し、コンテナで保持されている特定の値を検索します。コンテナの内容は first と last の 2 つの反復子を使用して記述されます。first が last と等しくない場合は、first で示される要素がテスト値と比較されます。この要素がテスト値と等しい場合、検出された要素を示す反復子が返されます。等しくない場合は、first 反復子が増分され、ループがもう一度繰り返されます。目標値を検索することなく、メモリー領域全体が調査される場合、アルゴリズムは 範囲の終端反復子を返します。

このアルゴリズムは入力反復子の 3 つの機能を示します。

• 入力反復子が他の反復子と等しいかどうかを比較できる。2 つの反復子が同じ位置をポイントしている場合は等しく、そうでない場合は等しくない。

• 演算子 * を使用して、反復子によって示される値を取得することにより、入力反復子を間接参照することができる。

• 演算子 ++ を使用して、シーケンスの次の要素を参照するように入力反復子を増分することができる。

既知の機能の動作はすべて適切な演算子の多重定義によって変更できるため、これらの機能はすべて C++ プログラムの新しい目的のために提供されることが可能です。この多重定義によって、反復子が実現されます。

入力反復子には、通常のポインタ、コンテナ反復子、入力ストリーム反復子の 3 種類があります。

通常のポインタ。通常のポインタは、入力反復子として使用することができます。実際に、通常のポインタに添字や追加を行うことができるため、ランダムアクセス値であり、これによって、入力反復子としても、出力反復子としても使用することができます。範囲の終端ポインタは、連続するメモリー領域の終端を記述し、間接参照演算子とインクリメント演算子には従来どおりの目的があります。たとえば、次の例では整数の配列で値 7 を検索します。

int data[100];
   ...
int * where = find(data, data+100, 7);

配下の配列の変更を許可しない定数ポインタは、宣言にキーワード const を配置するだけで作成することができます。

const int * first = data;
const int * last = data + 100;
   // 以下によって返される位置は変更できない
const int * where = find(first, last, 7);

通常のポインタにはランダムアクセス反復子と同じ機能があるため、標準 C++ ライブラリで提供されるコンテナと同様に、標準 C++ ライブラリのほとんどの汎用アルゴリズムを従来の C++ 配列と共に使用することができます。

コンテナ反復子。標準C++ ライブラリで提供されるさまざまなコンテナのために作成されるすべての反復子には、少なくとも入力反復子と同程度の汎用性があります。コレクションの最初の要素のための反復子は必ずメンバー関数 begin() によって作成され、一方、終了位置を示す反復子はメンバー関数 end() によって生成されます。たとえば、次の反復子は整数のリストで値 7 を検索します。

list<int>::iterator where = find(aList.begin(), aList.end(), 7);

反復子をサポートする各コンテナは、クラス宣言内に iterator という名前の型を提供します。この型を使用すると、反復子を一様に上記のように宣言することができます。アクセスされるコンテナが定数の場合、または const_iterator という記述が使用される場合は、反復子が定数反復子となります。

入力ストリーム反復子。標準 C++ ライブラリには、入力反復子を使用して入力ストリームで演算を行う機構があります。この機能はクラス istream_iterator によって提供されます。詳細については、2.3.1 節で説明します。

出力反復子は入力反復子と逆の関数を持っています。出力反復子は、シーケンスに値を割り当てるために使用することができますが、値にアクセスするために使用することはできません。たとえば、1 つのシーケンスから別のシーケンスへ値をコピーする汎用アルゴリズムで、出力反復子を使用することができます。

template <class InputIterator, class OutputIterator>
OutputIterator copy
   (InputIterator first, InputIterator last, OutputIterator result) 
{
    while (first != last) 
      *result++ = *first++;
    return result;
}

2 つの並列シーケンスを操作する汎用アルゴリズムは多数あります。2 番目のシーケンスが 1 組の反復子ではなく、開始反復子だけを使用して記述されることがよく起こります。この際には、2 番目のシーケンスに少なくとも 1 番目のシーケンスと同数の要素があることを前提としますが、確認は行われません。

以下に示すアルゴリズムでは、1 組の入力反復子で指定されたソース値の範囲と宛先の範囲の 2 つの範囲が操作されます。しかし、後者は 1 つの引数だけで指定されます。出力先にすべての値を取り込める容量があることが前提であり、そうでない場合は、エラーが発生します。

このアルゴリズムで示すように、出力反復子を代入のターゲットとして使用することによって、ポイントする要素を変更することができます。出力反復子は、このような目的にだけ間接参照演算子を使用することができます。出力反復子が示す要素を返したり、アクセスするために使用することはできません。

すでに説明したように、通常のポインタは、標準 C++ ライブラリでコンテナによって作成されるすべての反復子と同様に、出力反復子として使用することができます (通常のポインタはランダムアクセス反復子で、出力反復子のスーパーセットです)。たとえば、次のコードでは、通常の C 形式の配列から断片化された要素が標準 C++ ライブラリの vector にコピーされます。

int data[100];
vector<int> newdata(100);
   ...
copy (data, data+100, newdata.begin());

入力反復子機構を使用して、入力ストリームで演算を行う方法を提供する istream_iterator と同様に、標準 C++ ライブラリは、反復子と同様の方法で値を出力ストリームへ書き込み可能にするためのデータ型である ostream_iterator を提供します (2.3.2 節)。

他の形式の出力反復子には、挿入反復子があります (2.4 節)。挿入反復子は、出力反復子のコンテナへの挿入の間接参照・代入および増分の演算を変更します。これによって、copy() などの演算を list や set などの可変長コンテナと共に使用できるようになります。

順方向反復子は、入力反復子と出力反復子の機能を組み合わせたものです。この反復子では、値へのアクセスと変更の両方を行うことができます。順方向反復子を使用する関数の 1 つは、特定の値の発生を他の値と置換する replace() 汎用アルゴリズムです。このアルゴリズムは、以下のように書かれています。

template <class ForwardIterator, class T>
void 
   replace (ForwardIterator first, ForwardIterator last, 
            const T& old_value, const T& new_value)
{
    while (first != last) 
    {
    if (*first == old_value) 
        *first = new_value;
        ++first;
    }
}

通常のポインタは、標準 C++ ライブラリでコンテナによって作成されるすべての反復子と同様に、順方向反復子として使用することができます。たとえば、次のコードでは、整数の vector の値 7 のインスタンスが値 11 に置換されます。

replace (aVec.begin(), aVec.end(), 7, 11);

双方向反復子は、デクリメント演算子 -- をサポートし、コンテナの要素間を順方向、逆方向のどちらにも移動できるようにする点を除けば、順方向反復子と同じです。たとえば、双方向反復子をコンテナの値を反転する関数に使用し、結果を新しいコンテナに出力することができます。

template <class BidirectionalIterator, class OutputIterator>
OutputIterator 
   reverse_copy (BidirectionalIterator first,
                 BidirectionalIterator last,
                 OutputIterator result) 
{
    while (first != last) 
    *result++ = *--last;
    return result;
}

通常と同じく、最初に last 引数で示される値は、コレクションの一部とはみなされません。

たとえば、reverse_copy() 関数を使用して、リンクリストの値を反転させ、結果を vector に出力することができます。

list<int> aList;
 ....
vector<int> aVec (aList.size());
reverse_copy (aList.begin(), aList.end(), aVec.begin() );

アルゴリズムには、順方向または逆方向のどちらかで値にアクセスする以上の機能を必要とするものもあります。ランダムアクセス反復子を使用すると、添字によって値にアクセスし、従来のポインタとまったく同じ方法で (それぞれの値の間の要素数を算出するために) 1 つの値から他の値を減算するか、算術演算によって変更することができます。

従来のポインタを使用すると、配下のメモリーに算術演算を関連付けることができます。つまり、x+10 は、x 開始後の 10 個の要素のメモリーです。反復子を使用すると、論理的意味が保持されますが (x+10 は x から 10 番目の要素)、記述される物理アドレスは異なります。

ランダムアクセス識別子を使用するアルゴリズムには、ソートや 2 等分探索などの汎用演算が含まれます。たとえば、次のアルゴリズムはコンテナの要素をランダムにシャフルします。これは、標準 C++ ライブラリで提供される関数 random_shuffle() によく似ていますが、より単純です。

template <class RandomAccessIterator>
void
   mixup (RandomAccessIterator first, RandomAccessIterator last)
{
   while (first < last) 
   {
      iter_swap(first, first + randomInteger(last - first));
      ++first;
   }
}

---

注: ここで説明する関数 randomInteger は、後の節で示すプログラム例で頻繁に使用されます。

---

シーケンスで last が示す位置よりも first が示す位置の方が前である限り、プログラムは循環します。関係演算子を使用して比較できるのは、ランダムアクセス反復子だけです。他のすべての反復子を比較できるのは、等価または非等価だけです。ループのサイクルごとに、式 last - first で 2 つの制限値の間の要素数が算出されます。関数 randomInteger() は、0 と引数の間の乱数を生成します。標準の乱数発生関数を使用すると、この関数を次のように書くことができます。

unsigned int randomInteger (unsigned int n)
   // 0 以上 n 未満の乱数を整数で返す。
{
   return rand() % n;
}

この乱数値は反復子 first に追加され、コンテナ内でランダムに選択された値への反復子となります。この値は、反復子 first によって示される要素と共に入れ替えられるようになります。

反復子により、配下のコンテナの値の順序が自然に決定されます。vector または map の場合、順序はインデックス値の昇順となり、set の場合、コンテナ内に保持される要素の昇順となります。list の場合、順序は値の挿入から明示的に派生します。

逆方向反復子は、標準反復子によって指定される値と逆の順序で値を正確に算出します。vector または list の場合、逆方向反復子は最初に最後の要素を生成し、最初の要素を最後に生成します。set の場合、最初に最も大きい要素を生成し、最後に最も小さい要素を生成します。厳密には、逆方向反復子は新しいカテゴリの反復子ではなく、別の型の反復子を修正したものです。その結果、逆方向の双方向反復子や逆方向のランダムアクセス反復子ができます。双方向反復子やランダムアクセス反復子は、reverse_iterator テンプレートによって適用することができます。

list、set、map のデータ型は、逆方向の双方向反復子を生成する 1 組のメンバー関数を提供します。関数 rbegin() と rend() は、配下のコンテナを逆の順序で循環する反復子を生成します。このような反復子への増分はシーケンスを逆方向に移動し、デクリメントは順方向に移動します。

同様に、vector と deque のデータ型は、逆方向のランダムアクセス反復子を生成する関数 (同じく rbegin()、rend() という名前) を提供します。添字演算子や加算演算子は、このような反復子への増分と同様に、シーケンス内を逆方向に移動します。