C++ Basics: Compare Sorted Lists by Unmatched Occurrences
Use std::set_symmetric_difference to report occurrences that cannot be paired across two sorted lists.
Prepare a scratch directory
Tested on Linux x86_64 with GCC 14.2.0. You need a C++20-capable compiler and standard-library development headers, with g++ on PATH, plus 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 1Run the example
Save this as symmetric-difference-count-imbalance-demo.cpp:
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
std::vector<int> left{1, 1, 2, 4};
std::vector<int> right{1, 3, 4, 4};
std::vector<int> unmatched;
std::set_symmetric_difference(left.begin(), left.end(), right.begin(), right.end(),
std::back_inserter(unmatched));
std::cout << "unmatched:";
for (int value : unmatched) 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 symmetric-difference-count-imbalance-demo.cpp -o symmetric-difference-count-imbalance-demo &&
./symmetric-difference-count-imbalance-demoObserved output:
unmatched: 1 2 3 4Read the result
One 1 remains from the left and one 4 remains from the right. The unique 2 and 3 also appear, giving a sorted result of 1, 2, 3, 4.
Apply it carefully
These algorithms preserve multiplicity: a value appearing m times on one side and n times on the other contributes the absolute count difference. Deduplicate first if your question concerns membership alone. Both inputs must be sorted with the same ordering, and output must not overlap either input. The result does not identify which side contributed an unmatched entry; track that separately if needed.
The C++ working draft describes the relevant rules. This example uses C++20; the current working draft also includes later additions.
Clean up
Remove only the source and executable created here, then return to the starting directory:
rm -- symmetric-difference-count-imbalance-demo.cpp symmetric-difference-count-imbalance-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directoryIf the directory is not empty, inspect its remaining contents before removing anything else.
Acknowledgements
This post was created with assistance from AI.