use*_*312 -3 c++ arrays linked-list dynamic data-structures
如果我们拥有std::set并且std::vector可以动态增长和缩小,为什么我们需要链表？
NB我真的不明白,为什么会有这么多的选票.唐氏选民,请留下评论.
278*_*528 13
为什么我们需要链表？
链表是O(1)插入,删除,连接,等等.列表变大了？那么,系统保持正常运行.只是计划不需要随机访问.
向量在(可能)二进制块中增长,因此时间增长到相当大且相当快的时间.这是一个不可多得的时间.
在旧版Dell的以下输出中,在Ubuntu-15.04上使用g ++ 4.9.2,最后一列是自上次容量更改以来的毫秒时间.(最后一栏匆匆添加,为您重复使用该示例;)
Run Code Online (Sandbox Code Playgroud)element vector bytes stack use bytes heap use count capacity 'sizeof(vector)' (element count * element size) 0 0 24 0 0 1 1 24 4 0 2 2 24 8 0 3 4 24 12 0 5 8 24 20 0 9 16 24 36 0 17 32 24 68 0 33 64 24 132 0 65 128 24 260 1 129 256 24 516 0 257 512 24 1,028 0 513 1,024 24 2,052 0 1,025 2,048 24 4,100 0 2,049 4,096 24 8,196 0 4,097 8,192 24 16,388 1 8,193 16,384 24 32,772 2 16,385 32,768 24 65,540 3 32,769 65,536 24 131,076 8 65,537 131,072 24 262,148 12 131,073 262,144 24 524,292 28 262,145 524,288 24 1,048,580 50 524,289 1,048,576 24 2,097,156 38 1,048,577 2,097,152 24 4,194,308 76 2,097,153 4,194,304 24 8,388,612 149 4,194,305 8,388,608 24 16,777,220 300 8,388,609 16,777,216 24 33,554,436 601 16,777,217 33,554,432 24 67,108,868 1215 33,554,433 67,108,864 24 134,217,732 2475 67,108,865 134,217,728 24 268,435,460 4982 134,217,729 268,435,456 24 536,870,916 10247 268,435,457 536,870,912 24 1,073,741,828 21387
这有充分的理由吗？我不确定.
我使用矢量作为我的列表(几乎从未增长到技嘉大小,并且当我找到最大尺寸时添加保留的使用),对于我的fifo(处理文件和dirs创建数百万字符串),并且通常忽略列表,因为我如何使用矢量足够快(哎呀,不敢相信我只是大声说出来).
此表中的最后一个条目是向量容量达到512 K元素(从512 K - 1).分配,数据复制和擦除(使用小对象的noop dtors)但没有更多的push_back()s,导致堆栈上有1 G字节,耗时21秒.
(我想我不再希望在这台旧机器上安装8 Gig.)
编辑 - 2015年7月1日
我重新使用此代码重新生成表格的最后两行并捕获挂钟信息.
Run Code Online (Sandbox Code Playgroud)134,217,729 268,435,456 24 536,870,916 9769 268,435,457 536,870,912 24 1,073,741,828 20983 real 0m41.147s user 0m39.928s sys 0m1.164s
挂钟时间报告41秒.
产生最后一条输出线需要21秒(通过实时时钟以毫秒为单位测量),和
产生前29行的20秒......不仅仅是指数!
编辑 - 2015年7月3日 - 认为OP需要关于set vs linked-list的一些评论.
如果我们有std :: set [和...]可以动态增长和缩小,为什么我们需要链表呢？
来自cppreference.com:
std :: set是一个关联容器,包含一组有序的Key类型的唯一对象.使用密钥比较功能比较进行排序.搜索,删除和插入操作具有对数复杂性.集合通常实现为红黑树.
一方面,一个集合(我很少使用)有点像链表,因为会有节点(当实现为红黑树时),并且每个节点都是独立分配的.当集合变大时,系统保持相对正常运行(一致？)(至少直到节点进入交换(我说交换,而不是沼泽).
恕我直言,一套(rbtree)没有"工作积压".相反,树在每次插入/追加/删除工作上进行平衡.(我只能用一点小小的力气取笑一些这样的证据......对不起,没有桌子可看.)
当您查看红黑树时,您会发现rbtree不包含数据,只包含键(和颜色).
我可以想象一个只有数据中的键和颜色的链表(如集合).软件非常灵活.但是我的想象力让我失望了.
我非常欣赏关联容器的想法.我发现std :: map非常有用,它影响了我对几种软件挑战的看法.
但是,我还没有调查地图是如何完成其魔力的.更多要学习.
除了常量的插入/删除/拼接时间,链表提供了另一个有用的属性 - 当列表被更改时,迭代器不会失效(当然除了指向已删除元素的迭代器.因此,如果你有一个链表,你可以保留一个迭代器作为指向列表的指针.
虽然通过存储元素的索引可以获得与向量类似的效果,但使用列表并存储迭代器的优点是,无论列表发生什么,只要元素仍然存在,迭代器将始终指向同一个元素.如果使用了向量,则需要在向量中较早的元素被删除时修复索引.
小智 5
虽然目前给出的所有答案都是正确的,但我试着用适合C++初学者的单词来解释它.
std :: vector(或一般数组)的优点是你可以在相对较短的时间内通过索引访问它的任何元素.然而,缺点之一是在靠近开始中间的位置插入元件是相对昂贵的.在这种情况下,需要分配更多存储空间,并且必须将插入的存储器之后的所有元素复制到新位置.在最坏的情况下,无法分配额外空间,并且必须将整个阵列复制到新位置.
相反,访问列表的第1000个元素相对较慢,因为我们必须遵循999链接到列表的下一个元素.但是,在该位置插入新元素相对容易且快速.我们只需要为新元素分配空间并修改几个指针.
你看,向量有其特定的优势,列表也是如此.
因为在某些特定情况下我们有时需要O(1)插入/擦除性能.我们无法用set或实现目标vector.
+========+=========+=========+=========+===============+
| | Insert | Erase | Lookup | Iterator |
+========+=========+=========+=========+===============+
| vector | O(N) | O(N) | O(1) | Random Access |
+--------+---------+---------+---------+---------------+
| set | O(logN) | O(logN) | O(logN) | Sequential |
+--------+---------+---------+---------+---------------+
| list | O(1) | O(1) | O(N) | Sequential |
+--------+---------+---------+---------+---------------+