CODEWITHSUNDEEP
c++vectoriterator
Tom
Tom

Reputation: 1291

C++ Remove vector items that exist in another vector WHILE retaining order

std::vector<int> items = {1, 2, 3, 4, 5};
std::vector<int> removeItems = {2, 4};

I need to delete the values in items that are in removeItems, while retaining the order of items. Something like this:

items.remove(removeItems);

Output

items = {1, 3, 5}

Are there any built in vector methods that can achieve this? I haven't found any that accept another vector of items to remove. If not, whats the most efficient way of achieving this?

Edit

Erasing elements from a vector This post refers to removing one item at a time, I'm looking to delete a whole bunch at once in a more compact way then 

for(num in removeItems) {
    items.erase(std::remove(items.begin(), items.end(), num), items.end())
}

Because surely this way of removing items is very inefficient because you have to check the entire items vector twice (removeItems.size()) for each item in removeItems

Edit 2

Number of elements in items or removeItems will be in the range 0-10000

Upvotes: 0

Views: 975

Answers (2)

songyuanyao
songyuanyao

Reputation: 172924

You can apply erase-remove idiom, with help of std::remove_if and std::find.

std::vector<int> items = {1, 2, 3, 4, 5};
std::vector<int> removeItems = {2, 4};
items.erase(std::remove_if(std::begin(items),
                           std::end(items),
                           [&removeItems](auto i) { return std::find(std::begin(removeItems), std::end(removeItems), i) != std::end(removeItems); }),
            std::end(items));

Note that std::remove_if just shifts the elements to be removed to the back of the vector; these elements are erased by std::vector::erase later at a time.

Upvotes: 2

orlp
orlp

Reputation: 117681

The most efficient general form is to turn removeItems into an unordered set, and then remove elements from items by checking for membership.

std::unordered_set<int> removeSet(removeItems.begin(), removeItems.end());
items.erase(std::remove_if(items.begin(), items.end(), [&](int x) {
    return removeSet.count(x) != 0;
}), items.end());

If removeItems is small a linear scan is probably faster than turning it into an unordered set. For large removeItems the above is the most efficient, unless it has a very special form (such as only having small elements).

If both arrays are already sorted (like they are in your example, assuming that isn't coincidence) you can do even better than the above.

Upvotes: 2

Related Questions