如何返回包含不在集合中的元素的向量副本？

Question

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

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

该all_items向量包含所有已知的项目和bad_items载体包含坏的项目清单.这两个数据结构完全相互独立地填充.

编写一个返回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万个项目的向量上,上述方法在3.1s中运行.我替补标记了这种std::set_difference方法,它在大约2.1s内运行.感谢所有提供了很好答案的人.

Answer 1

正如jeffamaphone建议的那样,如果你可以对任何输入向量进行排序,你可以使用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;
}