第5章：イテレータとユーティリティ

はじめに

イテレータはSTLの中核概念です。本章では、iterator_traits、reverse_iterator、そして各種ユーティリティを学びます。

---

1. iterator_traits

1.1 なぜtraitsが必要か

テンプレートでイテレータを扱う際、その型情報が必要になります：

template<typename Iterator>
void algorithm(Iterator first, Iterator last) {
    // Iteratorが指す型は？
    // difference_typeは？
    // イテレータカテゴリは？
}

1.2 実装

namespace ft {

// プライマリテンプレート（クラスイテレータ用）
template<typename Iterator>
struct iterator_traits {
    typedef typename Iterator::difference_type   difference_type;
    typedef typename Iterator::value_type        value_type;
    typedef typename Iterator::pointer           pointer;
    typedef typename Iterator::reference         reference;
    typedef typename Iterator::iterator_category iterator_category;
};

// ポインタの特殊化
template<typename T>
struct iterator_traits<T*> {
    typedef ptrdiff_t                       difference_type;
    typedef T                               value_type;
    typedef T*                              pointer;
    typedef T&                              reference;
    typedef std::random_access_iterator_tag iterator_category;
};

// constポインタの特殊化
template<typename T>
struct iterator_traits<const T*> {
    typedef ptrdiff_t                       difference_type;
    typedef T                               value_type;
    typedef const T*                        pointer;
    typedef const T&                        reference;
    typedef std::random_access_iterator_tag iterator_category;
};

} // namespace ft

1.3 使用例

template<typename Iterator>
typename ft::iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last) {
    typedef typename ft::iterator_traits<Iterator>::iterator_category category;
    return _distance_impl(first, last, category());
}

// RandomAccessIterator用（O(1)）
template<typename Iterator>
typename ft::iterator_traits<Iterator>::difference_type
_distance_impl(Iterator first, Iterator last,
               std::random_access_iterator_tag) {
    return last - first;
}

// InputIterator用（O(n)）
template<typename Iterator>
typename ft::iterator_traits<Iterator>::difference_type
_distance_impl(Iterator first, Iterator last,
               std::input_iterator_tag) {
    typename ft::iterator_traits<Iterator>::difference_type n = 0;
    while (first != last) {
        ++first;
        ++n;
    }
    return n;
}

---

2. reverse_iterator

2.1 概念

reverse_iteratorは、イテレータを逆順に走査します：

通常のイテレータ:
[1] → [2] → [3] → [4] → end

reverse_iterator:
rbegin ← [4] ← [3] ← [2] ← [1] ← rend

注意: rbegin() は end() の位置を指し、
      *rbegin() は最後の要素を返す

2.2 実装

namespace ft {

template<typename Iterator>
class reverse_iterator {
public:
    typedef Iterator                                              iterator_type;
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    typedef typename iterator_traits<Iterator>::value_type        value_type;
    typedef typename iterator_traits<Iterator>::difference_type   difference_type;
    typedef typename iterator_traits<Iterator>::pointer           pointer;
    typedef typename iterator_traits<Iterator>::reference         reference;

protected:
    Iterator current;

public:
    // コンストラクタ
    reverse_iterator() : current() {}

    explicit reverse_iterator(iterator_type x) : current(x) {}

    template<typename Iter>
    reverse_iterator(const reverse_iterator<Iter>& other)
        : current(other.base()) {}

    // 基底イテレータを取得
    iterator_type base() const {
        return current;
    }

    // 間接参照（1つ前の要素を返す）
    reference operator*() const {
        Iterator tmp = current;
        return *--tmp;
    }

    pointer operator->() const {
        return &(operator*());
    }

    // インクリメント（基底イテレータをデクリメント）
    reverse_iterator& operator++() {
        --current;
        return *this;
    }

    reverse_iterator operator++(int) {
        reverse_iterator tmp = *this;
        --current;
        return tmp;
    }

    // デクリメント（基底イテレータをインクリメント）
    reverse_iterator& operator--() {
        ++current;
        return *this;
    }

    reverse_iterator operator--(int) {
        reverse_iterator tmp = *this;
        ++current;
        return tmp;
    }

    // ランダムアクセス
    reverse_iterator operator+(difference_type n) const {
        return reverse_iterator(current - n);
    }

