Halym2007's blog

What is the difference between them?
By Halym2007, history, 3 months ago, In English

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
  • Vote: I like it
  • +40
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by Halym2007 (previous revision, new revision, compare).

→ Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by Halym2007 (previous revision, new revision, compare).

→ Reply
»
3 months ago, # |
← Rev. 4   Vote: I like it -22 Vote: I do not like it

.

→ Reply
»
3 months ago, # |
← Rev. 3   Vote: I like it +68 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agree, but what is the difference between these two for a set.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is no difference in the final result for an ordered_set (like in this case).

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Difference will be in speed of execution. If you pass value to erase function, std::set has to search for it. If you pass pointer, it doesn't.

      → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it

First One s.erase(tr) -> O(1)

Second One s.erase(*tr) -> O(logN)

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 3   Vote: I like it +37 Vote: I do not like it

    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)?

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      Upon using iterator, it's constant time removal. However, I am not sure why such a useful blog is downvoted !

      → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Remember that complexity is an amortized constant, not a worst-time constant. [reference]

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate how that is true? I see that it is written but don't understand how it is O(1) amortized...

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply