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

Question

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

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

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

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

Answer 1

• 选择适合您的容器的迭代器类型：输入、输出、转发等。
• 使用标准库中的基本迭代器类。例如， std::iterator 与 random_access_iterator_tag。这些基类定义了 STL 所需的所有类型定义并执行其他工作。

• 为了避免代码重复，迭代器类应该是一个模板类，并通过“值类型”、“指针类型”、“引用类型”或所有这些（取决于实现）进行参数化。例如：

  // 迭代器类通过指针类型参数化
  模板 类 MyIterator {
      // 迭代器类定义放在这里
  };
  
  typedef MyIterator;迭代器类型；
  typedef MyIterator; const_iterator_type；
  

  注意 iterator_type 和 const_iterator_type 类型定义：它们是非常量和常量迭代器的类型。

另请参阅：标准库参考

编辑： std::自 C++17 起，iterator 已被弃用。请参阅此处的相关讨论。

Answer 2

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

您可以在 Github 上找到它

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

1. 创建您的“自定义迭代器” “ 班级。
2. 在“自定义容器”类中定义 typedef。
   • 例如typedef blRawIterator<类型>迭代器；
   • 例如typedef blRawIterator<常量类型> const_iterator;
3. 定义“开始”和“结束”函数
   • 例如迭代器begin(){return iterator(&m_data[0]);};
   • 例如const_iterator cbegin()const{return const_iterator(&m_data[0]);};
4. 我们完成了！！！

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

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

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

1. //------------------------ -------------------------------------------
   // 具有随机访问的原始迭代器
   //------------------------------------------------ -------------------
   模板<类型名称 blDataType>
   类 blRawIterator
   {
   民众：
   
       使用 iterator_category = std::random_access_iterator_tag;
       使用 value_type = blDataType;
       使用 Difference_type = std::ptrdiff_t;
       使用指针= blDataType*；
       使用引用 = blDataType&;
   
   民众：
   
       blRawIterator(blDataType* ptr = nullptr){m_ptr = ptr;}
       blRawIterator(const blRawIterator& rawIterator) = default;
       ~blRawIterator(){}
   
       blRawIterator&运算符=(const blRawIterator&rawIterator)=默认值；
       blRawIterator&运算符=(blDataType* ptr){m_ptr = ptr;return (*this);}
   
       运算符 bool()const
       {
           如果（m_ptr）
               返回真；
           别的
               返回假；
       }
   
       bool 运算符==(const blRawIterator& rawIterator)const{return (m_ptr == rawIterator.getConstPtr());}
       bool 运算符 !=(const blRawIterator& rawIterator)const{return (m_ptr != rawIterator.getConstPtr());}
   
       blRawIterator&运算符+=(const Difference_type&movement){m_ptr +=movement;return(*this);}
       blRawIterator&运算符-=(const Difference_type&movement){m_ptr -=movement;return(*this);}
       blRawIterator&运算符++(){++m_ptr;return(*this);}
       blRawIterator&运算符--(){--m_ptr;return (*this);}
       blRawIterator;运算符++(int){自动温度(*this);++m_ptr;返回温度;}
       blRawIterator;运算符--(int){auto temp(*this);--m_ptr;返回temp;}
       blRawIterator;运算符+(const Difference_type&movement){auto oldPtr = m_ptr;m_ptr+=movement;auto temp(*this);m_ptr = oldPtr;返回temp;}
       blRawIterator;运算符-(const Difference_type& moving){auto oldPtr = m_ptr;m_ptr-=movement;auto temp(*this);m_ptr = oldPtr;return temp;}
   
       Difference_type 运算符-(const blRawIterator& rawIterator){return std::distance(rawIterator.getPtr(),this->getPtr());}
   
       blDataType&运算符*(){返回*m_ptr;}
       const blDataType&运算符*()const{返回*m_ptr;}
       blDataType* 运算符->(){return m_ptr;}
   
       blDataType* getPtr()const{return m_ptr;}
       const blDataType* getConstPtr()const{return m_ptr;}
   
   受保护：
   
       blDataType* m_ptr;
   };
   //------------------------------------------------ -------------------
   

