C++イテレーターの仕組みと使い方

イテレーターが最も便利なのはアルゴリズムライブラリとの連携です。この仕組みを活用することで、アルゴリズムの実装に焦点を当てることができ、データ構造の詳細を気にする必要がありません。

イテレーターの基本的な使い方

例えば、std::copy_nは範囲内の要素をコピーするためのアルゴリズムです。この関数はさまざまなコンテナに対応しており、back_inserterやfront_inserterなどの上位イテレーターを使用することも可能です。

// std::vectorのコピー
std::vector<int> a1{2, 1, 3, 4};

std::vector<int> a2(a1.size() / 2);                 // 初期サイズは2
std::copy_n(a1.cbegin(), a1.size() / 2, a2.begin()); // a2には2,1がコピーされる

std::vector<int> a3;                                             // 初期サイズ0
std::copy_n(a1.cbegin(), a1.size() / 2, std::back_inserter(a3)); // a3には2,1がコピーされる

// std::list
std::list<int> lst1{12, 11, 13, 14};
std::list<int> lst2;
std::copy_n(lst1.cbegin(), lst1.size() / 2, std::back_inserter(lst2)); // lst2には12,11がコピーされる

// std::vector -> std::list
std::list<int> lst3;
std::copy_n(a1.cbegin(), a1.size() / 2, std::back_inserter(lst3)); // lst3には2,1がコピーされる

// std::list -> std::vector
std::vector<int> a4;
std::copy_n(lst1.cbegin(), lst1.size() / 2, std::back_inserter(a4)); // a4には12,11がコピーされる

要素のコピーは単純なmemcpyではなく、深コピーの可能性もあります。他の言語（例えばGo）では、標準ライブラリのアルゴリズムが限られているため、このような統一されたインターフェースがありません。

イテレーターの設計

STLのstd::copy関数の実装（GCC12の例）を見ると、イテレーターの設計思想が分かります。

template <bool _IsMove, bool _IsSimple, typename _Category>
struct __copy_move {
    template <typename _II, typename _OI>
    _GLIBCXX20_CONSTEXPR
    static _OI __copy_m(_II __first, _II __last, _OI __result) {
        for (; __first != __last; ++__result, (void)++__first)
            *__result = *__first;
        return __result;
    }
};

この実装で使用されている演算子は次の通りです。

• 同値演算子：`!=`、`==`、`<`、`<=`、`>`、`>=`
• インクリメント/デクリメント：`++`、`--`、`++(int)`、`--(int)`
• 要素へのアクセス：`*`、`->`

イテレーターは基本的にクラスとして設計されます。コンテナごとに異なるイテレーターを定義し、iterator_traitsを介して共通のインターフェースを提供します。

コンテナ固有のイテレーター

各コンテナのイテレーターは以下のようになっています。

• std::vector：`__normal_iterator`
• std::list：`_List_iterator`
• std::map：`_Rb_tree_iterator`

例えば、std::vectorのイテレーターは指针をラップしています。

reference operator*() const noexcept { return *_M_current; }

__normal_iterator &operator++() noexcept {
    ++_M_current;
    return *this;
}

std::listのイテレーターはリンクリストのノードを指针として管理しています。

reference operator*() const noexcept { return *static_cast<_Node *>(_M_node)->_M_valptr(); }

_Self &operator++() noexcept {
    _M_node = _M_node->_M_next;
    return *this;
}

std::mapのイテレーターは赤黒木のノードを指针として管理しています。

reference operator*() const noexcept {
    return *static_cast<_Link_type>(_M_node)->_M_valptr();
}

_Self &operator++() noexcept {
    _M_node = _Rb_tree_increment(_M_node);
    return *this;
}

イテレーターの実装と特徴

iterator_traitsはイテレーターの特性を定義します。例えば、std::vectorのイテレーターは次の特性を持ちます。

template <typename _Iterator>
struct __iterator_traits<
    _Iterator, __void_t<typename _Iterator::iterator_category,
                        typename _Iterator::value_type,
                        typename _Iterator::difference_type,
                        typename _Iterator::pointer,
                        typename _Iterator::reference>> {
    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;
};

template <typename _Iterator>
struct iterator_traits : public __iterator_traits<_Iterator> {};

この仕組みは、std::vectorやstd::mapなどのコンテナのイテレーターを統一的に扱うことを可能にします。

イテレーターの種類

イテレーターは大きく以下の種類に分かれます。

• reverse_iterator：コンテナを逆順にイテレートします。
• back_inserter：コンテナの末尾に要素を追加します。
• front_inserter：コンテナの先頭に要素を追加します。
• inserter：指定された位置に要素を挿入します。

イテレーターの有効性問題

イテレーターが無効になる場合として、コンテナの要素を削除する場合があります。

std::vectorの削除操作は以下のように実装されています。

template <typename _Alloc>
typename vector::iterator vector::_M_erase(
    iterator __position) {
    if (__position + 1 != end())
        std::copy(__position + 1, end(), __position);
    --this->_M_impl._M_finish;
    return __position;
}

std::listの削除操作は以下のように実装されています。

void _M_erase(iterator __position) noexcept {
    this->_M_dec_size(1);
    __position._M_node->_M_unhook();
    _Node *__n = static_cast<_Node *>(__position._M_node);
    _Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());
    _M_put_node(__n);
}

template <typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __position) noexcept {
    iterator __ret = iterator(__position._M_node->_M_next);
    _M_erase(__position._M_const_cast());
    return __ret;
}

std::mapの削除操作は以下のように実装されています。

iterator erase(iterator __position) {
    do {
        if (std::__is_constant_evaluated() &&
            !bool(__position != end()))
            __builtin_unreachable();
    } while (false);
    iterator __result = __position;
    ++__result;
    _M_erase_aux(__position);
    return __result;
}

削除後のイテレーターの有効性はコンテナの種類によって異なります。

• std::vector：要素削除後にイテレーターが指针する位置が変化します。
• std::list：削除された要素の指针は無効になります。
• std::map：削除された要素の指针は無効になります。

削除後のイテレーターを安全に使用するには、削除後の状態を管理する必要があります。例えば、std::mapの削除後のイテレーターは以下のように管理します。

std::map m1{{"lebron", 6}, {"tom", 2}, {"haha", 3}};
for (auto it = m1.begin(); it != m1.end();) {
    // 削除後のイテレーターを管理
    it = m1.erase(it);
}

以上の仕組みを活用することで、STLのアルゴリズムを柔軟に使用することができます。