set iterator is not like vector iterator i cant add to the iteratire so how can i do binary search on a set and how can i find the diffrence betwen two positions in a set
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3976 |
| 2 | tourist | 3815 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3614 |
| 5 | orzdevinwang | 3526 |
| 6 | ecnerwala | 3514 |
| 7 | Benq | 3482 |
| 8 | hos.lyric | 3382 |
| 9 | gamegame | 3374 |
| 10 | heuristica | 3357 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | -is-this-fft- | 166 |
| 3 | Um_nik | 161 |
| 3 | atcoder_official | 161 |
| 5 | djm03178 | 157 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 154 |
| 8 | luogu_official | 152 |
| 9 | awoo | 151 |
| 10 | TheScrasse | 147 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2025 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.01.2025 12:02:43 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
You can use :
s.lower_bound(x)s.upper_bound(x)thanks , but i want to find the index of the returned iterator from the function
It's impossible ! :(
But you can use Ordered_Set
ref: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/
Sounds like you need a self-balancing binary search tree. You can learn something about __gnu_pbds :: tree, which has implemented one.
index can be find using distance of required iterator with the begin iterator, distance is present in c++ stl.
That is O(n) if you use a set (or multiset, for that matter), since iterators work differently in those data structures. The reason it works in O(1) for a vector is that vectors have random-access iterators.
You can solve pbds if you are facing problem due to limitations in set and multiset. You can learn it from here: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/amp/
Make sure you are using c++20, because pbds use red-black tree and it applies operations in log(n) but it consumes slidely more time than set and multiset.C++20 is faster. So it should be preferred. You can see the blog to realise that: https://codeforces.me/blog/entry/113537
use ordered_set with s.order_of_key(x) which gives the position of x in log(n) time.