一般结束迭代器与容器`end()`的可递减要求

Question

我正在研究ReversibleContainer及其关联的LegacyRandomAccessIterators。它们包装了一个预先存在的数据结构，该结构表示一个可直接索引的对象集合。我决定允许迭代器独立存在，并使默认构造的迭代器代表“结束”：

// constructs an iterator that provides a view of 'data'
the_iterator (thedata *data, difference_type index = 0);

// constructs an iterator representing the end
the_iterator ();

所以我可以做例如：

std::for_each(the_iterator(data), the_iterator(), ...);

迭代器完成所有工作。容器非常轻巧。我实现了容器begin()，end()就像这样：

struct the_container {
    the_data *data; // <- object wrapped by this container
    the_iterator begin () { return the_iterator(data); }
    the_iterator end () { return the_iterator(); }
};

我让它工作得很好，但在测试中我意识到我搞砸了，它不符合基本的容器要求，因为：

• 事实证明，对于具有双向迭代end()器的容器，当容器非空时需要返回一个可递减的迭代器，但是
• 我默认构造的结束迭代器不存储有关 any 的任何信息thedata，因此它不能递减，因为它不知道任何特定集合的“最后一个元素”是什么。

所以我现在必须修理容器。我正在考虑的解决方案是（让data->number_of_items包含项目数）：

• 继续允许默认构造的迭代器表示“结束”。
• 也让the_iterator(data, data->number_of_items)代表“结束”，符合容器要求。这个迭代器是可递减的。

然后容器会做：

struct the_container {
    the_data *data; // <- object wrapped by this container
    the_iterator begin () { return the_iterator(data, 0); }
    the_iterator end () { return the_iterator(data, data->number_of_items); }
};

现在，这很好，它满足了所有Container要求。但是，我现在想知道是否允许我的默认构造迭代器存在。

那么，我的问题是：虽然Container对其返回的迭代器提出了可递减性要求，但end()对于仅表示某些数据的“结束”但不涉及容器的 的迭代器是否有类似的要求end()？

更正式地，如果：

• j 是一个双向迭代器
• container.empty() == false
• ( j == container.end() ) == true

那么是否--j需要有效并且需要最终指向容器的最后一个元素？在我的情况下，这种情况的一个例子是：

the_container container(data); // <- assume data->number_of_items > 0
the_iterator b = container.begin();
the_iterator e = container.end();
the_iterator j;

assert(container.empty() == false);
assert(e == j);
assert(distance(b, e) == distance(b, j));

-- e;  // <- this is required to be well-defined
-- j;  // <- but is this??

所以，是的，这就是我的问题。我担心，也许在 eg 中的某些实现<algorithm>可能会假设我的“结束”迭代器之一是可递减的，或者我正在破坏一些我不理解的微妙内容。

Answer 1

作为框架挑战，您在这里拥有的是一个哨兵。哨兵是您可以将迭代器与之进行比较的东西，但它不是迭代器。

激励示例是一种类型，当与 char 指针进行比较时，它只检查 char 指针的取消引用是否为空。您可以使用它来编写 C 级“读取字符串直到为空”，同时仍然使用for(:)循环等。

基于远程的for(:)循环得到了增强，以允许开始和结束具有不同的类型，以允许哨兵存在并最大限度地提高效率。

考虑用 end sentinal 替换默认构造的迭代器技巧。这不适用于许多 pre-ranges-v2 算法，但至少你正在尝试和真实的模式。

不，我不认为您的最终迭代器违反了规则。例如，==在标准下，来自两个容器的迭代器可能会产生无意义的结果。您的最终迭代器可以被视为来自具有可预测==行为的另一个容器的迭代器。

现在，当你将它传递给算法时会发生什么？这可能会使您的程序格式错误；该算法可以检测您提供的特征保证，并且您的假结束迭代器不是与开始迭代器位于同一容器中的有效双向迭代器。