我需要能够做到:
MySet<double> s;
/* some insertions, other ops... */
int idx = s.getElemenetIndex(-15.3);
如果 -15.3 不在集合中，则 idx 具有 -1，或者集合中 -15.3 的相对索引(即集合中的某些独特元素具有 getElemenetIndex()等于 0，另一个 -1，...直到设置大小 -1)。我不在乎顺序到底是什么，只要它存在即可。
- 我可以用
std::set()做这个吗？我的意思是，时间复杂度为 O(log(n))，其中 n = s.size()？我知道它的底层实现，一棵红黑树，允许这样...... - 如果不是
std::set，也许是其他一些现成的集合类？还是我需要自己动手？
注意事项:
- 关于动机 - 当我使用这个集合时，我实际上只需要索引。它太复杂而且与解释我将用它们做什么无关紧要。
- 我可以“ promise 不变性”，即您可以假设所有插入都是在第一次调用
getElementIndex()之前完成的。 - 插入(在第一个
getElementIndex()之前)必须摊销 O(log(n))；根本不需要支持删除。
最佳答案
鉴于您不需要在初始填充后修改集合，请使用排序 vector 。
- 使用
push_back填充(未排序):每个元素摊销 O(1) - 使用
std::sort排序:O(N*log(N)) 总计，O(log(N)) 每个元素摊销 - 使用
std::lower_bound查找迭代器:O(log(N)) - 检查是否相等，并使用
std::distance转换为索引:O(1)
关于c++ - 我需要一个(有序的)集合，我可以在其中快速检索成员元素的相对索引，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20708036/