Effective way to remove items from a vector

Question

I am currently planning to remove all elements from a vector that is not found in the set.

For instance:

#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 code above works, it is inefficient, as I start at the origin of the vector every time I delete an element.

Is there a better way?

Answer 1

Yes; you can use erase / delete idioms with a special 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 want to sort the range first, you have other options that might work better ( std::set_intersection , for example).

Answer 2

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

Answer 3

I would suggest copying the elements you want to save in another vector, instead of parsing the vector again from the beginning after each deletion. In addition, you must keep the iterator returned by the end() method outside the loop if the collections are no longer modified in the loop, since calling end() is expensive for some STL implementations. Some compilers optimize this, but not always.

Answer 4

This can help sort the vector first, since the set itself is ordered. An option would be to order the vector by existence in the set, and then cut all the objects at once.

Answer 5

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

It requires sorted vectors.

Answer 6

The remove_if () algorithm will do this, but you need a predicate to determine if there is an element in your collection.

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

If your vector is sorted, you can use set_intersection. It will also allow only one copy of each item found.