所以我的应用程序有包含 1 亿个甚至更多元素的容器。
我正在寻找一个容器，它在整个容器中的频繁插入和删除......包括靠近中间的地方，其行为 - 在时间上 - 比 std::deque （更不用说 std::vector）更好。对第 n 个元素的访问时间不需要像向量一样快，但应该比 std::list 中的完全遍历更好（无论如何每个元素都有巨大的内存开销）。
元素应按索引排序（如向量、双端队列、列表），因此 std::set 或 std::unordered_set 也不能正常工作。
在我坐下来自己编写这样一个容器之前：有人见过这样的野兽吗？我很确定 STL 没有这样的东西，期待 BOOST 我没有找到可以使用的东西，但我可能错了。
有什么提示吗？
如果您的应用程序以此类数据为中心，则可以使用整个 STL 替代大数据：
编辑：我实际上回答得有点快。1亿并不是一个很大的数字。例如，如果每个元素都是一个字节，您可以将其保存在 96MiB 数组中。因此，无论 STXXL 是否有用，元素的大小都应该大得多。
我认为您可以通过跳过列表获得所需的性能特征：
https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist
当然，这是您感兴趣的“可索引”部分——您实际上并不希望对项目进行排序。所以我需要做一些修改，作为练习。
您可能会发现 1 亿个列表节点开始占用 32 位地址空间，但在 64 位中可能不是问题。
尝试哈希映射。STL 有几个，都带有无序的命名前缀，例如 unorderd_map 等。它具有恒定的时间插入和查找给定一个好的散列算法。使用您的“庞大”数据集，哈希图很可能会满足您的需求。对应用程序进行轻微更改以覆盖接口的差异是微不足道的。
1）如果数据非常稀疏，即有很多零或可以这样表达，我强烈推荐一种利用这一点的数据结构：
2) 哈希映射应该对您描述的所有操作执行 O(1)，并且我之前提到的 sparsehash 实现特别节省空间；它还包括一种sparsetable更底层的类型，可以用来代替数组。
3）如果严格的排序不是那么重要（可能是，因为你提到的元素应该按索引排序），你可以swap将要擦除的元素删除到向量的末尾，然后resize在 O(1 ）。插入只是push_back.