Miral Miral - 9 months ago 60
C++ Question

Removing a known subset of items from a c++ vector


  • struct Item { int id; ... };

  • std::vector<Item> items;

  • std::vector<int> idsToRemove;

What's the most efficient / cleanest way to write the code that performs the removal (while retaining order)?

, this could be:

items.erase(std::remove_if(items.begin(), items.end(),
[&](const Item& i) {
return std::find(idsToRemove.begin(), idsToRemove.end(), i.id)
!= idsToRemove.end();
}), items.end());

Another way might be:

for (auto id : idsToRemove)
items.erase(std::remove(items.begin(), items.end(), id), items.end());
// or items.erase(std::find(items.begin(), items.end(), id));
// provided that we know id always exists in items

Neither of these feel particularly nice (and they both seem O(N*M)), though the second seems tidier than the first. Is there a better way?

(If it helps, while neither vector is sorted, it is known that
is a subset of ids in the same order that they appear in
, and that both arrays are small. And I can use Boost algorithms if there's something suitable over there.)

Answer Source

Since the ids in idsToRemove are known to be in items and in the same order, you can use a couple of iterators into items to keep track of the current compare element, the current destination, and walk thru idsToRemove and items, comparing both elements, moving the ones that you want to keep. At the end of that process, resize items to be the new smaller size.