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

240

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

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

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

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

ereOn
источник
Шаблон Итератора GoF вообще рассматривается?
DumbCoder
3
@DumbCoder: В C ++ часто желательно иметь итераторы, совместимые с STL, поскольку они будут прекрасно работать со всеми существующими контейнерами и алгоритмами, предоставляемыми STL. Хотя концепция похожа, есть некоторые отличия от схемы, предложенной GoF.
Бьорн Поллекс
Я разместил образец пользовательского итератора здесь
Valdemar_Rudolfovich
1
Сложность этих ответов говорит о том, что C ++ является либо языком, не достойным чего-либо, кроме домашних заданий для старшекурсников, либо ответы слишком сложны и неправильны. Должен быть более простой способ в Cpp? Как и CMake и Automake до его создания, сырой C, выпаренный из прототипа python, кажется намного проще, чем этот.
Кристофер

Ответы:

157
  • Выберите тип итератора, который подходит вашему контейнеру: ввод, вывод, пересылка и т. Д.
  • Используйте базовые классы итераторов из стандартной библиотеки. Например, 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определения типов: это типы для ваших неконстантных и константных итераторов.

Смотрите также: ссылка на стандартную библиотеку

РЕДАКТИРОВАТЬ: std::iterator устарела с C ++ 17. Смотрите соответствующую дискуссию здесь .

Андрей
источник
8
@Potatoswatter: не понизили это, но, эй, random_access_iteratorне в стандарте, и ответ не обрабатывает преобразование изменяемого в const. Вы, вероятно, хотите наследовать, например, std::iterator<random_access_iterator_tag, value_type, ... optional arguments ...>хотя.
Яков Галка
2
Да, я не совсем уверен, как это работает. Если у меня есть метод RefType operator*() { ... }, я на шаг ближе - но это не помогает, потому что мне все еще нужно RefType operator*() const { ... }.
Autumnsault
20
std::iterator устарел
diapir
5
Если это устарело, каков правильный «новый» способ сделать это?
SasQ
56

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

Вы можете найти его на Github

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

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

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

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

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

  1. //-------------------------------------------------------------------
    // Raw iterator with random access
    //-------------------------------------------------------------------
    template<typename blDataType>
    class blRawIterator
    {
    public:
    
        using iterator_category = std::random_access_iterator_tag;
        using value_type = blDataType;
        using difference_type = std::ptrdiff_t;
        using pointer = blDataType*;
        using reference = 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 difference_type& movement){m_ptr += movement;return (*this);}
        blRawIterator<blDataType>&                  operator-=(const difference_type& movement){m_ptr -= movement;return (*this);}
        blRawIterator<blDataType>&                  operator++(){++m_ptr;return (*this);}
        blRawIterator<blDataType>&                  operator--(){--m_ptr;return (*this);}
        blRawIterator<blDataType>                   operator++(int){auto temp(*this);++m_ptr;return temp;}
        blRawIterator<blDataType>                   operator--(int){auto temp(*this);--m_ptr;return temp;}
        blRawIterator<blDataType>                   operator+(const difference_type& movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
        blRawIterator<blDataType>                   operator-(const difference_type& movement){auto oldPtr = m_ptr;m_ptr-=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
    
        difference_type                             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 difference_type& movement){this->m_ptr -= movement;return (*this);}
        blRawReverseIterator<blDataType>&           operator-=(const difference_type& 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++(int){auto temp(*this);--this->m_ptr;return temp;}
        blRawReverseIterator<blDataType>            operator--(int){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;}
    
        difference_type                             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]);}

                            .
                            .
                            .
    // This is the pointer to the
    // beginning of the data
    // This allows the container
    // to either "view" data owned
    // by other containers or to
    // own its own data
    // You would implement a "create"
    // method for owning the data
    // and a "wrap" method for viewing
    // data owned by other containers

    blDataType*                                    m_data;
};
Энцо
источник
Я думаю, что оператор + и оператор- могут выполнять операции задом наперед. Похоже, оператор + вычитает движение из указателя, не добавляя, а оператор добавляет его. Это кажется задом наперед
пляже
Это для обратного итератора, оператор + должен идти назад, а оператор - должен идти вперед
Энцо
2
Потрясающие. Принятый ответ слишком высокого уровня. Это круто. Спасибо Энзо.
FernandoZ
Вам нужно отредактировать свой ответ. Предполагая, что m_data был выделен с элементами m_size, вы получаете Undefined Behavior: m_data[m_size]is UB. Вы можете просто исправить это, заменив его на m_data+m_size. Для обратных итераторов оба m_data[-1]и m_data-1неверны (UB). Для исправления reverse_iterators вам нужно будет использовать «трюки с указателями на следующий элемент».
Арно
Арно, я просто добавил член-указатель в пользовательский контейнерный класс, который лучше показывает, что я имел в виду.
Энцо
24

