Standard Template Library Programmer's Guide

For the first version, the one that takes two arguments:

• [first, last) is a valid range.

• [first, last) is a heap. That is, is_heap(first, last) is true .

For the second version, the one that takes three arguments:

• [first, last) is a valid range.

• [first, last) is a heap. That is, is_heap(first, last, comp) is true .

At most N * log(N) comparisons, where N is last – first .

int main() {

int A[] = {1, 4, 2, 8, 5, 7};

const int N = sizeof(A) / sizeof(int);

make_heap(A, A+N);

copy(A, A+N, ostream_iterator(cout, " "));

cout << endl;

sort_heap(A, A+N);

copy(A, A+N, ostream_iterator(cout, " "));

cout << endl;

}

[1] A heap is a particular way of ordering the elements in a range of Random Access Iterators [f, l) . The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *f is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap ), or to remove *f , in logarithmic time. Internally, a heap is a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.

push_heap , pop_heap , make_heap , is_heap , sort , stable_sort , partial_sort , partial_sort_copy

Category: algorithms

Component type: function

Is_heap is an overloaded name; there are actually two is_heap functions.

template

bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

template

inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp)

Is_heap returns true if the range [first, last) is a heap [1], and false otherwise. The two versions differ in how they define whether one element is less than another: the first version compares objects using operator< , and the second compares objects using a function object comp .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.

For the first version:

• RandomAccessIterator is a model of Random Access Iterator.

• RandomAccessIterator 's value type is a model of LessThan Comparable.

• The ordering on objects of RandomAccessIterator 's value type is a strict weak ordering , as defined in the LessThan Comparable requirements.

For the second version:

• RandomAccessIterator is a model of Random Access Iterator.

• StrictWeakOrdering is a model of Strict Weak Ordering.

• RandomAccessIterator 's value type is convertible to StrictWeakOrdering 's argument type.

• [first, last) is a valid range.

Linear. Zero comparisons if [first, last) is an empty range, otherwise at most (last – first) – 1 comparisons.

int A[] = {1, 2, 3, 4, 5, 6, 7};

const int N = sizeof(A) / sizeof(int);

assert(!is_heap(A, A+N));

make_heap(A, A+N);

assert(is_heap(A, A+N));

[1] A heap is a particular way of ordering the elements in a range of Random Access Iterators [f, l) . The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *f is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap ), or to remove *f , in logarithmic time. Internally, a heap is a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.

make_heap , push_heap , pop_heap , sort_heap

Categories: algorithms, utilities

Component type: function

Min is an overloaded name; there are actually two min functions.

template

const T& min(const T& a, const T& b);

template

const T& min(const T& a, const T& b, BinaryPredicate comp);

Min returns the lesser of its two arguments; it returns the first argument if neither is less than the other.

The two versions of min differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using the function object comp .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

For the first version:

• T is a model of LessThan Comparable.

For the second version:

• BinaryPredicate is a model of Binary Predicate.

• T is convertible to BinaryPredicate 's first argument type and to its second argument type.

const int x = min(3, 9);

assert(x == 3);

max , min_element , max_element , LessThan Comparable

Categories: algorithms, utilities

Component type: function

Max is an overloaded name; there are actually two max functions.

template

const T& max(const T& a, const T& b);

template

const T& max(const T& a, const T& b, BinaryPredicate comp);

Max returns the greater of its two arguments; it returns the first argument if neither is greater than the other.

The two versions of max differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using the function object comp .