Find common element between multiple vectors (no integer elements)

Question

Is there a C++ function that can find the common element between multiple vectors? The vector elements are not integers (in my case the elements are of type QPair).

The function would ideally have a set of vectors as an argument (the number of vectors to compare can vary) and return the common value of the vectors. I have ensured that there are no duplicates in each vector, but it is possible that there is no common element.

Example:

vec 1 [a,b]      vec 2 [c,d,a,e,h]     vec 3 [i,j,a]

Common value to return:

Yes for pre-sorted collections: https://en.cppreference.com/w/cpp/algorithm/set_intersection — Richard Critten, Sep 04 '18 at 15:25
There is nothing built in for this but there are algorithms that can help. Are these vectors sorted? — NathanOliver, Sep 04 '18 at 15:25
i'm still unfamiliar with the concept of sorting non-integer/non-string arrays. but no the vectors are not sorted — gin hill, Sep 04 '18 at 15:36
std::sort will sort containers of any type which has a < operator — Michael Surette, Sep 04 '18 at 15:38
@ginhill For that see [this](https://stackoverflow.com/questions/1380463/sorting-a-vector-of-custom-objects) — NathanOliver, Sep 04 '18 at 15:39
@NathanOliver ok ty, in that case i can probably sort the vectors. in that case what algorithms can help solve my problem ? — gin hill, Sep 04 '18 at 15:47
Welcome to SO. Please note, that `QPair` defines an [`operator<`](http://doc.qt.io/qt-5/qpair.html#operator-lt). However, `QPair` is a template and you didn't mention the types of first and second which are paired. So, for proper operation those first and second type have to provide an `operator<` as well. — Scheff's Cat, Sep 04 '18 at 15:55

Scheff's Cat · Answer 1 · 2018-09-05T07:51:16.467

As Richard mentioned in comment, intersection can be done easily with std::set_intersection(). The pre-condition are sorted containers.

Thereby, the "set" in set_intersection() could be understood rather in a mathematical sense – it is not limited to std::set. A sorted std::vector can be used as well.

To sort a std::vector, std::sort() can be used. In this case, the pre-condition is a possible order of elements i.e. the operator< is defined for the element type.

QPair defines an operator< which can be used if the types of first and second do as well.

As the OP didn't mention which types are QPaired, I chose std::string and double for my sample isectQPair.cc:

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

#include <QtCore>

int main()
{
  // prepare sample data
  typedef QPair<std::string, double> Pair;
  Pair
    a("Hello", 1.23),
    b("World", 2.34),
    c("Stack", 3.45),
    d("Overflow", 4.56),
    e("C++11", 5.67),
    f("C++14", 6.78),
    g("C++17", 7.89),
    h("C++20", 8.90),
    i("gin hill", 10.1),
    j("scheff", 0.0);
  std::vector<Pair> vec1({ a, b });
  std::vector<Pair> vec2({ c, d, a, e, h });
  std::vector<Pair> vec3({ i, j, a });
  // sort vectors
  std::sort(vec1.begin(), vec1.end());
  std::sort(vec2.begin(), vec2.end());
  std::sort(vec3.begin(), vec3.end());
  // intersect vectors
  std::vector<Pair> isect12;
  std::set_intersection(
    vec1.begin(), vec1.end(), vec2.begin(), vec2.end(),
    std::back_inserter(isect12));
  std::vector<Pair> isect123;
  std::set_intersection(
    isect12.begin(), isect12.end(), vec3.begin(), vec3.end(),
    std::back_inserter(isect123));
  // report
  const size_t n = isect123.size();
  std::cout << "Intersection contains " << n << " elements"
    << (n ? ':' : '.') << '\n';
  for (size_t i = 0; i < n; ++i) {
    const Pair &entry = isect123[i];
    std::cout << (i + 1) << ".: '" << entry.first
      << "', " << entry.second << '\n';
  }
  // done
  return 0;
}

isectQPair.pro:

SOURCES = isectQPair.cc

Qt = core

Compiled and tested on cygwin on Windows 10:

$ qmake-qt5 isectQPair.pro

$ make

$ ./isectQPair
Intersection contains 1 elements:
1.: 'Hello', 1.23

$

Live Demo on ideone (QPair replaced with std::pair)

Another nice Q/A concerning intersection can be found here: SO: how to find the intersection of two std::set in C++?.

Severin Pappadeux · Accepted Answer · 2018-09-04T17:31:10.727

You could make them into hash table and count them out. As soon as you found them again, bump counter. If counter for particular item is the same as number of vectors, you got yourself an intersection. No need to pre-sort vector of pairs, define weak or string ordering etc.

Along the lines:

#include <iostream>
#include <vector>
#include <list>
#include <unordered_map>

using Qpair = uint32_t; // should be std::pair<int, int> or similar
using Qpairs = std::vector<Qpair>;

int intersections(const std::list<Qpairs>& allpairs) {
    std::unordered_map<Qpair, int> m; // element vs counter

    auto count = allpairs.size(); // number of vectors to scan

    for(const auto& pairs: allpairs) { // loop over all vectors
        for (const auto& p : pairs) { // loop over elements in particular vector
            m[p] += 1;                // and count them
        }
    }

    int total_count = 0; // how many common elements are here
    for (const auto& e : m) {
        if (e.second == count) {
            ++total_count;
            // you could add e.first to output vector as well
        }
    }
    return total_count;
}

int main() {
    Qpairs v1{ 4, 2, 6, 8, 9 };
    Qpairs v2{ 1, 3, 8, 9, 4 };
    Qpairs v3{ 2, 8, 9, 5, 0 };

    std::list<Qpairs> l{ v1, v2, v3 };

    auto q = intersections(l);

    std::cout << q << '\n';

    return 0;
}

Find common element between multiple vectors (no integer elements)

2 Answers2