c++ - 我应该使用哪个容器来快速找到一个元素，知道通过构造它已经被订购了？

Question

我必须使用一个已经订购的容器，我需要一个快速查找功能。

我的想法是使用一个集合来利用它的 set.find，这应该足够快，但是用 set.insert 构建我的集合可能会很慢，因为我已经知道元素是有序的!

对于这部分，我可以只使用带有 vector.push_back 的 vector ，但是我应该自己编写 find 函数，它也会比 set::find...你有什么建议吗？

编辑:

• 容器需要修改，但总是有序的，它的大小总是相同的(但我不知道它是先验的)
• 没有重复的值。
• 发现的比插入的多得多。
• 我只需要知道它是否存在，而不是它的位置。
• 我找到了 std::binary_search。好吗？

Answer 1

如果输入范围已经排序，从一对迭代器构造一个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) 查找(平均而言，无法保证)。