C++ Basics: Combine Sorted Lists with Maximum Duplicate Counts

Use std::set_union when a combined list should retain the larger occurrence count of each key.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as set-union-duplicate-counts-demo.cpp:

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

int main()
{
    const std::vector<int> left{1, 2, 2, 4};
    const std::vector<int> right{2, 3, 3, 4};
    std::vector<int> combined;
    std::set_union(left.begin(), left.end(), right.begin(), right.end(),
                   std::back_inserter(combined));
    std::cout << "Union:";
    for (int value : combined) std::cout << ' ' << value;
    std::cout << '\n';
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic set-union-duplicate-counts-demo.cpp -o set-union-duplicate-counts-demo &&
./set-union-duplicate-counts-demo

Observed output:

Union: 1 2 2 3 3 4

Read the result

The output contains two copies of 2 and two copies of 3, because those are the maximum counts in either input. The shared 4 appears once. This differs from concatenating and sorting, which would add the duplicate counts together.

Apply it carefully

Sort both inputs using the same comparator before calling this algorithm, and keep the output separate. If the application needs exactly one of each key, remove duplicate runs from the result or normalize the inputs first. The set operation treats comparator-equivalent values as the same key; records with different payloads therefore need a deliberate representative-selection policy.

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- set-union-duplicate-counts-demo.cpp set-union-duplicate-counts-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.