jas*_*ine 41 c++ arrays stl list vector
我正在维护一个包含10个条目的固定长度表.每个项目都是4个字段的结构.将有数字位置指定的插入,更新和删除操作.我想知道哪个是用于维护此信息表的最佳数据结构:
array - insert/delete由于移位而占用线性时间; 更新需要恒定的时间; 没有空间用于指针; 使用[]访问项目的速度更快.
stl vector - 插入/删除由于移位而占用线性时间; 更新需要恒定的时间; 没有空间用于指针; 访问项目比数组慢,因为它是对operator []和链接列表的调用.
stl list - 插入和删除需要线性时间,因为在应用插入/删除之前需要迭代到特定位置; 指针需要额外的空间; 访问项目比数组慢,因为它是链接列表线性遍历.
现在,我的选择是使用数组.这是否合理？还是我错过了什么？
哪个更快:遍历列表,然后插入节点或在数组中移动项目以产生空位置然后将项目插入该位置？
衡量这种表现的最佳方法是什么？我可以只显示操作前后的时间戳吗？
Fra*_*ger 50
使用STLvector.它提供了同样丰富的界面,list并消除了管理阵列所需内存的痛苦.
您将不得不非常努力地暴露性能成本operator[]- 它通常会被内联.
我没有任何数字可以给你,但我记得读过性能分析,描述了插入和删除的vector<int>速度是多么快list<int>(当然在一定的规模下).问题的真相是我们使用的这些处理器非常快 - 如果你的矢量适合二级缓存,那么它真的会非常快.另一方面,列表必须管理会破坏L2的堆对象.
Don*_*eld 25
过早优化是万恶之源.
根据您的帖子,我认为没有理由在这里选择基于性能的数据结构.挑选最方便的东西,当且仅当性能测试表明它是一个问题时才返回进行更改.
小智 12
值得花一些时间来理解列表和向量之间的根本区别.两者之间最显着的区别是它们存储元素并跟踪它们的方式.
- 名单 -
List包含具有存储在其中的previous和next元素的地址的元素.这意味着无论列表大小如何,您都可以使用恒定速度O(1)在列表中的任何位置插入或删除元素.您还可以在任何地方以恒定速度拼接(插入另一个列表)到现有列表中.原因是list只需要为我们插入列表的元素更改两个指针(前一个和下一个).
如果您需要随机访问,列表并不好.因此,如果计划访问列表中的第n个元素 - 必须逐个遍历列表 - O(n)速度
- 矢量 -
Vector按顺序包含元素,就像数组一样.这对于随机访问非常方便.访问向量中的"第n"个元素是一个简单的指针计算(O(1)速度).然而,向矢量添加元素是不同的.如果想要在向量中间添加一个元素 - 必须重新分配该元素后面的所有元素,以便为新条目腾出空间.速度取决于矢量大小和新元素的位置.最糟糕的情况是在向量中插入位置2处的元素,最好的是附加新元素.因此 - 插入与速度O(n)一起工作,其中"n"是需要移动的元素的数量 - 不一定是矢量的大小.
还有其他差异涉及内存要求等,但理解列表和向量实际工作的这些基本原则真的值得花一些时间.
一如既往......" 过早优化是所有邪恶的根源 "所以首先要考虑什么更方便,让事情按照你想要的方式工作,然后进行优化.对于您提到的10个条目 - 无论您使用什么都无关紧要 - 无论您使用何种方法,您都将永远无法看到任何性能差异.
首选std :: vector over和array.矢量的一些优点是:
使用向量的最令人信服的理由是它使您免于显式内存管理,并且它不会泄漏内存.向量跟踪它用于存储其元素的内存.当向量需要更多元素内存时,它会分配更多内存; 当向量超出范围时,它释放内存.因此,用户无需关心向量元素的存储器的分配和释放.