c++ - 关联/随机访问容器

Question

我正在寻找一种数据结构来保存唯一元素的无序集合，它将支持以下操作

1. 在集合中任意位置插入/删除元素
2. 查询元素是否存在
3. 访问一个随机元素

天真地，1 和 2 建议使用关联容器，例如unordered_set，但是 3 在元素数量上是线性的。使用随机访问容器，例如vector，使 3 变得简单，1 可以在 O(1) 中完成，但 2 又是 O(N)。

问题是是否有解决这种线性复杂性的已知方法？

编辑:3 中的随机元素是指:给定 N 个元素的任意顺序，检索元素编号 j，其中 j 介于 0 和 N-1 之间.对于 std::vector 它只是下标，对于 std::list 或 std::set 它是递增列表/集合迭代器从 begin() 等开始 j 次

Answer 1

最适合您的任务的两个标准容器是 - 就像您说的那样，vector 具有 1. 和 2. O(n) 和 3. O(1) 和 set 1. 和 2. 在 O(log n) 中，3. 在 O(n) 中。根据数据结构的大小，算法的复杂性并不那么重要。 vector 具有数据局部性的额外优势，因此可以更好地利用 CPU 缓存。

如果元素的实际顺序无关紧要，vector 中的插入可以在分摊的 O(1) (push_back) 中完成，删除也可以完成如果您交换要删除的元素与最后一个元素并将其删除，则在摊销的 O(1) 中。

如果你真的有一个大数据结构，你可以使用Boost.Multi-Index构建一个数据结构，其中 1. 是 O(n)，2. 是 O(log n)，3. 是 O(1)。但是，就像我说的，如果您的数据结构不是很大，vector 应该就可以了。

如果随机访问索引中的顺序无关紧要，插入可以在分摊的 O(log n) (push_back) 中完成。对于删除，您不能使用 swap 技巧，因为这会使其他索引无效。