在阅读Eric Niebler的时候 范围提案,
我遇到过哨兵一词,作为最终迭代器的替代品。
我很难理解哨兵对末端迭代器的好处。
有人能提供一个明确的例子,说明发送给表的内容是不能用标准迭代器对完成的吗?
“一个 哨兵 是一个过去的迭代器的抽象。哨兵是
可用于表示范围结束的常规类型。一个
sentinel和表示范围的迭代器应为EqualityComparable。
当迭代器i比较等于时,sentinel表示一个元素
哨兵,我指向那个元素。“ - N4382
我认为哨兵在确定范围的结束时起着作用,而不仅仅是位置?
Sentinel只允许结束迭代器具有不同的类型。
在过去的迭代器上允许的操作是有限的,但这并没有反映在它的类型中。这不好 *
一个 .end()
迭代器,但编译器会让你。
哨兵没有一元解除引用,或 ++
, 除其他事项外。它通常受限于一个超过结束迭代器的最弱迭代器,但在编译时强制执行。
有一个回报。经常检测到最终状态比找到它更容易。有哨兵, ==
可以在编译时调度“检测其他参数是否超过结束”,而不是运行时间。
结果是,一些过去比C等效慢的代码现在编译为C级速度,例如使用复制空终止字符串 std::copy
。如果没有哨兵,你要么必须扫描以在复制之前找到结束,要么传入带有bool标志的迭代器,说“我是最终的哨兵”(或等效的),并检查它 ==
。
使用基于计数的范围时,还有其他类似的优点。另外,像拉链范围这样的东西1 变得更容易表达(结束zip哨兵可以保存两个源哨兵,如果任何一个哨兵做,则返回相等:zip迭代器要么只比较第一个迭代器,要么比较两者)。
另一种思考方式是算法倾向于不使用迭代器概念的完全丰富性作为过去的迭代器传递的参数,并且迭代器在实践中以不同的方式处理。 Sentinel意味着调用者可以利用这一事实,这反过来又让编译器更容易利用它。
1 拉链范围是从2个或更多范围开始时获得的拉链范围,并将它们像拉链一样“拉链”在一起。范围现在超过了各个范围元素的元组。推进zip迭代器可以推进每个“包含”的迭代器,同样可以解除引用和比较。
Sentinel只允许结束迭代器具有不同的类型。
在过去的迭代器上允许的操作是有限的,但这并没有反映在它的类型中。这不好 *
一个 .end()
迭代器,但编译器会让你。
哨兵没有一元解除引用,或 ++
, 除其他事项外。它通常受限于一个超过结束迭代器的最弱迭代器,但在编译时强制执行。
有一个回报。经常检测到最终状态比找到它更容易。有哨兵, ==
可以在编译时调度“检测其他参数是否超过结束”,而不是运行时间。
结果是,一些过去比C等效慢的代码现在编译为C级速度,例如使用复制空终止字符串 std::copy
。如果没有哨兵,你要么必须扫描以在复制之前找到结束,要么传入带有bool标志的迭代器,说“我是最终的哨兵”(或等效的),并检查它 ==
。
使用基于计数的范围时,还有其他类似的优点。另外,像拉链范围这样的东西1 变得更容易表达(结束zip哨兵可以保存两个源哨兵,如果任何一个哨兵做,则返回相等:zip迭代器要么只比较第一个迭代器,要么比较两者)。
另一种思考方式是算法倾向于不使用迭代器概念的完全丰富性作为过去的迭代器传递的参数,并且迭代器在实践中以不同的方式处理。 Sentinel意味着调用者可以利用这一事实,这反过来又让编译器更容易利用它。
1 拉链范围是从2个或更多范围开始时获得的拉链范围,并将它们像拉链一样“拉链”在一起。范围现在超过了各个范围元素的元组。推进zip迭代器可以推进每个“包含”的迭代器,同样可以解除引用和比较。
Sentinels和end迭代器类似,它们标记范围的结束。它们在如何检测到这一点方面存在差异;要么是在测试迭代器本身,要么是在迭代器上测试数据值。如果您已经对数据进行了测试,则哨兵可以允许您的算法“免费”完成,无需任何其他测试。这可以简化代码,也可以加快代码。
一个非常常见的标记是用于标记字符串结尾的零字节。没有必要为字符串的末尾保留单独的迭代器,可以在处理字符串本身的字符时确定它。此约定的缺点是字符串不能包含零字符。
请注意,我在阅读链接中的提案之前写了这个答案;这是哨兵的经典定义,可能与那里提出的定义不一致。
引入标记的主要动机是有很多迭代器操作被支持但通常从不需要最终迭代器 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库所做的。