コンテンツにスキップ

最終更新：2026-10-12

STL イテレータソースコード解析

0.はじめに

本節では前節のTraitsの特性を使い、iteratorのソースコードを研究して、簡単なiterator_categoryを実現するとともに、iteratorのソースコード構造を分析します。

そのように動くことを知るだけでなく、なぜそのように動くのかを知る。ソースコードの前には秘密はない！

1.抽出機（traits）を使って簡単なiterator_categoryの識別を実現する

前節でイテレータの役割を示しました。下図の通りです：

rela

イテレータは、シーケンスの要素を指すポインタの一種の抽象です。イテレータを使うことで、シーケンス中の特定の要素にアクセスしたり、シーケンス中の特定の要素の値を変更したり、イテレータを前後に進めたりすることができます。

イテレータにはよく見られる5つの型があります： value_type, difference_type, reference_type, pointer_type はいずれも traits と対応する部分特殊化で比較的簡単に抽出できます。

しかし、iterator_categoryも一般に5つあり、この関連型は比較的大規模なコーディング作業を引き起こします。

  • 単方向移動の読み取り専用イテレータ Input Iterator
  • 単方向移動の書き込み専用イテレータ Output Iterator
  • 単方向移動の読み書きイテレータ Forward Iterator
  • 双方向移動の読み書きイテレータ Bidirectional Iterator

iterator

例えば、私たちがadvanceII, advanceBI, advanceRAIを実装し、それぞれイテレータ型がInput Iterator、Bidirectional Iterator、Random Access Iteratorである場合の対応する実装を表すとします。

template<class Iterator>
void advance(Iterator& i) {
    if (is_random_access_iterator(i))
        advanceRAI(i,n);
    if (is_bidirectional_iterator(i))
        advanceBI(i,n);
    else
        advanceII(i,n);
}

しかしこのように実行時にどのバージョンを使うかを決めると、プログラムの効率に影響します。できればコンパイル時に正しいバージョンを選択したいものです。

**オーバーロード**という関数の機構でこの目標を達成できます。

advanceXX()にはいずれも2つの関数パラメータがあり、型はどちらも未定です（いずれもテンプレートパラメータのため）。同名にしてオーバーロード関数を形成するには、型が確定している関数パラメータを追加し、関数オーバーロード機構を有効に機能させなければなりません。

次のように設計します：**traits**がイテレータの種類を抽出できれば、この「イテレータ型」の関連型をadvancexxの第3パラメータとして使えます。この関連型はclass typeでなければならず、数値番号のようなものであってはなりません。コンパイラがそれに依存して**オーバーロード解決**を行うためです。

では実装に入ります。まず全体の構造図を示します：

itera

次のtagを定義します：

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
// 继承的好处就是，当函数需要用 input_iterator_tag 的时候
// 假设你传进一个forward_iterator_tag，它会沿继承向上找，知道符合条件

一連の tag を定義した後、advance関数をオーバーロードできます。これらの関数はアンダースコアで定義し、内部でのみ使用され、外部からは見えないことを表します。

// 继承的好处就是，当函数需要用 input_iterator_tag 的时候
// 假设你传进一个forward_iterator_tag，它会沿继承向上找，知道符合条件
// input iterator
template<class inputIterator, class distance>
inline void __advance(inputIterator&i, distance n,
                      input_iterator_tag) {
    std::cout << "input tag" << std::endl;
}
// output iterator
template<class outputIterator, class distance>
inline void __advance(outputIterator&i, distance n,
                      output_iterator_tag) {
    std::cout << "output tag" << std::endl;
}

// forward iterator
template<class ForwardIterator, class Distance>
inline void __advance(ForwardIterator &i, Distance n,
                      forward_iterator_tag) {
    std::cout << "forward tag" << std::endl;
}

// bidrectional iterator
template<class BidiectionalIterator, class Distance>
inline void __advance(BidiectionalIterator &i, Distance n,
                      bidiectional_iterator_tag) {
    std::cout << "bidrectional tag" << std::endl;

}

// RandomAccess iterator
template<class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator &i, Distance n,
                      random_access_iterator_tag) {
    std::cout << "randomaccess tag" << std::endl;

}

抽出機を定義します：

// traits 型别
template<class I>
struct Iterator_traits {
    typedef typename I::iterator_category iterator_category;
};

// 针对原生指针设计的"偏特化版"
template<class I>
struct Iterator_traits<I *> {
    typedef random_access_iterator_tag iterator_category;
};
template<class I>
struct Iterator_traits<const I *> {
    typedef random_access_iterator_tag iterator_category;
};

外部に公開するインターフェース：

// 对外接口
template<class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
    // 通过Ierator_traits询问它的iterator_category是谁
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    __advance(i, n, category()); // 各型别的重载
}

class typeを定義します：

// class type
template<class Category>
struct iterator {
    typedef Category iterator_category;
};

テストを始めます。上で定義したclass typeと生ポインタを使ってテストし、それぞれ抽出機の普通の抽出機と部分特殊化の抽出機に入り、対応するTagが得られるか見てみます。

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidiectional_iterator_tag> bidect;
    iterator<random_access_iterator_tag> random;
    advance(input, 10);
    advance(output, 10);
    advance(forward, 10);
    advance(bidect, 10);
    advance(random, 10);
    int *p=NULL;
    advance(p,10);
    return 0;
}

出力結果：

