简单链表Vs STL :: list.哪一个最好？

Question

简单链接列表:

struct Node { 
int x;
Node *next;
};

使用STL的用户定义简单链表和列表容器的主要优点/缺点是什么？那些拥有大量数据的LL的列表性能怎么样？

Answer 1

在大多数情况下,最好使用标准容器,因为它们在程序员中经过测试和熟知.考虑到标准C++库有自己的单个链表名为like

std::forward_list

因此,您的问题可以听起来更好地使用用户定义的单个链接列表或std::forward_list.我建议使用std::forward_list

然而,标准C++库需要一个带有方法的链表push_back.而且我已经建议,C++委员会应该加上这样的容器的C++标准库.我甚至给它起了个名字!:)

std::x_forward_list

Answer 2

从表面上看,这个问题可能看起来很简单,回答" std::list更安全,更有效,等等等等".

但这些方面是无关紧要的.

std::list通常没有其他标准库容器的优势.直到并包括C++ 03,它可以提供恒定的时间拼接,具体取决于实现.但是,在C++ 11中,通过要求它size()是恒定时间(你可以拥有一个或另一个是恒定时间,但不是两者),可以消除这种可能的优势.

因此,如果您想要持续时间拼接或链接列表的其他可能优势,您必须使用其他内容std::list.

比如,你的DIY本土名单.

恒定时间要求:C++11§23.2.1/ 4表96:

" a.size() size_type distance(a.begin(), a.end())不变

列是表达式,返回类型,操作语义和复杂性.