Comment fournir des itérateurs STL pour ma classe de collection?

Question

Possible en double:
How to correctly implement custom iterators and const_iterators ?

Je voudrais vraiment vous donner un STL comme itérateur pour une classe de collection d'entités que j'ai. En prime, j'aimerais bien que l'itérateur soit facilement réutilisable pour d'autres classes de collection. Le problème est que j'ai essayé de patauger dans le STL mais c'était trop complexe pour moi. Des conseils sur la façon de faire cela? Il n'a pas besoin d'être aussi complexe que les itérateurs STL, mais j'aimerais bien que je puisse simplement dire MyCollection::iterator it = o_MyCollection.begin() et ainsi de suite. :)

En tant que deuxième question, quelle est l'exigence de base pour cet itérateur si je dois le passer à un algorithme habituel comme for_each?

Answer 1

En supposant que votre collection est une liste indexée par un entier, cette classe d'itérateur que j'utilise dans une collection STL personnalisée peut vous aider. Il utilise le curiously recurring template pattern. Il n'est pas testé à 100% mais fonctionne dans mon code.

// 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 vous attend à fournir à la fois une classe "const_iterator" et un non-const "iterator". Pour ce faire, écrivez deux classes de base avec 5 typedefs chacune. Ma classe de collection est nommée mini_vector_t, donc j'utiliser les classes de base suivantes:

/// 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; 
}; 

Enfin, votre collection doit contenir typedefs pour const_iterator et iterator:

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

Si votre collection encapsule un tableau, alors alternative plus simple à tout cela est d'utiliser T * comme type iterator et const T * comme type de const_iterator:

typedef T* iterator; 
typedef const T* const_iterator; 

Rappelez-vous, la STL est conçu de façon à ce point Ils sont eux-mêmes des itérateurs.

Je pense que vous êtes censé faire quelque chose de plus pour déclarer que vos itérateurs sont "à accès aléatoire", mais je ne sais pas quoi.