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

Question

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

https://stackoverflow.com/a/347478/783510 I think you are looking for the so called "remove/erase" idiom — Philipp Claßen, Jun 05 '20 at 15:38
@PhilippClaßen No as they are removing individual members at a time. I'm looking to do it all at once — Tom, Jun 05 '20 at 15:40
_"I'm looking to delete a whole bunch at once in a more compact way then"_ It just composes... put it in a function!! — Asteroids With Wings, Jun 05 '20 at 15:43

orlp · Accepted Answer · 2020-06-05T15:44:12.503

2

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.

edited Jun 05 '20 at 15:44

answered Jun 05 '20 at 15:38

orlp

112,504
36
218
315

To be honest, with such a small `removeItems`, it's probably faster to just stick with the vector and do an _O(n*m)_ search sequence. – Asteroids With Wings Jun 05 '20 at 15:39
@AsteroidsWithWings Possibly, but I don't know how large the *real* `removeItems` is. This solution scales linearly with any amount of `items`/`removeItems`, whereas keeping the vector is quadratic. – orlp Jun 05 '20 at 15:40
1

Yes, it scales, but has worse _actual_ performance until you have many elements to remove. When writing code we should consider reality not just theoretical extensions. At the very least the answer should mention this. – Asteroids With Wings Jun 05 '20 at 15:41
@cdhowie It doesn't need to? – Asteroids With Wings Jun 05 '20 at 15:41
Thanks a lot! Worked like a charm, I had a hunch sets might have something to do with it! – Tom Jun 05 '20 at 18:11

songyuanyao · Answer 2 · 2020-06-05T16:04:04.217

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.

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

2 Answers2