1

I'm facing a problem when I delete duplicate values in a vector. I know that when a vector value gets deleted the vector gets re-allocated for maintaining the data without any "dark holes". The problem is that when I'm using remove() inside a loop, when the code runs back to the condition statement of it, I get an assertion failed message.

My question is: if I'm using nums.end() at a condition for the iteration, does it get a static value of an iterator, or for each iteration it returns a new iterator that points to the end of the new re-allocated vector? If it does or if not, what seems to be wrong with the incrementation?

while ( itfast != nums.end()) {
        if (*itslow == *itfast) {
            nums.erase(itfast);
        }
        else {
            itslow++;
            itfast++;
        }
    }
ishaishai
  • 73
  • 9
  • 2
    `nums.erase(itfast);` invalidates `itfast` **and** `itslow` as well. Use `itfast = nums.erase(itfast);` instead. Take case about `itslow` invalidation. Also, change `itslow++; itfast++;` to `++itslow; ++itfast;`. – Daniel Langr Sep 07 '19 at 15:00
  • Thats weird, when debugging before the change you've recommended I saw it incremented "itfast" to the next element, so what is so different about those two approaches? (I've also seen that erase returns the new iterator state after removing the element) – ishaishai Sep 07 '19 at 15:05
  • The difference is that your code causes **undefined behavior**. Simply said, the code has a bug in it which might not reveal itself sometimes (which is especially dangerous about undefined behavior). – Daniel Langr Sep 07 '19 at 15:08
  • Moreover, there are "canonical" ways how to remove duplicates from a vector. See, e.g., https://stackoverflow.com/a/1041939/580083. You have quite a big problem with invalidation of `itslow`. (Might be removed by working with indexes instead of iterators.) – Daniel Langr Sep 07 '19 at 15:09
  • Surely true, tried to work my way around the vector structure only. – ishaishai Sep 07 '19 at 15:13
  • BTW, `erase` will invalidate `end()` as well, so there is no "static" value. After each `erase`, the value of `end()` will be different. – Daniel Langr Sep 07 '19 at 15:15

1 Answers1

1

std::vector.erase invalidates the current iterator, but returns an iterator pointing to the next valid iterator passed the one erased.

itfast = nums.erase(itfast);

As Daniel pointed out, this will invalidate any other iterator you have so you must handle the itslow case as well.

When dealing with more complicated erasing it can be much simpler and less error prone to deal with indices instead, though there are also pitfalls regarding itslow if you remove an element and itslow >= removed element. Without seeing what your exact problem is I can't say precisely which to use.

Please see the cppreference for more details regarding erase. There are also several other questions very similar to this.

https://en.cppreference.com/w/cpp/container/vector/erase std::vector iterator invalidation

Kevin Bright
  • 71
  • 4
  • This hardly answers the question. You just pointed to a single problem. What about invalidation of `itslow`? Why don't you link the questions you are talking about? Why don't you provide some solution? The change you propose **will not make the code correct**. – Daniel Langr Sep 07 '19 at 15:13
  • Thanks Daniel for the feedback for my first answer. I made some adjustments and will keep those in mind. – Kevin Bright Sep 07 '19 at 15:33