C++ 如何正确实现自定义迭代器和 const_iterators？

Question

提问by ereOn

I have a custom container class for which I'd like to write the iteratorand const_iteratorclasses.

我有一个自定义容器类，我想为其编写iterator和const_iterator类。

I never did this before and I failed to find an appropriate how-to. What are the guidelines regarding iterator creation, and what should I be aware of ?

我以前从未这样做过，也没有找到合适的操作方法。关于迭代器创建的指导方针是什么，我应该注意什么？

I'd also like to avoid code duplication (I feel that const_iteratorand iteratorshare many things; should one subclass the other ?).

我还想避免代码重复（我觉得const_iterator并iterator分享了很多东西；应该一个子类化另一个吗？）。

Foot note: I'm pretty sure Boost has something to ease this but I can't use it here, for many stupid reasons.

脚注：我很确定 Boost 有一些东西可以缓解这个问题，但由于许多愚蠢的原因，我不能在这里使用它。

Answer 1

采纳答案by Andrey

Choose type of iterator which fits your container: input, output, forward etc.
Use base iterator classes from standard library. For example, std::iteratorwith random_access_iterator_tag.These base classes define all type definitions required by STL and do other work.
To avoid code duplication iterator class should be a template class and be parametrized by "value type", "pointer type", "reference type" or all of them (depends on implementation). For example:
```
// 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;
```
Notice iterator_typeand const_iterator_typetype definitions: they are types for your non-const and const iterators.

选择适合您的容器的迭代器类型：输入、输出、转发等。
使用标准库中的基迭代器类。例如，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类型定义：它们是非常量和常量迭代器的类型。

回答by Enzo

I'm going to show you how you can easily define iterators for your custom containers, but just in case I have created a c++11 library that allows you to easily create custom iterators with custom behavior for any type of container, contiguous or non-contiguous.

我将向您展示如何轻松地为您的自定义容器定义迭代器，但以防万一我创建了一个 c++11 库，它允许您轻松地为任何类型的容器创建具有自定义行为的自定义迭代器，连续或不连续。

You can find it on Github

你可以在 Github 上找到

Here are the simple steps to creating and using custom iterators:

以下是创建和使用自定义迭代器的简单步骤：

Create your "custom iterator" class.
Define typedefs in your "custom container" class.
- e.g. typedef blRawIterator< Type > iterator;
- e.g. typedef blRawIterator< const Type > const_iterator;
Define "begin" and "end" functions
- e.g. iterator begin(){return iterator(&m_data[0]);};
- e.g. const_iterator cbegin()const{return const_iterator(&m_data[0]);};
We're Done!!!

创建您的“自定义迭代器”类。
在“自定义容器”类中定义 typedef。
- 例如 typedef blRawIterator< Type > iterator;
- 例如 typedef blRawIterator< const Type > const_iterator;
定义“开始”和“结束”函数
- 例如 iterator begin(){return iterator(&m_data[0]);};
- 例如 const_iterator cbegin()const{return const_iterator(&m_data[0]);};
我们完成了！！！

Finally, onto defining our custom iterator classes:

最后，定义我们的自定义迭代器类：

NOTE:When defining custom iterators, we derive from the standard iterator categories to let STL algorithms know the type of iterator we've made.

注意：在定义自定义迭代器时，我们从标准迭代器类别派生，让 STL 算法知道我们创建的迭代器的类型。

In this example, I define a random access iterator and a reverse random access iterator:

在这个例子中，我定义了一个随机访问迭代器和一个反向随机访问迭代器：

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

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

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

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

Now somewhere in your custom container class:

现在在您的自定义容器类中的某处：

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

Answer 3

回答by Maxim Egorushkin

They often forget that iteratormust convert to const_iteratorbut not the other way around. Here is a way to do that:

他们经常忘记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;
};

In the above notice how IntrusiveSlistIterator<T>converts to IntrusiveSlistIterator<T const>. If Tis already constthis conversion never gets used.

在上面注意如何IntrusiveSlistIterator<T>转换为IntrusiveSlistIterator<T const>. 如果T已经是const这个转换永远不会被使用。

Answer 4

回答by Matthieu M.

Boost has something to help: the Boost.Iterator library.

Boost 有一些帮助：Boost.Iterator 库。

More precisely this page: boost::iterator_adaptor.

更准确地说，这个页面：boost::iterator_adaptor。

What's very interesting is the Tutorial Examplewhich shows a complete implementation, from scratch, for a custom type.

非常有趣的是教程示例，它显示了自定义类型的完整实现，从头开始。

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(); }
};

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(); }
};

The main point, as has been cited already, is to use a single template implementation and typedefit.

正如已经提到的，重点是使用单个模板实现和typedef它。

Answer 5

回答by Potatoswatter

I don't know if Boost has anything that would help.

我不知道 Boost 是否有任何帮助。

My preferred pattern is simple: take a template argument which is equal to value_type, either const qualified or not. If necessary, also a node type. Then, well, everything kind of falls into place.

我的首选模式很简单：取一个等于的模板参数value_type，无论是否为 const 限定。如有必要，还有一个节点类型。然后，好吧，一切都到位了。

Just remember to parameterize (template-ize) everything that needs to be, including the copy constructor and operator==. For the most part, the semantics of constwill create correct behavior.

只要记住参数化（模板化）所有需要的东西，包括复制构造函数和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;

Answer 6

回答by VinGarcia

There are plenty of good answers but I created a template headerI use that is quite concise and easy to use.

有很多好的答案，但我创建了一个模板标题，我使用它非常简洁且易于使用。

To add an iterator to your class it is only necessary to write a small class to represent the state of the iterator with 7 small functions, of which 2 are optional:

要将迭代器添加到您的类中，只需编写一个小类来表示具有 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);
};

Then you can use it as you would expect from an STL iterator:

然后，您可以像对 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
  }
}

I hope it helps.

我希望它有帮助。

C++ 如何正确实现自定义迭代器和 const_iterators？

提问by ereOn

采纳答案by Andrey

回答by Enzo

回答by Maxim Egorushkin

回答by Matthieu M.

回答by Potatoswatter

回答by VinGarcia

相关推荐

最近更新

标签

C++ 如何正确实现自定义迭代器和 const_iterators？

提问by ereOn

采纳答案by Andrey

回答by Enzo

回答by Maxim Egorushkin

回答by Matthieu M.

回答by Potatoswatter

回答by VinGarcia

相关推荐

C++ boost asiodeadline_timer

C++ for循环中的后缀和前缀增量运算符

C++ 使用 CMake 打开链接器标志

C++ 如何初始化作为类成员的 shared_ptr？

相关推荐

最近更新

标签