| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
both code did same.what is the difference?
First one :
set <int> s;
s.insert (1);s.insert (3);s.insert (5);
auto tr = s.lower_bound (2);
s.erase (tr);<-----------here
--------------------------
Second one :
set <int> s;
s.insert (1);s.insert (3);s.insert (5);
auto tr = s.lower_bound (2);
s.erase (*tr);<-----------here
Auto comment: topic has been updated by Halym2007 (previous revision, new revision, compare).
Auto comment: topic has been updated by Halym2007 (previous revision, new revision, compare).
.
The real difference is when you use multiset and have multiple values, the first code removes only one occurrence of 3(lower_bound of 2 in the set is 3) but the second one removes all of them.
The reason is that tr is a pointer to one element, while *tr is the value of the pointer, which when used in a multiset, removes all occurrences of that element.
Agree, but what is the difference between these two for a set.
There is no difference in the final result for an ordered_set (like in this case).
Difference will be in speed of execution. If you pass value to
erasefunction,std::sethas to search for it. If you pass pointer, it doesn't.tr is an iterator so is pointing to the memory address while *tr means dereferencing the iterator and is accessing value at that memory address
First One
s.erase(tr)-> O(1)Second One
s.erase(*tr)-> O(logN)Are you sure s.erase(tr) is O(1), shouldn't it also be O(log N) since std::set is implemented with red-black trees and deletion in a red-black tree is O(log N)?
Upon using iterator, it's constant time removal. However, I am not sure why such a useful blog is downvoted !
Remember that complexity is an amortized constant, not a worst-time constant. [reference]
Can you please elaborate how that is true? I see that it is written but don't understand how it is O(1) amortized...
You can not remove from rb tree single node in O(1). Because multiple rotations can be met. But in practice, this is almost always single rotation. So this is not amortized O(1), but O(1) with high probability.
Thank you
The first code snippet erases the element using the iterator directly.
The second code snippet dereferences the iterator to get the element's value before erasing.