哨兵节点如何提供优于 NULL 的好处?

2021-12-22 00:00:00 algorithm data-structures c++

在 哨兵节点维基百科页面上，它说哨兵节点相对于 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:

  1. 是什么让哨兵节点成为比 NULL 更好的设计?
  2. 您将如何在(例如)列表中实现哨兵节点?

推荐答案

如果您只是进行简单的迭代而不查看元素中的数据，那么使用哨兵就没有任何优势.

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.

相关文章