1

I have a vector V and I would like to store which elements of this vector I will later have to remove.

To do that I've used an other vector Y to store the iterators of the elements of V that I want to remove. So I iterate through Y to access the iterators of the elements I need to remove in V.

The problem is that when you erase elements from V, all the iterators in Y (pointing on elements of V) become invalid.

I can't find any answer but it seems so trivial that there must be a simple workaround, isn't it ?

gpalex
  • 826
  • 1
  • 11
  • 27
  • 1
    when erasing elements from vector, use backwards iterators (no more dereferencing issues) – lucasg Jul 03 '13 at 12:19

4 Answers4

5

Use V.erase(std::remove_if(V.begin(), V.end(), MyPredicate()), V.end())

rectummelancolique
  • 2,247
  • 17
  • 13
  • Your predicate that decides whether the elements it gets passed is to be removed or not. – rectummelancolique Jul 03 '13 at 12:18
  • The thing that determines whether an element should be erased or not (see here for more details: http://stackoverflow.com/questions/6854039/correct-way-to-define-a-predicate-function-in-c) – Talvalin Jul 03 '13 at 12:19
  • Exept that in this case the predicate is not simple, that would require double the work (too greedy in term of computing power) – gpalex Jul 03 '13 at 12:19
  • 2
    Why would it require double the work? The code that tests your "to be removed" condition has to be written somewhere. Whether it's written inside your `for` loop or in the `operator()` of a `struct MyPredicate` does not double the amount of work and makes your code more versatie. – rectummelancolique Jul 03 '13 at 12:22
  • Don't you mean `V.erase(V.begin(), std::remove_if(V.begin(), V.end(), MyPredicate()))` – PureW Jul 03 '13 at 14:32
  • No, I really don't. Try it :) – rectummelancolique Jul 03 '13 at 15:36
3

You can use std::vector<unsigned> indices to store the index values of each element.

Sceptical Jule
  • 889
  • 1
  • 8
  • 26
2

Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators, pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements they were referring to before the call.

http://www.cplusplus.com/reference/vector/vector/erase/

So if the elements (iterators) of Y are sorted, you could just iterate over Y backwards and delete the corresponding elements in V. This works since only iterators to later elements in V are invalidated when you erase elements in V.

PureW
  • 4,568
  • 3
  • 19
  • 27
  • This seems like it would work, but keep in mind that .erase() returns the _next iterator_, so you'd have to make sure and decrement it. Also [this post](http://stackoverflow.com/questions/6096279/keeping-a-valid-vectoriterator-after-erase) has some useful discussion. – Pat Lillis Jul 03 '13 at 12:22
  • No, you wouldn't need the return value of erase. Since you are deleting elements in V starting from the end, you never invalidate your iterators in Y. – PureW Jul 03 '13 at 12:23
0

This is about complexity.

You can erase elements from higher indices to lower indices, in that case your approach will work, but each time you erase an element of a vector, the ones following it will be relocated. This has complexity linear in the number of element following the erased element, so I would expect sort of quadratic compexity, or O(number_of_elements * number_of_elements_to_be_erased).

If the number of deletions is high, and the indices of elements to erase are distributed more or less uniformly over the entire range, a better solution from the complexity point of view would be to work on the complement of "element to be erased". Instead, it would be "elements to be retained", you would copy the elements which should stay to a new array and assign it to the old one. This is linear in the number of elements in the vector, O(number_of_elements).

Better still, if you have a complete control over the implementation and can change std::vector for std::list, you could proceed with the rest exactly as you described, with no ill side effects. In that case, the erases are also efficient, done in constant time, so the entire operation is O(number_of_elements_to_be_erased).

ondrejdee
  • 476
  • 2
  • 8
  • But wouldn't a copy be more expensive than a deletion ? – gpalex Jul 03 '13 at 12:38
  • Depends on #elements to be erased, and where they are. You are right that in my analysis, I assumed that the number of deletions is high, and are distributed uniformly over all indices. Edited the answer accordingly. – ondrejdee Jul 03 '13 at 12:41
  • @gpalex imagine that your vector is long (=1000, say), and you should delete first 10 elements. This means relocating the 1000 elements 10 times (10000 operations). Compared to this, copying means going over the array just once (1000 operations). – ondrejdee Jul 03 '13 at 12:45
  • @gpalex added complexities in O() notation to make it more readable. – ondrejdee Jul 03 '13 at 12:48
  • Yes but it depends on the data a lot – gpalex Jul 03 '13 at 12:49
  • I do not know the details of your problem, but HTH. You can't go wrong with using std::list from the erase complexity point of view, but this may be something which can't be done (e.g. you need need random access) – ondrejdee Jul 03 '13 at 12:51