动态数组宽度id?

发布于 2024-11-26 21:01:20 字数 255 浏览 6 评论 0原文

我需要 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

望她远 2024-12-03 21:01:20

我可能会使用向量和空闲 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.

叫思念不要吵 2024-12-03 21:01:20

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

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

A std::map could 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.

一袭白衣梦中忆 2024-12-03 21:01:20

看来最好使用的容器是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.

转瞬即逝 2024-12-03 21:01:20

向量提供恒定时间随机访问,“id”可以简单地是向量的偏移量(索引)。 deque 类似,但不连续存储所有项目。

如果 ID 值可以从 0 开始(或从 0 开始的已知偏移并单调递增),则这两种方法都适用。随着时间的推移,如果存在大量删除,vectordeque 可能会变得稀疏,这可能是有害的。

std::map 不存在填充稀疏的问题,但查找从恒定时间变为对数时间,这可能会影响性能。

boost::unordered_map 可能是迄今为止最好的,因为在给定问题的情况下,哈希表的最佳情况可能具有最佳的整体性能特征。然而,使用 boost 库可能是必要的——但是,如果您的 STL 实现中可用,则 std::tr1 中也有 unordered 容器类型。

A vector gives constant-time random access, the "id" can simply be the offset (index) into the vector. A deque is 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 vector or deque can become sparsely populated, which may be detrimental.

std::map doesn't have the problem of becoming sparsely populated, but look ups move from constant time to logarithmic time, which could impact performance.

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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文