Overview

In this section we will describe the generic algorithms in the standard library that are specific to ordered collections. These are summarized by the following table:

Name	Purpose
Sorting Algorithms Sections Sorting Algorithms and Partial Sort
`sort`	rearrange sequence, place in order
`stable_sort`	sort, retaining original order of equal elements
`partial_sort`	sort only part of sequence
`partial_sort_copy`	partial sort into copy
Find Nth largest Element Section nth Element
`nth_element`	locate nth largest element
Binary Search Section Binary Search
`binary_search`	search, returning boolean
`lower_bound`	search, returning first position
`upper_bound`	search, returning last position
`equal_range`	search, returning both positions
Merge Ordered Sequences Section Merge Ordered Sequences
`merge`	combine two ordered sequences
Set Operations Section Set Operations
`set_union`	form union of two sets
`set_intersection`	form intersection of two sets
`set_difference`	form difference of two sets
`set_symmetric_difference`	form symmetric difference of two sets
`includes`	see if one set is a subset of another
Heap operations Section Heap Operations
`make_heap`	turn a sequence into a heap
`push_heap`	add a new value to the heap
`pop_heap`	remove largest value from the heap
`sort_heap`	turn heap into sorted collection

Ordered collections can be created using the standard library in a variety of ways. For example:

The containers set, multiset, map and multimap are ordered collections by definition.

A list can be ordered by invoking the sort() member function.

A vector, deque or ordinary C++ array can be ordered by using one of the sorting algorithms described later in this section.

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

Obtaining the Sample Programs

Almost all the algorithms described in this section have two versions. The first version uses the less than operator (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: Sorting Algorithms). Since this argument is optional, we will write it within square brackets in the description of the argument types.

A sequence is considered to be ordered if for every valid (that is, denotable) iterator i with a denotable successor j, it is the case that 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.

Include Files

As with the algorithms described in Chapters 12, before you can use any of the algorithms described in this section in a program you must include the algorithm header file:

   # include <algorithm>