如何使用lower_bound / upper_bound从std :: set获取索引号？

Question

我正在尝试使用STL提供的二进制搜索功能，该功能要求首先对向量进行排序。因此，这就是为什么我尝试直接使用Set的原因，所以我不必先排序。

但是以下列方式使用时，

`

#include <bits/stdc++.h>
using namespace std;
int main(){
set <int> mn = {11, 33, 44, 66, 80,90};
auto it= mn.lower_bound(55);
cout<<it-mn.begin();
    return 0;
}

`

发生错误，说：

错误：与'operator-'不匹配（操作数类型为'std :: _ Rb_tree_const_iterator'和'std :: set :: iterator'

如何在这里使用set获取返回的迭代器的索引号？

PS：我也尝试过使用set :: lower_bound，但是显示相同的错误。

Answer 1

set的迭代器是双向迭代器，这意味着您不能减去其中两个。

您可以这样计算距离：std::distance(mn.begin(), it)，但是您需要注意，对于双向迭代器，这是O(N)操作-不是恒定时间。