Они часто забывают, что 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это преобразование никогда не используется.

Максим Егорушкин
источник
На самом деле, вы также можете сделать это наоборот, определив конструктор копирования, который является шаблоном, он не скомпилируется, если вы попытаетесь привести базовый тип constк non- const.
Матье М.
Разве вы не в конечном итоге с инвалидом IntrusiveSlistIterator<T const, void>::operator IntrusiveSlistIterator<T const, void>() const?
Potatoswatter
Ах, это действительно так, но Comeau предупреждает, и я подозреваю, что и многие другие тоже. enable_ifМожет исправить это, но ...
Potatoswatter
Я не стал беспокоиться о enable_if, потому что компилятор все равно его отключил, хотя некоторые компиляторы выдают предупреждение (g ++, будучи хорошим парнем, не предупреждает).
Максим Егорушкин
1
@Matthieu: Если использовать шаблонный конструктор, то при преобразовании const_iterator в итератор компилятор выдает ошибку внутри конструктора, из-за чего пользователь в замешательстве почесывает голову и произносит полный текст. С оператором преобразования, который я разместил, компилятор просто говорит, что нет подходящего преобразования из const_iterator в итератор, что, IMO, более понятно.
Максим Егорушкин
23

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его.

Матье М.
источник
Можете ли вы объяснить смысл этого комментария? // a private type avoids misuse
Кевинарпе
@kevinarpe: enablerникогда не предназначался для того, чтобы вызывающий был провайдером, поэтому я предполагаю, что они делают его приватным, чтобы избежать случайных попыток его пропустить. Я не думаю, что это может создать какую-либо проблему для фактической передачи, поскольку защита заключается в enable_if.
Матье М.
16

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

Мой предпочтительный шаблон прост: возьмите аргумент шаблона, равный value_type, либо 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;
Potatoswatter
источник
Примечание: похоже, что ваши преобразования iterator-> const_iterator и обратно не работают.
Максим Егорушкин
@ Максим: Да, я не могу найти примеры использования моей техники: vP. Я не уверен, что вы имеете в виду, что преобразования нарушены, поскольку я просто не иллюстрировал их, но может быть проблема с доступом curиз итератора противоположной константности. Решение, которое приходит на ум friend my_container::const_iterator; friend my_container::iterator;, таково, но я не думаю, что именно так я и делал раньше ... в любом случае, этот общий план работает.
Potatoswatter
1
* сделать это friend classв обоих случаях.
Potatoswatter
Прошло некоторое время, но сейчас я вспоминаю, что преобразования должны быть основаны (SFINAE) на правильности инициализации базовых элементов. Это следует за SCARY (но этот пост предшествует этой терминологии).
Potatoswatter
13

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

Чтобы добавить итератор в ваш класс, необходимо написать небольшой класс для представления состояния итератора с 7 небольшими функциями, из которых 2 являются необязательными:

#include <iostream>
#include <vector>
#include "iterator_tpl.h"

struct myClass {
  std::vector<float> vec;

  // Add some sane typedefs for STL compliance:
  STL_TYPEDEFS(float);

  struct it_state {
    int pos;
    inline void begin(const myClass* ref) { pos = 0; }
    inline void next(const myClass* ref) { ++pos; }
    inline void end(const myClass* ref) { pos = ref->vec.size(); }
    inline float& get(myClass* ref) { return ref->vec[pos]; }
    inline bool cmp(const it_state& s) const { return pos != s.pos; }

    // Optional to allow operator--() and reverse iterators:
    inline void prev(const myClass* ref) { --pos; }
    // Optional to allow `const_iterator`:
    inline const float& get(const myClass* ref) const { return ref->vec[pos]; }
  };
  // Declare typedef ... iterator;, begin() and end() functions:
  SETUP_ITERATORS(myClass, float&, it_state);
  // Declare typedef ... reverse_iterator;, rbegin() and rend() functions:
  SETUP_REVERSE_ITERATORS(myClass, float&, it_state);
};

Затем вы можете использовать его так, как вы ожидаете от итератора STL:

int main() {
  myClass c1;
  c1.vec.push_back(1.0);
  c1.vec.push_back(2.0);
  c1.vec.push_back(3.0);

  std::cout << "iterator:" << std::endl;
  for (float& val : c1) {
    std::cout << val << " "; // 1.0 2.0 3.0
  }

  std::cout << "reverse iterator:" << std::endl;
  for (auto it = c1.rbegin(); it != c1.rend(); ++it) {
    std::cout << *it << " "; // 3.0 2.0 1.0
  }
}

Я надеюсь, что это помогает.

VinGarcia
источник
1
Этот файл шаблона решил все мои проблемы с итератором!
Perrykipkerrie