Kick out duplicate entries across vectors

Question

I have vectors and I would like to retrieve one vector that contains all entries which aren't duplicated anywhere in all input vectors.

#include <vector>
int main() {

  std::vector<int> a = {2, 1, 3};
  std::vector<int> b = {99, 1, 3, 5, 4};
  std::vector<int> c = {5, 6, 7, 1};

  // magic to retrieve {2, 99, 4, 6, 7} (order doesn't matter)

}

Is there a library function that can help performing this task efficiently?

I'm not tied to using vectors. The solution could include lists, sets, or whatever are most appropriate for the task.

Answer 1

Using unordered_map, O(N) space complexity and O(N) time complexity:

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

std::vector<int>
get_unique_values(std::initializer_list<std::vector<int>> vectors)
{
  std::unordered_map<int, size_t> tmp;
  auto insert_value_in_tmp = [&tmp](int v) {
    auto i = tmp.find(v);
    if (i == tmp.end())
      tmp[v] = 1;
    else if (i->second != 2)
      i->second = 2;
  };

  for ( auto& vec : vectors) {
    for ( auto vec_value : vec ) {
      insert_value_in_tmp(vec_value);
    }
  }

  std::vector<int> result;
  for (auto v : tmp) {
    if (v.second == 1)
      result.push_back(v.first);
  }

  return result;
};

int main() {

  std::vector<int> a = {2, 1, 3};
  std::vector<int> b = {99, 3, 5, 4};
  std::vector<int> c = {5, 6, 7};

  std::vector<int> result = get_unique_values({a,b,c});

  for (auto v : result) {
    std::cout << v << " ";
  }
  std::cout << '\n';

  return 0;
}