Swo extensions and C++: examples

As we have seen in a prior entry, swo extensions are an alternative formulation of the partition-based semantics used to describe the acceptable arguments to C++ binary search algorithms. This means that if a sequence [start, finish) of elements of type A is ordered with respect to some swo less_A and we have an swo extension less_AB with interface:

struct less_AB
{
 bool operator()(const A&,const B&);
 bool operator()(const B&,const A&);
};

then we can use C++ binary search algorithms with arguments of type B, using less_AB as the comparison predicate.

The following are examples of swo extensions with some practical interest:

If A = std::tuple<A1,...,An> and less_A is a lexicographical swo on A, we can define a swo extension less_AB on B = std::tuple<A1,...,Am>, m≤n, as follows: comparing a = (a1,...,an) and b = (b1,...bm) is equivalent to comparing b' = (a1,...,am) and b with the lexicographical order on B obtained by using the first m componenents of less_A.

Let A1,...,An be types forming a single-inheritance hierarchy tree T rooted at A1, <_T a swo between types induced by a preorder traversal of T and a predicate less_A on polymorphic objects of base type A1 such that less_A()(x,y) iff type(x) <_T type(y). Given a fixed Ai we define the predicate less_Ai by less_Ai()(x,y) = less_A()(x,y) if either x or y is not of type Ai or derived, false otherwise. Technically speaking, less_Ai is not a swo extension of less_A because ranges coincide, but it can be shown to be equivalent in all respects to a true swo extension (replace the left and right arguments by some set isomorphic to the original but different to it). In practical terms, the existence of this swo extension shows that we can binary search for all objects derived from some fixed type Ai if the objects are sorted according to a preorder traversal of their type hierarchy. This is obvious once we observe that preorder traversals "pack" elements belonging to the same hierarchy subtree, i.e. they render them adjacently. This property of preorder traversals with respect to single inheritance hierarchies is used in some languages for implementing efficient dispatch algorithms.