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

Question

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

23

在阅读Eric Niebler的范围提案时，我遇到了“sentinel”这个术语，它用来替代end迭代器。我很难理解sentinel相对于end迭代器的优势。能否给出一个清晰的示例说明sentinel带来的好处，而标准迭代器对此无法做到？

“sentinel是past-the-end迭代器的抽象。 Sentinel是Regular类型，可用于表示范围的结尾。一个表示范围的sentinel和迭代器应该具有相等比较运算符。当迭代器i与sentinel进行比较且i指向那个元素时，sentinel表示一个元素。”-- N4382

我认为sentinel作为函数在确定范围结尾方面的工作要比仅使用位置更加有效。

- Trevor Hickey

3个回答

5

引入哨兵的中心动机在于，有很多迭代器操作是支持的，但通常对于结束迭代器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 次增量后停止（以获取计数范围）
遇到 \0 时停止，即 *it = '\0'（用于循环遍历 C 字符串）
在 12 点（午餐时间）停止等。

此外，在性能方面，一个人可以利用编译时信息来进行检查（例如，将上面的 N 视为编译时参数）。在这种情况下，编译器可能能够更好地优化代码。

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

- davidhigh

4

哨兵和结束迭代器类似，它们都标记了一个范围的结尾。它们的不同之处在于如何检测结尾；你可以测试迭代器本身，也可以测试迭代器上的数据值。如果你已经对数据进行了测试，哨兵可以让你的算法“免费”完成，无需任何额外的测试。这可以简化代码或使其更快。

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

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

- Mark Ransom

4

在编写Python中所称的生成器（generator）代码时，它们也很有用。端点未知，可能无法确定（例如，使用istream_iterator包装套接字或管道，在此情况下，直到另一端关闭其写入句柄，您才会知道是否完成。）。哨兵描述了“完成状态”的逻辑状态，而不是特定定义的情景相关状态（例如，当迭代器达到 vector.begin()+vector.size() 时被视为完成）。 - ShadowRanger

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yakk - Adam Nevraumont · Accepted Answer

Sentinel 简单来说就是允许末尾迭代器具有不同的类型。

对于一个 past-the-end 迭代器，允许的操作是有限的，但这并没有反映在它的类型上。使用 * 操作符对 .end() 迭代器进行解引用是不正确的，但编译器会让你这么做。

sentinel 没有一元解引用或者 ++ 等操作符。通常它的限制与最弱的末尾迭代器相同，但是它在编译时被强制执行。

这样做是有好处的。通常检测结束状态比找到结束状态更容易。有了 sentinel，== 可以在编译时分派到“检测另一个参数是否已超过结束点”的代码，而不是运行时。

结果是，一些曾经比 C 语言版本慢的代码现在已经可以编译成与 C 相同的速度了，例如使用 std::copy 复制空终止字符串。如果没有 sentinel，您要么必须在复制之前扫描以查找结尾，要么传入带有布尔标志“我是结束标记”（或等效标记）的迭代器，并在 == 时进行检查。

在使用基于计数的范围时，还有其他类似的优点。此外，一些像 zip 范围这样的东西更容易表达（end zip sentinel 可以包含两个源 sentinel，并在任何一个 sentinel 相等时返回相等：zip 迭代器只比较第一个迭代器或同时比较两个迭代器）。

另一种思考方式是，算法往往不会在作为 past-the-end 迭代器传递的参数上使用迭代器概念的所有丰富性，而实际上处理该迭代器的方法完全不同。Sentinel 意味着调用者可以利用这一事实，从而使编译器更容易利用它。

¹ Zip 范围是当您从两个或更多范围开始并将其“拉链”在一起时得到的。该范围现在涵盖单个范围元素的元组。推进 zip 迭代器会推进每个“包含”的迭代器，反之亦然。