C++ 具有固定索引的可增长、紧密打包的数据结构

Question

我有一组原始数据类型，需要通过某种 ID 进行跟踪。

我正在寻找一种数据结构，可以让我把它们紧紧地打包，并且集合需要根据需要增长。

C++ std::vector 将是一个完美的解决方案，除了当它删除一个元素时，一些索引可能会被更改，所以我不能再通过它的索引引用一个元素。 map我也想过，可惜包装不紧

我的解决方案是重写std::vector，比如当一个条目被删除时，条目被标记为'dirty'，当需要一个新的条目时，它可以尝试重新使用[=20] =] 条目，如果不可能，只需增长为 std::vector.

但我的问题似乎很普遍，我相信有人运行遇到过这个问题。我需要重新发明轮子还是有人可以给我指明另一个方向？

Answer 1

您跟踪已删除（"dirty" 用您的说法）条目的想法很常见，称为使用 "free list."

另一个想法是简单地使用指针（每个数据的地址）作为 ID。

Answer 2

您可以使用 vector<boost::optional<T>>。

要删除一个项目：

vec[val.id] = boost::none; // now this slot is empty

要添加项目：

auto it = std::find(vec.begin(), vec.end(), boost::none);
if (it == vec.end()) {
    val.id = vec.size(); // or however
    vec.push_back(val);
}
else {
    // this is an empty slot, overwrite it
    val.id = std::distance(vec.begin(), it);
    *it = val;
}

为了提高效率，您还可以在擦除时保留一个单独的空闲索引列表 - 但这只是在一般想法之上的优化。

Answer 3

我迟到了，但是如何将最后一个元素与要删除的元素交换并将该元素从向量的背面弹出呢？免费列表也是一个很好的解决方案，但可能会过度设计它，具体取决于您在做什么。

C++ 具有固定索引的可增长、紧密打包的数据结构

C++ Growable, Tightly Packed Data Structure with fixed indices

c++

stl

data-structures