迭代器类的指南

Question

我有一个用C++实现的红黑树。它支持STL映射的功能，树节点包含键和相应的映射值。我想为此编写一个迭代器类，但是我不知道该如何着手。我应该将其定义为树类的内部类吗？请问有什么写法指南和资源可以提供吗？

感谢您！

- Izza

---

提供给您的信息是，大多数STL实现都基于红黑树来实现std::map，因此除非这是为了教育目的，否则您可以考虑使用std::map而不是自己制作。 - Luc Touraille

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标准!

- Kornel Kisielewicz

---

非常感谢你，Kornel。这正是我在寻找的，而且非常有用 :D - Izza

@Kornel：还有一个问题，你能否解释一下在第二个注释后面的代码行，*iterator( element init = 0 ) : current(init) {}**吗？ 我无法理解冒号后面的部分。 谢谢！ - Izza

@isurulucky，这是一个初始化列表（http://www.codeguru.com/forum/showthread.php?t=464084） - Kornel Kisielewicz

基本上与 iterator( element* init = 0 ) { current = init;} 相同。 - Kornel Kisielewicz

这种方法唯一的问题是，在“iterator”和“const_iterator”之间存在很多重复。 - Matthieu M.

Answer 2

我想提供一些建议。

首先，需要注意的是，`iterator`和`const_iterator`很可能有许多共同之处。然而，即使它们的代码相似，也不完全相同。这就需要使用模板。

其次，需要注意的是，应该可以从`iterator`（隐式地）构建一个`const_iterator`，但反过来不行。

第三个需要注意的是，如果您希望拥有类似于`map`的接口，那么还需要提供`reverse_iterator`和`const_reverse_iterator`。

从风格上看，我倾向于不将`iterator`本身的实现放在类中。当类实现被大量代码淹没时，我发现它很难阅读，因此我建议将其实现放在类外部。

最后，我强烈推荐使用Boost.Iterator。您可能不会使用它，但请阅读相关材料，它会为您提供如何编写一次代码并用于四种类型的见解！

快速示例：

namespace detail {
  template <class Value> class base_iterator;
}

template <class Value>
class container
{
public:
  typedef detail::base_iterator<Value> iterator;
  typedef detail::base_iterator<Value const> const_iterator;

  typedef boost::reverse_iterator<iterator> reverse_iterator;
  typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
};

我不知道你是否有同感，但是当我只需要完成四分之一的工作并使用编译器/库来填充其余部分时，我会感觉很好 :)

- Matthieu M.

Answer 3

迭代器类需要是一个嵌套类，或者至少是一个typedef，将your_map::iterator别名为在其他地方定义的某种类型。嵌套类通常是最干净/最简单的路线。

就资源而言，一个可能的帮助来源是Boost::iterator库，其中包括旨在使迭代器更易于实现的组件。

- Jerry Coffin

---

+1 给 boost::iterator，但如果有人自己编写红黑树而不使用 STL，则他可能不会使用 Boost。 - Kornel Kisielewicz

@Kornel：可能是这样——我必须承认，我编写的所有迭代器都是“从头开始”，以标准作为我的主要资源…… - Jerry Coffin