Efficient way to remove items from vector

Question

Currently, I plan to remove all items from vector, which is not found in a set.

For example :

#include <vector>
#include <set>
#include <string>
#include <iostream>

using namespace std;

int main() {
    std::set<string> erase_if_not_found;
    erase_if_not_found.insert("a");
    erase_if_not_found.insert("b");
    erase_if_not_found.insert("c");

    std::vector<string> orders;
    orders.push_back("a");
    orders.push_back("A");
    orders.push_back("A");
    orders.push_back("b");
    orders.push_back("c");
    orders.push_back("D");

    // Expect all "A" and "D" to be removed.
    for (std::vector<std::string>::iterator itr = orders.begin(); itr != orders.end();) {
        if (erase_if_not_found.find(*itr) == erase_if_not_found.end()) {
            orders.erase(itr);
            // Begin from start point again? Do we have a better way?
            itr = orders.begin();
        } else {
            ++itr;
        }
    }

    for (std::vector<std::string>::iterator itr = orders.begin(); itr != orders.end(); ++itr) {
        std::cout << *itr << std::endl;
    }

    getchar();
}

Although the above code work, it is not efficient, as I begin from vector's start point each time I delete an item.

Is there a better way?

Answer 1

Yes, there is a better way - you can move the items that are to be removed at the end of the vector. Then just cut out the ending of the vector after the loop ends.

Answer 2

I would suggest to copy elements you want to keep in another vector instead of parsing again the vector from the beginning after each removal. Also, you should store the iterator returned by end() method outside the loop if the collections are not modified anymore in the loop as calling end() is costly for some STL implementations. Some compilers are optimizing that, but not always.

Answer 3

It may help to sort first the vector, as the set is itself ordered. A variant could be to order the vector by existance in the set, then chop all items at once.

Answer 4

Yes; you can use the erase/remove idiom with a custom predicate:

template <typename SetT>
struct not_contained_in_set_impl
{
    not_contained_in_set_impl(const SetT& s) : set_(s) { }

    template <typename T>
    bool operator()(const T& v)
    {
        return set_.find(v) == set_.end();
    }

    const SetT& set_;
};

template <typename SetT>
not_contained_in_set_impl<SetT> not_contained_in_set(const SetT& s)
{
    return not_contained_in_set_impl<SetT>(s);
}

Used as:

orders.erase(
    std::remove_if(orders.begin(),
                   orders.end(),
                   not_contained_in_set(erase_if_not_found)), 
    orders.end());

[compiled in my head on the fly]

If you are willing to sort the range first, you have other options that may perform better (std::set_intersection, for example).

Answer 5

I'm not sure if what you ask for is the intersection of two vectors, but if so, you might take a look at std::set_intersection.

It requires sorted vectors though.

Answer 6

The algorithm remove_if() will do this but you need a predicate to determine if the item is not in your set.

You can also use remove_copy_if() to copy your items into a new vector.

If your vector is sorted you can use set_intersection. That would also only allow one copy of each found element.