C++之父:链表是原罪吗?



  • 翻译改编自https://isocpp.org/blog/2014/06/stroustrup-lists

    链表是原罪吗?

    作者:Bjarne Stroustrup

    根据Web的某些角落,我的印象是向量总是比链表更好,而且我不了解其他数据结构,例如树(例如std::set)和哈希表(例如std::unordered_map)。显然,那是荒谬的。

    问题似乎是约翰·本特利曾向我提出的一个有趣的小练习:将一系列随机整数插入到一个排序的序列中,然后按照原位置的顺序逐个删除这些元素定:你是否使用了vector(连续分配的元素序列)或list?我用这个例子来说明一些观点,鼓励思考算法,数据结构和机器架构,得出结论:

    • 不要不必要地存储数据
    • 保持数据紧凑
    • 以可预测的方式访问内存。

    注意结论中没有vectorlist。请不要将示例与示例中的示例混淆。

    这个例子的目的是说明一些一般原则并让人们思考。最初,大多数人说“当然选择list!”(我已经多次尝试过这个问题),因为“中间”有许多插入和删除(list很擅长)。这个答案是完全错误的。

    我多年来一直在使用这个例子,并且让研究生实施并测量了这个练习和不同练习的几十种变体。其他人的例子和测量可以在网上找到。

    • 我尝试了map(它们比list要好得多,但仍比vector慢)
    • 我已经尝试了更大的元素大小
    • 我使用Binary Search和暴力插入向量(是的,它们甚至进一步加速)
    • 我查看了我的理论(不,我没有违反任何大O复杂性规则;只是某些操作对于一个数据结构而言比另一个更加昂贵)
    • 我有预先分配的链接(这比std::list遍历仍然性能更好)
    • 我使用了单链表forward_lists,(这没有多大区别,但是确保用户代码100%相当有点难度)
    • 我知道(并且说)500K列表并不常见(但这对我的要点无关紧要)。我们使用许多结构(大型和小型),其中可以选择链接和连续的表示。
    • 我知道listpush_front()更快,vectorpush_back()更快

    我的观点不是关于列表。它们有它们的用途,但这个例子不是其中之一。请不要将示例与示例用于说明的内容混淆。这个例子是关于内存的使用:我们经常创建一个数据结构,对它进行一些


 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

Looks like your connection to Dian was lost, please wait while we try to reconnect.