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:

a

Answer 1

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++?.

Answer 2

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;
}