2. //------------------------------------------------ ---------------------------------
   // 具有随机访问的原始反向迭代器
   //------------------------------------------------ -------------------
   模板<类型名称 blDataType>
   blRawReverseIterator 类：公共 blRawIterator;
   {
   民众：
   
       blRawReverseIterator(blDataType* ptr = nullptr):blRawIterator(ptr){}
       blRawReverseIterator(const blRawIterator& rawIterator){this->m_ptr = rawIterator.getPtr();}
       blRawReverseIterator(const blRawReverseIterator& rawReverseIterator) = default;
       ~blRawReverseIterator(){}
   
       blRawReverseIterator&运算符=(const blRawReverseIterator& rawReverseIterator) = default;
       blRawReverseIterator&运算符=(const blRawIterator&rawIterator){this->m_ptr = rawIterator.getPtr();return (*this);}
       blRawReverseIterator&运算符=(blDataType* ptr){this->setPtr(ptr);return (*this);}
   
       blRawReverseIterator&运算符+=(const Difference_type&movement){this->m_ptr-=movement;return(*this);}
       blRawReverseIterator&运算符-=(const Difference_type&movement){this->m_ptr +=movement;return(*this);}
       blRawReverseIterator&运算符++(){--this->m_ptr;return (*this);}
       blRawReverseIterator&运算符--(){++this->m_ptr;return(*this);}
       blRawReverseIterator;运算符++(int){auto temp(*this);--this->m_ptr;返回temp;}
       blRawReverseIterator;运算符--(int){auto temp(*this);++this->m_ptr;返回temp;}
       blRawReverseIterator;运算符+(const int& moving){auto oldPtr = this->m_ptr;this->m_ptr-=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;}
       blRawReverseIterator;运算符-(const int& moving){auto oldPtr = this->m_ptr;this->m_ptr+=movement;auto temp(*this);this->m_ptr = oldPtr;return temp;}
   
       Difference_type 运算符-(const blRawReverseIterator& rawReverseIterator){return std::distance(this->getPtr(),rawReverseIterator.getPtr());}
   
       blRawIterator; base(){blRawIterator; forwardIterator(this->m_ptr); ++向前迭代器；返回前向迭代器；}
   };
   //------------------------------------------------ -------------------
   

现在在您的自定义容器类中的某个位置：

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

他们经常忘记 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 如何转换为 IntrusiveSlistIterator。如果T已经是const这个转换永远不会被使用。

Answer 4

Boost 有一些可以提供帮助的东西：Boost.Iterator 库。

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

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

模板 
类node_iter
  : 公共 boost::iterator_adaptor<
        node_iter<值> // 衍生的
      , 值* // 基数
      , boost::use_default // 值
      , boost::forward_traversal_tag // 类别或遍历
    >
{
 私人的：
    结构启用器{}； // 私有类型可以避免误用

 民众：
    节点迭代器()
      : node_iter::iterator_adaptor_(0) {}

    显式 node_iter(Value* p)
      : node_iter::iterator_adaptor_(p) {}

    // 迭代器可转换为 const_iterator，反之亦然
    模板
    节点迭代器（
        node_iter<其他值>常量&其他
      ，类型名 boost::enable_if<
            boost::is_convertible;
          , 推动者
        >::类型 = 启动器()
    ）
      : node_iter::iterator_adaptor_(other.base()) {}

 私人的：
    朋友类 boost::iterator_core_access;
    voidincrement() { this->base_reference() = this->base()->next(); }
};

正如已经引用的那样，要点是使用单个模板实现和 typedef 它。

Answer 5

不知道Boost有没有什么帮助。

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

只需记住参数化（模板化）所有需要的东西，包括复制构造函数和运算符==。在大多数情况下，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

有很多好的答案，但我创建了一个 模板标头 我使用它相当简洁易用。

要向你的类添加一个迭代器，只需要编写一个小类来用 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 equals(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
  }
}

我希望它有帮助。

Answer 7

我看到这篇文章，很惊讶这里没有真正提到一个简单的方法。使用像 std::iterator 描述的那样指向值的指针显然是非常通用的方法。但你也许可以做一些更简单的事情。当然，这是一种简单化的方法，可能并不总是足够的，但如果是的话，我将其发布给下一个读者。

您的类中的基础类型很可能是一个 STL 容器，它已经为您定义了迭代器。如果是这种情况，您可以简单地使用它们定义的迭代器，而不必真正创建自己的迭代器。

这是一个例子：

class Foo {

  std::vector<int>::iterator begin() { return data.begin(); }
  std::vector<int>::iterator end() { return data.end(); }

  std::vector<int>::const_iterator begin() const { return data.begin(); }
  std::vector<int>::const_iterator end() const { return data.end(); }


private:
  std::vector<int> data

};

Answer 8

我有兴趣知道这是如何正确，但似乎可以作为内部数据存储的自定义迭代器

template<typename T>
struct iterator_type
{
    using self_type             = iterator_type;
    using iterator_category     = std::random_access_iterator_tag;
    using difference_type       = std::ptrdiff_t;
    using value_type            = std::remove_cv_t<T>;
    using pointer               = T*;
    using reference             = T&;

    iterator_type( pointer ptr ) noexcept
        : _ptr{ ptr }
    {}

    reference operator*() noexcept { return *_ptr; }
    pointer operator->() noexcept { return _ptr; }

    self_type operator++() noexcept { ++_ptr; return *this; }
    self_type operator++(int) noexcept { self_type tmp = *this; ++_ptr; return tmp; }

    self_type operator--() noexcept { --_ptr; return *this; }
    self_type operator--(int) noexcept { self_type tmp = *this; --_ptr; return tmp; }

