Efficient way to filter items from std :: vector

Question

I finished the following code to filter out some bad elements from std :: vector:

#include <iostream> #include <vector> #include <algorithm> typedef struct mystruct { int id; std::string name; }; int main() { std::vector<mystruct> all_items = {{151, "test1"}, {154, "test4"}, {152, "test2"}, {151, "test1"}, {151, "test1"}, {153, "test3"}}; std::vector<int> bad_ids = {151, 152}; std::vector<mystruct> filter_items; for (const auto& item : all_items) { if ( std::find(bad_ids.begin(), bad_ids.end(), item.id) != bad_ids.end() ) { std::cout << "id: " << item.id << " is bad" << std::endl; } else { std::cout << "id: " << item.id << " is good item" << std::endl; filter_items.emplace_back(item); } } for (auto f : filter_items) { std::cout << "Good item: " << f.id << std::endl; } } 

Is there a more efficient way? Is it possible to use std :: remove_copy_if or boost here and how?

Answer 1

Yes, you can use std :: remove_copy_if , for example

 std::remove_copy_if( all_items.begin(), all_items.end(), std::back_inserter(filter_items), [&bad_ids](const mystruct& item) { return std::find(bad_ids.begin(), bad_ids.end(), item.id) != bad_ids.end(); }); 

Live

Or you can use std :: remove_if and erase bad elements on a vector, like

 all_items.erase( std::remove_if( all_items.begin(), all_items.end(), [&bad_ids](const mystruct& item) { return std::find(bad_ids.begin(), bad_ids.end(), item.id) != bad_ids.end(); }), all_items.end()); 

Live

Answer 2

expands on @songyuanyao's correct answer, it never bothers to keep a small library of helper containers to make the code more expressive.

 #include <iostream> #include <vector> #include <algorithm> struct mystruct { int id; std::string name; }; template<class T, class A, class Pred> std::vector<T, A> copy_unless(std::vector<T, A> container, Pred&& pred) { container.erase(std::remove_if(container.begin(), container.end(), std::forward<Pred>(pred)), container.end()); return container; } template<class Container, class Pred> bool any_match(Container&& container, Pred&& pred) { return std::find_if(container.begin(), container.end(), pred) != container.end(); } int main() { std::vector<mystruct> all_items = {{151, "test1"}, {154, "test4"}, {152, "test2"}, {151, "test1"}, {151, "test1"}, {153, "test3"}}; std::vector<int> bad_ids = {151, 152}; auto is_bad = [&bad_ids](mystruct const& item) { auto match_id = [&item](int id){ return item.id == id; }; return any_match(bad_ids, match_id); }; auto filter_items = copy_unless(all_items, is_bad); for (auto&& f : filter_items) { std::cout << "Good item: " << f.id << std::endl; } } 

I am sure that I remember such a library in boost, but for life I do not remember what it is.

Answer 3

I suggest Boost Range:

Live on coliru

 int main() { myvec all_items = { { 151, "test1" }, { 154, "test4" }, { 152, "test2" }, { 151, "test1" }, { 151, "test1" }, { 153, "test3" } }; auto is_good = [bad_ids = std::set<int> { 151, 152 }](mystruct v) { return bad_ids.end() == bad_ids.find(v.id); }; // just filter on the fly: for (auto& f : all_items | filtered(is_good)) { std::cout << "Good item: " << f.id << std::endl; } // actually copy: auto filter_items = boost::copy_range<myvec>(all_items | filtered(is_good)); } 

Print

 Good item: 154 Good item: 153 

Improvement ...

You can improve the style by slightly changing the situation:

Assuming you have a utility like contains :

 template <typename... Arg, typename V> bool contains(std::set<Arg...> const &set, V const &v) { return set.end() != set.find(v); } template <typename... Arg, typename V> bool contains(std::vector<Arg...> const &vec, V const &v) { return vec.end() != std::find(vec.begin(), vec.end(), v); } 

Then it becomes more readable:

Live on coliru

 auto is_good = [&bad_ids](auto& v) { return !contains(bad_ids, v.id); }; for (auto& f : all_items | filtered(is_good)) { std::cout << "Good item: " << f.id << std::endl; } 

Now I feel that the entire list of bad_ids can also be dynamic. But if it is not, you can be more "in place" using Phoenix:

Peak Hipster:

Live on coliru

 for (auto& f : all_items | filtered(!contains_(std::set<int> { 151, 152 }, arg1->*&mystruct::id))) { std::cout << "Good item: " << f.id << std::endl; } 

I know. This pushes him for no good reason, but hey. Just show :)

Answer 4

Why not use the partition algorithm? It will reconfigure all_items so that the good items are placed first and the bad ones afterwards.

http://en.cppreference.com/w/cpp/algorithm/partition