Инструкции к классу итератора
У меня есть Красное Черное дерево, реализованное в C++. Это поддерживает функциональность карты STL. Древовидные узлы содержат ключи и отображенные значения. Я хочу записать класс итератора для этого, но я застреваю с тем, как сделать это. Я должен сделать это внутренним классом Древовидного класса? Кто-либо может дать мне некоторые инструкции по тому, как записать это + некоторые ресурсы??
Спасибо!!
3 ответа
Конечно, прочтите эту прекрасную статью о написании итераторов 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-компилятором!
Я подумал, что добавлю свой небольшой набор советов.
Первое, что я хотел бы отметить, это то, что итератор и const_iterator , скорее всего, имеют много общего в своей реализации. Однако, хотя их код похож, он не совсем идентичен. Это требует шаблонов.
Второе, что я хотел бы отметить, это то, что const_iterator должен быть сконструирован из итератора (неявно), но не наоборот.
Третье, что я хотел бы отметить, это то, что если вы хотите иметь интерфейс, подобный map , вам необходимо предоставить reverse_iterator и const_reverse_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;
};
Не знаю, как вы, но мне хорошо, когда я делаю только четверть работы и использую компилятор / библиотеку, чтобы заполнить остальное за меня :)
Класс итератора должен быть либо вложенным классом, либо, по крайней мере, typedef, который присваивает your_map :: iterator псевдоним некоторого типа, определенного в другом месте. Однако вложенный класс обычно является самым чистым / простым путем.
Что касается ресурсов, то одним из возможных источников помощи может быть библиотека Boost :: iterator , которая включает компоненты, предназначенные для упрощения реализации итераторов.