Руководство к классу итераторов - PullRequest
Новая
       12

Руководство к классу итераторов

8 голосов
/ 03 июня 2010

У меня есть красное Черное дерево, реализованное в c ++ . Он поддерживает функциональность карты STL. Узлы дерева содержат ключи и сопоставленные значения. Я хочу написать класс итератора для этого, но я застрял в том, как это сделать. Должен ли я сделать это внутренний класс класса дерева? Кто-нибудь может дать мне несколько советов о том, как написать это + некоторые ресурсы ??

Спасибо !!

Ответы [ 3 ]

8 голосов
/ 03 июня 2010

Конечно, прочитайте эту прекрасную статью о написании итераторов 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!

2 голосов
/ 03 июня 2010

Я думал, что добавлю свой маленький пакет советов.

Первое, что я хотел бы отметить, - это то, что iterator и const_iterator, скорее всего, имеют много общего в своей реализации. Однако, хотя их код похож, он не совсем идентичен. Это напрашивается на шаблоны.

Второе, что я хотел бы отметить, это то, что const_iterator должен быть конструируемым из iterator (неявно), но не наоборот.

Третье, что я хотел бы отметить, - это то, что если вы хотите иметь интерфейс, подобный map, то вам также необходимо предоставить reverse_iterator и 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;
};

Я не знаю о вас, но мне хорошо, когда я делаю только четверть работы и использую компилятор / библиотеку, чтобы заполнить остальное для меня:)

1 голос
/ 03 июня 2010

Класс итератора должен быть либо вложенным, либо, по крайней мере, typedef, который псевдоним your_map::iterator указывает на некоторый тип, определенный в другом месте. Хотя вложенный класс обычно является самым чистым / простым маршрутом.

Что касается ресурсов, одним из возможных источников помощи будет библиотека Boost :: iterator , которая включает компоненты, предназначенные для упрощения реализации итераторов.

...