Rogue Wave banner
Previous fileTop of DocumentContentsIndexNext file

14.1 Overview

In this section we describe the generic algorithms in the Standard C++ Library that are specific to ordered collections. These algorithms are summarized in Table 20:

Table 20 -- Generic algorithms specific to ordered collections

AlgorithmPurpose 
Sorting algorithms
sort()
Rearranges sequence, places in order
stable_sort()
Sorts, retaining original order of equal elements
partial_sort()
Sorts only part of sequence
partial_sort_copy()
Partial sorts into copy
Nth largest element algorithm
nth_element()
Locates nth largest element
Binary search algorithms
binary_search()
Searches, returning boolean
lower_bound()
Searches, returning first position
upper_bound()
Searches, returning last position
equal_range()
Searches, returning both positions
Merge ordered sequences algorithm
merge()
Combines two ordered sequences
Set operations algoithms
set_union()
Forms union of two sets
set_intersection()
Forms intersection of two sets
set_difference()
Forms difference of two sets
set_symmetric_difference()
Forms symmetric difference of two sets
includes()
Sees if one set is a subset of another
Heap operations algorithms
make_heap()
Turns a sequence into a heap
push_heap()
Adds a new value to the heap
pop_heap()
Removes largest value from the heap
sort_heap()
Turns heap into sorted collection

Ordered collections can be created using the Standard C++ Library in a variety of ways. For example:

Like the generic algorithms described in Section 13, the algorithms described here are not specific to any particular container class. This means that they can be used with a wide variety of types. However, many of them do require the use of random-access iterators. For this reason they are most easily used with vectors, deques, or ordinary arrays.

Almost all the algorithms described in this section have two versions. The first version uses the less than operator < for comparisons appropriate to the container element type. The second, and more general, version uses an explicit comparison function object, which we will write as Compare. This function object must be a binary predicate (see Section 3.2). Since this argument is optional, we will write it within square brackets in the description of the argument types.

A sequence is considered ordered if for every valid or denotable iterator i with a denotable successor j, the comparison Compare(*j, *i) is false. Note that this does not necessarily imply that Compare(*i, *j) is true. It is assumed that the relation imposed by Compare is transitive, and induces a total ordering on the values.

In the descriptions that follow, two values x and y are said to be equivalent if both Compare(x, y) and Compare(y, x) are false. Note that this need not imply that x == y.

14.1.1 Include Files

As with the algorithms described in Chapter 13, before you can use any of these algorithms in a program you must include the algorithm header file:


Previous fileTop of DocumentContentsIndexNext file

OEM Edition, ©Copyright 1999, Rogue Wave Software, Inc.
Contact Rogue Wave about documentation or support issues.