C++ 哨兵节点如何提供优于 NULL 的好处？

How does a sentinel node offer benefits over NULL?

提问by spbots

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

在哨兵节点维基百科页面上，它说哨兵节点相对于 NULL 的好处是：

• 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:

我真的不明白对哨兵节点的检查如何更快（或如何在链表或树中正确实现它们），所以我想这更多是一个两部分的问题：

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

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

采纳答案by ltjax

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::listwhere you want to find a specific value x.

但是，将它用于“查找”类型的算法时会有一些真正的收获。例如，想象一个链表列表std::list，您想在其中查找特定值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...):

但是有了哨兵（当然， end 实际上必须是一个真正的节点……）：

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 xcannot be found in your "valid" elements.

您会看到不需要额外的分支来测试列表的末尾 - 该值始终保证在那里，因此end()如果x在您的“有效”元素中找不到，您将自动返回。

For another cool and actually useful application of sentinels, see "intro-sort", which is the sorting algorithm that's used in most std::sortimplementations. It has a cool variant of the partition algorithm that uses sentinels to remove a few branches.

有关哨兵的另一个很酷且实际有用的应用程序，请参阅“intro-sort”，这是大多数std::sort实现中使用的排序算法。它有一个很酷的分区算法变体，它使用哨兵来删除一些分支。

回答by 6502

I think that a little code example would be a better explanation than a theoretic discussion.

我认为一个小代码示例比理论讨论更好。

The following is the code for node deletion in a doubly-linked list of nodes where NULLis used to mark the end of the list and where two pointers firstand lastare used to hold the address of first and last node:

以下是在节点的双向链表节点删除代码，其中NULL用于标记列表的结束和两个指针first和last用于保持第一和最后一个节点的地址：

// Using NULL and pointers for first and last
if (n->prev) n->prev->next = n->next;
        else first = n->next;
if (n->next) n->next->prev = n->prev;
        else last = n->prev;

and this is the same code where instead there is a special dummy node to mark the end of the list and where the address of first node in the list is stored in the nextfield of the special node and where the last node in the list is stored in the prevfield of the special dummy node:

这是相同的代码，其中有一个特殊的虚拟节点来标记列表的末尾，列表中第一个节点的地址存储在next特殊节点的字段中，列表中的最后一个节点存储在其中在prev特殊虚拟节点领域：

// Using the dummy node
n->prev->next = n->next;
n->next->prev = n->prev;

The same kind of simplification is also present for node insertion; for example to insert node nbefore node x(having x == NULLor x == &dummymeaning insertion in last position) the code would be:

节点插入也存在同样的简化；例如在节点n之前插入节点x（在最后一个位置插入x == NULL或x == &dummy意味着插入）代码将是：

// Using NULL and pointers for first and last
n->next = x;
n->prev = x ? x->prev : last;
if (n->prev) n->prev->next = n;
        else first = n;
if (n->next) n->next->prev = n;
        else last = n;

and

和

// Using the dummy node
n->next = x;
n->prev = x->prev;
n->next->prev = n;
n->prev->next = n;

As you can see the dummy node approach removed for a doubly-linked list all special cases and all conditionals.

正如您所看到的，双链表的所有特殊情况和所有条件都删除了虚拟节点方法。

The following picture represents the two approaches for the same list in memory...

下图表示内存中相同列表的两种方法......

回答by Paul R

The answer to your question (1) is in the last sentence of the linked Wikipedia entry: "As nodes that would normally link to NULL now link to "nil" (including nil itself), it removes the need for an expensive branch operation to check for NULL."

您的问题 (1) 的答案在链接的维基百科条目的最后一句话中：“作为通常链接到 NULL 的节点现在链接到“nil”（包括 nil 本身），它消除了对昂贵的分支操作的需要检查 NULL。”

Normally you need to test a node for NULL before accessing it. If instead you have a valid nilnode then you don't need to do this first test, saving a comparison and a conditional branch, which can otherwise be expensive on modern superscalar CPUs when the branch is mis-predicted.

通常，您需要在访问节点之前测试节点是否为 NULL。相反，如果你有一个有效的nil节点，那么你不需要做这个第一次测试，保存一个比较和一个条件分支，否则当分支被错误预测时，这在现代超标量 CPU 上可能会很昂贵。

