C++ Basics: Find Common Values in Sorted Ranges

Use set_intersection with sorted inputs and an output inserter that grows the destination.

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-intersection-sorted-ranges-demo.cpp:

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

int main() {
    const std::vector<int> first_values{1, 2, 2, 4, 6};
    const std::vector<int> second_values{2, 2, 2, 3, 6};
    std::vector<int> shared_values;
    std::set_intersection(first_values.begin(), first_values.end(),
                          second_values.begin(), second_values.end(),
                          std::back_inserter(shared_values));
    std::cout << "Common values:";
    for (int value : shared_values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
    std::cout << "Result size: " << shared_values.size() << '\n';
}

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

g++ -std=c++20 -Wall -Wextra -Werror -pedantic set-intersection-sorted-ranges-demo.cpp -o set-intersection-sorted-ranges-demo &&
./set-intersection-sorted-ranges-demo

Observed output:

Common values: 2 2 6
Result size: 3

Read the result

The result contains two copies of 2 because the first input has two and the second has three. The algorithm retains the smaller multiplicity, not just one copy of each value. Both inputs also contain 6. back_inserter appends to the initially empty destination.

Apply it carefully

Both input ranges must be sorted using the same ordering supplied to the intersection. Sort unsorted inputs first or choose another approach. The destination must not overlap either input. Passing shared_values.begin() while the vector is empty would not provide writable elements; back_inserter avoids that mistake.

The C++ working draft describes the relevant library rules. This example uses only C++20 facilities, even though the linked draft also documents newer additions.

Clean up

Remove only the source and executable created here, then remove the empty practice directory:

rm -- set-intersection-sorted-ranges-demo.cpp set-intersection-sorted-ranges-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.