在Sentinel Node Wikipedia页面上,它说到一个哨兵节点优于NULL的好处是:
我真的不了解针对哨兵节点的检查会更快(或如何在链接列表或树中正确实施检查),所以我想这更多是一个两部分的问题:
如果仅执行简单的迭代而不查看元素中的数据,则哨兵没有任何优势。
但是,将其用于“查找”类型算法时会获得一些实际收益。例如,假设std::list您想在其中找到特定值的链表列表x。
std::list
x
如果没有哨兵,您将要做的是:
for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here { if (*i == x) // second branch here return i; } return list.end();
但是使用前哨(当然,终点实际上必须是一个真正的节点……):
iterator i=list.begin(); *list.end() = x; while (*i != x) // just this branch! ++i; return i;
您会看到不需要额外的分支来测试列表的结尾-始终保证该值在那里,因此,end()如果x在“有效”元素中找不到该值,则会自动返回。
end()
有关哨兵的另一个很酷且实际上有用的应用程序,请参阅“介绍排序”,这是大多数std::sort实现中使用的排序算法。它是分区算法的一个很酷的变体,它使用哨兵删除一些分支。
std::sort