c++ - 我应该使用什么 STL 容器来行走一棵树？

Question

我不知道双向是否意味着我可以编写 rbegin() 或者我是否可以减少迭代器。

我有一棵只向前的树，这不是问题。我想走它是。我现在正在做的是每次我访问一个分支时我都会推送 current_iterator。现在的问题是我正在遍历一个分支并调用一个函数。该函数需要访问列表中的先前节点。

所以我写了 it=current_iterator 并打算写 --it 来倒带。作为一个快速测试，我写了 --o.begin()==o.end() 看看我是否能做到这一点。我遇到断言错误。

我正在使用双端队列。我可以使用什么容器允许我在迭代器上编写 = ，在迭代过程中前进和后退？似乎我还需要保留 o 的拷贝，以便我可以比较 .begin() 和 .end()。推荐的容器和技术是什么？

Answer 1

双端队列迭代器是随机访问的。您可以递增和递减它们。

问题可能是您试图递减 begin 返回的迭代器。这样做并不能保证给你列表的末尾——双端队列不是循环的。 (我认为这是未定义的行为，所以它可以给你结束，但我怀疑任何实现实际上都是那样做的。)

换句话说，您对是否可以递减迭代器的测试不是有效测试；您从中得出的不能递减迭代器的结论也是无效的。您可以递减任何有效的双端队列迭代器，只要新位置也有效即可。