c++ - 从 vector 的 vector 中移除重叠

Question

基本上我在做的是集合覆盖问题，从具有相同数字的 vector 中删除重复项。一个例子:

排序后我有以下 vector vector :

{{1,2,3,4,5},{2,3,7,8},{10,11,12}}

现在，我想从 2nd vector 中删除出现的 2,3 并再次排序 ...

 {{1,2,3,4,5},{10,11,12},{7,8}}

我已经实现了一些代码来对 vector 的 vector 进行排序，但是我无法从具有较小大小的 vector 中删除匹配项？

排序函数:

sort(ROWS.begin(),ROWS.end(),VectorsSort());

感谢您的帮助。

Answer 1

把它拆开，拿走你需要的东西:

#include <algorithm>
#include <vector>

struct binary_search_pred
{
    typedef bool result_type;

    explicit binary_search_pred(std::vector<int> const& v) : v_(&v) { }

    bool operator ()(int const& i) const
    {
        return std::binary_search(v_->begin(), v_->end(), i);
    }

private:
    std::vector<int> const* v_;
};

struct size_comparison_desc
{
    typedef bool result_type;

    typedef std::vector<int> const& arg_t;
    bool operator ()(arg_t a, arg_t b) const
    {
        return b.size() < a.size();
    }
};

void set_cover(std::vector<std::vector<int> >& vec)
{
    typedef std::vector<std::vector<int> > vec_t;
    typedef vec_t::iterator iter_t;
    typedef vec_t::const_iterator citer_t;

    if (vec.empty() || vec.size() == 1)
        return;

    for (iter_t v = vec.begin() + 1, v_end = vec.end(); v != v_end; ++v)
        for (citer_t p = vec.begin(); p != v; ++p)
            v->erase(
                std::remove_if(v->begin(), v->end(), binary_search_pred(*p)),
                v->end()
            );
    std::sort(vec.begin(), vec.end(), size_comparison_desc());
}

(请注意，set_cover 要求包含的 std::vector<int> 给定必须已经排序。)

---

编辑#1:

根据现已删除的评论中的要求，一个围绕 std::map<int, std::vector<int>> 的版本而不是 std::vector<std::vector<int>> (使用原始代码中的 binary_search_pred):

#include <algorithm>
#include <map>
#include <vector>

void set_cover(std::map<int, std::vector<int> >& m)
{
    typedef std::map<int, std::vector<int> > map_t;
    typedef map_t::iterator iter_t;
    typedef map_t::const_iterator citer_t;

    if (m.empty() || m.size() == 1)
        return;

    for (iter_t v = ++m.begin(), v_end = m.end(); v != v_end; ++v)
        for (citer_t p = m.begin(); p != v; ++p)
            v->second.erase(
                std::remove_if(
                    v->second.begin(),
                    v->second.end(),
                    binary_search_pred(p->second)
                ),
                v->second.end()
            );
}

请注意 map这里将始终按其键排序，而不是按包含的 vector的大小(这是你想要的)。也许你想要一个 std::vector<std::pair<int, std::vector<int>>>相反？

---

编辑#2:

根据现已删除的评论中的要求，一个围绕 std::vector<std::pair<int, std::vector<int>>> 的版本而不是 std::map<int, std::vector<int>> (使用原始代码中的 binary_search_pred):

#include <algorithm>
#include <utility>
#include <vector>

struct size_comparison_desc
{
    typedef bool result_type;

    typedef std::pair<int, std::vector<int> > const& arg_t;
    bool operator ()(arg_t a, arg_t b) const
    {
        return b.second.size() < a.second.size();
    }
};

void set_cover(std::vector<std::pair<int, std::vector<int> > >& vec)
{
    typedef std::vector<std::pair<int, std::vector<int> > > vec_t;
    typedef vec_t::iterator iter_t;
    typedef vec_t::const_iterator citer_t;

    if (vec.empty() || vec.size() == 1)
        return;

    for (iter_t v = vec.begin() + 1, v_end = vec.end(); v != v_end; ++v)
        for (citer_t p = vec.begin(); p != v; ++p)
            v->second.erase(
                std::remove_if(
                    v->second.begin(),
                    v->second.end(),
                    binary_search_pred(p->second)
                ),
                v->second.end()
            );
    std::sort(vec.begin(), vec.end(), size_comparison_desc());
}