c++ - 动态数组宽度ID？

Question

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

数据类型需要这些功能：

• int Insert() - 返回 ID
• 删除（整数 ID）
• Get(ID) - 返回元素

我应该使用什么数据类型？我查看了 Vector 和 List，但似乎找不到任何类型的 ID。另外，我查看了 map 和 hastable，这些可能有用。但是，我不确定该选择什么。

Answer 1

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

否则，您可能想使用地图并只跟踪未使用的最低 id 并在插入时分配它。

Answer 2

似乎最好使用的容器是 unordered_map。它基于哈希。您可以在 O(n) 中插入、删除或搜索元素。

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

容器的选择仍然很大程度上取决于使用强度。例如，如果您发现元素稀有，则向量和列表可能没问题。这些容器没有 find 方法，但<algorithm>库包含它。

Answer 3

Astd::map可以为您工作，它允许将键与值相关联。关键是您的ID，但您应该在向地图添加元素时自己提供它。

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

Answer 4

Avector提供恒定时间随机访问，“ id”可以简单地作为向量的偏移量（索引）。Adeque类似，但不会连续存储所有项目。

如果 ID 值可以从 0 开始（或从 0 开始的已知偏移量并单调递增），则这些中的任何一个都是合适的。随着时间的推移，如果有大量的移除，vector或者deque可能变得稀疏，这可能是有害的。

std::map不存在人口稀少的问题，但是查找从恒定时间变为对数时间，这可能会影响性能。

boost::unordered_map may be the best yet, as the best case scenario as a hash table will likely have the best overall performance characteristics given the question. However, usage of the boost library may be necessary -- but there are also unordered container types in std::tr1 if available in your STL implementation.