Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Sorted Lists

The next type of searchable container that we consider is a sorted list . A sorted list is like an ordered list: It is a searchable container that holds a sequence of objects. However, the position of an item in a sorted list is not arbitrary. The items in the sequence appear in order, say, from the smallest to the largest. Of course, for such an ordering to exist, the relation used to sort the items must be a total order.

In addition to the basic repertoire of operations supported by all searchable containers, sorted lists provide the following operations:

FindPosition: used to find the position of an object in the sorted list;
operator []: used to access the object at a given position in the sorted list;
Withdraw: used to remove the object at a given position from the sorted list.

These operations have similar semantics to the like-named ones for ordered lists. Conspicuous by their absence are the operations InsertAfter and InsertBefore which are provided by the OrderedList class. These operations are not provided for sorted lists because they allow arbitrary insertions, but arbitrary insertions do not necessarily result in sorted lists.

Program gives the declaration of the class which is used to represent sorted lists: SortedList. Like its unsorted counterpart, the class SortedList is derived from the class List which is in turn derived from SearchableContainer. No new member functions are added to the inherited interface.

program10482
Program: SortedList Class Definition

Sorted lists are very similar to ordered lists. As a result, we can make use of the code for ordered lists when implementing sorted lists. Specifically, we will consider an array-based implementation of sorted lists that is derived from the ListAsArray class defined in Section , and a pointer-based implementation of sorted lists that is derived from the ListAsLinkedList class given in Section .