    reverse_iterator& operator+=(difference_type n) {
        current -= n;
        return *this;
    }

    reverse_iterator operator-(difference_type n) const {
        return reverse_iterator(current + n);
    }

    reverse_iterator& operator-=(difference_type n) {
        current += n;
        return *this;
    }

    reference operator[](difference_type n) const {
        return *(*this + n);
    }
};

// 比較演算子
template<typename Iterator1, typename Iterator2>
bool operator==(const reverse_iterator<Iterator1>& lhs,
                const reverse_iterator<Iterator2>& rhs) {
    return lhs.base() == rhs.base();
}

template<typename Iterator1, typename Iterator2>
bool operator!=(const reverse_iterator<Iterator1>& lhs,
                const reverse_iterator<Iterator2>& rhs) {
    return lhs.base() != rhs.base();
}

template<typename Iterator1, typename Iterator2>
bool operator<(const reverse_iterator<Iterator1>& lhs,
               const reverse_iterator<Iterator2>& rhs) {
    return lhs.base() > rhs.base();  // 逆順なので逆の比較
}

// ... 他の比較演算子 ...

// 算術演算子
template<typename Iterator>
reverse_iterator<Iterator>
operator+(typename reverse_iterator<Iterator>::difference_type n,
          const reverse_iterator<Iterator>& it) {
    return reverse_iterator<Iterator>(it.base() - n);
}

template<typename Iterator1, typename Iterator2>
typename reverse_iterator<Iterator1>::difference_type
operator-(const reverse_iterator<Iterator1>& lhs,
          const reverse_iterator<Iterator2>& rhs) {
    return rhs.base() - lhs.base();
}

} // namespace ft

---

3. enable_if

3.1 SFINAEとは

SFINAE = "Substitution Failure Is Not An Error"

テンプレート引数の置換に失敗しても、コンパイルエラーにならず、そのオーバーロード候補から除外されます。

3.2 実装

namespace ft {

// プライマリテンプレート（条件がfalseの場合）
template<bool Cond, typename T = void>
struct enable_if {};

// 特殊化（条件がtrueの場合）
template<typename T>
struct enable_if<true, T> {
    typedef T type;
};

} // namespace ft

3.3 使用例

// 整数型の場合のみ有効な関数
template<typename T>
typename ft::enable_if<ft::is_integral<T>::value, bool>::type
is_odd(T val) {
    return val % 2 == 1;
}

// vectorのrangeコンストラクタで使用
template<typename T, typename Alloc>
template<typename InputIterator>
vector<T, Alloc>::vector(
    InputIterator first,
    InputIterator last,
    const allocator_type& alloc,
    typename ft::enable_if<!ft::is_integral<InputIterator>::value>::type*
) : _alloc(alloc), _data(NULL), _size(0), _capacity(0) {
    // 本当のイテレータの場合の処理
}

---

4. is_integral

4.1 実装

namespace ft {

// デフォルト（非整数型）
template<typename T>
struct is_integral {
    static const bool value = false;
    typedef bool value_type;
    typedef is_integral type;
};

// 各整数型の特殊化
template<> struct is_integral<bool>               { static const bool value = true; };
template<> struct is_integral<char>               { static const bool value = true; };
template<> struct is_integral<signed char>        { static const bool value = true; };
template<> struct is_integral<unsigned char>      { static const bool value = true; };
template<> struct is_integral<wchar_t>            { static const bool value = true; };
template<> struct is_integral<short>              { static const bool value = true; };
template<> struct is_integral<unsigned short>     { static const bool value = true; };
template<> struct is_integral<int>                { static const bool value = true; };
template<> struct is_integral<unsigned int>       { static const bool value = true; };
template<> struct is_integral<long>               { static const bool value = true; };
template<> struct is_integral<unsigned long>      { static const bool value = true; };
template<> struct is_integral<long long>          { static const bool value = true; };
template<> struct is_integral<unsigned long long> { static const bool value = true; };

// const/volatile修飾子を除去
template<typename T> struct is_integral<const T>
    : is_integral<T> {};
template<typename T> struct is_integral<volatile T>
    : is_integral<T> {};
template<typename T> struct is_integral<const volatile T>
    : is_integral<T> {};

} // namespace ft

