Как использовать 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) операция - не постоянное время.