c++ мета - Как правильно реализовать пользовательские итераторы и const_iterators?





тег теги (6)


Я не знаю, поможет ли Boost что-нибудь, что поможет.

Мой предпочтительный шаблон прост: возьмите аргумент шаблона, который равен value_type , либо const, либо const. При необходимости, также тип узла. Тогда все хорошо.

Просто не забудьте параметризовать (template-ize) все, что должно быть, включая конструктор копирования и operator== . По большей части семантика const будет создавать правильное поведение.

template< class ValueType, class NodeType >
struct my_iterator
 : std::iterator< std::bidirectional_iterator_tag, T > {
    ValueType &operator*() { return cur->payload; }

    template< class VT2, class NT2 >
    friend bool operator==
        ( my_iterator const &lhs, my_iterator< VT2, NT2 > const &rhs );

    // etc.

private:
    NodeType *cur;

    friend class my_container;
    my_iterator( NodeType * ); // private constructor for begin, end
};

typedef my_iterator< T, my_node< T > > iterator;
typedef my_iterator< T const, my_node< T > const > const_iterator;

У меня есть собственный контейнерный класс, для которого я бы хотел написать классы iterator и const_iterator .

Я никогда не делал этого раньше, и мне не удалось найти подходящую методику. Каковы руководящие принципы создания итератора, и о чем я должен знать?

Я также хотел бы избежать дублирования кода (я чувствую, что const_iterator и iterator разделяют много вещей, должен ли один подкласс другой?).

Нога: я уверен, что Boost может что-то облегчить, но я не могу использовать его здесь, по многим глупым причинам.




Они часто забывают, что iterator должен преобразовать в const_iterator но не наоборот. Вот как это сделать:

template<class T, class Tag = void>
class IntrusiveSlistIterator
   : public std::iterator<std::forward_iterator_tag, T>
{
    typedef SlistNode<Tag> Node;
    Node* node_;

public:
    IntrusiveSlistIterator(Node* node);

    T& operator*() const;
    T* operator->() const;

    IntrusiveSlistIterator& operator++();
    IntrusiveSlistIterator operator++(int);

    friend bool operator==(IntrusiveSlistIterator a, IntrusiveSlistIterator b);
    friend bool operator!=(IntrusiveSlistIterator a, IntrusiveSlistIterator b);

    // one way conversion: iterator -> const_iterator
    operator IntrusiveSlistIterator<T const, Tag>() const;
};

В приведенном выше уведомлении, как IntrusiveSlistIterator<T> преобразуется в IntrusiveSlistIterator<T const> . Если T уже const это преобразование никогда не используется.




  • Выберите тип итератора, который подходит вашему контейнеру: ввод, вывод, пересылка и т. Д.
  • Используйте базовые классы итераторов из стандартной библиотеки. Например, std::iterator с random_access_iterator_tag Эти базовые классы определяют все определения типов, требуемые STL, и выполняют другую работу.
  • Чтобы избежать дублирования кода, класс итератора должен быть классом шаблона и параметризоваться «тип значения», «тип указателя», «тип ссылки» или все из них (зависит от реализации). Например:

    // iterator class is parametrized by pointer type
    template <typename PointerType> class MyIterator {
        // iterator class definition goes here
    };
    
    typedef MyIterator<int*> iterator_type;
    typedef MyIterator<const int*> const_iterator_type;
    

    Обратите внимание на определения типа iterator_type и const_iterator_type : они являются типами ваших неконстантных и константных итераторов.

См. Также: стандартная библиографическая ссылка




Я расскажу вам, как вы можете легко определить итераторы для своих пользовательских контейнеров, но на всякий случай я создал библиотеку c ++ 11, которая позволяет вам легко создавать пользовательские итераторы с настраиваемым поведением для любого типа контейнера, смежных или без constiguous.

Вы можете найти его на github по адресу https://github.com/navyenzo/blIteratorAPI

Ниже приведены простые шаги по созданию и использованию пользовательских итераторов:

  1. Создайте свой «пользовательский итератор».
  2. Определите typedefs в классе «пользовательский контейнер».
    • Например: typedef blRawIterator< Type > iterator;
    • Например: typedef blRawIterator< const Type > const_iterator;
  3. Определить функции «начать» «конец»
    • Для ex: iterator begin(){return iterator(&m_data[0]);};
    • Для ex: const_iterator cbegin()const{return const_iterator(&m_data[0]);};
  4. Были сделаны!!!

Наконец, чтобы определить наши пользовательские классы итераторов:

ПРИМЕЧАНИЕ. При определении пользовательских итераторов мы выводим из стандартных категорий итераторов, чтобы алгоритмы STL знали тип итератора, который мы создали

В этом примере я определяю итератор случайного доступа и обратный итератор случайного доступа:

1.

