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

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

我还希望避免代码重复(我觉得const_iterator和iterator共享很多东西;一个应该子类化另一个吗?)

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


当前回答

Boost可以提供帮助:Boost。迭代器库。

更准确地说是本页: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(); } };

正如前面提到的,要点是使用单个模板实现并对其进行类型定义。

其他回答

我不知道Boost有没有什么有用的东西。

我喜欢的模式很简单:取一个模板参数,它等于value_type,无论是否有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,而不是相反。这里有一个方法:

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,则此转换永远不会被使用。

Boost可以提供帮助:Boost。迭代器库。

更准确地说是本页: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(); } };

正如前面提到的,要点是使用单个模板实现并对其进行类型定义。

我偶然看到这篇文章,很惊讶这里没有提到一个简单的方法。使用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

};

有很多好的答案,但我创建了一个模板标题,我使用它是相当简洁和易于使用。

要在类中添加迭代器,只需要编写一个小类,用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
  }
}

我希望这能有所帮助。