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


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

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

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


8633
now


起源



答案:


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 拉链