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

Question

在阅读Eric Niebler的范围提议时,
我遇到了哨兵一词,作为最终迭代器的替代品.
我很难理解哨兵对末端迭代器的好处.
有人可以提供一个明确的例子,说明发送到表中的内容是不能用标准迭代器对完成的吗？

" 哨兵是过去的迭代器的抽象.哨兵是常规类型,可用于表示范围的结束.表示范围的哨兵和迭代器应为EqualityComparable.哨兵表示一个元素.迭代器我比较等于哨兵,我指向那个元素." - N4382

我认为哨兵在确定范围的结束时起着作用,而不仅仅是位置？

Answer 1

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

在过去的迭代器上允许的操作是有限的,但这并没有反映在它的类型中.它不是确定*一个.end()迭代,但是编译器会放过你的.

哨兵没有一元解除引用,或者++除其他外.它通常受限于一个超过结束迭代器的最弱迭代器,但在编译时强制执行.

有回报.经常检测结束状态比找到它更容易.使用sentinel,==可以在编译时调度"检测其他参数是否超过结束",而不是运行时.

结果是,一些过去比C等效慢的代码现在编译为C级速度,例如使用复制空终止字符串std::copy.如果没有哨兵,你要么必须扫描以在复制之前找到结束,要么传入带有bool标志的迭代器,说"我是最终的哨兵"(或等效物),并检查它==.

使用基于计数的范围时,还有其他类似的优点.此外,一些像zip范围¹这样的东西变得更容易表达(结束zip的标记可以保存两个源标记,并且如果任何一个标记执行,则返回相等:zip迭代器要么只比较第一个迭代器,要么比较两者).

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

¹拉链范围是从2个或更多范围开始时所获得的,并将它们像拉链一样"拉链"在一起.范围现在超过了各个范围元素的元组.推进一个zip迭代器推进每个"包含"的迭代器,并同样用于解除引用和比较.

Answer 2

引入哨兵的核心动机是有很多迭代器操作受支持，但通常不需要最终迭代器end()。例如，通过 取消引用它*end()、通过 递增它++end()等等几乎没有任何意义 (*)。

相比之下， 的主要用法end()仅仅是将其与迭代器进行比较it，以表明 是否it位于刚刚迭代的事物的末尾。而且，与编程中的惯例一样，不同的需求和不同的应用程序会提出新的类型。

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

这里的主要优点是获得了抽象和更好的关注点分离，基于此编译器可能能够执行更好的优化。在代码中，基本思想是这样的（这只是为了解释，与 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（以获得计数范围）
• \0当遇到a 时停止，即*it = '\0'（用于循环 C 字符串）
• 12点就停下来（吃午饭），等等。

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

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