optimization: vector.erase() of pointer

user_15635253 0
Viewed 31

I have a question about deleting a dynamic vector of pointers and optimization.

Here is my code. It checks wether an element has to be set to nullptr and then it delete all those elements.

for (auto* el : elements)
    {
        if (el != 0)
            // do something
        else
            el = nullptr;
    }
    elements.erase(std::remove(elements.begin(), elements.end(), nullptr), elements.end());

Is the complexity of this operation onerous for the machine ? And if it is, then is there a better way of doing it and it is worth it ? Because, here, the preservation of the index order is not important for me.

Thank you !

vector pointers erase optimization
1 Answers

Is the complexity of this operation onerous for the machine ?

It is a bit costly, but not much more than the previous operation. Indeed, remove will typically check the value of each item, and if an item needs to be removed, the algorithm shifts the item on the right to put it on the current analysed item. erase is often relatively cheap since it just resizes the vector to skip the remaining garbage at the end (generally without any copy or reallocation) and call the destructor of the discarded items (costly only if there is a lot of them and the destructor is non-trivial). This operation can be as costly as the previous one.

And if it is, then is there a better way of doing it and it is worth it ? Because, here, the preservation of the index order is not important for me.

Yes, this is possible: you can just iterate over the array with a classical loop and swap the current item with the one of the end to discard it. You need to maintain a end iterator moving from the end to the beginning. The loop stops when the end iterator is reached. Note that the swapped items coming from the end should be checked by your predicate too.

Alternatively, you could just use std::partition at this algorithm does a quite similar job and is simpler: it puts the items validating a given condition to the left part and put the other on the right part. You can then just resize the array to remove the unwanted right part.

std::partition should is bit less efficient than the other swap-based approach only if there is a lot of item to remove since it has to maintain the consistency of both sides.

Here is an (untested) example with std::partition:

auto discardedBegin = partition(elements.begin(), elements.end(), doSomething);
elements.erase(discardedBegin, elements.end());
user_129395570
Related