0

I was doing this leetcode question of removing duplicates from sorted vector and return new size of vector, I came up with obvious simple approach to remove duplicates. but during my time of answering the question i found out erase() invalidate the itrator after deletion. but why i used this code it got accepted and i ran it on some other online compilers with some test cases and it also worked there. i don't understand why i can use previously initialized itrator even though it should be invalidated.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0)
        {
            return 0;
        }
       for(auto i=nums.rend()-1;i>nums.rbegin();i--)
       {
           int seclast=*(i-1);
           if(seclast==*i)
           {
               nums.erase(i);
               // i--;
           }
       }
       return nums.size();
    }
};
mch
  • 9,424
  • 2
  • 28
  • 42
meivinay
  • 9
  • 4
  • 3
    Undefined behaviour doesn't mean "absolutely will not work" it means "don't depend on it." Often to get things to break you'll have to do something other than the most trivial thing possible. In practice undefined behaviour only visibly manifests when you've allocated something else on the stack in the place formerly occupied by the thing you're still (erroneously) referencing. – tadman May 14 '21 at 18:23
  • Does this answer your question? [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) – mch May 14 '21 at 18:25
  • `erase` only invalidates iterators after the removed item. – mch May 14 '21 at 18:25
  • Tip: Don't use `*(i+n)` use `i[n]`. – tadman May 14 '21 at 18:27
  • *i don't understand why...* -- Welcome to the world of C++, where if you make a mistake like this (or perceived mistake like this), anything can happen, including "works correctly". – PaulMcKenzie May 14 '21 at 18:29
  • aka *"the world where we rely on guarantees rather than examine the latest implementation and hope it keeps working the same way on next vm upgrade"*. – spectras May 14 '21 at 18:35
  • Side note: Removing while iterating is a common source of errors. It is rerecommended that you employ the [Erase-Remove Idiom](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom) instead. – user4581301 May 14 '21 at 18:39
  • Please note, that beside anything else, this is extremely inefficient implementation. – SergeyA May 14 '21 at 18:43
  • i know its a inefficient apporoach, i know i can use i[n[, i know and thankful for everyhting you all recommending, but can you please also answer the question, why i can use same itrator even after erase a element (my code definetly removing elements from vector). – meivinay May 14 '21 at 19:03
  • @mch the link you gave says erase invalidate iterator after or at removal of element. Thats the main concern ,my code is definetly removing elements but not invalidating itrator. or does rend() does not follow this property? – meivinay May 14 '21 at 19:09
  • Invalidated doesn't necessarily mean gone, overwritten or will crash the program if you use it. It means you can't count on what will happen. See the first comment. Why is this? Because any testing required to ensure predictable behaviour would be a performance penalty for programs that are written correctly and do not use invalidated iterators. In the land of the C++, speed is almost always king. – user4581301 May 14 '21 at 20:04

0 Answers0