Local Definition

A linear ordering on a finite collection of objects may be described as follows: each object has exactly one immediate predecessor object and one immediate successor object with two exceptions: A first object has no predecessor and a last object has no successor.

A linear ordering is also known as a total ordering or a simple ordering.

Mathematical Definition

A binary relationship $ a \leq b $ (read as a precedes or equals b) between two objects is said to be a linear 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 = b $, and
• The relationship is transitive: if $ a \leq b $ and $ b \leq c $, this implies that $ a \leq c $.

We will say that $ a < b $ (read as a precedes b) if $ a \leq b $ and $ a \ne b $.

Given $ n $ objects which have a linear 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 $ as is shown in Figure 1.

Figure 1. The ordering of 10 objects.

Implicit and Explicit Linear Orderings

A linear 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:

bool operator<= ( Rational const &p, Rational const &q ) {
	return p.numerator*q.denominator <= q.numerator*p.denominator;
}

For example, if a container has the values 24, 3, 13, 36, 5, 8, 30, 12, 17, and 29, they may be ordered as shown in Figure 2.

Figure 2. The ordering of 10 specific integers.

Alternatively, the programmer can explicitly define the linear ordering: one object precedes another because it was explicitly placed in that location. The most common example of such an explicit linear ordering is a string: the string "Hello world!" is an ordered sequence of twelve characters.

Operations

Operations which may be performed on a container with objects which satisfy an equivalence relation include:

Additional Operations on Linear Orderings

• Access the first or last object in the linear ordering,
• More generally, access the k^th object in the linear ordering,
• Given a reference to an object in the linear ordering, access the next larger or previous smaller object in the container.
• Provide a means for stepping through the objects in the container in order.

Additional Operations on Implicitly Defined Linear Orderings

Given an implicit linear ordering, it is possible to pose additional operations:

• Given an object $ a $, find the preceding or next object in the container (the value $ a $ need not be in the container),
• Given an object $ a $, find the number of objects in the container either preceding or succeeding $ a $ (the value $ a $ need not be in the container),

Additional Operations on Explicitly Defined Linear Orderings

Given an explicit linear ordering, other operations include:

• Insert a new object or replace the object at the kth position,
• Given a reference to the k^th object, insert a new object either before or after that object; or delete the object before or after the k^th object.

Any text editor must store the contents of a file in a linear order and any edit to the text will changed the linear ordering.