Ordered Containers and Their Implementation

We continue with the second branch of the containers specification hierarchy, that of ordered containers Figure 1 Consideration starts with class order, which is general enough to serve as a base class not only for classes stack, queue, and list, but also for a great many other applications. The underlying new concept is a linear ordering method, called greater-than?, which is assumed to be available to order the items in a container. By characterizing this method as a state-representing query, we obtain a generic capability to order container contents that can be readily specialized to any appropriate subclass. In particular, by properly defining greater-than? for stack, queue, and list, we can derive their behaviors from the base class order. (We will show later in this chapter how this differs from the usual specifications of stacks and queues, which don’t take advantage of state-representing queries.)