[C++] How to compare and remove elements that does not have same value between 3 vectors?

Question

Hello there,

I need to remove every elements that doesn't have same value between 3 vectors or more. For example,

vector<int> Vector1, Vector2, Vector3;
for(int i = 2; i < 7; i++) Vector1.push_back(i); // Vector1 = {2, 3, 4, (5), (6)}
for(int i = 3; i < 8; i++) Vector2.push_back(i); // Vector2 = {3, 4, (5), (6), 7}
for(int i = 5; i < 10; i++) Vector3.push_back(i); // Vector3 = {(5), (6), 7, 8, 9}

We know that all of the vectors has 2 elements with same value: 5 and 6. Now how do I get these values and store them to a new vector?

Any kind of help would be appreciated :)

Answer 1

If all the vectors are ordered then you just scan them each time checking the lowest number until you pass it on one of the other two. if you can't find it, you drop it, each time you check the lowest number you get.

Example:

T1 = first element (v1) T2 = firest elemnt (v2) T3 = first element (v3)

find out the loweset one between the 3 if there is no equals - drop it and get the next val, and try again.

if all the vectors has the numbers going up (ordered) you'll find all matches.

Answer 2

If the vectors are not ordered and it is not possible to sort them, you can use this (in-efficient) approach:

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

typedef std::vector<int> IntVec;
typedef std::vector<IntVec> TwoDIntVec;

IntVec
intvec_union(const TwoDIntVec& vec)
{
  IntVec result;
  size_t vec_size = vec.size();
  if (vec_size < 3) return result;
  const IntVec& vec1 = vec[0];
  size_t sz = vec1.size();
  for (size_t i=0; i<sz; ++i)
    {
      bool found = true;
      int val = vec1[i];
      for (size_t j=1; j<vec_size; ++j)
    {
      const IntVec& v = vec[j];
      if (std::find(v.begin(), v.end(), val) == v.end())
        {
          found = false;
          break;
        }
    }
      if (found) result.push_back(val);
    }
  return result;
}

// test
int
main()
{
  IntVec Vector1, Vector2, Vector3;
  for(int i = 2; i < 7; i++) Vector1.push_back(i); // Vector1 = {2, 3, 4, (5), (6)}
  for(int i = 3; i < 8; i++) Vector2.push_back(i); // Vector2 = {3, 4, (5), (6), 7}
  for(int i = 5; i < 10; i++) Vector3.push_back(i); // Vector3 = {(5), (6), 7, 8, 9}
  TwoDIntVec v;
  v.push_back(Vector1);
  v.push_back(Vector2);
  v.push_back(Vector3);
  IntVec result = intvec_union(v); // result = {5,6}
  return 0;
}

Answer 3

You have set_intersection in the standard algorithms library(vectors must be sorted):

// This code does it for two vectors only

vector<int> a, b, r;

for(int i = 0; i < 10; i++)
{
    a.push_back(i);
    b.push_back(i+5);
}

set_intersection(
    a.begin(), a.end(),
    b.begin(), b.end(),
    back_inserter(r));

Answer 4

For me the fastest solution is to build the set with elements from all vectors. Every time you inserts element that is not unique you increment his counter. Elements with counter equal numbers of vectors should be deleted.

However the simplest implementation is to make map (for most cases I think it is fast enough):

// only pseudo code
map<int,int> elems;
for( vector<int>& v : vectors )
    for( int i : v ) {
        map<int,int>::iterator itr = elems.find(i);
        if( itr == elems.end() )
             elems[i] = 1;
        else itr->second++;
    }

for( pair<int,int>& p : elems )
    if( p.second == vectors.size() )
       erase_from_vectors( p.first );

If your vectors are really huge you may build multimap that in value contains vector::iterators. Then you can remove those elements from vectors without looking through them.

Answer 5

This seems to work, although it looks ugly:

