logo标签列表

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

c++iteratorconst-iterator
306

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

我以前从未做过这个，也找不到合适的指南。关于迭代器创建有哪些指导方针，我应该注意什么？

我还想避免重复代码（我觉得const_iterator和iterator有很多共同点; 是否应该将一个子类化为另一个？）。

注：我相信Boost有一些工具可以简化这个过程，但由于很多愚蠢的原因，我不能在这里使用它。

3
相关问题集合：迭代器类型可以直接继承“const_iterator”吗？ 在实现const和non-const迭代器时如何避免代码重复？ - sbi
4
在C++中，通常希望具有符合STL标准的迭代器，因为它们可以很好地与STL提供的所有现有容器和算法配合使用。虽然这个概念类似，但与GoF提出的模式存在一些差异。 - Björn Pollex
2
这些答案的复杂性表明，C++可能只适合于晋升到本科生的家庭作业，或者这些答案过于复杂和错误。Cpp中一定有更简单的方法？就像相对于make的CMake和Automake一样，从Python原型中沸腾出来的原始C似乎比这个要容易得多。 - Chris
2
@Chris C++确实是值得学习的。C++的复杂性和学习曲线可以看作是为其相对独特的极度优化的抽象付出的代价。有人说零成本抽象，在现代C++中，这在许多情况下确实是发生的。 - Pavel Šimerda
2
@PavelŠimerda 哈哈，是的，总的来说我完全不同意我之前的评论。我想我当时更多地考虑了“一定有更简单的方法”的想法。 - Chris
显示剩余3条评论
9个回答
176
  • 根据你的容器选择适合它的迭代器类型：输入、输出、前向等。
  • 使用标准库中的基本迭代器类。例如，std::iterator和random_access_iterator_tag这样的基本类别定义了STL所需的所有类型定义，并完成其他工作。

  • 为避免代码重复，迭代器类应该是一个模板类，并且应该由"value type"，"pointer type"，"reference type"或所有这些（取决于实现）进行参数化。例如：

    // 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++17起，std::iterator已被弃用。相关讨论请参见此处。

8
我没有对此进行投票，但是，“random_access_iterator”不在标准库中，而且回答没有处理可变到常量的转换。你可能想继承自例如“std::iterator<random_access_iterator_tag, value_type, ... optional arguments ...>”。 - Yakov Galka
2
是的，我不太确定这是如何工作的。如果我有方法 RefType operator*() { ... }，我离成功又近了一步 - 但这并没有什么帮助，因为我还需要 RefType operator*() const { ... }。 - Translunar
31
std::iterator已被弃用。 - diapir
25
如果这个已经被弃用了，那么正确的“新”方法是什么？ - SasQ
2
@SasQ 你只需要自己定义成员类型（这并不需要太多额外的工作）- 或者创建一个类似于 std::iterator 的模板，如果你喜欢的话。 - Ted Lyngmo
显示剩余3条评论
82
我将向您展示如何轻松定义自定义容器的迭代器，但以防万一，我创建了一个C++11库，可以让您轻松地为任何类型的容器（连续或非连续）创建具有自定义行为的自定义迭代器。
  • 您可以在Github上找到它
  • 以下是创建和使用自定义迭代器的简单步骤：
    1. 创建“自定义迭代器”类。
    2. 在“自定义容器”类中定义typedef。
      • 例如：typedef blRawIterator< Type > iterator;
      • 例如：typedef blRawIterator< const Type > const_iterator;
    3. 定义“begin”和“end”函数
      • 例如：iterator begin(){return iterator(&m_data[0]);};
      • 例如：const_iterator cbegin()const{return const_iterator(&m_data[0]);};
    4. 我们完成了！！！

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

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

    在本例中，我定义了一个随机存取迭代器和一个反向随机存取迭代器：

    //-------------------------------------------------------------------
