c++ - 如何返回包含不在集合中的元素的 vector 拷贝？

Question

假设我有以下两个数据结构:

std::vector<int> all_items;
std::set<int> bad_items;

all_items vector 包含所有已知项和 bad_items vector 包含坏项列表。这两个数据结构完全独立地填充。

编写返回 std::vector<int> 的方法的正确方法是什么？包含 all_items 的所有元素不在 bad_items ？

目前，我有一个笨拙的解决方案，我认为可以更简洁地完成。我缺乏对 STL 函数适配器的理解。因此问题。我目前的解决方案是:

struct is_item_bad {
    std::set<int> const* bad_items;
    bool operator() (int const i) const {
        return bad_items.count(i) > 0;
    }
};

std::vector<int> items() const {
    is_item_bad iib = { &bad_items; };
    std::vector<int> good_items(all_items.size());
    std::remove_copy_if(all_items.begin(),  all_items.end(), 
                        good_items.begin(), is_item_bad);
    return good_items; 
}

假设all_items , bad_items , is_item_bad和 items()都是一些包含类的一部分。有没有办法写它们items() getter 这样:

• 方法中不需要临时变量吗？
• 它不需要自定义仿函数，struct is_item_bad ？

我曾希望只使用 count std::set 上的方法作为一个仿函数，但我还没有找到用 remove_copy_if 来表达它的正确方法算法。

编辑:修复了 items() 中的逻辑错误.实际代码没有问题，是转录错误。

编辑: 我接受了一个不使用 std::set_difference 的解决方案因为它更通用，即使 std::vector 也能正常工作没有排序。我选择在我的代码中使用 C++0x lambda 表达式语法。我的决赛 items()方法如下所示:

std::vector<int> items() const {
    std::vector<int> good_items;
    good_items.reserve(all_items.size());
    std::remove_copy_if(all_items.begin(), all_items.end(),
                        std::back_inserter(good_items),
                        [&bad_items] (int const i) {
                            return bad_items.count(i) == 1;
                        });
}

在大约 800 万个项目的 vector 上，上述方法在 3.1 秒内运行。我替补标记了 std::set_difference进近，它在大约 2.1 秒内运行。感谢所有提供出色答案的人。

Answer 1

正如 jeffamaphone 所建议的，如果你可以对任何输入 vector 进行排序，你可以使用 std::set_difference，它是高效且代码更少的:

#include <algorithm>
#include <set>
#include <vector>

std::vector<int> 
get_good_items( std::vector<int> const & all_items,
                std::set<int> const & bad_items )
{
    std::vector<int> good_items;

    // Assumes all_items is sorted.
    std::set_difference( all_items.begin(),
                         all_items.end(),
                         bad_items.begin(),
                         bad_items.end(),
                         std::back_inserter( good_items ) );

    return good_items;
}