---

5. pair と make_pair

5.1 pair

namespace ft {

template<typename T1, typename T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;

    // コンストラクタ
    pair() : first(), second() {}

    pair(const T1& a, const T2& b) : first(a), second(b) {}

    template<typename U1, typename U2>
    pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}

    // 代入演算子
    pair& operator=(const pair& p) {
        first = p.first;
        second = p.second;
        return *this;
    }
};

// 比較演算子
template<typename T1, typename T2>
bool operator==(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return lhs.first == rhs.first && lhs.second == rhs.second;
}

template<typename T1, typename T2>
bool operator!=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return !(lhs == rhs);
}

template<typename T1, typename T2>
bool operator<(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return lhs.first < rhs.first ||
           (!(rhs.first < lhs.first) && lhs.second < rhs.second);
}

template<typename T1, typename T2>
bool operator<=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return !(rhs < lhs);
}

template<typename T1, typename T2>
bool operator>(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return rhs < lhs;
}

template<typename T1, typename T2>
bool operator>=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return !(lhs < rhs);
}

} // namespace ft

5.2 make_pair

namespace ft {

template<typename T1, typename T2>
pair<T1, T2> make_pair(T1 x, T2 y) {
    return pair<T1, T2>(x, y);
}

} // namespace ft

---

6. equal と lexicographical_compare

6.1 equal

namespace ft {

// バージョン1: デフォルト比較
template<typename InputIterator1, typename InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2) {
    while (first1 != last1) {
        if (!(*first1 == *first2))
            return false;
        ++first1;
        ++first2;
    }
    return true;
}

// バージョン2: カスタム比較関数
template<typename InputIterator1, typename InputIterator2,
         typename BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, BinaryPredicate pred) {
    while (first1 != last1) {
        if (!pred(*first1, *first2))
            return false;
        ++first1;
        ++first2;
    }
    return true;
}

} // namespace ft

6.2 lexicographical_compare

辞書順比較：

namespace ft {

// バージョン1: デフォルト比較
template<typename InputIterator1, typename InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2) {
    while (first1 != last1) {
        if (first2 == last2 || *first2 < *first1)
            return false;
        else if (*first1 < *first2)
            return true;
        ++first1;
        ++first2;
    }
    return first2 != last2;
}

// バージョン2: カスタム比較関数
template<typename InputIterator1, typename InputIterator2, typename Compare>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2,
                             Compare comp) {
    while (first1 != last1) {
        if (first2 == last2 || comp(*first2, *first1))
            return false;
        else if (comp(*first1, *first2))
            return true;
        ++first1;
        ++first2;
    }
    return first2 != last2;
}

} // namespace ft

---

7. イテレータカテゴリ

7.1 カテゴリタグ

// STL標準のタグ（<iterator>で定義）
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 {};

7.2 カテゴリによるディスパッチ

template<typename Iterator>
void advance(Iterator& it,
             typename ft::iterator_traits<Iterator>::difference_type n) {
    typedef typename ft::iterator_traits<Iterator>::iterator_category category;
    _advance_impl(it, n, category());
}

// RandomAccessIterator用
template<typename Iterator>
void _advance_impl(Iterator& it,
                   typename ft::iterator_traits<Iterator>::difference_type n,
                   std::random_access_iterator_tag) {
    it += n;
}

// BidirectionalIterator用
template<typename Iterator>
void _advance_impl(Iterator& it,
                   typename ft::iterator_traits<Iterator>::difference_type n,
                   std::bidirectional_iterator_tag) {
    if (n >= 0) {
        while (n--) ++it;
    } else {
        while (n++) --it;
    }
}

// InputIterator用
template<typename Iterator>
void _advance_impl(Iterator& it,
                   typename ft::iterator_traits<Iterator>::difference_type n,
                   std::input_iterator_tag) {
    while (n--) ++it;
}

---

まとめ

本章で学んだこと：

• iterator_traits: イテレータの型情報を取得
• reverse_iterator: 逆順走査
• enable_if: SFINAEによる条件付きオーバーロード
• is_integral: 整数型判定
• pair/make_pair: 2つの値のペア
• equal/lexicographical_compare: 範囲の比較

次章では、テストと最適化を学びます。