Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

14.1 Overview

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

Table 20: Generic algorithms specific to ordered collections 

Algorithm Purpose

Sorting algorithms


Sorts only part of sequence


Partial sorts into copy


Rearranges sequence, places in order


Sorts, retaining original order of equal elements

Nth largest element algorithm


Locates nth largest element

Binary search algorithms


Searches, returning a boolean value


Searches, returning both positions


Searches, returning first position


Searches, returning last position

Merge ordered sequences algorithm


Combines two ordered sequences

Set operations algoithms


Compares two sorted sequences and returns true if every element in the range [first2, last2) is contained in the range [first1, last1)


Forms intersection of two sets


Forms difference of two sets


Forms symmetric difference of two sets


Forms union of two sets

Heap operations algorithms


Turns a sequence into a heap


Adds a new value to the heap


Removes largest value from the heap


Turns heap into sorted collection

Ordered collections can be created using the C++ Standard 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 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.3). 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 DocumentContentsIndex pageNext file