17

在阅读 Eric Niebler 的范围提案时，
我遇到了哨兵一词作为结束迭代器的替代品。
我很难理解哨兵相对于结束迭代器的好处。
有人可以提供一个清晰的例子来说明哨兵带来的标准迭代器对无法完成的事情吗？

“哨兵是结束迭代器的抽象。哨兵是常规类型，可用于表示范围的结束。哨兵和表示范围的迭代器应为 EqualityComparable。哨兵表示一个元素，当迭代器 i 比较等于哨兵，并且 i 指向那个元素。” -- N4382

我认为哨兵作为确定范围结束的功能，而不仅仅是位置？

4

3 回答 3

16

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

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

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

有回报。通常检测最终状态比找到它更容易。使用哨兵，==可以在编译时而不是运行时分派以“检测另一个参数是否超过结尾”。

结果是一些过去比 C 等效代码慢的代码现在编译到 C 级速度，例如使用std::copy. 如果没有哨兵，您要么必须扫描以找到副本之前的结尾，要么传入带有布尔标志的迭代器，上面写着“我是末端哨兵”（或等效），然后在==.

使用基于计数的范围时还有其他类似的优点。此外，诸如 zip 范围1之类的东西变得更容易表达（末端 zip 哨兵可以同时保存两个源哨兵，并且如果其中一个哨兵存在则返回相等：zip 迭代器要么只比较第一个迭代器，要么比较两者）。

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

1一个 zip range 是当您从 2 个或多个 range 开始时得到的，然后像拉链一样将它们“压缩”在一起。该范围现在位于各个范围元素的元组之上。推进一个 zip 迭代器推进每个“包含”的迭代器，同样用于解引用和比较。

于 2015-10-02T08:07:16.083 回答
3

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

相比之下，of 的主要用途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（以获得计数范围）
  • 遇到a 时停止\0，即*it = '\0'（用于循环 C 字符串）
  • 到 12 点时停止（吃午饭），依此类推。

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

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

于 2017-09-22T01:01:56.313 回答
3

哨兵和结束迭代器的相似之处在于它们标记了范围的结束。它们的不同之处在于如何检测到这一端。您正在测试迭代器本身，或者您正在测试迭代器的数据值。如果您已经在对数据执行测试，则哨兵可以让您的算法“免费”完成，而无需任何额外的测试。这可以简化代码，或者使其更快。

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

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

于 2015-10-02T04:37:39.167 回答