关联/随机访问容器 [英] associative / random access container
问题描述
我在寻找一个数据结构来保存唯一元素的无序集合，这将支持以下操作：
I'm looking for a data structure to hold an unordered collection of unique elements, which would support the following operations
- 插入/
- 查询某个元素是否存在
- 访问随机元素
朴素，1和2建议使用关联容器，例如 unordered_set ，但是3在元素数量上是线性的。使用随机访问容器，例如向量，使3容易，1可以在O（1）中完成，但是2又是O（N）。
Naively, 1 and 2 suggest using an associative container, e.g. unordered_set, but then 3 is linear in number of elements. Using a random access container, e.g. vector, makes 3 easy, 1 can be done in O(1), but then 2 is again O(N).
问题是，如果有一个已知的方法围绕这个线性复杂性？
The question is if there's a known way around this linear complexity?
编辑：由3中的随机元素表示：给定N个元素的任意排序，检索元素号 j 其中 j 在0和N-1之间。对于 std :: list 或，它只是下标， std :: set 它从 begin（）等开始增加列表/集合迭代器j次。
By a random element in 3 I mean: given an arbitrary ordering of N elements, retrieve an element number j where j is between 0 and N-1. For an std::vector it's just subscripting, for an std::list or an std::set it's incrementing the list/set iterator j times starting from begin() etc.
推荐答案
我一直在寻找这样的数据结构很长一段时间。
I have been looking for such a data structure for a long time.
最近，我发现相当有前途的库，它具有您所寻找的所有功能。
Recently, I found quite promising library which has all the functionality that you are looking for.
在O（log n）中查看随机存取的cntree :: set。
See the cntree::set with random access in O(log n).
。
http://dl.dropbox.com/u/8437476 /works/countertree/index.html
虽然它似乎正在开发中，但我认为它非常实用。
Although it seems to be under development, I see it is quite usable.
这篇关于关联/随机访问容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