    bool operator==( const self_type &other ) const noexcept { return _ptr == other._ptr; }
    bool operator!=( const self_type &other ) const noexcept { return _ptr != other._ptr; }

private:
    pointer _ptr;
};


template<typename T>
using const_iterator_type = iterator_type<std::add_const_t<T>>;

然后我只需将它们添加到我的类中，并且似乎按预期工作。

template<typename T>
class Container
{
public:
    using iterator               = iterator_type<T>;
    using const_iterator         = const_iterator_type<T>;
    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

...

    iterator begin() { return _begin; }
    iterator end() { return _begin + _size; }

    const_iterator cbegin() const { return _begin; }
    const_iterator cend() const { return _begin + _size; }

    reverse_iterator rbegin() { return reverse_iterator(_begin + _size); }
    reverse_iterator rend() { return reverse_iterator(_begin); }

    const_reverse_iterator crbegin() const { return const_reverse_iterator(_begin + _size); }
    const_reverse_iterator crend() const { return const_reverse_iterator(_begin); }

private:
    T*         _begin;
    size_t     _size;
    size_t     _capacity;
};

唯一的事情是用 std::cbegin()、std::rcbegin()、std::cend() 来实现> 和 std::rcend() 函数我必须扩展 std 命名空间：

namespace std
{
    template<typename T>
    typename Container<T>::const_iterator cbegin( Container<T> &c ) { return c.cbegin(); }

    template<typename T>
    typename Container<T>::const_iterator cend( Container<T> &c ) { return c.cend(); }

    template<typename T>
    typename Container<T>::const_reverse_iterator crbegin( Container<T> &c ) { return c.crbegin(); }

    template<typename T>
    typename Container<T>::const_reverse_iterator crend( Container<T> &c ) { return c.crend(); }
}

Answer 9

已测试代码。
具有自定义迭代器实现的自定义向量

#include<iostream>
using namespace std;

// vector + iterator
class dviter{
    int index;
    int* data;
    public:
    dviter(int *values, int offset) : data(values), index(offset) {
    }
    int operator*() {
        return data[index];
    }
    bool operator != (const dviter& obj){
        return (this->index != obj.index);
    }
    dviter& operator++(){
        ++index;
        return *this;
    }

};
class dvector {
    int* data = nullptr;
    int capacity = 5;
    int index = 0;
    public:
    dvector(){
        data = new int[capacity];
    }
    void push(int val) {
        if(notFull()) {
            data[index] = val;
            ++index;
            return;
        }
            int *temp = new int(2 * capacity);
            for(int i = 0; i < index; i++){
                temp[i] = data[i];
            }
            capacity = 2 * capacity;
            delete [] data;
            data = nullptr;
            data = temp;
            push(val);
        
    }
    void pop() {
        if(notEmpty()) {
            --index;
            return;
        }
        cout << "nothing to pop "<< endl;
    }
    bool notEmpty() {
        return (index > 0) ? true : false;
    }
    bool notFull() {
        return (index < (capacity)) ? true : false;
    }
   
    void printoff() {
        for (int i = 0; i < index; i++) {
            cout << data[i] << "  ";
        }
        cout <<endl;
    }
 
    int currentItem(int index) {
        return data[index];
    }

    dviter* begin() {
        return new dviter(data, 0);
    }
    dviter* end() {
        return new dviter(data, index);
    }
};



int main() {
    dvector p;
    p.push(1);
    p.push(2);
    p.push(3);

    auto* it1 = p.begin();
    auto* it2 = p.end();
    while( (*it1)!=  (*it2)) {
        cout <<  *(*it1) <<  endl;
        ++(*it1);
    }
}

Answer 10

检查下面的代码，它有效

#define MAX_BYTE_RANGE 255

template <typename T>
class string
{
public:
    typedef char *pointer;
    typedef const char *const_pointer;
    typedef __gnu_cxx::__normal_iterator<pointer, string> iterator;
    typedef __gnu_cxx::__normal_iterator<const_pointer, string> const_iterator;

    string() : length(0)
    {
    }
    size_t size() const
    {
        return length;
    }
    void operator=(const_pointer value)
    {
        if (value == nullptr)
            throw std::invalid_argument("value cannot be null");
        auto count = strlen(value);
        if (count > 0)
            _M_copy(value, count);
    }
    void operator=(const string &value)
    {
        if (value.length != 0)
            _M_copy(value.buf, value.length);
    }
    iterator begin()
    {
        return iterator(buf);
    }
    iterator end()
    {
        return iterator(buf + length);
    }
    const_iterator begin() const
    {
        return const_iterator(buf);
    }
    const_iterator end() const
    {
        return const_iterator(buf + length);
    }
    const_pointer c_str() const
    {
        return buf;
    }
    ~string()
    {
    }

private:
    unsigned char length;
    T buf[MAX_BYTE_RANGE];

    void _M_copy(const_pointer value, size_t count)
    {
        memcpy(buf, value, count);
        length = count;
    }
};