//-------------------------------------------------------------------
// Raw iterator with random access
//-------------------------------------------------------------------
template<typename blDataType>
class blRawIterator : public std::iterator<std::random_access_iterator_tag,
                                           blDataType,
                                           ptrdiff_t,
                                           blDataType*,
                                           blDataType&>
{
public:

    blRawIterator(blDataType* ptr = nullptr){m_ptr = ptr;}
    blRawIterator(const blRawIterator<blDataType>& rawIterator) = default;
    ~blRawIterator(){}

    blRawIterator<blDataType>&                  operator=(const blRawIterator<blDataType>& rawIterator) = default;
    blRawIterator<blDataType>&                  operator=(blDataType* ptr){m_ptr = ptr;return (*this);}

    operator                                    bool()const
    {
        if(m_ptr)
            return true;
        else
            return false;
    }

    bool                                        operator==(const blRawIterator<blDataType>& rawIterator)const{return (m_ptr == rawIterator.getConstPtr());}
    bool                                        operator!=(const blRawIterator<blDataType>& rawIterator)const{return (m_ptr != rawIterator.getConstPtr());}

    blRawIterator<blDataType>&                  operator+=(const ptrdiff_t& movement){m_ptr += movement;return (*this);}
    blRawIterator<blDataType>&                  operator-=(const ptrdiff_t& movement){m_ptr -= movement;return (*this);}
    blRawIterator<blDataType>&                  operator++(){++m_ptr;return (*this);}
    blRawIterator<blDataType>&                  operator--(){--m_ptr;return (*this);}
    blRawIterator<blDataType>                   operator++(ptrdiff_t){auto temp(*this);++m_ptr;return temp;}
    blRawIterator<blDataType>                   operator--(ptrdiff_t){auto temp(*this);--m_ptr;return temp;}
    blRawIterator<blDataType>                   operator+(const ptrdiff_t& movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
    blRawIterator<blDataType>                   operator-(const ptrdiff_t& movement){auto oldPtr = m_ptr;m_ptr-=movement;auto temp(*this);m_ptr = oldPtr;return temp;}

    ptrdiff_t                                   operator-(const blRawIterator<blDataType>& rawIterator){return std::distance(rawIterator.getPtr(),this->getPtr());}

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

    blDataType*                                 getPtr()const{return m_ptr;}
    const blDataType*                           getConstPtr()const{return m_ptr;}

protected:

    blDataType*                                 m_ptr;
};
//-------------------------------------------------------------------

2.

//-------------------------------------------------------------------
// Raw reverse iterator with random access
//-------------------------------------------------------------------
template<typename blDataType>
class blRawReverseIterator : public blRawIterator<blDataType>
{
public:

    blRawReverseIterator(blDataType* ptr = nullptr):blRawIterator<blDataType>(ptr){}
    blRawReverseIterator(const blRawIterator<blDataType>& rawIterator){this->m_ptr = rawIterator.getPtr();}
    blRawReverseIterator(const blRawReverseIterator<blDataType>& rawReverseIterator) = default;
    ~blRawReverseIterator(){}

    blRawReverseIterator<blDataType>&           operator=(const blRawReverseIterator<blDataType>& rawReverseIterator) = default;
    blRawReverseIterator<blDataType>&           operator=(const blRawIterator<blDataType>& rawIterator){this->m_ptr = rawIterator.getPtr();return (*this);}
    blRawReverseIterator<blDataType>&           operator=(blDataType* ptr){this->setPtr(ptr);return (*this);}

    blRawReverseIterator<blDataType>&           operator+=(const ptrdiff_t& movement){this->m_ptr -= movement;return (*this);}
    blRawReverseIterator<blDataType>&           operator-=(const ptrdiff_t& movement){this->m_ptr += movement;return (*this);}
    blRawReverseIterator<blDataType>&           operator++(){--this->m_ptr;return (*this);}
    blRawReverseIterator<blDataType>&           operator--(){++this->m_ptr;return (*this);}
    blRawReverseIterator<blDataType>            operator++(ptrdiff_t){auto temp(*this);--this->m_ptr;return temp;}
    blRawReverseIterator<blDataType>            operator--(ptrdiff_t){auto temp(*this);++this->m_ptr;return temp;}
    blRawReverseIterator<blDataType>            operator+(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr-=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;}
    blRawReverseIterator<blDataType>            operator-(const int& movement){auto oldPtr = this->m_ptr;this->m_ptr+=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;}

    ptrdiff_t                                   operator-(const blRawReverseIterator<blDataType>& rawReverseIterator){return std::distance(this->getPtr(),rawReverseIterator.getPtr());}

    blRawIterator<blDataType>                   base(){blRawIterator<blDataType> forwardIterator(this->m_ptr); ++forwardIterator; return forwardIterator;}
};
//-------------------------------------------------------------------

Теперь где-то в вашем пользовательском классе контейнера:

template<typename blDataType>
class blCustomContainer
{
public: // The typedefs

    typedef blRawIterator<blDataType>              iterator;
    typedef blRawIterator<const blDataType>        const_iterator;

    typedef blRawReverseIterator<blDataType>       reverse_iterator;
    typedef blRawReverseIterator<const blDataType> const_reverse_iterator;

                            .
                            .
                            .

public:  // The begin/end functions

    iterator                                       begin(){return iterator(&m_data[0]);}
    iterator                                       end(){return iterator(&m_data[m_size]);}

    const_iterator                                 cbegin(){return const_iterator(&m_data[0]);}
    const_iterator                                 cend(){return const_iterator(&m_data[m_size]);}

    reverse_iterator                               rbegin(){return reverse_iterator(&m_data[m_size - 1]);}
    reverse_iterator                               rend(){return reverse_iterator(&m_data[-1]);}

    const_reverse_iterator                         crbegin(){return const_reverse_iterator(&m_data[m_size - 1]);}
    const_reverse_iterator                         crend(){return const_reverse_iterator(&m_data[-1]);}

                            .
                            .
                            .
};

УДАЧИ!!!




У Boost есть что поделать: библиотека Boost.Iterator.

Точнее, эта страница: boost::iterator_adaptor .

Что очень интересно, это пример учебника, который показывает полную реализацию с нуля для настраиваемого типа.

template <class Value>
class node_iter
  : public boost::iterator_adaptor<
        node_iter<Value>                // Derived
      , Value*                          // Base
      , boost::use_default              // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
    >
{
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    node_iter()
      : node_iter::iterator_adaptor_(0) {}

    explicit node_iter(Value* p)
      : node_iter::iterator_adaptor_(p) {}

    // iterator convertible to const_iterator, not vice-versa
    template <class OtherValue>
    node_iter(
        node_iter<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue*,Value*>
          , enabler
        >::type = enabler()
    )
      : node_iter::iterator_adaptor_(other.base()) {}

 private:
    friend class boost::iterator_core_access;
    void increment() { this->base_reference() = this->base()->next(); }
};

Основной момент, как уже упоминалось, заключается в использовании единственной реализации шаблона и ее typedef .




Вот пример исходного итератора указателя.

Вы не должны использовать класс iterator для работы с необработанными указателями!

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <assert.h>

template<typename T>
class ptr_iterator
    : public std::iterator<std::forward_iterator_tag, T>
{
    typedef ptr_iterator<T>  iterator;
    pointer pos_;
public:
    ptr_iterator() : pos_(nullptr) {}
    ptr_iterator(T* v) : pos_(v) {}
    ~ptr_iterator() {}

    iterator  operator++(int) /* postfix */         { return pos_++; }
    iterator& operator++()    /* prefix */          { ++pos_; return *this; }
    reference operator* () const                    { return *pos_; }
    pointer   operator->() const                    { return pos_; }
    iterator  operator+ (difference_type v)   const { return pos_ + v; }
    bool      operator==(const iterator& rhs) const { return pos_ == rhs.pos_; }
    bool      operator!=(const iterator& rhs) const { return pos_ != rhs.pos_; }
};

template<typename T>
ptr_iterator<T> begin(T *val) { return ptr_iterator<T>(val); }


template<typename T, typename Tsize>
ptr_iterator<T> end(T *val, Tsize size) { return ptr_iterator<T>(val) + size; }

Обходное окружение на основе диапазона Raw pointer. Пожалуйста, исправьте меня, если есть лучший способ сделать цикл, основанный на диапазоне, от необработанного указателя.

template<typename T>
class ptr_range
{
    T* begin_;
    T* end_;
public:
    ptr_range(T* ptr, size_t length) : begin_(ptr), end_(ptr + length) { assert(begin_ <= end_); }
    T* begin() const { return begin_; }
    T* end() const { return end_; }
};

template<typename T>
ptr_range<T> range(T* ptr, size_t length) { return ptr_range<T>(ptr, length); }

И простой тест

void DoIteratorTest()
{
    const static size_t size = 10;
    uint8_t *data = new uint8_t[size];
    {
        // Only for iterator test
        uint8_t n = '0';
        auto first = begin(data);
        auto last = end(data, size);
        for (auto it = first; it != last; ++it)
        {
            *it = n++;
        }

        // It's prefer to use the following way:
        for (const auto& n : range(data, size))
        {
            std::cout << " char: " << static_cast<char>(n) << std::endl;
        }
    }
    {
        // Only for iterator test
        ptr_iterator<uint8_t> first(data);
        ptr_iterator<uint8_t> last(first + size);
        std::vector<uint8_t> v1(first, last);

        // It's prefer to use the following way:
        std::vector<uint8_t> v2(data, data + size);
    }
    {
        std::list<std::vector<uint8_t>> queue_;
        queue_.emplace_back(begin(data), end(data, size));
        queue_.emplace_back(data, data + size);
    }
}




c++ iterator const-iterator