动态数组宽度id？
我需要 C++ 中的某种动态数组，其中每个元素都有自己的由 int 表示的 id。
该数据类型需要以下函数：
- int Insert() - 返回 ID
- Delete(int ID)
- Get(ID) - 返回 Element
我应该使用什么数据类型？我查看了 Vector 和 List，但似乎找不到任何类型的 ID。我还查看了地图和急速表，这些可能很有用。然而我不确定该选择什么。
I need some sort of dynamic array in C++ where each element have their own id represented by an int.
The datatype needs these functions:
- int Insert() - return ID
- Delete(int ID)
- Get(ID) - return Element
What datatype should I use? I'we looked at Vector and List, but can't seem to find any sort of ID. Also I'we looked at map and hastable, these may be usefull. I'm however not sure what to chose.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我可能会使用向量和空闲 id 列表来处理删除，然后索引就是 id。这插入和获取的速度非常快，并且相当容易管理（唯一的技巧是已删除项目的空闲列表）。
否则，您可能想要使用映射并仅跟踪最低的未使用 id 并在插入时分配它。
I would probably use a vector and free id list to handle deletions, then the index is the id. This is really fast to insert and get and fairly easy to manage (the only trick is the free list for deleted items).
Otherwise you probably want to use a map and just keep track of the lowest unused id and assign it upon insertion.
std::map可以为您工作，它允许将键与值关联。 键将是您的 ID，但您应该在向地图添加元素时自行提供它。哈希表是一种可用于实现无序映射的基本机制。它对应于std::unordered_map。
A
std::mapcould work for you, which allows to associate a key to a value. The key would be your ID, but you should provide it yourself when adding an element to the map.An hash table is a sort of basic mechanism that can be used to implement an unordered map. It corresponds to std::unordered_map.
看来最好使用的容器是unordered_map。
它是基于哈希的。您可以在 O(n) 内插入、删除或搜索元素。
目前unordered_map不在STL中。如果你想使用 STL 容器，请使用 std::map。
它是基于树的。插入、删除和搜索元素的时间复杂度为 O(n*log(n))。
尽管如此，容器的选择很大程度上取决于使用强度。例如，如果您发现稀有元素，向量和列表就可以。这些容器没有 find 方法，但
It seems that the best container to use is unordered_map.
It is based on hash. You can insert, delete or searche for elements in O(n).
Currently unordered_map is not in STL. If you want to use STL container use std::map.
It is based on tree. Inserts, deletes and searches for elements in O(n*log(n)).
Still the container choice depends much on the usage intensity. For example, if you will find for elements rare, vector and list could be ok. These containers do not have find method, but
<algorithm>library include it.向量提供恒定时间随机访问，“id”可以简单地是向量的偏移量（索引）。deque类似，但不连续存储所有项目。如果 ID 值可以从 0 开始（或从 0 开始的已知偏移并单调递增），则这两种方法都适用。随着时间的推移，如果存在大量删除，
vector或deque可能会变得稀疏，这可能是有害的。std::map不存在填充稀疏的问题，但查找从恒定时间变为对数时间，这可能会影响性能。boost::unordered_map可能是迄今为止最好的，因为在给定问题的情况下，哈希表的最佳情况可能具有最佳的整体性能特征。然而，使用 boost 库可能是必要的——但是，如果您的 STL 实现中可用，则std::tr1中也有unordered容器类型。A
vectorgives constant-time random access, the "id" can simply be the offset (index) into the vector. Adequeis similar, but doesn't store all items contiguously.Either of these would be appropriate, if the ID values can start at 0 (or a known offset from 0 and increment monotonically). Over time if there are a large amount of removals, either
vectorordequecan become sparsely populated, which may be detrimental.std::mapdoesn't have the problem of becoming sparsely populated, but look ups move from constant time to logarithmic time, which could impact performance.boost::unordered_mapmay 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 alsounorderedcontainer types instd::tr1if available in your STL implementation.