Is remove_if and then effectively erase the vector?

Question

Although there are a few questions about remove_if + erase for vector. I could not find what the action of such an action is. When I write:

myVector.erase(remove_if(myVector.begin(), myVector.end(), some_predicate), myVector.end()); 

Delete if will return the iterator to the last matching element + 1 (let it name X). I believe this will happen in O (n).

But how will erasing work?

• If the erase tries to remove from X in myVector.end (), it will be O (n ^ 2), because it will copy the vector to a new location, and O (n) new allocations from the heap will be allocated.
• But if it removes from myVector.end () in X, it can do it in O (n) and, more importantly, it will not allocate new memory (something I'm trying to avoid).

Thanks.

Answer 1

Consider this vector:

 |0|1|2|3|4|5|6|7|8|9| 

We use remove_if to remove all elements that are multiples of 4:

 std::remove_if(v.begin(), v.end(), [](auto i){ return i != 0 && !(i%4); }); 

This starts iterating through the vector with the X iterator until it finds an element where the predicate returns true:

 |0|1|2|3|4|5|6|7|8|9| X 

This is the first item we want to remove.

Then it creates another iterator pointing to the next element, Y = X + 1, and checks the predicate for * Y:

 |0|1|2|3|4|5|6|7|8|9| XY 

The predicate is false, so we want to save this element, so it assigns the next element to the element that we want to delete by doing *X = std::move(*Y) :

 |0|1|2|3|5|5|6|7|8|9| XY *X = std::move(*Y) 

So, we have two iterators X and Y, where X points to the next element in "output" (that is, elements that we don’t delete), and Y is the next element to be deleted.

We move both iterators to the next position, check the predicate for Y (which is false again), and perform another assignment:

 |0|1|2|3|5|6|6|7|8|9| XY *X = std::move(*Y) 

Then he does the same in the following position:

 |0|1|2|3|5|6|7|7|8|9| XY *X = std::move(*Y) 

And then it moves on, but discovers that the predicate is true for Y

 |0|1|2|3|5|6|7|7|8|9| XY 

Thus, it simply increments Y, which skips this element and therefore does not copy it to the "output" position in X:

 |0|1|2|3|5|6|7|7|8|9| XY 

The predicate is not valid for Y, so it assigns it to X:

 |0|1|2|3|5|6|7|9|8|9| XY *X = std::move(*Y) 

Then it increases X and Y again

 |0|1|2|3|5|6|7|9|8|9| XY 

Now Y goes past the end, so we return X (which indicates the end of the output sequence, that is, the elements that we want to save).

After remove_if X remove_if we call v.erase(X, v.end()) , so the vector calls the destructors for each element from X to the end:

 |0|1|2|3|5|6|7|9|~|~| X end 

And then sets the size so that the vector ends with X:

 |0|1|2|3|5|6|7|9| end 

After that, v.capacity() >= v.size()+2 , because the memory that was used by the two finite elements is still present, but not used.

Answer 2

The complexity of vector::erase is well defined :

Linear: the number of calls to the destructor T coincides with the number of elements to be erased, the assignment operator T is called the number of times equal to the number of elements in the vector after the elements to be erased

How it will work inside (i.e. how exactly it is going to remove your elements) has nothing to do with it.

The complexity of remove_if also defined and

Exactly std :: distance (first, last) of the predicate application.

So your code has linear complexity.

Answer 3

Why not use the podkap pop approach? We deceived a lot with the optimization of erasure in vectors and found that it is the fastest, since it has O(1) complexity. The only drawback is that it does not keep order. Which is fine - a lot of things. Here is a template method for such an operation:

 template<typename T> inline typename std::vector<T>::iterator unorderedErase(std::vector<T>& p_container, typename std::vector<T>::iterator p_it) { if (p_it != p_container.end() - 1) { std::swap(*p_it, p_container.back()); p_container.pop_back(); return p_it; } // else p_container.pop_back(); return p_container.end(); }