c++ - 为什么我要在 C++ 中实现我自己的双向链表？

Question

除了通过在 C++ 中实现我自己的双向链表来学习一些东西的学术方面之外，当已经有 std::list 时，实现我自己的双向链表是否有任何实际的现实优势？对于某项任务，我是否可以自己提高效率，或者 std::list 多年来已经改进得如此之多，以至于在大多数情况下它是双向链表的最佳实现？

score 7 · Accepted Answer

当已经有 std::list 时，实现我自己的双向链表是否有任何实际的现实优势？

可能不是。

我可以自己使某项任务更有效率吗？

也许 - 取决于任务。例如，您可能只需要一个单链表，它最终可能会更快。

还是 std::list 多年来被改进得如此之多，以至于在大多数情况下它是双向链表的最佳实现？

大概。

所有这些东西的最佳答案可能是“使用标准实现，直到它不起作用，然后弄清楚你将要做什么。”

score 2 · Accepted Answer

“我为什么要在 C++ 中实现双向链表？”

你不会。即使您需要一个双向链表，您也可以避免重新发明轮子并使用现有的实现。

score 2 · Accepted Answer

2

如果你不得不问这个问题，答案是否定的。

于 2013-10-09T17:17:27.970 回答

score 1 · Accepted Answer

您几乎永远不会想要或不需要实现自己的list. 就此而言，如果标准库涵盖了任何内容，您几乎不会想要或不需要重新实现您自己的任何内容。

也有例外。这些例外是，嗯...例外。出于性能原因会进行例外处理，通常是在性能要求非常高的情况下。但是，只有当您已经证明标准库提供的功能对于您的特定用途来说是一个可衡量的问题时，才能负责任地做出这些例外。

score 0 · Accepted Answer

是的，双向链表可能比std::list特定任务更有效。中存在算法复杂性权衡std::list，您的任务可能会从相反的决定中受益。

具体来说，std::list在 C++11 中是必需的，在 C++03 中建议使用 constant-time size()。也就是说，元素的数量必须存储在对象中。

这意味着 4 参数版本splice()必然具有线性复杂性，因为它需要计算从一个列表移动到另一个列表的元素数量，以便更新两个大小（除了在某些特殊情况下，例如源列表在拼接，或者两个列表是同一个对象）。

但是，如果您要进行大量拼接，那么您可能更喜欢以相反的方式使用它们——恒定时间splice()和size()最坏情况下的线性时间函数（当在列表中完成拼接时更多）最近比上次更新大小时）。

碰巧的是，GNU 的实现std::list做出了这个选择，并且不得不为了 C++11 的一致性而改变。所以即使这是你想要的，你也不一定要自己完全实现。只需清除旧的 GNU 代码并更改名称，使其成为有效的用户代码。

5 回答 5