Why do we need transitivity of equivalence

Question

Most C++ STL algorithms API impose certain requirements on comparator functions like transitivity (see Cppreference for details). The requirements are intuitively understandable except for the transitivity of equivalence (aka transitivity of incomparability):

• if a and b are equivalent (i.e. !(a < b) && !(b < a)) and b and c are equivalent (i.e. !(b < c) && !(c < b)) then a and c must be equivalent as well.

What is the intuition behind this requirement?

For the mathematically inclined: I do understand that transitivity of equivalence allows us to define a strict total order over equivalence classes but this does not add much to understanding...

Answer 1

If you drop the requirement, then you are only requiring a partial order.

This immediately has two issues that come to mind:

1. Incomparability is not an equivalence relation any more, so e.g. containers like std::set can't use it to determine equivalence of keys any more. This could of course be worked around by having them take an explicit equivalence relation as additional parameter as e.g. std::unordered_set does.

2. Finding a total order that extends a partial order is not possible efficiently. Suppose that in a set of N objects, all are incomparable except for object A and object B. You need to test worse case all pairs of elements in order to figure out that A and B need a particular order because incomparability of any two elements doesn't imply anything any more about comparison with other elements. So something like std::sort could not be specified to have N*log(N) worse case complexity. I also expect that it would generally make it impossible to implement O(log(N)) operations required for e.g. std::set/std::map.

Answer 2

My own take on this question.

All fast sorting algorithms rely on transitivity of equivalence. For example the main step of quicksort, partitioning algorithm, selects a pivot element and puts all lesser elements to the left and greater ones to the right of pivot:

  loop forever 
    // Move the left index to the right at least once and while the element at
    // the left index is less than the pivot
    do i := i + 1 while A[i] < pivot
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot
    do j := j - 1 while A[j] > pivot

    // If the indices crossed, return
    if i >= j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

Equivalent elements will be positioned around pivot in unpredictable ways. If there are two elements a and b that are equivalent to pivot but not equivalent to each other (e.g. a < b) they may easily be arranged in wrong order (b, a) by the above algorithm.

Many other STL algorithms (e.g. std::min or std::min_element) do not rely on transitivity of equivalence at all and could have been specified to require just partial ordering. I suspect weak ordering is currently required for them to keep the language standard slightly simpler.