迭代器类的指南

Question

我有一个用c ++实现的红黑树.它支持STL映射的功能.树节点包含键和映射的值.我想为此编写一个迭代器类,但我仍然坚持如何做到这一点.我应该将它作为Tree类的内部类吗？任何人都可以给我一些指导如何写它+一些资源？

谢谢!!

Answer 1

当然,阅读这篇关于编写STL迭代器的好文章,它可能会为您提供所需的概述:

http://www.drdobbs.com/184401417

通常,是的,内部类是好的,因为迭代器需要访问特定于实现的树节点:

struct container { ...
public:
  struct iterator {
    // these typedefs are needed if you want to be STL compatible
    typedef std::forward_iterator_tag iterator_category;
    typedef T         value_type;
    typedef T*        pointer;
    typedef T&        reference;
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;

    // the element points to your implementation node
    iterator( element* init = 0 ) : current(init) {}
    T& operator*() { return current->data; } // dereference
    const T& operator*() const { return current->data; }
    iterator& operator++() { // prefix
      if ( current ) current = current->next;
      return *this;
    }
    iterator operator++(int) { // postfix
      iterator temp = *this;
      ++*this;
      return temp;
    }
    bool operator==(const iterator& x) const { return current == x.current; }
    bool operator!=(const iterator& x) const { return current != x.current; }

  private:
    // the element points to your implementation node
    element* current;
  }
  ...

这里的好处是,虽然迭代器是公共的,但元素仍然可以保持私有:).是的,上面的代码也是STL编译器!