9

私は c++ で実装された Red Black ツリーを持っています。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は実装の多くが共通している可能性が非常に高いということです。ただし、コードは似ていますが、完全に同一というわけではありません。これにはテンプレートが必要です。

2 番目に注意したいのは、aは(暗黙的に) const_iteratoran から構築可能であるべきですが、その逆はできないということです。iterator

3 番目に注意したいことは、- のmapようなインターフェイスが必要な場合は、reverse_iteratorandconst_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;
};

あなたのことはわかりませんが、作業の 4 分の 1 だけを行い、コンパイラー/ライブラリーを活用して残りを埋めてくれると気分が良くなります :)

于 2010-06-03T07:02:55.837 に答える
1

反復子クラスは、ネストされたクラスであるか、少なくともyour_map::iterator他の場所で定義されている型にエイリアスする typedef である必要があります。ただし、ネストされたクラスは通常、最もクリーンで簡単なルートです。

リソースに関して言えば、 Boost::iteratorライブラリが役立つ可能性があります。これには、イテレータの実装を容易にするためのコンポーネントが含まれています。

于 2010-06-03T05:50:00.190 に答える