基本上作为夏季项目,我一直在浏览wikipedia page上的数据结构列表并尝试实现它们.我上学期参加了一门C课程并发现它非常有趣,作为我实施二项式堆的最后一个项目 – 这也非常有趣.也许我很讨厌,但我喜欢数据结构.
无论如何,足够的背景故事.项目进展顺利,我从二叉树开始.为了更进一步,我需要创建迭代器来遍历树.我已经决定为每个遍历方法(常规迭代器和常量迭代器)创建两种类型的迭代器,我只是不知道如何做到这一点.我听说从stl的迭代器继承,甚至使用boosts 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
};
我想就是这样 – 谢谢你的时间！如果您需要其他信息,请告诉我们.
解决方法
有两种可能的方法来实现树的遍历.你可以：
>有节点只是指向他们的“子”,以及保持堆栈的迭代器(因此,胖迭代器)
>让节点具有父指针(就像你的那样),迭代器只是指向给定节点的指针(精益迭代器)
这是一个设计权衡,STL实现者通常采用精益方式,因为迭代器(在STL中)应该是便宜的复制.
2. Easy Iterators vs From scratch迭代器
还有几种方法可以实现迭代器：
> From Scratch：你自己做所有事情,包括定义typedef,所有运算符重载等等……
>简单：您使用Boost.Iterator自己实现尽可能少的代码
我基本上将从std :: iterator继承为“从头开始”的情况,因为它只提供了5个typedef …
是否选择其中一个确实取决于您的情况：
>出于学习目的,我建议多次使用“From Scratch”方式
>出于生产目的,我建议采用“From Scratch”方式(从Boost继承并不节省太多,但它确实使调试会话/内存转储复杂化,至少使用gdb,因为gdb暴露了基类)
>为了快速测试,我建议采用“简单”方式
请注意,您可能处于一个奇怪的情况,您的迭代器无法真正构建在Boost.Iterator之上,在这种情况下,您将别无选择,只能自己构建它.
3. Const和非const迭代器
这也许是重点.
如果仅为此,则值得查看Boost.Iterator,因为它们公开了实现一个迭代器(模板化)的技术,它将涵盖两种情况.
查看Iterator Adaptor中的Tutorial Example部分：
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：typedef BaseIterator< Value> iterator和typedef BaseIterator< Value const>常量性.
