c++ - 无序、固定大小的基于内存池的频繁插入和删除的容器

Question

我正在寻找一个容器来存储动态增长和缩小的对象系列，我知道其大小接近但永远不会超过给定的界限。容器不需要订购，所以我对任何类型的插入都很满意，无论它发生在哪里。而且，我希望所有的对象都存储在某个固定连续的内存池中，但我不要求在某个时间点实际占用的内存是内存池中的一个连接区间。

STL 或 boost 中是否有提供上述内容的容器/分配器？

似乎一个合理的方法是使用从固定大小的内存池中获取内存的链表，但我宁愿为此使用一些已经存在和完善的实现，而不是尝试自己做.

谢谢!

Answer 1

因为你需要元素是连续的，我认为你应该选择 std::vector , 调用 reserve在一开始。

正如我在评论中所说，一旦您需要连续内存，您就必须在中间删除时移动某些内容，并且该行为已由 std::vector 处理。使用 remove/erase idiom .

除此之外，如果您只使用 vector 插入，或者根据您的设计查找将是昂贵的:

• 要么你总是在末尾添加新元素，查找元素会花费你，但插入将很轻松
• 或者您在每次插入后对 vector 进行排序(这会产生成本)，使用 std::equal_range 查找会快很多。

否则如果你能负担得起额外的std::unordered_set<std::vector<your_element>::iterator>使用自定义散列/等于，您可以通过查找 std::unordered_set<> 来获得公平的插入/查找比率找到您的元素的存储位置。