如何使用 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;
}

'

发生错误，指出：

错误：与"运算符-"不匹配(操作数类型为"std：：_Rb_tree_const_iterator"和"std：：set：：迭代器">

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

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

Answer 1

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

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

Answer 2

我也遇到了类似的问题，所以我使用了排序向量而不是集合并执行了操作(它 - v.begin(((。

Answer 3

因为它基于一棵树，你不能只是从中随机减去开头。例如，向量是一种线性数据结构，这意味着您可以对其应用这种操作。

如果要执行此操作，可以使用Ordered_set。您可以在gnu_pbds命名空间中找到它。

这是它的链接： https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/