动态数组宽度ID？

Question

我需要某种在C++中的动态数组，其中每个元素都有一个int表示的自己的id。

数据类型需要这些功能：

• INT插入（） - 返回ID
• 删除（INT ID）
• 获取（ID） - 返回元素

什么数据类型应我用？我查看了矢量和列表，但似乎无法找到任何类型的ID。另外我看了一下地图和hastable，这些可能是有用的。但我不知道该选什么。

Answer 1

A std::map可以为你工作，它允许将一个键与一个值相关联。 密钥将是您的ID，但在将元素添加到地图时应自己提供。

散列表是一种可用于实现无序映射的基本机制。它对应于std :: unordered_map。

Answer 2

看来最好使用的容器是unordered_map。 它基于哈希。您可以插入，删除或搜索O（n）中的元素。

目前unordered_map不在STL中。如果你想使用STL容器使用std :: map。 它基于树。插入，删除和搜索O（n * log（n））中的元素。

容器的选择依赖于使用强度。例如，如果你会发现罕见的元素，矢量和列表可以确定。这些容器没有find方法，但<algorithm>库包含它。

Answer 3

我可能会使用一个向量和空闲id列表来处理删除，然后索引是id。这是非常快的插入和获取，并相当容易管理（唯一的窍门是免费清单删除项目）。

否则，您可能想要使用地图，并跟踪最低未使用的ID并在插入时指定它。

Answer 4

A vector给出恒定时间随机存取，“id”可以简单地是向量中的偏移（索引）。 A deque与此类似，但不会连续存储所有项目。

如果ID值可以从0开始（或从0开始的已知偏移量并单调增加），这两种方法都适用。随着时间的推移，如果有大量的清除，vector或deque可能会变得稀疏，这可能是有害的。

std::map不存在人口稀少的问题，但外观从常量时间变为对数时间，这可能会影响性能。

boost::unordered_map可能是最好的，因为作为散列表的最佳情况可能具有给出该问题的最佳总体性能特征。但是，可能需要使用boost库，但如果在STL实现中可用，还可以使用std::tr1中的unordered容器类型。