由网友(^.^你给了她一个肩膀~)分享简介：在前哨淋巴结维基百科页面它说，在空前哨淋巴结的好处是：在操作速度提高降低算法code尺寸在提高数据结构的鲁棒性（可以说）。我真的不知道如何对前哨淋巴结的检查将会更快（或如何正确地实现他们在一个链表或树），所以我想这更多的是一个问题的两个部分：是什么原因导致了前哨淋巴结比空？更好的设计在（例如）的列表，你将如何实现...

在前哨淋巴结维基百科页面它说，在空前哨淋巴结的好处是：

在操作速度提高 降低算法code尺寸 在提高数据结构的鲁棒性（可以说）。

我真的不知道如何对前哨淋巴结的检查将会更快（或如何正确地实现他们在一个链表或树），所以我想这更多的是一个问题的两个部分：

是什么原因导致了前哨淋巴结比空？更好的设计 在（例如）的列表，你将如何实现一个前哨淋巴结？ 解决方案

有没有优势，如果你只是做简单的重复，而不是在寻找中的元素进行数据的哨兵。

然而，当使用它的发现类型的算法是一些真正的收获。例如，假设一个链接列表清单的std ::列表要找到一个特定的值 X 。

你会做什么，而不哨兵是：

 的（迭代器I = list.begin（！）; I = list.end（）; ++ I）//先在这里支
{
  如果（*我== X）//第二支在这里
    返回我;
}
返回list.end（）;
 

但随着哨兵（当然，实际上到底有是这是一个真正的节点...）：

 迭代器I = list.begin（）;
* list.end（）= X;

而（* I！= X）//只是这个分支！
  ++我;

返回我;
 

您看有没有需要额外的分支来测试列表的末尾 - 值总是保证在那里，所以你会自动返回端（）如果 X 不能在您的有效的元素被发现。

有关哨兵的另一个很酷，实际上有用的应用程序，请参见介绍排序，这是在大多数的std ::使用排序实现排序算法。它具有使用哨兵删除几根树枝分割算法的一个很酷的变种。

On the Sentinel Node wikipedia page it says that the benefits of a sentinel node over NULL are :

Increased speed of operations Reduced algorithmic code size Increased data structure robustness (arguably).

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:

What causes the sentinel node to be a better design than NULL? How would you implement a sentinel node in (for example) a list?

解决方案

There's no advantage with sentinels if you're just doing simple iteration and not looking at the data in the elements.

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.

What you would do without sentinels is:

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
  if (*i == x) // second branch here
    return i;
}
return list.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;

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.

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.