回答by J T

I will try to answer in the context of the standard template library:

我将尝试在标准模板库的上下文中回答：

1) In a call to "next()", NULL does not necessarily indicate end-of-list. What if a memory error occurred? Returning a sentinel node, is a definitive way to indicate that end-of-list had occurred, and not some other outcome. In other words, NULL could indicate a variety of things, not just end-of-list.

1) 在对“next()”的调用中，NULL 不一定表示列表结束。如果发生内存错误怎么办？返回一个哨兵节点，是一种明确的方式来表明已经发生了列表末尾，而不是其他一些结果。换句话说，NULL 可以表示各种事物，而不仅仅是列表的结尾。

2) This is just one possible method: when you create your list, create a private node that is not shared outside of the class (called "lastNode" for instance). Upon detecting that you have iterated to the end of the list, have "next()" return a reference to "lastNode". Also have a method called "end()" return a reference to "lastNode". Lastly, depending on how you implement your class, you might need to override the comparison operator for this to work properly.

2）这只是一种可能的方法：当您创建列表时，创建一个不在类外部共享的私有节点（例如称为“lastNode”）。在检测到您已迭代到列表末尾后，让“next()”返回对“lastNode”的引用。还有一个名为“end()”的方法返回对“lastNode”的引用。最后，根据您实现类的方式，您可能需要覆盖比较运算符才能正常工作。

Example:

例子：

class MyNode{

};

class MyList{

public:
    MyList () : lastNode();

    MyNode * next(){

       if (isLastNode) return &lastNode;
       else return //whatever comes next
    }

    MyNode * end() {

       return &lastNode;
    }

    //comparison operator
    friend bool operator == (MyNode &n1, MyNode &n2){

        return (&n1 == &n2); //check that both operands point to same memory
    }


private:
    MyNode lastNode;
};


int main(){

  MyList list;
  MyNode * node = list.next();

  while ( node != list.end() ){ 

     //do stuff!

     node = list.next();
  }

  return 0; 
}

回答by Han XIAO

Let's first set aside sentinel. In terms of code complexity, for the answer in ltjax, he provides us with the code

我们先把哨兵放在一边。在代码复杂度方面，对于ltjax中的答案，他给我们提供了代码

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
  if (*i == x) // second branch here
    return i;
}
return list.end();

The code can be better formed as:

代码可以更好地形成为：

auto iter = list.begin();
while(iter != list.end() && *iter != x)
    ++iter;
return iter;

Because of the cluttered(grouped) loop termination condition, one can easily see the loop termination condition without remembering all loop termination condition when going through the loop body to reason about correctness, and type less. Be aware of the bool circuit here though.

由于杂乱（分组）循环终止条件，在遍历循环体以推理正确性时，无需记住所有循环终止条件，就可以轻松看到循环终止条件，并且键入更少。不过要注意这里的 bool 电路。

The point is that the sentinel used in here is not for reduced code complexity, but it helps us to reduce index checking in each loop. For linear search, we begin with checking if the index is with valid range, and if in, then check if the value is what we want, without the use of sentinel. But with sentinel which is placed at the end with desired value, we can dispense with index boundary checking, but only check the value, since the loop is guaranteed to terminate. This belongs to sentinel controlled loop: repeat until the desired value is seen.

重点是这里使用的哨兵不是为了降低代码复杂度，而是帮助我们减少每个循环中的索引检查。对于线性搜索，我们首先检查索引是否在有效范围内，如果在，则检查该值是否是我们想要的，而不使用哨兵。但是对于以期望值放在末尾的哨兵，我们可以免除索引边界检查，而只检查值，因为循环保证终止。这属于哨兵控制循环：重复直到看到所需的值。

Recommend reading: Introduction to algorithms,third edition, and if you have pdf format, just search for the keyword sentinel to have it all. In fact, This example is so concise and intriguing. Discussions on how to hunt for an elephant and Elephant in Cairo may interest you. Of course I am not talking about hunting elephants in real.

推荐阅读：算法导论第三版，如果你有pdf格式，搜索关键词sentinel就可以了。事实上，这个例子是如此简洁和耐人寻味。关于如何在开罗寻找大象和大象的讨论可能会让您感兴趣。当然，我不是在谈论真正的狩猎大象。