[C++][Algorithm][design] predicate callable logic for sorting (and any of the ordering function/algorithm call)

Reference:
https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/
https://vsdmars.blogspot.com/2018/06/c-regular-type.html

https://www.youtube.com/watch?v=2FAi2mNYjFA

Concept:

std::equality_comparable

Type:

std::nan

Design by contract (link to defensive programming)

P: precondition

Q: operation

R: postcondition

Domain (as in math)

Domain of operation is used in the ordinary math sense to denote the set of values over which an operation is (required to be) defined.

This set can change over time. Each component may place additional requirements on the domain of an operation.

These requirements can be inferred from the uses that a component makes of the operation and are generally constrained to those values accessible through the operation's arguments.

Domain of the operation is NOT the types of the arguments.

 

Safety & Correctness

• An operation is safe if it cannot lead to UB
• directly or indirectly
• even if the operation preconditions are violated
• An unsafe operation may lead to UB if preconditions ever are violated
• Either directly or during subsequent operations, safe or not

Code that violates preconditions is incorrect.

Requirements for correctness

• A correctly implemented operation guarantees that:
• If preconditions are satisfied
• The operation will either succeed, result matches post conditions
• Or report failure, return an error, thrown an exceptions, set errno etc.
• Any objects being mutated by the operations must be left in a "known or determinable state"
• A weaker requirement than valid
• If preconditions is not satisfied
• If the operation is safe
• The result is unspecified which could include:
• Failure
• Trapping
• Leaving any object being mutated by the operations in an unspecified, possibly invalid state.
• If the operations is unsafe
• The behavior is undefined(Full STOP)

Compiler can do /anything/ if there's an UB(stripping expressions etc.)

We could exploit contract to work for us; e.g. unsigned (contracted with mod(2^b))

Strong preconditions

• Pros
• flexibility of implementation
• ascribe meaning and intent to an operation
• simplify requirements and reasoning about code
• Cons
• limit clever uses that exploit otherwise defined behavior
• allow for variance in behavior between implementations

ALWAYS refer to C++ ISO for contract of std::

A tl;dr take away for predicator of sorting

When calling any of the ordering functions including

• std::sort
• std::find

compare functions(aka predicate) much comply with the strict weak ordering which formally means the following:

• Irreflexivity: x < x is false (strict partial order rule)
• Asymmetry: x < y and y < x cannot be both true (strict partial order rule)
• Transitivity: x < y and y < z imply x < z (strict partial order rule)
• Transitivity of incomparability: x == y and y == z imply x == z, where x == y means x < y and y < x are both false (equivalence relations on incomparable elements rule)

Above conditions are used for optimization purposes and an abide by is a must for code correctness.