阵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:

1. 阵列 - 插入/删除需要因移线性时间;更新时间是固定的;没有空间用于指针;访问使用[]项目更快。

1. 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的载体 - 插入/删除需要因移线性时间;更新时间是固定的;没有空间用于指针;访问一个项目是不是一个数组要慢，因为它是运营商[]和链表的电话。

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列表 - 插入和删除需要线性时间，因为你需要在申请前插入迭代到特定位置/删除;需要额外的空间用于指针;访问一个项目是不是一个数组要慢，因为它是一个链表线性遍历。

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 矢量 。它提供了一个同样丰富的接口为列表并删除管理该阵列需要记忆的痛苦。

Use STL vector. It provides an equally rich interface as list and removes the pain of managing memory that arrays require.

您将不得不非常努力地揭露的性能成本运算符[] - 它通常被内联

You will have to try very hard to expose the performance cost of operator[] - it usually gets inlined.

我没有任何号码给你，但我记得读这描述了矢量＆lt性能分析; INT＆GT; 比列表＆LT快; INT＆GT; 甚至插入和删除（下当然具有一定规模）。事情的真相是，这些处理器我们采用的是非常快的 - 如果你的矢量在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屋！