从std::vector中过滤元素的高效方法

Question

我已经编写了以下代码，以便从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;
    }
}

有没有更高效的方法？能否在这里使用std::remove_copy_if或Boost？

- georgeliatsos

---

如果您有可用的代码需要改进，最好在SE Code Review上询问。 - user0042

谢谢！我能轻松地将它转移到SE代码审查中吗，还是应该复制/粘贴它？ - georgeliatsos

是的，只需复制您整个问题标记。将其作为问题放在那里，然后删除此问题。 - user0042

你的应用程序中bad_ids有多少元素？如果超过几个，那么使用集合可能会更好。 - rustyx

@RustyX：我预计bad_ids中会有一些元素是非唯一的。 - georgeliatsos

Answer 1

是的，你可以使用std::remove_copy_if，例如：

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(); });

现场演示

或者您可以使用std::remove_if和erase直接在向量上删除坏元素，例如：

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

现场

- songyuanyao

Answer 2

扩展 @songyuanyao 的正确答案，保留一些容器的帮助函数有助于使代码更易于理解。

#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;
    }
}

我确定在boost库中有类似的库，但我想不起来是哪一个。

- Richard Hodges

---

你有没有考虑过使用Boost Range？也许可以。 - sehe

@sehe 我想那就是了。有趣的是我从未使用过它。我对算法接口不太熟悉——将返回类型指定为模板参数的想法似乎有点古老。我相信我们作为一个社区可以做得更好。 - Richard Hodges

copy_range是其中的异类。顺便说一下，Boost就是我们社区。一起贡献吧 :) - sehe

@sehe 正在解决方案。我相信我们可以制定出具有表现力、高效和100%安全的算法。保持更新。 - Richard Hodges

Answer 3

我建议使用Boost Range： 在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));
}

打印

Good item: 154
Good item: 153

优化...

你可以通过将一些内容进行提取来改善样式：

假设你拥有像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);
}

然后它变得更易读：

在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;
}

现在，我觉得整个bad_ids列表可能也可以是动态的。但如果不是，您可以更加“原地”使用Phoenix：

巅峰时尚：

在Coliru上实时展示

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

我知道。这没有任何好处，但是嘿。只是展示 :)

- sehe

Answer 4

为什么不使用“partition”算法？它会重新排列“all_items”，使好的项目排在前面，坏的排在后面。

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

- Andrew Dwojc

---

std::remove_if 也有效地完成了相同的操作。移除是通过移动（通过移动赋值）范围内的元素来完成的，使得不需要移除的元素出现在范围的开头。 - AdityaG15