哨兵和结束迭代器有什么区别？

Question

在阅读 Eric Niebler 的 range proposal、
我遇到了术语哨兵作为结束迭代器的替代。
我很难理解 sentinel 相对于结束迭代器的好处。
有人可以提供一个明确的例子，说明 senintel 给 table 带来的是标准迭代器对无法完成的事情吗？

"A sentinel is an abstraction of a past-the-end iterator. Sentinels are Regular types that can be used to denote the end of a range. A sentinel and an iterator denoting a range shall be EqualityComparable. A sentinel denotes an element when an iterator i compares equal to the sentinel, and i points to that element." -- N4382

我认为 sentinel 的作用是确定范围的结束，而不仅仅是位置？

Answer 1

哨兵和结束迭代器的相似之处在于它们标记范围的结束。它们的不同之处在于如何检测到这一端；您要么在测试迭代器本身，要么在迭代器上测试数据值。如果您已经在对数据执行测试，哨兵可以让您的算法完成 "for free" 而无需任何其他测试。这可以简化代码，或使其更快。

一个非常常见的标记是用于标记字符串结尾的零字节。不需要为字符串的末尾保留一个单独的迭代器，它可以在您处理字符串本身的字符时确定。此约定的缺点是字符串不能包含零字符。

请注意，我在阅读 link 中的提案之前写了这个答案；这是哨兵的经典定义，可能与那里提出的定义不一致。

Answer 2

Sentinel 只是允许结束迭代器具有不同的类型。

尾后迭代器允许的操作是有限的，但这没有反映在它的类型中。 * 一个 .end() 迭代器是不行的，但是编译器会让你。

哨兵没有一元取消引用，或者 ++，等等。它通常与结束迭代器之后的最弱迭代器一样受到限制，但在编译时强制执行。

有回报。通常检测最终状态比找到它更容易。使用哨兵，== 可以在编译时分派到 "detect if the other argument is past the end"，而不是运行时间。

结果是一些过去比 C 等效代码慢的代码现在可以编译到 C 级别的速度，例如使用 std::copy 复制空终止字符串。如果没有哨兵，您要么必须扫描以找到副本之前的结尾，要么传入带有 bool 标志的迭代器 "I am the end sentinel"（或等效项），然后在 ==.

上检查它

使用基于计数的范围时，还有其他类似的优势。此外，像 zip ranges¹ 之类的东西变得更容易表达（结束 zip 哨兵可以包含两个源哨兵，并且 return 如果任一哨兵都相等：zip 迭代器要么只比较第一个迭代器，或比较两者）。

另一种思考方式是，算法往往不会在作为结束迭代器传递的参数上使用迭代器概念的全部丰富性，并且迭代器在实践中的处理方式不同。 Sentinel 意味着调用者可以利用这一事实，这反过来又让编译器更容易利用它。

¹ zip 范围是从 2 个或更多范围开始时得到的，"zip" 它们像拉链一样组合在一起。范围现在超过各个范围元素的元组。推进 zip 迭代器会推进每个 "contained" 迭代器，以及取消引用和比较。

Answer 3

引入哨兵的主要动机是有很多迭代器操作是受支持的，但通常不需要用于结束迭代器 end()。例如，通过 *end() 取消引用它、通过 ++end() 递增它几乎没有任何意义，依此类推 (*)。

相比之下，end() 的主要用途只是将它与迭代器 it 进行比较，以表明 it 是否在它刚刚迭代的事物的末尾.并且，像编程中一样，不同的需求和不同的应用程序建议使用一种新类型。

range-v3 库将这个观察变成了一个假设（通过一个概念实现）：它为 end() 引入了一个新类型并且只要求它与相应的迭代器是相等可比较的 - - 但不需要通常的迭代器操作）。这种新型 end() 被称为 sentinel。

这里的主要优点是获得了抽象和更好的关注点分离，基于此编译器可能能够执行更好的优化。在代码中，基本思路是这样的（这只是为了解释，与range-v3库无关）：

struct my_iterator;    //some iterator
struct my_sentinel
{
     bool is_at_end(my_iterator it) const
     {
         //here implement the logic when the iterator is at the end
     }
};

auto operator==(my_iterator it, my_sentinel s)  //also for (my_sentinel s, my_iterator it)
{
    return s.is_at_end(it); 
}

看到抽象了吗？现在，您可以在 is_at_end 函数中实现任何您想要的检查，例如：

永不停止（获得无限范围）
在 N 增量后停止（以获得计数范围）
遇到 [=21=] 时停止，即 *it = '[=22=]'（用于循环 C 字符串）
12 点钟停止（吃午饭），依此类推。

此外，关于性能，可以在检查中使用编译时间信息（例如，将上面的 N 视为编译时间参数）。在这种情况下，编译器可能能够更好地优化代码。

(*) 请注意，这并不意味着这种操作通常没有用。例如，--end() 在某些地方可能很有用，参见例如this question。然而，似乎可以在没有这些的情况下实现标准库——这就是 range-v3 库所做的。

哨兵和结束迭代器有什么区别？

What's the difference between a sentinel and an end iterator?

c++

iterator

range

sentinel

c++17