C++之父:链表是原罪吗?
-
翻译改编自https://isocpp.org/blog/2014/06/stroustrup-lists
链表是原罪吗?
作者:Bjarne Stroustrup
根据Web的某些角落,我的印象是向量总是比链表更好,而且我不了解其他数据结构,例如树(例如
std::set
)和哈希表(例如std::unordered_map
)。显然,那是荒谬的。问题似乎是约翰·本特利曾向我提出的一个有趣的小练习:将一系列随机整数插入到一个排序的序列中,然后按照原位置的顺序逐个删除这些元素定:你是否使用了
vector
(连续分配的元素序列)或list
?我用这个例子来说明一些观点,鼓励思考算法,数据结构和机器架构,得出结论:- 不要不必要地存储数据
- 保持数据紧凑
- 以可预测的方式访问内存。
注意结论中没有
vector
和list
。请不要将示例与示例中的示例混淆。这个例子的目的是说明一些一般原则并让人们思考。最初,大多数人说“当然选择
list
!”(我已经多次尝试过这个问题),因为“中间”有许多插入和删除(list
很擅长)。这个答案是完全错误的。我多年来一直在使用这个例子,并且让研究生实施并测量了这个练习和不同练习的几十种变体。其他人的例子和测量可以在网上找到。
- 我尝试了
map
(它们比list
要好得多,但仍比vector
慢) - 我已经尝试了更大的元素大小
- 我使用Binary Search和暴力插入向量(是的,它们甚至进一步加速)
- 我查看了我的理论(不,我没有违反任何大O复杂性规则;只是某些操作对于一个数据结构而言比另一个更加昂贵)
- 我有预先分配的链接(这比std::list遍历仍然性能更好)
- 我使用了单链表forward_lists,(这没有多大区别,但是确保用户代码100%相当有点难度)
- 我知道(并且说)500K列表并不常见(但这对我的要点无关紧要)。我们使用许多结构(大型和小型),其中可以选择链接和连续的表示。
- 我知道
list
的push_front()
更快,vector
的push_back()
更快
我的观点不是关于列表。它们有它们的用途,但这个例子不是其中之一。请不要将示例与示例用于说明的内容混淆。这个例子是关于内存的使用:我们经常创建一个数据结构,对它进行一些