数组 vs 向量 vs 列表 [英] array vs vector vs list
问题描述
我正在维护一个包含 10 个条目的固定长度表.每个项目都是一个类似 4 个字段的结构.将有插入、更新和删除操作，由数字位置指定.我想知道用于维护此信息表的最佳数据结构是什么:
I am maintaining a fixed-length table of 10 entries. Each item is a structure of like 4 fields. There will be insert, update and delete operations, specified by numeric position. I am wondering which is the best data structure to use to maintain this table of information:
array - 由于移位，插入/删除需要线性时间；更新需要恒定的时间；没有空间用于指针；使用 [] 访问项目更快.
array - insert/delete takes linear time due to shifting; update takes constant time; no space is used for pointers; accessing an item using [] is faster.
stl 向量 - 由于移位，插入/删除需要线性时间；更新需要恒定的时间；没有空间用于指针；访问项目比数组慢，因为它是对 operator[] 和链表的调用.
stl vector - insert/delete takes linear time due to shifting; update takes constant time; no space is used for pointers; accessing an item is slower than an array since it is a call to operator[] and a linked list .
stl list - 插入和删除需要线性时间，因为您需要在应用插入/删除之前迭代到特定位置；指针需要额外的空间；访问项比数组慢，因为它是链表线性遍历.
stl list - insert and delete takes linear time since you need to iterate to a specific position before applying the insert/delete; additional space is needed for pointers; accessing an item is slower than an array since it is a linked list linear traversal.
现在，我的选择是使用数组.有道理吗?还是我错过了什么?
Right now, my choice is to use an array. Is it justifiable? Or did I miss something?
哪个更快:遍历列表，然后插入一个节点或移动数组中的项目以产生一个空位置，然后在该位置插入项目?
Which is faster: traversing a list, then inserting a node or shifting items in an array to produce an empty position then inserting the item in that position?
衡量这种表现的最佳方法是什么?我可以只显示操作前后的时间戳吗?
What is the best way to measure this performance? Can I just display the timestamp before and after the operations?
推荐答案
使用 STL vector.它提供了与 list 同样丰富的接口，并消除了管理数组所需内存的痛苦.
Use STL vector. It provides an equally rich interface as list and removes the pain of managing memory that arrays require.
您将不得不非常努力地暴露 operator[] 的性能成本 - 它通常会被内联.
You will have to try very hard to expose the performance cost of operator[] - it usually gets inlined.
我没有任何数字可以给你，但我记得读过性能分析，其中描述了 vector 如何比 list 更快，即使对于插入也是如此并删除(当然在一定大小下).事情的真相是我们使用的这些处理器非常快 - 如果您的向量适合 L2 缓存，那么它会非常快.另一方面，列表必须管理会杀死 L2 的堆对象.
I do not have any number to give you, but I remember reading performance analysis that described how vector<int> was faster than list<int> even for inserts and deletes (under a certain size of course). The truth of the matter is that these processors we use are very fast - and if your vector fits in L2 cache, then it's going to go really really fast. Lists on the other hand have to manage heap objects that will kill your L2.
这篇关于数组 vs 向量 vs 列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
