C++，實現二叉樹的自定義迭代器（長）

Question

請保持好 - 這是我的第一個問題。 = P

基本上作爲一個暑期項目，我一直在瀏覽wikipedia page上的數據結構列表並試圖實現它們。上個學期我參加了一門C++課程，發現它非常有趣，作爲最後一個項目，我實現了一個Binomial堆 - 這也非常有趣。也許我很討厭，但我喜歡數據結構。

無論如何，足夠的背景故事。該項目進展順利，我從Binary Trees開始。儘管我需要創建遍歷樹的迭代器，但要進一步深入。我已經決定爲每個遍歷方法（常規迭代器和常量迭代器）創建兩種類型的迭代器，但我不知道如何執行此操作。我聽說過從stl的迭代器的東西繼承，甚至使用提升iterator_facade（這似乎是一個很好的選擇）

我甚至沒有試圖寫迭代器代碼，因爲我不知道從哪裏開始，但我在github上有我的當前代碼。你可以看看here。

如果你反對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.脂肪迭代器VS精益迭代

有實現樹的遍歷兩種可能的方式。您可以：

• 有一個簡單的指向是保持一個堆棧自己的「孩子」，和迭代器節點（因此，脂肪迭代）
• 有有父指針（像你這樣）節點，和迭代器只是指向給定節點（瘦迭代）

這是一個設計權衡，STL的實現者通常會瘦的方法，因爲迭代器（在STL）應該是便宜複製。

2。易迭代器VS從無到有的迭代器

也有實現迭代幾種方法：

• 從零開始：你自己做的一切，其中包括typedef的定義，所有的運算符重載等...
• 容易：您使用Boost.Iterator自己執行儘可能少的代碼儘可能

我基本上算從std::iterator繼承爲「從頭開始」的局面，因爲它提供了一個只有5 typedef ...

是否選擇一種或另一種完全取決於您的情況：

• 對於學習的目的，我建議去了「從零開始」的方式幾次
• 的生產用，我建議去了「從零開始」的方式（與Boost繼承不會節省很多，但它確實複雜調試會話/內存轉儲，至少用gdb，因爲GDB暴露基類）
• 爲了快速測試，我會推薦走「易」路

請注意，你可能會在一個奇怪的情況下你的迭代器不能真正對Boost.Iterator上方內置，在這種情況下，你別無選擇，只能自己去建立它。

3.常量和非const迭代器

這或許是要點。

如果只是爲了這一點，這是值得看的Boost.Iterator，因爲它們暴露於實現一個迭代器（模板），將覆蓋都箱子技術。

看在Iterator Adaptor的教程例部分：

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沒有反向轉換是可能的。

不管你做什麼，重複使用相同的伎倆：模板化上Value一個BaseIterator，並且提供兩個類型定義：​​和typedef BaseIterator<Value const> const_iterator。

Answer 2

實現此目的的一種方法是在迭代器中有一個跟蹤父節點的堆棧。每次到達一個節點時，它都不是一片葉子，將它推入堆棧並按照搜索順序進入下一個節點。一旦你點擊一個葉子，處理它，然後返回到堆棧頂部的節點。重複廣告Nausium，直到你訪問了所有東西。