CODEWITHSUNDEEP
c++vectorbooststl
Miral
Miral

Reputation: 13030

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

Given:

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.)

Upvotes: 1

Views: 2276

Answers (3)

Rerito
Rerito

Reputation: 6086

I suppose your elements have unique IDs, so instead of storing the elements to remove in an std::vector, just store them in an std::unordered_set.

This way, the std::remove_if way is really clean:

struct Item {
    int id;
};

// ...
std::vector<Item> items;
std::unordered_set<int> idsToRemove;
items.erase(
    std::remove_if(std::begin(items), std::end(items), [&](Item const& it) {
            return (idsToRemove.find(it.id) != std::end(idsToRemove));
        }),
    std::end(items));

Complexity (amortized) will be O(N) where N is the number of elements in the vector.

Upvotes: 0

Miral
Miral

Reputation: 13030

I don't consider this a real answer to the question as stated (since it moves the goalposts), but it's something I found while investigating it and it may be of use to future searches.

In the case where you don't have the idsToRemove passed in externally, but need to iterate through the items anyway to decide which to remove, then there's a fairly nice way to do this in O(N):

#include <boost/range/algorithm_ext/erase.hpp>

boost::range::remove_erase_if(items, [&](const Item& item)
{
    // do whatever else you want to item
    // return true to erase the item, or
    return false; // to keep it
});

Internally it's based around std::remove_if, but it's much tidier and resembles range-based-for.

Upvotes: 0

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

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.

Upvotes: 2

Related Questions