c++ - 如何处理多个迭代器类型

Question

我有一个自定义数据结构，可以通过多种方式访问​​。我想尽量使这个数据结构尽可能符合 STL 标准。所以我已经有了很多 typedef，它们为模板参数提供了 STL 名称。到目前为止，这对我来说一切如常。

但是我不太确定如何正确地将迭代器添加到我的数据结构中。我面临的主要问题是，数据结构上会有多个迭代策略。最简单的用例是遍历所有元素，这将由数据结构上符合 STL 的迭代器很好地处理。然而，人们可能还想访问在某种程度上类似于给定键的元素。我还想以一种可以与 STL 交互的方式遍历所有这些相似的元素。

这些是我到目前为止想到的想法:

• 只提供一种类型的迭代器:

这基本上就是 std::map 所做的。子范围的开始和结束迭代器由 std::map::lower_bound() 和 std::map::upper_bound() 提供。

但是这很好用，因为 begin()、end()、lower_bound() 和 upper_bound 返回的迭代器() 是兼容的，即可以为 operator==() 赋予非常明确的含义。在我的例子中，这很难做到正确，甚至可能无法给出一些清晰的语义。例如，我可能会遇到 it1==it2 但 ++it1!=++it2 的情况。我不确定 STL 是否允许这样做。

• 提供多种类型的迭代器:

更容易提供干净的 operator==() 语义。另一方面很讨厌，因为它增加了类型的数量。

• 提供一种类型的迭代器并使用 STL::algorithms 进行专门访问

我不确定这是否可能。迭代器应该以某种方式(直接或在备忘录中)保存迭代状态。使用这种方法意味着特化所有 STL::algorithms 并直接在特化中访问谓词。很可能是不可能的，如果可能的话，这是一个非常糟糕的主意。

现在我主要选择版本 1，即只提供一种类型的迭代器。但是由于我不清楚如何清理语义，所以我还没有决定。

你会如何处理？

Answer 1

标准容器支持两种迭代策略和两种迭代器类型:::iterator 和 ::reverse_iterator。您可以使用 std::reverse_iterator 的构造函数及其成员函数 base() 在两者之间进行转换。

根据迭代策略的相似程度，提供到不同迭代器类型的转换可能容易也可能不容易。这个想法是结果应该指向目标类型的迭代策略中的“等效位置”。对于反向迭代器，这种等价性是这样定义的:如果你在那个点插入，结果是相同的。因此，如果 rit 是反向迭代器，vec.insert(rit.base(), ...) 会在 rit“之前”插入一个元素在反向迭代中，也就是说在容器中rit 指向的元素之后。这是非常棘手的，并且只会在迭代策略完全不相关时变得更糟。但是，如果您的所有迭代器类型都是(或可以看起来像)遍历所有元素的“普通”迭代器的包装器，那么您可以根据该底层迭代器位置定义转换。

如果有添加或删除容器元素的成员函数，您实际上只需要转换，因为您可能不想为每个迭代器类型提供单独的重载(就像标准容器不为反向迭代器定义 insert 和 erase)。如果迭代器仅用于指向元素，那么您很可能不需要它们。

如果不同的迭代策略都以正常顺序迭代元素的子集，那么请查看 boost::filter_iterator。

I probably would get some cases where it1==it2 but ++it1!=++it2. I am not sure if this is allowed by the STL.

如果我理解正确，你从 thing.normal_begin() 开始得到 it1，从 开始得到 it2 >thing.other_policy_begin()。标准容器没有定义比较属于不同范围的相同类型的迭代器的结果，所以如果你确实使用了一个通用类型，那么我认为这会很好，只要文档清楚地表明虽然 operator == 确实有效，范围根据迭代器的来源而分开。

例如，您可以有一个 skip_iterator，它将每次调用 ++ 时应向前​​移动的步数作为构造函数参数。然后您可以在比较中包含该整数，以便 thing.skip_begin(1) != thing.skip_begin(2)，或者您可以排除它以便 thing.skip_begin(1 ) == thing.skip_begin(2) 但是 ++(++(thing.skip_begin(1))) ==++(thing.skip_begin(2))。我认为只要有记录就可以，或者你可以记录比较它们是 UB，除非它们来自相同的起点。