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

Question

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

我从来没有这样做过，我没有找到合适的方法。关于迭代器创建的指导原则是什么？我应该注意什么？

我也想避免代码重复（我觉得const_iterator和iterator分享很多东西;如果一个子类是另一个？）。

注脚：我敢肯定，加速了东西来缓解这一点，但我不能在这里使用它，对于许多愚蠢的理由。

Answer 1

• 选择迭代其适合你容器的类型：输入，输出，从向前标准库等
• 使用基本的迭代器类。例如，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类型定义：他们是类型的非const和const迭代器。

另请参见：standard library reference

Answer 2

我不知道，如果加速有什么关系，这将有助于。

我的优选图案是简单的：取的模板的参数，它等于value_type，无论是常量合格与否。如有必要，也是一种节点类型。那么，好吧，一切都会落到实处。

只要记住参数（模板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; 

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<T>转换为IntrusiveSlistIterator<T const>。如果T已经为const，则此转换永远不会被使用。

Answer 4

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它。

Answer 5

我将向您展示如何为您的自定义容器轻松定义迭代器，但以防万一我创建了一个C++ 11库，使您可以轻松创建具有自定义行为的自定义迭代器，以适应任何类型的集装箱，连续或非连续的。

您可以在https://github.com/navyenzo/blIteratorAPI

发现它在github下面是简单的步骤来创建和使用自定义的迭代器：

1. 创建“自定义迭代”级。
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. We'r e完成！

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

注：当定义自定义迭代器，我们从标准的迭代器分类导出，让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]);} 

          . 
          . 
          . 
}; 

GOOD LUCK！

Answer 6

有很多很好的答案，但我有一个template header我使用它是相当简洁和易于使用。

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

我希望它有帮助。