void intersection(std::vector<std::vector<int>*> valList, std::vector<int>& intersectionList)
{
    if(valList.size() < 2)
    {
     return;
    }

    std::vector<std::vector<int>*>::iterator iter = valList.begin();
    std::vector<std::vector<int>*>::iterator endIter = valList.end();

    for(; iter != endIter; ++iter)
    {
     std::vector<int>* pVec = *iter;
     std::sort(pVec->begin(), pVec->end());
    }

    iter = valList.begin();
    endIter = valList.end();

    std::vector<int>* pFirstVec = *iter;
    std::vector<int>* pSecondVec = *(iter + 1);

    iter = iter + 2;

    std::set_intersection(pFirstVec->begin(), pFirstVec->end(), pSecondVec->begin(), pSecondVec->end(), std::back_inserter(intersectionList));

    for(; iter != endIter; ++iter)
    {
     std::vector<int> temp;
     std::vector<int>* pVec = *iter;

     std::set_intersection(pVec->begin(), pVec->end(), intersectionList.begin(), intersectionList.end(), std::back_inserter(temp));

     intersectionList = temp;
     std::sort(intersectionList.begin(), intersectionList.end());
    }


}

int main()
{ 
    std::vector<int> Vector1, Vector2, Vector3, Vector4;
for(int i = 2; i < 7; i++) Vector1.push_back(i); // Vector1 = {2, 3, 4, (5), (6)}
for(int i = 3; i < 8; i++) Vector2.push_back(i); // Vector2 = {3, 4, (5), (6), 7}
for(int i = 5; i < 10; i++) Vector3.push_back(i); // Vector3 = {(5), (6), 7, 8, 9}
for(int i = 6; i < 12; i++) Vector4.push_back(i); // Vector3 = {(6),7,8,9,10,11}

std::vector<int> r;

std::vector<std::vector<int>*> v;
v.push_back(&Vector1);
v.push_back(&Vector2);
v.push_back(&Vector3);
v.push_back(&Vector4);

intersection(v,r);
    return 0;
}

Answer 6

Other answers seems to assume that the vectors are sorted or don't have repeated values (I think gba's answer fails in that case). This one works in every cases and still try to be efficient. It removes all elements found in every vectors.

template <class C>
struct is_in{
 const C & c_;
 bool b_;
 is_in(C c, bool b = true) : c_(c), b_(b) {}
 bool operator() (typename C::value_type v){
  return b_ == (c_.find(v) != c_.end());
 }
};

int main() {
 set<int> s(v.front().begin(), v.front().end());
 typedef is_in<set<int> > is_in_set;

 vector< vector<int> >::iterator i;
 for(i = v.begin()+1; i != v.end(); ++i) {
  //s is the intersection of every vectors before i
  set<int> new_s;
  //copy in new_s all elements of *i unless they are not in s
  remove_copy_if(i->begin(), i->end(), insert_iterator<set<int> >(new_s, new_s.begin()),
    is_in_set(s, false));
  swap(s, new_s);
 }

 for(i = v.begin(); i != v.end(); ++i) {
  //erase all elements of *i which are in s
  i->erase(remove_if(i->begin(), i->end(),
    is_in_set(s)), i->end());
 }
 vector<int> res_vec(s.begin(), s.end());
}

Answer 7

This approach relies on having sorted input vectors, but after that will only do an linear walk through the current and next vectors to be compared, keeping the matching elements in the first vector. It doesn need to do a full search for each element. The algorithm is reasonably container neutral, requiring only forward iterators so will work with vectors, lists, singly linked lists, raw arrays, etc.

The essential building block for this algorithm is a function that removes elements from a sorted range that aren't in a second sorted range. I'm using the std::remove convention of swapping unwanted elements to the end of the range and returning an iterator pointing to start of the unwanted elements. It's O(n + m).

template<class Input1, class Input2>
Input1 inplace_intersection(Input1 first1, Input1 last1, Input2 first2, Input2 last2)
{
    using std::swap;

    Input1 nextslot(first1);

    for( ; first1 != last1; ++first1 )
    {
        // Skip elements from the second range that are
        // smaller than the current element.
        while( first2 != last2 && *first2 < *first1 )
            ++first2;

        // Do we have a match? If so keep
        if( first2 != last2 && !(*first1 < *first2) )
        {
            if( first1 != nextslot )
                swap( *first1, *nextslot );

            ++nextslot;
        }
    }

    return nextslot;
}

With this building block you can operate on sorted vectors this.

std::vector<int> initial;

// fill...

std::vector<int>::iterator first = initial.begin(), last = initial.end();

last = inplace_intersection( first, last, scnd.begin(), scnd.end() );

last = inplace_intersection( first, last, thrd.begin(), thrd.end() );

// etc...

initial.erase( last, erase.end() );

If your input vectors aren't sorted, then you can sort them in place if possible, or otherwise create sorted copies.