Standard Template Library Programmer's Guide

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.

Definition

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.

Requirements on types

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.

Preconditions

• [first, last) is a valid range.

Complexity

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

Example

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));

Notes

[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.

See also

make_heap, push_heap, pop_heap, sort_heap

Minimum and maximum

min

Categories: algorithms, utilities

Component type: function

Prototype

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

template <class T>
const T& min(const T& a, const T& b);
template <class T, class BinaryPredicate>
const T& min(const T& a, const T& b, BinaryPredicate comp);

Description

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.

Definition

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

Requirements on types

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.

Example

const int x = min(3, 9);
assert(x == 3);

See also

max, min_element, max_element, LessThan Comparable

max

Categories: algorithms, utilities

Component type: function

Prototype

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

template <class T>
const T& max(const T& a, const T& b);
template <class T, class BinaryPredicate>
const T& max(const T& a, const T& b, BinaryPredicate comp);

Description

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.