从向量的向量去除重叠 [英] Remove overlap from vectors of vectors

问题描述

我基本上做的是设置封面问题，从具有相同数字的向量中删除重复：一个示例

我有以下向量向量排序后：

{{1,2,3,4,5}，{2,3,7,8}，{10,11,12} NOW i想要从第二个向量中删除事件，它是2,3并再次排序... {{1,2,3,4,5}，{10,11,12}，{7,8}

我已经实现了一些代码来排序向量的向量，但我有问题，从具有较小的大小的向量中删除出现次数？

排序函数：
sort（ROWS.begin（），ROWS.end（），VectorsSort（））; code>

感谢您的帮助。

解决方案

分开选择，接受您需要的：

  #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 
 {
 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>常数& 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

$ b

$ <$ c $> $ b

---

编辑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& ：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 这里总是按照它的键，而不是包含的向量的大小（这是你想要的）。也许你想要一个 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> >常数& 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（））; 
} 
  

What basically i'm doing is the set cover problem, removing duplicate from the vectors that has the same numbers: An example

i have the following vectors of vectors after sorting:

{ {1,2,3,4,5},{2,3,7,8},{10,11,12} NOW i would like to remove the occurrence from 2nd vector which is 2,3 and sort again ... {{1,2,3,4,5},{10,11,12},{7,8}

I have implemented some code to sort the vectors of vectors but i have problem removing the occurrences from the vector that has less size?

The sort function: sort(ROWS.begin(),ROWS.end(),VectorsSort());

Thanks for the help.

解决方案

Pick this apart and take what you need:

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

(Note that set_cover requires that the contained std::vector<int>s given must already be sorted.)

---

EDIT #1:

As requested in now-deleted comments, a version oriented around std::map<int, std::vector<int>> instead of std::vector<std::vector<int>> (use binary_search_pred from the original code):

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

Note that the map here will always be sorted by its key, never by the contained vector's size (which is what you appear to want). Maybe you want a std::vector<std::pair<int, std::vector<int>>> instead?

---

EDIT #2:

As requested in now-deleted comments, a version oriented around std::vector<std::pair<int, std::vector<int>>> instead of std::map<int, std::vector<int>> (use binary_search_pred from the original code):

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

这篇关于从向量的向量去除重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！