问题 哨兵和结束迭代器有什么区别?


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

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

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


8633
2017-10-02 04:28


起源



答案:


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

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

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

有一个回报。经常检测到最终状态比找到它更容易。有哨兵, == 可以在编译时调度“检测其他参数是否超过结束”,而不是运行时间。

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

使用基于计数的范围时,还有其他类似的优点。另外,像拉链范围这样的东西1 变得更容易表达(结束zip哨兵可以保存两个源哨兵,如果任何一个哨兵做,则返回相等:zip迭代器要么只比较第一个迭代器,要么比较两者)。

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


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


10
2017-10-02 08:07



拉链范围是什么? - Walter
@walter添加了脚注 - Yakk - Adam Nevraumont
嗯。但是zip解码器不能是RandomAccessIterator reference 与...不完全相同 value_type&。所以一些标准算法可能不起作用(正如你所说的那样) 你自己)。那有什么好处呢? - Walter
该提案正在改变标准。我不知道它是否解决了这个问题,但我确实记得有些讨论。 @walter - Yakk - Adam Nevraumont
@Walter我们对Ranges TS的使命是将概念引入STL,这是不可能的 一些 破损。因此,我们不像标准库的典型扩展那样受限制。这不是从第一原则重写的任务,但我们被允许打破一些事情,特别是当它意味着修复已经破坏的其他事情时。例如,代理迭代器。 - Casey


答案:


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

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

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

有一个回报。经常检测到最终状态比找到它更容易。有哨兵, == 可以在编译时调度“检测其他参数是否超过结束”,而不是运行时间。

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

使用基于计数的范围时,还有其他类似的优点。另外,像拉链范围这样的东西1 变得更容易表达(结束zip哨兵可以保存两个源哨兵,如果任何一个哨兵做,则返回相等:zip迭代器要么只比较第一个迭代器,要么比较两者)。

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


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


10
2017-10-02 08:07



拉链范围是什么? - Walter
@walter添加了脚注 - Yakk - Adam Nevraumont
嗯。但是zip解码器不能是RandomAccessIterator reference 与...不完全相同 value_type&。所以一些标准算法可能不起作用(正如你所说的那样) 你自己)。那有什么好处呢? - Walter
该提案正在改变标准。我不知道它是否解决了这个问题,但我确实记得有些讨论。 @walter - Yakk - Adam Nevraumont
@Walter我们对Ranges TS的使命是将概念引入STL,这是不可能的 一些 破损。因此,我们不像标准库的典型扩展那样受限制。这不是从第一原则重写的任务,但我们被允许打破一些事情,特别是当它意味着修复已经破坏的其他事情时。例如,代理迭代器。 - Casey


Sentinels和end迭代器类似,它们标记范围的结束。它们在如何检测到这一点方面存在差异;要么是在测试迭代器本身,要么是在迭代器上测试数据值。如果您已经对数据进行了测试,则哨兵可以允许您的算法“免费”完成,无需任何其他测试。这可以简化代码,也可以加快代码。

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

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


2
2017-10-02 04:37



当你编写Python中被称为生成器的代码时,它们也很有用。终点未知,可能无法知晓(例如, istream_iterator 包裹套接字或管道,在另一端关闭其写入句柄之前,您将不知道是否已完成。标记描述了“完整”的逻辑状态,而不是完整的情景依赖和特定定义(例如,当迭代器到达时完成 vector.begin() + vector.size())。 - ShadowRanger


引入标记的主要动机是有很多迭代器操作被支持但通常从不需要最终迭代器 end()。例如,通过解除引用它几乎没有任何意义 *end(),通过增加它 ++end(), 等等 (*)。

相比之下,主要用途 end() 仅仅是将它与迭代器进行比较 it 为了表明是否 it 它只是迭代的事情的最后。而且,与编程中的通常一样,不同的要求和不同的应用程序提出了一种新的类

range-v3库将这种观察转化为一种假设(通过概念实现):它引入了一种新的类型 end() 并且只要求它与相应的迭代器相等 - 但不需要通常的迭代器操作。这种新型 end() 被称为a 哨兵

这里的主要优点是获得的抽象和更好的关注点分离,基于此,编译器可能能够执行更好的优化。在代码中,基本思想是这个(这只是为了解释而与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库所做的。


0
2017-09-22 01:01