Compare named requirement expressed with C++20 concepts

user_4438463 0
Viewed 258

I am writing a sorting algorithm, that takes a comparison function, similar to std::sort:

template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

It seems to me that the template parameter Compare perfectly matches the Compare named requirement. I am trying to understand how to specify that constraint using C++ 20 concepts, such as std::strict_weak_order and std::equivalence_relation, but I am slightly confused.

If I quote the article on cppreference,

The type T satisfies Compare if The type T satisfies BinaryPredicate, and Given
comp, an object of type T equiv(a, b), an expression equivalent to !comp(a, b) && !comp(b, a)

std::strict_weak_ordering could capture my constraints on comp in the description above, but what about equiv? std::equivalence_relation takes a relation as a first template parameter. What would it be in my sorting function?

c++-concepts c++20 c++
1 Answers

In C++, named requirements are wider in capabilities than concepts and constraints.

For example, I can have a named requirement that some algorithms halts. On the other hand, there is no way to make a concept that requires an algorithm halts.

Concepts can check some things, but they cannot check everything. So the named requirement Compare says first that the thing must be a BinaryPredicate. BinaryPredicate can be described as a concept and provided as a constraint.

Confirming

if comp(a,b)==true then comp(b,a)==false

would require either a proof subsystem of C++ to be added and the formal proof to be passed in alongside comp, or checking every single value of the types you pass to comp.

There are languages where you can pass around formal proofs of properties, and those formal proofs are checked to validate function arguments. C++ is not one of them.

Rice's theorem states that you cannot take code and verify its non-trivial properties. To pull off something similar to what you want, code would have to be augmented with proofs of what you claim about it. This extra information could then be required by constraints. Using the Turing tar pit, you could even augment C++ with this capability, but it wouldn't look much like C++ afterwards (and that is coming from me, who likes to add named operators to C++ for fun).

TL;DR not all named requirements can be expressed as concepts. Concepts can check some things, but not everything. Documenting additional requirements beyond what concepts constrain parameters is a thing in C++.

user_17746670
Related