input tag
output tag
forward tag
bidrectional tag
randomaccess tag
randomaccess tag

すべて期待通りで、抽出機を通じて、各イテレータのtag、および生ポインタのtagを取得できました。

もう少し複雑に考えましょう。advanceの戻り値の型を知りたい場合はどうすればよいでしょうか？

まずadvanceの戻り値を変更します：

// 对外接口
template<class InputIterator, class Distance>
inline typename Iterator_traits<InputIterator>::iterator_category
advance(InputIterator &i, Distance n) {
    // 通过Ierator_traits询问它的iterator_category是谁
    typedef typename Iterator_traits<InputIterator>::iterator_category category;
    return __advance(i, n, category()); // 各型别的重载
}

続いて__advanceの戻り値を変更します：

// input iterator
template<class inputIterator, class distance>
inline typename Iterator_traits<inputIterator>::iterator_category
__advance(inputIterator &i, distance n,
          input_iterator_tag) {
    std::cout << "input tag" << std::endl;
    return input_iterator_tag();
}

// output iterator
template<class outputIterator, class distance>
inline typename Iterator_traits<outputIterator>::iterator_category
__advance(outputIterator &i, distance n,
          output_iterator_tag) {
    std::cout << "output tag" << std::endl;
    return output_iterator_tag();
}

// forward iterator
template<class ForwardIterator, class Distance>
inline typename Iterator_traits<ForwardIterator>::iterator_category
__advance(ForwardIterator &i, Distance n,
          forward_iterator_tag) {
    std::cout << "forward tag" << std::endl;
    return forward_iterator_tag();
}

// bidrectional iterator
template<class BidiectionalIterator, class Distance>
inline typename Iterator_traits<BidiectionalIterator>::iterator_category
__advance(BidiectionalIterator &i, Distance n,
          bidiectional_iterator_tag) {
    std::cout << "bidrectional tag" << std::endl;
    return bidiectional_iterator_tag();
}

// RandomAccess iterator
template<class RandomAccessIterator, class Distance>
inline typename Iterator_traits<RandomAccessIterator>::iterator_category
__advance(RandomAccessIterator &i, Distance n,
          random_access_iterator_tag) {
    std::cout << "randomaccess tag" << std::endl;
    return random_access_iterator_tag();
}

voidを対応する抽出機に変更するだけです。

最後にテストを修正し、戻り値を追加します：

int main() {
    iterator<input_iterator_tag> input;
    iterator<output_iterator_tag> output;
    iterator<forward_iterator_tag> forward;
    iterator<bidiectional_iterator_tag> bidect;
    iterator<random_access_iterator_tag> random;
    input_iterator_tag inputIteratorTag = advance(input, 10);
    output_iterator_tag outputIteratorTag = advance(output, 10);
    forward_iterator_tag forwardIteratorTag = advance(forward, 10);
    bidiectional_iterator_tag bidiectionalIteratorTag = advance(bidect, 10);
    random_access_iterator_tag randomAccessIteratorTag = advance(random, 10);
    int *p = NULL;
    random_access_iterator_tag v = advance(p, 10);
    return 0;
}

以上で、簡単なイテレータ型のコンパイラによる判別の実装が完了しました。

2.STLソースコード解析：Iterator

bits/stl_iterator_base_types.hでも上述のようになっています（実際、上のものはSTLソースコードの簡単版で、よく似ています）。一緒に見てみましょう。

（1）tag

 ///  Marking input iterators.
  struct input_iterator_tag { };

  ///  Marking output iterators.
  struct output_iterator_tag { };

  /// Forward iterators support a superset of input iterator operations.
  struct forward_iterator_tag : public input_iterator_tag { };

  /// Bidirectional iterators support a superset of forward iterator
  /// operations.
  struct bidirectional_iterator_tag : public forward_iterator_tag { };

  /// Random-access iterators support a superset of bidirectional
  /// iterator operations.
  struct random_access_iterator_tag : public bidirectional_iterator_tag { };

私が上で使ったものと同じです。

（2）iterator_traits抽出機。中には5種類が含まれますが、上ではそのうちの1つ：iterator_categoryしか実装していません。したがってSTLでは、コンテナとアルゴリズムの橋であるiteratorは、次の5つの typedef を含まなければなりません。

template<typename _Iterator>
struct iterator_traits
{
  typedef typename _Iterator::iterator_category iterator_category;
  typedef typename _Iterator::value_type        value_type;
  typedef typename _Iterator::difference_type   difference_type;
  typedef typename _Iterator::pointer           pointer;
  typedef typename _Iterator::reference         reference;
};

（3）iterator

上で触れたclass typeは下のものの簡単版です。比較してみると、違いはなく、テンプレートパラメータが増え、typedefが増えただけです。

template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
       typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
  /// One of the @link iterator_tags tag types@endlink.
  typedef _Category  iterator_category;
  /// The type "pointed to" by the iterator.
  typedef _Tp        value_type;
  /// Distance between iterators is represented as this type.
  typedef _Distance  difference_type;
  /// This type represents a pointer-to-value_type.
  typedef _Pointer   pointer;
  /// This type represents a reference-to-value_type.
  typedef _Reference reference;
};

以上で、iteratorとtraitsの特性の分析は終わりです。STLソースコードの奥義を一緒に探求しましょう。侯捷先生が言うように：ソースコードの前には秘密はない。

関連トピック

コメント