比較載體和刪除載體，其中所有元素已經在另一個載體內

Question

我使用載體向量來存儲id數字，我想比較所有這些元素並刪除其中的所有值已經在另一個元素內的元素。

說我在我的矢量4個元素這樣

[[1，2，3，4]，[1，2，3]，[3]，[1,2,3,5] ]

在這個例子中，第二個和第三個元素應該被刪除。

什麼是最快的算法來解決這個問題？

Answer 1

以下是一種可能的解決方案。

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

typedef std::vector<int> VI; 
typedef std::vector<std::vector<int>> VVI; 

VVI DeleteDups(VVI vvi) { 
    std::map<int,int> map; 

    for(auto const& vi : vvi) 
    for(auto const& i : vi) 
     ++map[i]; 

    vvi.erase(
    std::remove_if(begin(vvi), end(vvi), 
     [&map](const VI& vi)->bool { 
     for(int i : vi) 
      if(map[i] == 1) return false; 
     return true; 
     }), 
    end(vvi)); 
    return vvi; 
} 

void Dump(const VVI& vvi) { 
    std::cout << "["; 
    for(auto const& vi : vvi) { 
    std::cout << "["; 
    for(int i : vi) 
     std::cout << i << ", "; 
    std::cout << "], "; 
    } 
    std::cout << "]\n"; 
} 

int main() { 
    Dump(DeleteDups({ {1,2,3,4}, {1,2,3}, {3}, {1,2,3,5} })); 
} 

Answer 2

這裏滿足「已經在另一個元素內」的解決方案需求，而不僅僅是元素的「唯一性」。

對於[[1,2,3,4]，[1,2,3]，[3]，[1,2,3,5]]，輸出爲[[1,2,3,4 ]，[1,2,3,5]]。

對於[[1,2,3,4]，[1,2,3]，[3,4]，[1,2,3,5]]，輸出爲[[1,2,3] ，4]，[1,2,3,5]]。

它的工作原理如下：

1. 生成地圖它映射值，以它的容器
2. 對於每個矢量的矢量，計算每個值的容器的交叉點。如果結果交集中有多個項目（即，不僅是自交），那麼這樣的矢量將被移除。

---

#include <boost/container/vector.hpp> 
#include <boost/range/algorithm.hpp> 
#include <boost/assign/list_of.hpp> 
#include <boost/unordered_map.hpp> 
#include <boost/foreach.hpp> 

#include <iterator> 
#include <iostream> 
#include <ostream> 
#include <cstddef> 
#include <string> 

using namespace boost::assign; 
using namespace boost; 
using namespace std; 

template<typename VecVec,typename OutputIterator> 
void delete_included(const VecVec &vv,OutputIterator out) 
{ 
    typedef typename range_value<VecVec>::type vec_type; 
    typedef typename const vec_type *vec_id; 
    typedef typename range_value<vec_type>::type value_type; 

    unordered_map<value_type,container::vector<vec_id> > value_in; 
    container::vector<vec_id> all_vec_indexes; 
    BOOST_FOREACH(const vec_type &vec,vv) 
    { 
     all_vec_indexes.push_back(&vec); 
     BOOST_FOREACH(const value_type &value,vec) 
     { 
      value_in[value].push_back(&vec); 
     } 
    } 
    container::vector<vec_id> included_in; 
    container::vector<vec_id> intersect; 
    BOOST_FOREACH(const vec_type &vec,vv) 
    { 
     included_in=all_vec_indexes; 
     BOOST_FOREACH(const value_type &value,vec) 
     { 
      intersect.clear(); 
      set_intersection(included_in,value_in[value],back_inserter(intersect)); 
      swap(included_in,intersect); 
      if(included_in.size()==1) 
       break; 
     } 
     if(included_in.size()==1) 
     { 
      *out=vec; 
      ++out; 
     } 
    } 
} 
template<typename VecVec> 
void print(const VecVec &vv) 
{ 
    typedef typename range_value<VecVec>::type vec_type; 
    typedef typename range_value<vec_type>::type value_type; 

    cout << string(16,'_') << endl; 
    BOOST_FOREACH(const vec_type &vec,vv) 
    { 
     copy(vec,ostream_iterator<const value_type&>(cout," ")); 
     cout << endl; 
    } 
} 

int main(int argc,char *argv[]) 
{ 
    container::vector<container::vector<int> > vv 
    (list_of 
     (list_of (1)(2)(3)(4)) 
     (list_of (1)(2)(3)) 
     (list_of (3)) 
     (list_of (1)(2)(3)(5)) 
    ); 
    print(vv); 

    container::vector<container::vector<int> > result; 
    delete_included(vv,back_inserter(result)); 
    print(result); 
    return 0; 
}