この節では、反復子の機能を使用してアルゴリズムの柔軟性や効率を向上させる手法について説明します。
場合によっては、ランダムアクセス反復子を使用して最も効率的に実装できるアルゴリズムが、低機能の反復子を使用して実装されることもあります。標準 C++ ライブラリには、単一のアルゴリズムが、渡される反復子の機能に基づいて複数の異なる実装を実現できる基本型が含まれています。以下の例は、同一アルゴリズムの複数バージョンを設定する通常の手法を示しています。
// これは、反復子が単純ポインタでない限り、
// 反復子が標準基本型から派生されることを要求していることに注意
namespace my_namespace {
template <class Iterator>
Iterator union(Iterator first1, Iterator last1,
Iterator first2, Iterator last2,
Iterator Result)
{
return union_aux(first1,last1,first2,last2,Result,
iterator_traits<first1>());
}
template <class Iterator>
Iterator union_aux(Iterator first1, Iterator last1,
Iterator first2, Iterator last2,
Iterator Result, forward_iterator_tag)
{
// 一般的であるが効率の劣る実装
}
template <class Iterator>
Iterator union_aux(Iterator first1, Iterator last1,
Iterator first2, Iterator last2,
Iterator Result,
random_access_iterator_tag)
{
// より効率的な実装
}
} // my_namespace の終わり
iterator_traits テンプレートは、テンプレートのインスタンス化に使用される型に基づいて、値、差分、ポインタ、参照、カテゴリの型定義を提供します。上記の例では、iterator_traits::iterator_category を使用して反復子の機能を決定し、次に特殊化を使用してアルゴリズムの最も利用可能性の高い実装を決定しています。iterator_traits が機能するためには、アルゴリズムに渡される反復子が単純ポインタ型であるか、反復子テンプレートから派生されるか、アルゴリズム自体が value_type、difference_type、pointer、reference、iterator_category の型を決定する必要があります。iterator_category 型は、input_iterator_tag、output_iterator_tag、forward_iterator_tag、bidirectional_iterator_tag、random_access_iterator_tag のいずれかになる必要があります。
iterator_traits テンプレートを使用するときは、アルゴリズムのデフォルトの実装は一般に順方向反復子を要求することに注意してください。アルゴリズムが、単純ポインタ型または基本標準反復子からの派生型ではない反復子を検出すると、このデフォルトバージョンが使用されます。入出力反復子は順方向反復子より機能が劣りますが、アルゴリズムの要求は、一般に読み取り・書き込み機能を要求することに注意してください。
また iterator_traits は、部分特殊化をサポートするコンパイラでのみ有効なことにも注意してください。これは、ポインタ型の iterator_traits の特殊化にこの機能が使用されるためです。コンパイラが部分特殊化をサポートしない場合、基本型 __iterator_category() を使用することができます。反復子引数を使用してこの関数を呼び出すと、iterator_traits を使用した場合に得られるタグと同じタグが返されます。たとえば、上記の例の iterator_traits を使用する代わりに、以下の行を使用することができます。
return union_aux(first1,last1,first2,last2,Result,
__iterator_category(first1));
反復子の指示する値の型または反復子間の距離を表す型を検出するには、iterator_traits::value_type および iterator_traits::difference_type を使用します。カテゴリ型の場合と同様に、部分特殊化が使用できないときは、代替関数 __value_type() または __distance_type() を使用します。このどちらの関数も、__iterator_category() の場合とまったく同様に、引数に反復子を使用します。
基本型 value_type を使用して、反復子の指示する値の型を決定することができます。同様に、基本型 distance_type を使用して、反復子間の距離を表す型を検出することもできます。
機能性に関係なく、2 つの反復子間の距離を効率よく検出するには、基本型 distance を使用します。基本型 distance は、16.4.1 節 の手法を使用して、4 つの異なる実装の 1 つに呼び出しプログラムを送ります。順方向反復子の実装は、次のように 2 つの反復子によって定義される範囲を進む必要があるため、効率は大幅に向上します。
Distance d = 0; while (start++ != end) d++;
これに対し、ランダムアクセス反復子の実装は、単に終了反復子から開始反復子を差し引くだけです。
Distance d = end - start;
基本型 advance を使用することで、同様の効率化を図ることもできます。この基本型を使用して、特定の反復子について、できる限り効率的に任意の数のステップを順方向または逆方向に進むことができます。