Would C++ standard algorithms be faster if comparators were required to be strict total orderings rather than just strict weak orderings?

Question

Many C++ standard algorithms, like std::sort(), assume that the comparator comp is a strict weak ordering and it cannot be assumed that comp has any another (nice) properties. But many times comp does have more properties than just being a strict weak ordering. In particular, many times comp is a strict total order (so in particular, exactly one of the following is always true for all a and b: comp(a, b), comp(b, a), or a = b). For example, the usual operator<() on float-points, integers, and std::strings are all strict total orders.

By limiting itself to only assuming that comp is a strict weak ordering, does the C++ standard library limit itself to using less than optimal algorithms? Said differently, if the C++ standard algorithms assumed that comparators were strict total orderings instead of just strict weak orderings, then would some standard algorithms be faster than what's currently implemented?

Update: To be more exact about what "strict total ordering" means, let's suppose that the STL assumed that comp (operating on objects of type T) had all of the nice order-theoretic properties that operator<() on ints has. (So if you want, we may also assume that there is also an operator==() defined on objects of type T that works as you'd expect; this assumption is optional and you can make different assumptions if you'd like.) Could any STL algorithms be made faster?

More generally, if the STL made "nicer" assumptions about comp (i.e. assumed more than that comp is a mere strict weak ordering) then could any STL algorithms be made faster?

Answer 1

For example, the usual operator<() on float-points, integers, and std::strings are all strict total orders.

So you are only talking about similarity of state, not true equality (whatever that is in a language with mutable state).

By limiting itself to only assuming that comp is a strict weak ordering, does the C++ standard library limit itself

No. The premise is wrong. The containers and algorithm library (the algorithms generating sorted sequences, those operating on sorted ranges, and the ordered associatives containers) is not limiting itself in any way, by definition: it says explicitly that an equivalence relation, which as far as I know isn't named (let's call it Sim) can be defined in term of the comparison Comp:

Sim (x,y) <=> !Comp(x,y) && !Comp(y,x)

So you have your strict order, just call Sim an "equality" and overload operator== to be defined as Sim.

So the only issue is the silliness of using a binary comparison function, which implies multiple scan of f.ex. strings to determine equality, and not having access to a ternary comparison (like strcmp). If you had access to Sim directly, you still would call Comp than Sim in case of equality, or alternatively Comp then another Comp.

Only when you a priori suspect that "equality" is the most probable result would you use Sim then Comp. This is absurd.

Three way is better for comparing sequences. Go three way.