// 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;}
};
//-------------------------------------------------------------------
    现在，在您的自定义容器类中的某个位置：

    • （原文）

    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;
};
    我认为operator+和operator-的操作可能是相反的。看起来operator+正在从指针中减去移动，而operator-正在添加它。这似乎是相反的。 - Beached
    1
    对于逆向迭代器，operator+ 应该向后移动，operator- 应该向前移动。 - Enzo
    3
    太棒了。被接受的答案过于高级。这太棒了。谢谢恩佐。 - FernandoZ
    那个 explicit operator bool() 是一个非常糟糕的想法，请永远不要这样做。它让 while(it++) 看起来合理，但实际上完全是错误的。 - Mooing Duck
    2
    反向迭代器是无用的，因为标准库提供了一个反向迭代器适配器。而且你没有让迭代器类型能够从const迭代器中赋值。 - Toby Speight
    显示剩余8条评论
    30

    他们经常忘记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”转换为非“const”，它将无法编译。 - Matthieu M.
    1
    @Matthieu：如果使用模板构造函数，当将const_iterator转换为iterator时，编译器会在构造函数内部产生错误，使用户感到困惑和无语。而使用我发布的转换运算符，编译器只会说没有适合的从const_iterator到iterator的转换，这在我看来更加清晰明了。 - Maxim Egorushkin
    转换运算符并不能解决所有成员比较运算符的问题。编译器不会尝试转换你调用的对象，因此如果你的第一个操作数是非 const 的，但第二个操作数不是，那么该运算符就没有定义。 - Khaur
    @MaximYegorushkin 取 IntrusiveSlistIterator<T, void> a; 和 IntrusiveSlistIterator<T const, void> b;。b==a 是有效的，因为 a 被转换为 const 版本，但 a==b 不是，因为运算符需要一个非 const 迭代器并且不能转换为它。在第二种情况下，不会尝试将 a 转换为 const 迭代器，因为 operator== 是一个成员方法。 - Khaur
    @Khaur 你是对的，但这与转换运算符无关。这是成员比较运算符的工作方式。修复很简单 - 将成员比较变为非成员，请参见代码的更新版本。 - Maxim Egorushkin
    显示剩余4条评论
    26
    Boost有一个帮助工具：Boost.Iterator库。
    更准确地说，是这个页面：boost::iterator_adaptor。
    非常有趣的是Tutorial Example，它展示了一个完整的实现，从头开始，用于自定义类型。 
    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。

    你能解释一下这个注释的意思吗？// 一个私有类型避免了滥用 - kevinarpe
    @kevinarpe：enabler 永远不打算由调用方提供，因此我的猜测是它们将其设为私有以避免人们意外尝试传递它。我认为，一时半会儿并不会有任何问题，如果实际传递了它，因为保护措施在 enable_if 中。 - Matthieu M.
    @orenrevenge：这是从链接中复制/粘贴的，包括格式。欢迎来到Boost代码... - Matthieu M.
    18
    我不知道Boost是否有任何可以帮助的东西。
    我的首选模式很简单：使用一个等于value_type的模板参数，可以是const限定或非const限定。如果需要，还可以使用节点类型。然后，所有的东西都会自然而然地落实到位。
    只需记住对所有需要的内容进行参数化（模板化），包括复制构造函数和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 和 back 函数出了问题。 - Maxim Egorushkin
    @Maxim：是的，我实际上找不到使用我的技巧的任何示例:vP。我不确定你所说的转换有什么问题，因为我只是没有说明它们，但从相反的constness迭代器访问cur可能会有问题。我想到的解决方案是friend my_container::const_iterator; friend my_container::iterator;，但我不认为这就是我以前做过的...无论如何，这个一般的概述是有效的。 - Potatoswatter
    1
    在这两种情况下都要声明为 友元类。 - Potatoswatter
    已经过了一段时间，但我现在回想起来，转换应该基于成员初始化的格式良好性（通过SFINAE）。这遵循SCARY模式（但此帖子早于该术语的出现）。 - Potatoswatter
    15

    有很多好的答案，但我创建了一个模板头文件，我使用它非常简洁易用。

    要向您的类添加迭代器，只需要编写一个小类来表示迭代器状态，并编写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
  }
}

    我希望它能帮助到你。

    5
    我看到这篇文章，惊讶的是没有提到一种简单的方法。像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

};
    通过这样做，你违反了Foo对象的封装原则，允许迭代器直接修改底层容器，而不真正了解它。此外，从迭代器返回的值可能不是保存在STL容器中的值：例如，你可能只想提供实际保存的一部分内容，或者在返回之前进行某些转换。 - Adrian Maire
    有趣。我没有从这个角度考虑过它。谢谢。但是所有其他解决方案都面临同样的问题，不是吗？无论Foo类是什么，定义任何非const迭代器都会提供对其存储数据的不受限制的访问权限。 - Keivan
    4

    我想知道这个做法的正确性如何，但它似乎可以作为一个自定义迭代器来访问内部数据存储

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

    检查下面的代码，它可以工作。

    #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;
    }
};
    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接