Set Algorithms

Set Union with Unsorted Inputs

What happens if the input sets for set_union() are not sorted?

Abstract art representing computer programming

If the input sets for std::ranges::set_union() are not sorted, the behavior of the algorithm is undefined. This means you cannot rely on it to produce correct or consistent results.

The std::ranges::set_union() algorithm assumes that both input ranges are sorted in ascending order by default, or according to a provided comparator if specified.

Here’s what could happen with unsorted inputs:

  1. Incorrect Results: The union might not contain all unique elements from both sets.
  2. Duplicates: The result may include duplicates even if the inputs are supposed to represent sets (which by definition should not have duplicates).
  3. Unpredictable Behavior: The algorithm might not work correctly, leading to unexpected outputs.

Consider this example with unsorted inputs:

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

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

  std::ranges::set_union(A, B, Results.begin());
  for (auto x : Results) {
    std::cout << x << ", ";
  }
}
3, 1, 2, 4, 5, 3,

In this output, you can see duplicates due to the unsorted inputs leading to undefined behavior.

Sorting Before Union

To ensure correct results, always sort the input ranges before calling std::ranges::set_union(). Here’s how to do it:

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

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

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

  auto[last1, last2, result_last] =
    std::ranges::set_union(A, B, Results.begin());

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

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

Here, std::sort() is used to sort A and B before performing the union. The result is the correct union of the two sets.

Always ensure your inputs are sorted to guarantee correct behavior when using std::ranges::set_union().

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