| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3857 |
| 2 | jiangly | 3747 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3591 |
| 6 | gamegame | 3477 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3463 |
| 9 | ecnerwala | 3451 |
| 10 | heuristica | 3431 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | -is-this-fft- | 161 |
| 3 | Qingyu | 160 |
| 4 | Dominater069 | 158 |
| 5 | atcoder_official | 157 |
| 6 | adamant | 155 |
| 7 | Um_nik | 152 |
| 8 | djm03178 | 151 |
| 9 | luogu_official | 150 |
| 10 | awoo | 148 |
Hello everyone, I hope you are doing well, can anybody explain to me why this code costs O(n) on sets and multiset but in the other side it costs O(log(n)) on the sorted vectors.
the code ->
multiset ms; int x ; auto it = upper_bound(ms.begin() , ms.end() , x) ;
between this code cost O(log(n)) auto it = ms.upper_bound(x);
Auto comment: topic has been updated by Radiohead___ (previous revision, new revision, compare).
Multisets and sets in c++ cannot be queried for k-th element, in contrast to sorted vectors. The upper_bound function implemented for sets is different from the general purpose upper_bound, and the latter will take O(n) as specified in the c++ documentation: "On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average." Set iterators in c++ support the advance ++ or -- operations, and that's why it will take O(n) for the general upper bound in sets.
In addition, if you need to access the kth element, try using an order-statistic tree