哪种数据结构最适合这种情况？

Question

对于我的游戏，在对象进入传感器时，我需要将其添加到一个列表中，在对象离开传感器时，需要从该列表中将其移除。我还需要能够快速找到该对象。

因此，我需要实现以下功能：

快速添加、快速删除和快速查找。

考虑到在任何时候，该数据结构大约会有10个对象，请问使用哪种数据结构最好？

谢谢。

- jmasterx

---

我需要它能够快速添加、快速删除和快速查找。 QuickStruct 是最好的选择。 - unkulunkulu

一个想象中的理想数据结构。 - unkulunkulu

Answer 1

当使用10个对象时，任何容器（如std::vector，deque或set）都可以胜任，且在进行性能分析之前无法确定哪种容器的性能更好。

如果您不知道该使用什么容器，也许您会发现std::set具有更好的语法来查找元素。在这种情况下，我会使用它，因为我不想写std::find(v.begin(), v.end(), sensor)，而可以简单地写s.find(sensor)。

总的来说，不要使用std::list。在C++中使用链表需要一个强有力的理由（如常数时间拼接操作），而另一些数据结构在大多数操作中执行得更好（除了拼接操作）。在这里，我看不到使用list而不是例如set的任何意义。

- Alexandre C.

---

集合提供了良好的查找速度，但插入和删除元素的速度不如列表快。应该考虑哪个操作更经常执行。 - neodelphi

@neodelphi：在集合中找到要插入或删除的位置比在列表中快。所以我不会像你那样绝对肯定。此外，在10个元素的向量中插入和删除可能比在列表中快得多（出于数据局部性的原因）。很难说哪个容器的性能更好，但我坚信 std::list 的表现不如其他容器。强制自己仅在必要时使用链表是一个好主意，因为它们的整体性能非常差。 - Alexandre C.

Answer 2

我建议使用std::list，因为它非常适合插入和删除元素。

- neodelphi

---

我甚至不会说它对于元素的插入是好的。在这方面它相当慢。 - GManNickG

因为链表必须为每个元素动态分配一个节点。这很慢。 - GManNickG

向向量中插入元素速度较慢！对于大量对象，链表中的插入操作可能具有很好的性能，因为它是常数时间。 - neodelphi

Answer 3

快速添加、快速删除和快速查找，你要求不多啊！根据你的说法，我会建议使用链表，但这也取决于添加、删除和查找的频率。如果你更频繁地进行查找而不是添加或删除，请做出相应的改变。

实际上，唯一的方法就是尝试几种不同的选择并计时。

- jahhaj

Answer 4

我认为链表是最好的选择。由于规模较小，移动指针的操作不会影响性能。

- CrackerJack9