如何爲我的集合類提供類似迭代器的STL？

Question

可能重複：
How to correctly implement custom iterators and const_iterators ?

我真的想提供一個STL迭代器一樣對實體集合類我已經得到了。作爲獎勵，如果迭代器可以輕鬆地重用於其他集合類，那麼我會喜歡它。問題是我曾試圖通過STL進行研究，但對我來說這太複雜了。有關如何做到這一點的任何建議？它不需要像STL迭代器那麼複雜，但是如果我只能說MyCollection::iterator it = o_MyCollection.begin()等等，我會喜歡它。 :)

作爲第二個問題，如果我將它傳遞給像for_each這樣的常用算法，此迭代器的基本要求是什麼？

Answer 1

假設您的集合是一個由整數索引的列表，我在自定義STL集合中使用的這個迭代器類可能會對您有所幫助。它使用curiously recurring template pattern。它不是100％測試，但在我的代碼中工作。

// common_safe_iterator is instantiated to produce both const_iterator and 
// iterator types. It called "safe" because it is not necessarily invalidated 
// by changes to the collection size, and it calls at() on the target 
// collection, which is supposed to throw an exception if the index is 
// out-of-range, instead of calling [] which does not. 
template<class base> 
class common_safe_iterator : public base { 
protected: 
    // base must contain the following 5 typedefs 
    typedef typename base::reference reference; 
    typedef typename base::pointer pointer; 
    typedef typename base::vector_t vector_t; 
    typedef typename base::const_iterator_t const_iterator_t; 
    typedef typename base::iterator_t iterator_t; 
    vector_t* _vec; 
    size_type _pos; 
public: 
    typedef common_safe_iterator<base> self; 
    friend const_iterator_t; 

    common_safe_iterator(vector_t* vec, size_type pos) : _vec(vec), _pos(pos) { } 
    common_safe_iterator(const iterator_t& copy) : _vec(copy._vec), _pos(copy._pos) { } 

    reference operator*() const { return _vec->at(_pos); } 
    pointer operator->() const { return &_vec->at(_pos); } 

    self& operator++() // prefix ++ 
     { ++_pos; return *this; } 
    self& operator--() // prefix -- 
     { --_pos; return *this; } 
    self& operator+=(int amt) 
     { _pos += amt; return *this; } 
    bool operator==(const self& x) const 
     { return (x._vec == _vec) && (x._pos == _pos); } 
    int operator-(const self& base) const 
     { assert(base._vec == _vec); return _pos - base._pos; } 
    // Returns true if the iterator can be dereferenced 
    bool is_valid() const 
     { return _vec != NULL && _pos < _vec->size(); } 

    ///////////////////////////////////////////////////////// 
    // Operators that are defined in terms of other operators 

    self operator++(int) // postfix ++ 
    { 
     self tmp = *this; // copy ourselves 
     ++*this; 
     return tmp; 
    } 
    self operator--(int) // postfix -- 
    { 
     self tmp = *this; // copy ourselves 
     --*this; 
     return tmp; 
    } 
    self& operator-=(int amt) 
    { 
     return *this += -amt; 
    } 
    bool operator!=(const self& x) const 
    { 
     return !(*this == x); 
    } 
    bool operator>(const self& x) const 
    { 
     return *this - x > 0; 
    } 
    bool operator>=(const self& x) const 
    { 
     return *this - x >= 0; 
    } 
    bool operator<(const self& x) const 
    { 
     return *this - x < 0; 
    } 
    bool operator<=(const self& x) const 
    { 
     return *this - x <= 0; 
    } 
    self operator+(int amt) const 
    { 
     self tmp = *this; 
     return tmp += amt; 
    } 
    self operator-(int amt) const 
    { 
     self tmp = *this; 
     return tmp -= amt; 
    } 
    reference operator[](int index) const 
    { 
     self tmp = *this; 
     tmp += index; 
     return *tmp; 
    } 
}; 

STL期望您提供「const_iterator」和非const「迭代器」類。要做到這一點，編寫兩個基類，每個基類有5個typedefs。我的集合類被命名爲mini_vector_t，所以我用下面的基類：

/// iterator and const_iterator differ only in these typedefs. 
/// const_iterator_base is the base class of const_iterator, while 
/// iterator_base is the base class of iterator; both iterator and 
/// const_iterator are typedefs of common_safe_iterator. 
struct iterator_base; 
struct const_iterator_base 
{ 
    typedef const typename mini_vector_t::value_type& reference; 
    typedef const typename mini_vector_t::value_type* pointer; 
    typedef const mini_vector_t vector_t; 
    typedef common_safe_iterator<const_iterator_base> const_iterator_t; 
    typedef common_safe_iterator<iterator_base> iterator_t; 
}; 
struct iterator_base 
{ 
    typedef typename mini_vector_t::value_type& reference; 
    typedef typename mini_vector_t::value_type* pointer; 
    typedef mini_vector_t vector_t; 
    typedef common_safe_iterator<const_iterator_base> const_iterator_t; 
    typedef common_safe_iterator<iterator_base> iterator_t; 
}; 

最後，你的收藏必須包含常量性和迭代器類型定義：

typedef common_safe_iterator<const_iterator_base> const_iterator; 
typedef common_safe_iterator<iterator_base> iterator; 

如果您的集合包裝了一個數組，然後這一切更簡單的選擇是使用T *作爲你的迭代器類型，和const T *作爲您的const_iterator類型：

typedef T* iterator; 
typedef const T* const_iterator; 

記住，STL被設計成點ers本身就是迭代器。

我想你應該做一些額外的事情來聲明你的迭代器是「隨機訪問」，但我不知道是什麼。