C ++, Реализация пользовательского итератора для двоичных деревьев (long)

Question

Пожалуйста, будьте милы - это мой первый вопрос.= P

В основном, как летний проект, я просматривал список структур данных на странице википедии и пытался реализовать их.Я взял курс C ++ в прошлом семестре и нашел, что это было очень весело, в качестве финального проекта я реализовал Binomial Heap - это было также очень весело.Может быть, я идиот, но мне нравятся структуры данных.

В любом случае, достаточно предыстории.Проект идет хорошо, я начинаю с Binary Trees.Чтобы пойти гораздо дальше, мне нужно создать итераторы для обхода деревьев.Я уже решил, что создам два типа итераторов для каждого метода обхода (обычный итератор и константный итератор), я просто не знаю, как это сделать.Я слышал о наследовании от итераторов stl, или даже об использовании бустеров iterator_facade (что кажется хорошим вариантом)

Я даже не пытался написать код итератора, так как не знаю, с чего начать,но у меня есть текущий код на GitHub.Вы можете проверить это здесь .

В случае, если вы против github, я вставляю соответствующие определения классов.Реализации этих функций на самом деле не помогут, но если они вам понадобятся по какой-то причине, дайте мне знать.Кроме того, класс узла имеет родительский указатель для итерационных целей.

#ifndef __TREES_HXX
#define __TREES_HXX
#include <cstdlib>  // For NULL
#include <algorithm> // for std::max

// Node class definition. These nodes are to be used for any
// tree where the structure is
//    node
//     /\
// left  right
//  /\    /\
//
// etc., basically two children.
template <typename T>
class Node
{
  public:
    T data_;
    Node<T>* left_;
    Node<T>* right_;
    Node<T>* parent_; // Needed for iterators

    explicit Node(T const&);
    Node(Node<T> const&);
};

template <typename T>
class BinaryTree
{
  protected:
    typedef Node<T>* node_t;
    size_t tree_size;

  public:
    typedef T value_type;

    explicit BinaryTree();
    explicit BinaryTree(T const&);
    ~BinaryTree();

    virtual node_t insert(node_t&, T) = 0;
    virtual T& lookup(node_t const&, T const&) const = 0;
    inline virtual size_t size() const;
    inline virtual size_t depth(node_t const&) const;
    inline bool empty() const;
    inline void clear(node_t);

    node_t root;
};

Это базовое расширение двоичного дерева нашего абстрактного класса, в основном это (будет) BST.Для примера, почему мне нужны итераторы, посмотрите на определение функции поиска.Он должен возвращать итератор к узлу, где найден материал.

/* Implementation of our Binary Tree is in
 * this file. The node class is in Trees.hxx
 * because it's intended to be a general class.
 */

 #ifndef __BINARY_TREE_HXX
 #define __BINARY_TREE_HXX

 #include "Trees.hxx"


 template <typename T>
 class BiTree : public BinaryTree<T>
 {
   private:
     typedef typename BinaryTree<T>::node_t node_t;

   public:
     typedef typename BinaryTree<T>::value_type value_type;

     BiTree() : BinaryTree<T>()
     {
     }

     BiTree(T const& data) : BinaryTree<T>(data)
     {
     }

     node_t insert(node_t&, T);
     T& lookup(node_t const&, T const&) const; // Note: This should return an iterator to the node where the stuff is found
 };

Я думаю, это все - спасибо за ваше время!Если вам нужна дополнительная информация, дайте мне знать.

Answer 1

1.Fat Iterators vs Lean Iterators

Существует два возможных способа реализации обхода дерева.Вы можете:

• иметь узлы, которые просто указывают на их "потомков", и итераторы, которые хранят стек (таким образом, толстые итераторы )
• имеют узлыкоторые имеют родительский указатель (как ваш) и итераторы, которые являются просто указателями на данный узел ( худшие итераторы )

Это компромиссный дизайн, обычно разработчики STLидите экономным путем, потому что итераторы (в STL) должны быть дешевыми для копирования.

2.Простые итераторы против итераторов с нуля

Есть также несколько способов реализации итераторов:

• С нуля: вы делаете все сами, включая определение typedef, все перегрузки операторов и т. Д....
• Легко: вы используете Boost.Iterator, чтобы самостоятельно реализовать как можно меньше кода

Я в основном считаю наследование от std::iterator ситуацией "с нуля",поскольку он обеспечивает всего 5 typedef ...

Выбор того или другого действительно зависит от вашей ситуации:

• Для целей обучения я бы порекомендовал "С нуля "несколько раз
• В производственных целях я бы рекомендовал идти" С нуля "(наследование от Boost не сильно экономит, но усложняет отладку сеансов / дампов памяти, по крайней мере, с GDBпотому что GDB предоставляет базовые классы)
• Для быстрого тестирования я бы порекомендовал пойти "Легким" способом

Обратите внимание, что вы можете оказаться в странной ситуацииздесь ваш итератор не может быть построен поверх Boost.Iterator, и в этом случае у вас не будет другого выбора, кроме как создать его самостоятельно.

3.Константные и неконстантные итераторы

Это, пожалуй, главный вопрос.

Если только для этого стоит взглянуть на Boost.Iterator, потому что они раскрывают технику реализации один итератор (шаблонный), который будет охватывать оба случая.

Посмотрите на Пример учебника в разделе Итератор Adapter :

template <class Value>
class node_iter
  : public boost::iterator_adaptor<
        node_iter<Value>                // Derived
      , Value*                          // Base
      , boost::use_default              // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
    >
{
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    node_iter()
      : node_iter::iterator_adaptor_(0) {}

    explicit node_iter(Value* p)
      : node_iter::iterator_adaptor_(p) {}

    /// !!! Highlight !!!
    template <class OtherValue>
    node_iter(
        node_iter<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue*,Value*>
          , enabler
        >::type = enabler()
    )
      : node_iter::iterator_adaptor_(other.base()) {}

 private:
    friend class boost::iterator_core_access;
    void increment() { this->base_reference() = this->base()->next(); }
};

Третий конструктор является ключевой точкой для получения пары итераторов const и не- const с автоматическим преобразованием из const в не- const без обратного преобразованиявозможно.

Что бы вы ни делали, используйте один и тот же трюк: шаблонизируйте BaseIterator на Value и предоставьте два определения типа: typedef BaseIterator<Value> iterator и typedef BaseIterator<Value const> const_iterator.

Answer 2

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