Miral Miral - 1 month ago 9
C++ Question

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

Given:


  • 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)?

Using
remove_if
, 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
idsToRemove
is a subset of ids in the same order that they appear in
items
, and that both arrays are small. And I can use Boost algorithms if there's something suitable over there.)

Answer

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.

Comments