Set Algorithms

Handling Duplicates in Set Union

How do I handle duplicates in set_union()?

Abstract art representing computer programming

The std::ranges::set_union() algorithm handles duplicates by ensuring that the resulting set contains only unique elements from both sets, but it preserves duplicates from within each individual set.

Example with Duplicates

Consider the following example where both input sets contain duplicates:

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

int main() {
  std::vector<int> A {1, 2, 2, 3};
  std::vector<int> B {2, 3, 4, 5};
  std::vector<int> Results;
  Results.resize(A.size() + B.size());

  auto [AEnd, BEnd, UnionEnd] = std::ranges::set_union(A, B, Results.begin());

  Results.erase(UnionEnd, Results.end());

  for (auto x : Results) {
    std::cout << x << ", ";
  }
}
1, 2, 2, 3, 4, 5,

In this example, the input sets A and B both contain the element 2 multiple times.

The set_union() algorithm ensures that the result contains the duplicates from within each set but does not add extra duplicates.

How It Works

The set_union() algorithm compares elements from both sets and inserts elements from both sets into the result container, preserving duplicates within each set.

It assumes the input sets are sorted. If the inputs are not sorted, you need to sort them first:

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

int main() {
  std::vector<int> A{1, 3, 2, 2};
  std::vector<int> B{5, 4, 3, 2};
  std::vector<int> Results;
  Results.resize(A.size() + B.size());

  std::sort(A.begin(), A.end());
  std::sort(B.begin(), B.end());

  auto [AEnd, BEnd, UnionEnd] =
    std::ranges::set_union(A, B, Results.begin());

  Results.erase(UnionEnd, Results.end());

  for (auto x : Results) {
    std::cout << x << ", ";
  }
}
1, 2, 2, 3, 4, 5,

Custom Comparators

If you use a custom comparator, ensure it correctly identifies duplicates based on your criteria. For example:

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

int main() {
  std::vector<int> A{3, 2, 1};
  std::vector<int> B{5, 4, 3, 2};
  std::vector<int> Results;
  Results.resize(A.size() + B.size());

  // Custom comparator for descending order
  auto Comparer = [](const int& A, const int& B) {
    return A > B;
  };

  std::sort(A.begin(), A.end(), Comparer);
  std::sort(B.begin(), B.end(), Comparer);

  auto [AEnd, BEnd, UnionEnd] =
    std::ranges::set_union(
      A, B, Results.begin(), Comparer);

  Results.erase(UnionEnd, Results.end());

  for (auto x : Results) {
    std::cout << x << ", ";
  }
}
5, 4, 3, 2, 1,

In this case, the custom comparator ensures the union is formed in descending order, and duplicates are still handled appropriately.

Summary

  • std::ranges::set_union() preserves duplicates within each set.
  • Input sets must be sorted; otherwise, sort them before using the algorithm.
  • Custom comparators should correctly identify duplicates based on your criteria.

Using std::ranges::set_union() ensures your union results are always unique and correctly ordered according to the given criteria.

Answers to questions are automatically generated and may not have been reviewed.

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved