哨兵节点如何提供优于 NULL 的好处? [英] How does a sentinel node offer benefits over NULL?
问题描述
在 哨兵节点维基百科页面上，它说哨兵节点相对于 NULL 的好处是:
On the Sentinel Node wikipedia page it says that the benefits of a sentinel node over NULL are :
- 提高操作速度
- 减少算法代码大小
- 增强了数据结构的稳健性(可以说是).
我真的不明白对哨兵节点的检查如何更快(或者如何在链表或树中正确实现它们)，所以我想这更多是一个两部分的问题:
I don't really understand how the checks against a sentinel node would be faster (or how to properly implement them in a linked list or tree), so I suppose this is more of a two part question:
- 是什么让哨兵节点成为比 NULL 更好的设计?
- 您将如何在(例如)列表中实现哨兵节点?
推荐答案
如果您只是进行简单的迭代而不查看元素中的数据，那么使用哨兵就没有任何优势.
There's no advantage with sentinels if you're just doing simple iteration and not looking at the data in the elements.
但是，将其用于查找"类型算法时会获得一些实际收益.例如，想象一个链表列表 std::list，您想在其中查找特定值 x.
However, there's some real gain when using it for "find" type algorithms. For example, imagine a linked list list std::list where you want to find a specific value x.
没有哨兵你会做什么:
for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
if (*i == x) // second branch here
return i;
}
return list.end();
但是有了哨兵(当然，end 实际上必须是一个真正的节点……):
But with sentinels (of course, end actually has to be a real node for this...):
iterator i=list.begin();
*list.end() = x;
while (*i != x) // just this branch!
++i;
return i;
您看到不需要额外的分支来测试列表的末尾 - 该值始终保证在那里，因此如果 x，您将自动返回 end() 在您的有效"元素中找不到.
You see there's no need for the additional branch to test for the end of the list - the value is always guaranteed to be there, so you will automatically return end() if x cannot be found in your "valid" elements.
对于另一个很酷且实际有用的哨兵应用程序，请参阅intro-sort"，这是大多数 std::sort 实现中使用的排序算法.它有一个很酷的分区算法变体，它使用哨兵来删除一些分支.
For another cool and actually useful application of sentinels, see "intro-sort", which is the sorting algorithm that's used in most std::sort implementations. It has a cool variant of the partition algorithm that uses sentinels to remove a few branches.
这篇关于哨兵节点如何提供优于 NULL 的好处?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
