9

我有一个用 c++ 实现的红黑树。它支持 STL 映射的功能。树节点包含键和映射的值。我想为此编写一个迭代器类,但我不知道该怎么做。我应该让它成为Tree 类的内部类吗?谁能给我一些关于如何编写它的指南+一些资源?

谢谢你!!

4

3 回答 3

9

当然,阅读这篇关于编写 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 兼容的!

于 2010-06-03T05:44:41.133 回答
2

我想我会添加我自己的一小部分建议。

我想指出的第一件事是,iterator它们const_iterator的实现很可能有很多共同点。但是,即使它们的代码相似,也不完全相同。这需要模板。

我要注意的第二件事是 aconst_iterator应该可以从 a 构造iterator(隐式),但不能反过来。

我要注意的第三件事是,如果您希望有一个类似map的接口,那么您还需要提供一个reverse_iteratorand const_reverse_iterator

从风格的角度来看,我倾向于不把iterator自身的实现放在类中。当类实现中包含太多代码以至于您难以查看可用的类型和方法时,我发现它不可读。出于这个原因,我建议将实现放在课堂之外。

最后,我绝对推荐 Boost.Iterator。您可能不会使用它,但请阅读材料,它会让您深入了解如何编写一次代码并将其用于 4 种!

快速说明:

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;
};

我不了解你,但当我只完成四分之一的工作并利用编译​​器/库为我完成其余部分时,我感觉很好 :)

于 2010-06-03T07:02:55.837 回答
1

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

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

于 2010-06-03T05:50:00.190 回答