The Standard Template Library

While Abstract Sets, Multisets, Maps, and Multimaps do not require an ordering per se, the Standard Template Library (STL) does require that the objects placed into the containers set, multiset, map, and multimap must satisfy a weak ordering. A weak ordering can be thought of as being similar to a linear ordering, but there may be an equivalence classes of objects which are mutually related.

Local Definition

A weak ordering on a finite collection of objects may be described as follows: the objects may be partitioned into classes such that all the objects in the same class are related and each class has exactly one immediate predecessor class and one immediate successor class with two exceptions: A first class has no predecessor and a last class has no successor.

Mathematical Definition

A binary relationship $a \leq b $ (read as a precedes or is equivalent to b) between two objects is said to be a weak ordering if:

• For any $ a $ and $ b $, either $ a \leq b $ or $ b \leq a $,
• If both $ a \leq b $ and $ b \leq a $ it follows that $ a \sim b $, and
• The relationship is transitive: if $ a \leq b $ and $ b \leq c $, this implies that $ a \leq c $.
• The equivalence relationship is transitive: if $ a \sim b $ and $ b \sim c $, this implies that $ a \sim c $.

We will say that $ a < b $ (read as a precedes b) if $ a \leq b $ and $ a \not\sim b $ and the relationship defined by < describes a strict weak order.

Given $ n $ objects which have a weak ordering, we may order them $ a_1, a_2, a_3, \ldots, a_n $ such that $ a_1 \leq a_2 \leq a_3 \leq \ldots \leq a_n $ however, there may be objects which are equivalent to each other at any point. An example is shown in Figure 1.

Figure 1. The weak ordering of 12 objects.

Implicit and Explicit Linear Orderings

A weak ordering between to objects a and b may be implicitly defined through the operation a <= b which returns a Boolean value. In this case, the relationship depends only on the objects themselves. In C++, the operator<= may be overloaded as is demonstrated in this code block which compares two rational numbers:

class Pair {
	public:
		int x, y;
};

// Examples of strict weak orderings

bool operator< ( Pair const &p, Pair const &q ) {
	return p.x < q.x;
}

bool operator< ( Pair const &p, Pair const &q ) {
	return (p.x + p.y) < (q.x + q.y);
}

bool operator< ( Pair const &p, Pair const &q ) {
	return std::min(p.x, p.y) < std::min(q.x, q.y);
}

Weak orderings tend to be implicitly defined. It is not common to explicitly set objects in a weak order.

Operations on Weak Orderings

The additional operations which may occur for a weak ordering include those of the linear ordering and those of the equivalence classes.

Weak Orders and Hash Functions

A hash of an object onto an integer could be used to determine an artificial weak order the same way in which it could be used for a hash table. In this case, however, as there no possibility of ensuring that two objects will not hash to the same value, it is necessary to use a data structure such as the multiset and multimap, as they allow repetitions of objects within the same equivalence class.

Example Using the C++ STL

In the source code directory are four files which demonstrate the behaviour of the four classes set, multiset, map, and multimap. In each case, the object being inserted (either as objects or being used as keys) is an ordered pair (i, j) where only the first entry is compared. Thus, for example, all pairs (3, n) are considered to be equal.