divyanshuGupta's blog

Regarding time complexity of erase in std::set
By divyanshuGupta, history, 4 years ago, In English

Is there any massive time complexity difference between erasing a value from the set using -- set_name.erase(iterator) and set_name.erase(set_name.find(iterator)) when we are sure that iterator refers to a value present in the set..i am asking this because this shows time limit exceeded but this one does not shows any time limit exceeded ...please help

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

set.erase(iterator) is O(1) while set.erase(value) is O(log set.size())

set.erase(value) == set.erase(set.find(value))

→ Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

In your first submission(TLE) you are not using the multiset::erase(iterator) version but instead using the multiset::erase(val). Since you have derefernced the reverse iterator auto it = *values.rbegin();, it stores the value at the end of the multiset.

According to C++ Reference, the complexity of

  1. multiset::erase(iterator) -> constant

  2. multiset::erase(val) -> logarithmic in container size, plus linear in the number of elements removed.

Since the second version removes every occurence of the value(if present) present in the multiset.

And if you need to remove only 1 occurence of the multiple then you should use multiset::find(val) to get a iterator and then remove using the 1st version.

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

Bro, you're just copying map<int, ll> every time in dfs, it's pretty heavy, you know.

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

auto it = *values.rbegin(); it is not iterator it is value because pointer return value on using *; auto it = values.begin(); if use it, it run

→ Reply