3

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

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

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

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

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

4

4 回答 4

3

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

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

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

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

于 2012-05-28T21:55:46.117 回答
1

找这样的数据结构很久了。

最近，我发现了一个很有前途的库，它具有您正在寻找的所有功能。

请参阅 O(log n) 中随机访问的 cntree::set。

链接在这里。 http://dl.dropbox.com/u/8437476/works/countertree/index.html

虽然它似乎正在开发中，但我认为它非常有用。

于 2012-06-13T15:08:24.983 回答
1

取决于您对#3 的需求std::unordered_set可能非常合适。

我一直在寻找具有上述属性的容器，以便可以遍历所有类似于for(int i = 0; i < myset.size(); ++i) process(myset[i]);. 我发现这个页面描述了std::unordered_set::bucket_count(),std::unordered_set::begin(size_t bucket_number)和std::unordered_set::end(size_t bucket_number).

如果您有 OpenMP 循环，这将变得非常方便，因此您可以编写：

std::unordered_set<Element> myset;

#pragma omp parallel for
for(int i = 0; i < myset.bucket_count(); ++i) {
   for(auto it = myset.begin(i); it != myset.end(i); ++it)
      processElement(*it);
}

这仍然不允许您直接访问myset[i]，但它非常接近，因为您可以访问编号存储桶中的元素。

于 2016-01-23T10:02:24.483 回答
0

std::unordered_set. 如果使用索引j作为键，访问元素不是 O(N)，而是 O(1)。

如果您有一个要用于查找的唯一索引并且您不关心其他排序，那么您还打算使用什么作为关联容器的键？

于 2012-05-28T21:52:40.550 回答