2

我有 BST 的基本（无随机化、排序等）实现。我想添加迭代器实现并使 BST 适用于基于范围的 for 循环。所以我需要 begin()、end() 成员函数和迭代器递增。

我了解 begin() 应该做什么-将迭代器返回到最左下角的节点，并且该线程讨论了遍历 BST 的不同可能性（=递增迭代器）

但是 end() 应该将迭代器提供给最后一个元素。这是我不明白的实际问题，在 BST 的上下文中这是什么意思？

4

3 回答 3

3

结束迭代器不一定必须超过最后一个元素（这对向量有意义，但对树来说则不那么重要）。它必须只是一个迭代器，可以清楚地识别为无效迭代器，用于指示已到达数据结构的末尾。

实际上，这可以通过多种方式完成，具体取决于您的迭代器如何引用它所指向的内容。例如，如果它使用指向树节点的指针，则可以将空指针用于结束迭代器。

于 2014-11-20T15:48:50.497 回答
1

一个使用两个额外指针的非常简单的方案是在 BST 顶部简单地覆盖一个双向链接的循环列表。然后，您的end()迭代器只需指向一个哨兵节点。它还使您的迭代器递增/递减非常简单。

BST::iterator &
BST::iterator::operator++() {
  n = n->next;
  return *this;
}

等等。请注意，使用这样的哨兵意味着end迭代器不需要特殊处理。您可以减少它并获得完全正确的行为。

于 2014-11-20T17:48:22.073 回答
0

尽管我发表了评论，但 Sander De Dycker 的想法是正确的。我有另一种思考方式。

所有支持迭代器的容器都有一个逻辑顺序。因为vector排序基于插入的完成方式——索引/下标排序。因为map它set基于密钥排序。因为multimap两者multiset兼而有之。对于unordered_map等，这种说法非常微不足道，但我仍然可以争论散列算法和冲突处理。

在逻辑排序中，您可以引用有序元素，但有时引用每个元素之间的边界是有意义的。从逻辑上讲（在某些情况下甚至是实现）这很方便......

|     |     |     |     |     |     |     |     |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| |
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ |
|     |     |     |     |     |     |     |     |
0     1     2     3     4     5     6     7     8

您决定零“界限”的位置独立于零项目的位置，但您总是得到一个简单的加法/减法关系。如果最小边界与最小元素编号相同，则最后一个边界比最后一个元素多一个编号。因此end，作为最后一个元素的过去。

在二叉树实现中，每个节点可以被认为有两个边界——元素的任一侧。在这个方案中，除了begin和之外的每个边界都end出现两次。您可以使用元素 0 的 RHS 或 LHS 或元素 1 来表示边界 1。因此，原则上您可以使用节点指针和标志。但是，您可能会在可能的情况下选择最方便的一种，而不是对大多数边界使用两种表示形式 - 您不仅指的是右边界，而且还指的是取消引用时想要查看的元素。这意味着该标志只会在引用时设置end，在这种情况下，无论如何您都不应该支持取消引用。

IOW 遵循这个逻辑告诉你，你真的不需要遵循这个逻辑，尽管我认为它仍然是一个有用的心理模型。您真正需要的只是end. 也许包含指向最终指针的指针（作为例如递减该迭代器的起点）对该表示很有用。也许在某些情况下，在内部使用伪迭代器来识别两个等效边界是不同的，这很方便。

考虑到例如多路树，其中每个节点都包含一组元素，出现了类似但略有不同的模型和选择。

基本上，我认为在心理上将绑定位置识别为不同但与项目位置相关是很有用的，但是这种心理模型不应限制您的实现选择——它可能会激发替代方案，但它只是一个心理模型。

于 2014-11-20T16:24:55.767 回答