Erasing multiple items from std::vector-CodePudding

I'm thinking about some different ways of erasing several pointers of a std::vector of pointers. I know that de erase/remove_if idiom is a good suit, but I'm thinking about a situation in which I have a container of pointers to remove from the std::vector that I have, something like this:

std::vector<Object*> elementsToRemove;
 ... // fill elementsToRemove
 
 RemoveObjects(elementsToRemove, myObjectsVector)

I'm asking about this because in my project we are facing some performance issues mostly because of item-by-item removal of vector containers, which imply in several reallocations.

One way that I'm considering to implement this is with the erase/remove_if idiom, in which the predicate of the remove_if is a function that checks if the Object* is in the elementsToRemove Container.

Anyone have a better sugestion of how to approach this problem?

I'm considering to implement this is with the erase/remove_if idiom, in which the predicate of the remove_if is a function that checks if the Object* is in the elementsToRemove Container. However, this approach will require n x r comparisons (n is the number of Objects, and r is the number of objects to remove).

CodePudding user response：

If you can sort both vectors then you need only a single pass through both for remove_if (erase is linear as well):

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    std::vector<int>  X{1,2,3,4,5,6,7,8,9};
    std::vector<int>  remove{1,3,6,7};

    auto first = remove.begin();

    auto it = std::remove_if(X.begin(),X.end(),[&](int x) {
        while (first != remove.end() && *first < x)   first;        
        return (first != remove.end() && *first == x);     
    });

    X.erase(it,X.end());
    for (const auto& x : X ) std::cout << x << " ";
}

Sorting is O(N logN) so you'd get that in total.

Alternatively you can sort only RemoveObjects then looking up an element in it can be done via binary search.

Note that comparing the pointers via < is unspecified. Comparing them via std::less on the other does yield a (implementation defined) strict total order. std::sort uses std::less by default, you should need to consider that the resulting ordering is not necessarily consisten with <.