### dg25's blog

By dg25, history, 7 weeks ago,

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

• +5

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by dg25 (previous revision, new revision, compare).
 » 7 weeks ago, # | ← Rev. 3 →   0 set.erase(iterator) is O(1) while set.erase(value) is O(log set.size())set.erase(value) == set.erase(set.find(value))
 » 7 weeks ago, # |   +15 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 multiset::erase(iterator) -> constant 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.
•  » » 7 weeks ago, # ^ |   +1 ok..thanks got it..
 » 7 weeks ago, # |   +1 Bro, you're just copying map every time in dfs, it's pretty heavy, you know.
•  » » 7 weeks ago, # ^ |   +1 It still gets accepted if we remove '&'