我正要实现自己的类以有效地从数组中删除，但我想我会问是否已经存在类似的东西。我想要的是类似列表的访问效率，但使用数组。出于缓存一致性的原因，我想使用一个数组，因此我不必不断地调用内存分配器（就像在分配节点时使用 std::list 一样）。
我想做的是创建一个包含两个数组的类。第一个是一组元素，第二个数组是一组整数，其中每个整数是第一个数组中的一个空闲槽。因此，我可以相当容易地从数组中添加/删除元素，而无需为它们分配新内存，只需从空闲列表中获取索引并将其用于新元素即可。
这样的事情已经存在了吗？如果我自己做，我还必须制作我自己的迭代器，所以你可以迭代集合，避免数组中的任何空槽，我不太喜欢。
谢谢。
注意：我想在片场执行的操作是：
如果保持元素的顺序无关紧要，请使用交换和弹出。
将最后一个元素复制/移动到要删除的元素上，然后弹出后面的元素。超级简单高效。您甚至不需要为删除元素而进行特殊检查，因为如果您使用标准 C++ 向量和操作，它就会工作（tm）。
*iter = std::move(container.back());
container.pop_back();
我不记得 pop_back() 是否使向量上的迭代器无效，但我认为不会。如果是这样，只需直接使用索引或重新计算一个新的有效迭代器。
auto delta = iter - container.begin();
// mutate container
iter = container.begin() + delta;
您可以通过将有关“空”插槽的信息存储在空插槽的空间中来使用单个数组。
对于 array 中连续的空槽块A，例如k从 index 开始的槽n，存储(k, n')在 location A[n]（其中n'是下一个空闲索引块的索引）。如果您的数组存储字大小的对象，您可能必须将两个整数打包成一个单词。
您实际上是在存储一个空闲块的链表，就像内存管理器可能做的那样。
编写代码有点麻烦，但这将允许您在 O(1) 时间内分配一个空闲索引，并在 O(n) 时间内遍历分配的索引，其中 n 是分配的插槽数。尽管在最坏的情况下，释放索引将花费 O(n) 时间：这与碎片化内存的问题相同。
对于第一个空闲块，您可以单独存储索引，也可以采用从不分配的约定，A[0]以便始终从那里开始空闲索引搜索。
std::list<T>实际上听起来确实与您工作的理论上正确的数据结构完全一样，因为它支持您列出的四种操作，所有操作都具有最佳的空间和时间复杂度。std::list<T>::iterator是一个句柄，即使您在列表中添加/删除其他项目也仍然有效。
可能有一个自定义分配器（即not std::allocator<T>），您可以使用它std::list<T, Allocator>来获得所需的性能（内部池节点，然后每次添加或删除节点时不要进行运行时分配）。但这可能是矫枉过正。
我会开始使用std::list<T>带有默认分配器的 a ，然后如果您发现性能对您的应用程序来说太差，则只查看自定义分配器或其他数据结构。
std::map在您的情况下可能有用。