如何处理多种迭代器类型

Question

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

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

到目前为止，这些是我考虑过的想法：

• 仅提供一种类型的迭代器：

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

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

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

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

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

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

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

你会如何处理这个问题？

Answer 1

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

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

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

如果不同的迭代策略都按正常顺序对元素子集进行迭代，则查看 boost::filter_iterator。

我可能会遇到 it1==it2 但 ++it1!=++it2 的情况。我是
不确定 STL 是否允许这样做。

如果我理解正确的话，你从 thing.normal_begin() 开始得到 it1，从 thing 开始得到 it2。 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 除非它们来自相同的起点。

Answer 2

为什么更多类型会成为问题？它并不一定意味着更多的代码。例如，您可以使您的迭代器类型模板采用迭代策略作为模板参数。然后，迭代策略可以提供迭代的实现：

struct iterate_all_policy {
    iterate_all_policy(iterator<iterate_all_policy> & it) : it(it) {}

    void advance() { /* implement specific advance here */ }
private:
    iterator<iterate_all_policy> & it;
}

您可能必须使迭代策略类成为迭代器类型的朋友。