c++ - 集合数据结构中应该返回的 end() 迭代器是什么？

Question

这确实是编程硬件，但我不是要代码，而是当我调用迭代器函数 end() 时我想返回什么？最大值/最右设置节点？

我相信对于 begin()，我们只是得到了 root 的迭代器，对，因为它是我们输入的第一件事。

同样对于这个 Set Data Structure 迭代器中的 operator++，我们只是要根据从根开始的树的遍历来增加迭代器？

感谢您的帮助。

Answer 1

传统上end()返回结构末尾的一个过去。否则，您将无法使用current != end()循环遍历整个结构。std::vector 就是这种情况，但是对于更复杂的数据结构，迭代器更复杂。但是您应该始终能够end()通过使用operator++指向可迭代结构中最终元素的迭代器来访问。

您不能取消引用end()元素，这通常是未定义的行为。

Answer 2

如果你自己实现数据结构，你可以决定什么end()意思。它必须是一个正确类型的迭代器，并且是一个可以与将普通迭代器递增到集合中最后一个元素之外的结果相匹配的值。因为集合中的迭代器是双向的，所以您返回的特定值需要能够走到集合中的前一个值。

一种常见的方法是在容器中使用一个哨兵节点，该节点保存指向数据结构中第一个和最后一个元素的指针，并使用指向该节点的迭代器（不包含正确的值）作为end()迭代器。

在 的情况下begin()，它不代表树根的值，而是最小的值，所以它将是树中最左边的节点。