C++ Basics: Compare Unordered Contents Without Sorting the Inputs

Use std::is_permutation to compare value counts while ignoring sequence order.

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 is-permutation-counts-demo.cpp:

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

int main()
{
    const std::vector<int> expected{1, 2, 2};
    const std::vector<int> reordered{2, 1, 2};
    const std::vector<int> changed{1, 1, 2};
    std::cout << std::boolalpha;
    std::cout << "Reordered: " << std::is_permutation(expected.begin(), expected.end(), reordered.begin(), reordered.end()) << '\n';
    std::cout << "Changed counts: " << std::is_permutation(expected.begin(), expected.end(), changed.begin(), changed.end()) << '\n';
}

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

g++ -std=c++20 -Wall -Wextra -Werror -pedantic is-permutation-counts-demo.cpp -o is-permutation-counts-demo &&
./is-permutation-counts-demo

Observed output:

Reordered: true
Changed counts: false

Read the result

The reordered vector has the same multiset of values, so it passes. The changed vector has one fewer 2 and one extra 1, so it fails despite containing the same distinct keys. Neither input needs sorting or is modified.

Apply it carefully

Use the overload with both end iterators when input lengths can differ. Matching distinct membership is weaker than matching occurrence counts. The general algorithm can perform quadratically many comparisons, so for large inputs consider sorting copies or using an appropriate frequency table. A custom predicate must express an equivalence relation; approximate floating-point comparisons often do not.

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 -- is-permutation-counts-demo.cpp is-permutation-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.