UnorderedRangeEquals calls Comparator function with different argument orders

[gfrontera]

Describe the bug
When using UnorderedRangeEquals to compare two ranges of different types, the Comparator function is called assuming the order of arguments does not matter.

Let's assume that I want to compare a range of elements of type A against another range of elements of type B. I have implemented a Comparator function:
bool compareAB(const A& a, const B& b);

However, when providing that Comparator function to UnorderedRangeEquals, compilation will fail because it calls the Comparator function as compareAB(a, b) as well as compareAB(b, a), and it expects the Comparator function to work either way.

Expected behavior
UnorderedRangeEquals should call the Comparator function providing always the arguments in the same order: the first argument should correspond to an element in the first range, and the second element to an element in the second range.

Reproduction steps
This simple program triggers the error:

#include <catch2/catch_test_macros.hpp>
#include <catch2/matchers/catch_matchers.hpp>
#include <catch2/matchers/catch_matchers_range_equals.hpp>

struct A {
    int i;
};

struct B {
    int j;
};

TEST_CASE("Test") {
    std::vector<A> va = {{1},{2},{3},{4}};
    std::vector<B> vb = {{4},{2},{3},{1}};

    CHECK_THAT(va, Catch::Matchers::UnorderedRangeEquals(vb,
            [](auto v1, auto v2) {return v1.i == v2.j;}));
}

See in Compiler Explorer: https://godbolt.org/z/ajnb9468s

Platform information:

• OS: Ubuntu 24.04
• Compiler+version: Clang 20.1.2
• Catch version: v3.11.0

[horenmar]

Hmmm, I see why you'd want this, but I don't think it is possible. The underlying code is a reimplementation of is_permutation, and it requires the custom comparator to be able to stand in for operator==(A, A), operator==(A, B), and operator==(B, A). The last can be replaced by wrapping operator==(A, B) in a lambda that reverses the arguments, but I don't see a way around the self-comparisons without changing the algorithm to be completely different.

This in effect means that the two types have to be identical, or the comparator has to provide overloaded to support multiple different argument types, at which point asking for the (B, A) overload is not much extra effort.

This is also reflected in the stdlib's is_permutation:

If ForwardIt1 and ForwardIt2 have different value types, the program is ill-formed.

[horenmar]

After bit of further thinking: this would be possible by relaxing the requirements on the matcher. The current implementation is modeled after stdlib's algorithms, which are limited to not cause allocations internally. However, the (A, A) comparison overload could be avoided by allocating a bitmap, and using that to keep track of paired elements in both ranges.

This would mean

1. An extra allocation for every match call. This is probably acceptable, as the underlying algorithm is O(N^2), and the cost of allocating N bits is relatively small in comparison. It can increase the memory pressure a bit though, up to about 8% when comparing 2 ranges of single byte characters.
2. It would force some of the cases that are currently fast into the slow O(N^2) path.