gpt4 book ai didi

C++,为二叉树实现自定义迭代器(长)

转载 作者:可可西里 更新时间:2023-11-01 18:21:27 30 4
gpt4 key购买 nike

请保持友善 - 这是我的第一个问题。 =P

基本上作为一个暑期项目,我一直在研究 wikipedia page 上的数据结构列表。并尝试实现它们。上学期我参加了 C++ 类(class),发现它非常有趣,作为我实现二项式堆的期末项目——这也非常有趣。也许我很 Nerd ,但我喜欢数据结构。

无论如何,足够的背景故事。该项目进展顺利,我从二叉树开始。为了走得更远,我需要创建迭代器来遍历树。我已经决定为每个遍历方法创建两种类型的迭代器(常规迭代器和 const 迭代器),我只是不知道该怎么做。我听说过从 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
};

我想就是这样了 - 感谢您的宝贵时间!如果您需要更多信息,请告诉我。

最佳答案

1。胖迭代器与精益迭代器

有两种可能的方式来实现树的遍历。您可以:

  • 有简单地指向它们的“ child ”的节点,以及保持堆栈的迭代器(因此,胖迭代器)
  • 节点有父指针(像你的),迭代器只是指向给定节点的指针(精简迭代器)

这是一种设计权衡,STL 实现者通常采用精益方式,因为迭代器(在 STL 中)被认为复制起来很便宜。

2。 Easy Iterators vs From scratch 迭代器

还有几种实现迭代器的方法:

  • 从头开始:您自己做所有事情,包括定义 typedef、所有运算符重载等...
  • 简单:您使用 Boost.Iterator 自己实现尽可能少的代码

我基本上算继承自std::iterator作为“从头开始”的情况,因为它仅提供 5 typedef ...

是否选择其中一个实际上取决于您的情况:

  • 出于学习目的,我建议采用“从零开始”的方式几次
  • 出于生产目的,我建议采用“从头开始”的方式(从 Boost 继承并不会节省太多,但它确实会使调试 session /内存转储复杂化,至少对于 gdb 来说是这样,因为 gdb 公开了基类)
  • 为了快速测试,我建议采用“简单”方式

请注意,您可能会遇到一种奇怪的情况,您的迭代器无法真正构建在 Boost.Iterator 之上,在这种情况下,您别无选择,只能自己构建它。

3。 Const 和非常量迭代器

这也许是重点。

如果仅仅是为了这个,那么值得看看 Boost.Iterator,因为它们公开了实现一个迭代器(模板化)的技术,它将涵盖两种情况。 p>

查看 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的关键点和非 constconst 自动转换的迭代器到非 const没有可能的反向转换。

无论你做什么,重复使用相同的技巧:模板化 BaseIteratorValue ,并提供两个类型定义:typedef BaseIterator<Value> iteratortypedef BaseIterator<Value const> const_iterator .

关于C++,为二叉树实现自定义迭代器(长),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6366684/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com