C++ Basics: Subtract Sorted Inventories with Duplicate Counts

Use std::set_difference to remove requested occurrences from a sorted inventory.

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-difference-multiplicity-demo.cpp:

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

int main()
{
    const std::vector<int> available{1, 2, 2, 3, 5};
    const std::vector<int> used{2, 4};
    std::vector<int> remaining;
    std::set_difference(available.begin(), available.end(), used.begin(), used.end(),
                        std::back_inserter(remaining));
    std::cout << "Remaining:";
    for (int item : remaining) std::cout << ' ' << item;
    std::cout << '\n';
}

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

g++ -std=c++20 -Wall -Wextra -Werror -pedantic set-difference-multiplicity-demo.cpp -o set-difference-multiplicity-demo &&
./set-difference-multiplicity-demo

Observed output:

Remaining: 1 2 3 5

Read the result

One occurrence of 2 is consumed, so another remains. The unavailable value 4 does not add anything to the output. This is a multiset-style subtraction: each key retains max(available count minus used count, zero) occurrences.

Apply it carefully

Both ranges must be sorted with the same comparison, and the destination must not overlap either input. The name does not require std::set containers; sorted vectors work and can retain duplicates. It also does not validate whether every requested item was available. If shortages should be errors, check that requirement separately before applying the result.

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-difference-multiplicity-demo.cpp set-difference-multiplicity-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.