c++ - 索引集(用于在 vector 中有效删除)

Question

我正要实现我自己的类以有效地从数组中删除，但我想我会问一下是否已经存在类似的东西。我想要的是类似列表的访问效率，但使用数组。出于缓存一致性的原因，我想使用一个数组，因此我不必不断地调用内存分配器(就像在分配节点时使用 std::list 一样)。

我想做的是创建一个包含两个数组的类。第一个是一组元素，第二个数组是一组整数，其中每个整数都是第一个数组中的一个空闲槽。因此，我可以相当轻松地从数组中添加/删除元素，而无需为它们分配新内存，只需从空闲列表中获取索引并将其用于新元素即可。

这样的东西已经存在了吗？如果我自己做，我还必须制作自己的迭代器，这样您就可以迭代集合，避免数组中出现任何空槽，我不太喜欢那样。

谢谢。

注意:我要对集合进行的操作有:

1. 迭代
2. 通过索引(或我认为的“句柄”)随机访问单个元素
3. 删除集合中任意位置的元素
4. 向集合中添加一个元素(顺序不重要)

Answer 1

std::list<T>实际上听起来确实与您的工作理论上正确的数据结构完全一样，因为它支持您列出的四个操作，所有操作都具有最佳的空间和时间复杂度。 std::list<T>::iterator是一个句柄，即使您在列表中添加/删除其他项目也仍然有效。

可能有一个自定义分配器(即 不是 std::allocator<T> )可以与 std::list<T, Allocator> 一起使用获得你想要的性能(内部池节点，然后每次添加或删除节点时不要进行运行时分配)。但这可能有点矫枉过正。

我会开始使用 std::list<T>使用默认分配器，如果您发现性能对您的应用程序来说太差，则只查看自定义分配器或其他数据结构。