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 typeT
satisfies BinaryPredicate, and Given
comp, an object of typeT
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?
CodePudding user response:
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 .