除了从实现自己的C++双向链表中学习某些学术方面外，当已经存在std::list时，实现自己的双向链表是否有任何实际的现实优势？我能否为特定任务自己更有效地完成工作，或者多年来std::list已经被完善得如此之多，以至于在大多数情况下它是双向链表的最佳实现方式？
5个回答
7
当已经有std::list时，实现自己的双向链表是否有任何实际优势？
可能没有。
对于某些任务，我能否自己更有效地完成呢？
也许-这取决于任务。例如，您可能只需要一个单向链表，这可能会更快。
或者多年来，std::list已经被改进得如此之好，以至于在大多数情况下它是双向链表的最佳实现吗？
很可能是。
所有这些问题的最佳答案可能是“使用标准实现，直到它不起作用，然后再想出你要做什么。”
可能没有。
对于某些任务，我能否自己更有效地完成呢？
也许-这取决于任务。例如，您可能只需要一个单向链表，这可能会更快。
或者多年来，std::list已经被改进得如此之好，以至于在大多数情况下它是双向链表的最佳实现吗？
很可能是。
所有这些问题的最佳答案可能是“使用标准实现，直到它不起作用，然后再想出你要做什么。”
- Carl Norum
1
1现在，如果你只需要一个单向链表，可以使用
std::forward_list。 - Mike Seymour2
"为什么我要在C++中实现双向链表？"
您不需要。即使您需要双向链表，也应该避免重复造轮子并使用现有的实现。
- LihO
2
如果你不得不问这个问题，那答案就是“不”。
- youdontneedtothankme
1
您几乎永远不需要或不想要实现自己的
当然也有例外情况。这些例外是非常特殊的。通常出于性能原因才会做出这些例外，尤其是在性能需求极高的情况下。但是只有在您已经证明标准库提供的功能对您的特定使用存在可衡量的问题时，才可以负责任地做出这些例外。
list。事实上，如果它已经被标准库覆盖，您几乎永远不需要或不想要重新实现您自己的任何东西。当然也有例外情况。这些例外是非常特殊的。通常出于性能原因才会做出这些例外，尤其是在性能需求极高的情况下。但是只有在您已经证明标准库提供的功能对您的特定使用存在可衡量的问题时，才可以负责任地做出这些例外。
- John Dibling
0
是的，对于某些任务而言，双向链表可能比std::list更高效。在std::list中存在算法复杂度的权衡，您的任务可能从相反的决策中受益。
具体来说，在C++11中需要使用std::list，在C++03中建议使用，以获得常数时间的size()。也就是说，元素数量必须存储在对象中。
这意味着，4个参数版本的splice()必然具有线性复杂度，因为它需要计算从一个列表移动到另一个列表的元素数量，以更新两个列表的大小（除非在某些特殊情况下，例如剪接后源列表为空或两个列表是同一对象）。
但是，如果您要频繁进行剪接操作，则可能更喜欢将它们颠倒过来-具有常数时间的splice()和size()函数，在最坏情况下（当列表上次更新大小之后进行了剪接）具有线性时间。
std::list 实现做出了这个选择，并不得不为符合 C++11 标准而进行更改。因此，即使这是您想要的，您也不一定必须完全自己实现它。只需擦拭旧的 GNU 代码并更改名称，使其成为有效的用户代码即可。- Steve Jessop
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
std::list实现，然后忘记自己实现它。 - Zetastd::list替代品之前，您应该考虑编写自己的分配器。 - Simple