我必须使用一个在构造上已经订购的容器，并且我需要一个快速查找功能。
我的想法是使用一个集合来利用它的set.find，这应该足够快，但是使用set.insert构建我的集合可能会很慢，因为我已经知道元素是有序的!
对于这部分，我可以只使用带有 vector.push_back 的 vector ，但是我应该自己编写 find 函数，它也会比 set::find...你有什么建议？
编辑:
- 容器需要修改，但始终是有序的，并且其大小始终相同(但我事先不知道)
- 没有重复值。
- 查找次数比插入次数多得多。
- 我只需要知道它是否存在，而不是它的位置。
- 我找到了 std::binary_search。好用吗？
最佳答案
如果输入范围已经排序，则从一对迭代器构造一个 set 保证是 O(N)，因此您可以直接使用它。 (参见例如http://en.cppreference.com/w/cpp/container/set/set。)
后续插入的时间复杂度为 O(log N)。
尽管如果总大小不是那么大，排序的 vector 往往会击败其他所有内容，因为它对缓存非常友好。 std::binary_search 的复杂度为 O(log N)，与 set::find 相同。
std::unordered_set 不关心您的顺序，但确实为您提供了 O(1) 查找(平均而言，没有保证)。
关于c++ - 我应该使用哪个容器来快速找到一个元素，因为知道通过构造它已经被订购了？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34830807/