Data Structures in C++:Additional Components of the STL

Additional Components of the STL

Sorting, Searching, and Selection

The Standard Library includes a rich set of functions that can be applied to the standard containers. Some of the algorithms include routines for sorting, searching, copying (possibly with substitutions), shuffling, reversing, rotating, merging, and so on. In all there are over sixty generic algorithms. In this section we highlight those related to efficient sorting, selection, and binary search.

Sorting

Sorting in C++ is accomplished by use of function template sort. The parameters to sort represent the start and endmarker of a (half-open range in a) container, and an optional comparator:

• void sort( iterator begin, iterator end )

• void sort( iterator begin, iterator end, Comparator cmp )

The iterators must support random access. As an example, in

the first call sorts the entire container, v, in non-decreasing order. The second call sorts the entire container in non-increasing order. The third call sorts the first five elements of the container in non-decreasing order. The sorting algorithm is generally quicksort, which yields an O(N log N ) algorithm on average. However, O(N log N ) worst-case performance is not guaranteed.

The C++ library inherits the sorting routine qsort from C. qsort uses pointers to functions to perform its comparison making it significantly slower on average than the sort routine. Furthermore, many implementations use a version of quicksort that has been shown to provide quadratic behavior on some commonly occurring inputs [1]. Avoid using qsort.

Selection

The function template nth element is used for selection, and as expected has O(N ) average- case running time. The parameters include a pair of iterators, and k:

• void nth element( iterator begin, int k, iterator end )

• void nth element( iterator begin, int k, iterator end, Comparator c)

As a result of calling nth element, the item in the kth position is the kth smallest element, where counting as usual in C++ begins at 0.

Thus, in

nth_element( v.begin( ), 0, v.end( ) );

nth_element( v.begin( ), 0, v.end( ), greater<int>( ) );

nth_element( v.begin( ), v.begin( ) + ( v.end( ) - vbegin( ) / 2 ), v.end( ) );

the first call places the smallest element in the position given by v.begin( ), the second call places the largest element in that position, and the third call places the median in the middle position.

Searching

Several generic searching algorithms are available for containers. The most basic is:

• iterator find( iterator begin, iterator end, const Object & x ): re- turns an iterator representing the first occurrence of x in the half-open range specified by begin and end, or end if x is not found.

find is simply a sequential search. If the range is sorted, binary search can be used to find an object in logarithmic time. A comparator can be provided, or the default ordering can be used. The signatures for binary search are:

• iterator binary search( iterator begin, iterator end, const Object & x )

• iterator binary search( iterator begin, iterator end, const Object & x, Comparator cmp )

equal range, lower bound, and upper bound search sorted ranges and behave with the same semantics as the identically named member functions in set.

Non-Standard Extensions

Some implementations of the STL contain additional classes. Eventually, these might be- come part of C++.

A rope is a container that behaves like a string but is optimized for large strings. The implementation of a rope (the name is a play on long string) makes use of trees of reference- counted substrings, and allows operations such as assignment, concatenation, and substring to be performed more efficiently than with a regular string.

A slist is a singly-linked list. Because in a standard list, insert and erase add and re- move prior to the position given in the iterator, those operations are linear-time in an slist in some implementations. If so, you’ll find additional member functions insert after and erase after that provide constant-time performance.

The hash set, hash map, hash multiset, and hash multimap containers support sets and maps at O(1) average time per operation, using hash tables. Generally speaking, these are instantiated with a type of object being stored, a comparison function (that defaults to ==), and a hash function. Unfortunately, there are several competing designs which are not compatible with each other, and it remains to be seen which design will eventually be chosen to join the Standard Library.