Set Algorithms

Set Union with Unsorted Inputs

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

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().

This Question is from the Lesson:

Set Algorithms

An introduction to set algorithms, and how to implement them using the C++ standard library

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

This Question is from the Lesson:

Set Algorithms

An introduction to set algorithms, and how to implement them using the C++ standard library

Part of the course:

Professional C++

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

Free, unlimited access

This course includes:

• 124 Lessons
• 550+ Code Samples
• 96% Positive Reviews
• Regularly Updated
• Help and FAQ
Free, Unlimited Access

Professional C++

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