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