This chapter discusses the algorithms library. These algorithms cover sequences, sorting, and numerics.

Overview of Algorithms Library

The standard provides for various algorithms that a C + + program may use to perform algorithmic operations on containers and other sequences.

The algorithms library consists for four sections.

• "25.1 Non-modifying Sequence Operations"
• "25.2 Mutating Sequence Operators"
• "25.3 Sorting And Related Operations"
• "25.4 C library algorithms"

Header <algorithm>

The header algorithm provides classes, types and functions for use with the standard C++ libraries.

The standard algorithms can work with program defined data structures, as long as these data structures have iterator types satisfying the assumptions on the algorithms.

The names of the parameters used in this chapter reflect their usage.

A predicate parameter is used for a function object that returns a value testable as true. The binary predicate parameter takes two arguments..

Header <Algorithm> Synopsis:

namespace std {
template<class InputIterator, class Function>
Function for_each(InputIterator first, 
	InputIterator last, Function f);
template<class InputIterator, class T>
InputIterator find(InputIterator first, 
	InputIterator last, const T& value); 
template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, 
	InputIterator last, Predicate pred); 
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end
	(ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2); 
template<class ForwardIterator1, 
		class ForwardIterator2,	class BinaryPredicate> 
ForwardIterator1 find_end
	(ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2,  
	BinaryPredicate pred); 
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of
	(ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2); 
template<class ForwardIterator1, 
		class ForwardIterator2, class BinaryPredicate> 
ForwardIterator1 find_first_of
	(ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2, 
	BinaryPredicate pred); 
template<class ForwardIterator>
ForwardIterator adjacent_find
	(ForwardIterator first,  ForwardIterator last); 
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find
	(ForwardIterator first, ForwardIterator last, 
	BinaryPredicate pred); 
template<class InputIterator, class T>
typename iterator_traits<InputIterator>
	::difference_type count
	(InputIterator first, InputIterator last, const T& value);
template<class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type count_if
	(InputIterator first, InputIterator last, Predicate pred); 
template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch
	(InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2); 
template <class InputIterator1, class InputIterator2, 
		class BinaryPredicate> 
pair<InputIterator1, InputIterator2> mismatch
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, BinaryPredicate pred); 
template<class InputIterator1, class InputIterator2>
bool equal
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2); 
template <class InputIterator1, class InputIterator2, 
		class BinaryPredicate> 
bool equal
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, BinaryPredicate pred); 
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search 
	(ForwardIterator1 first1, ForwardIterator1 last1, 
	ForwardIterator2 first2, ForwardIterator2 last2); 
template<class ForwardIterator1, class ForwardIterator2,
		class BinaryPredicate> ForwardIterator1 search 
	(ForwardIterator1 first1, ForwardIterator1 last1, 
	ForwardIterator2 first2, ForwardIterator2 last2, 
	BinaryPredicate pred); 
template<class ForwardIterator, class Size, class T>
ForwardIterator search_n
	(ForwardIterator first, ForwardIterator last,
	Size count, const T& value); 
template <class ForwardIterator, class Size, 
		class T, class BinaryPredicate> 
ForwardIterator1 search_n
	(ForwardIterator first, ForwardIterator last,
	Size count, const T& value, BinaryPredicate pred); 
template<class InputIterator, class OutputIterator>
OutputIterator copy
	(InputIterator first, InputIterator last,
	OutputIterator result); 
template<class BidirectionalIterator1,
	 class BidirectionalIterator2> 
BidirectionalIterator2 copy_backward 
	(BidirectionalIterator1 first, BidirectionalIterator1 last, 
	BidirectionalIterator2 result); 

template<class T> void swap(T& a, T& b);
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges
	(ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2); 
template<class ForwardIterator1, class ForwardIterator2>
void iter_swap
	(ForwardIterator1 a, ForwardIterator2 b);
template<class InputIterator, class OutputIterator, 
		class UnaryOperation>
OutputIterator transform
	(InputIterator first, InputIterator last,
	OutputIterator result, UnaryOperation op); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator, class BinaryOperation> 
OutputIterator transform
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, OutputIterator result, 
	BinaryOperation binary_op); 
template<class ForwardIterator, class T> void replace
	(ForwardIterator first, ForwardIterator last,
	const T& old_value, const T& new_value); 
template<class ForwardIterator, class Predicate, class T>
void replace_if
	(ForwardIterator first, ForwardIterator last,
	Predicate pred, const T& new_value); 
template<class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy
	(InputIterator first, InputIterator last, 
	OutputIterator result, const T& old_value, const T& new_value); 
template<class Iterator, class OutputIterator, 
		class Predicate, class T>
OutputIterator replace_copy_if
	(Iterator first, Iterator last, OutputIterator result, 
	Predicate pred, const T& new_value); 
template<class ForwardIterator, class T>
void fill
	(ForwardIterator first, ForwardIterator last, const T& value);
template<class OutputIterator, class Size, class T>
void fill_n
	(OutputIterator first, Size n, const T& value); 
template<class ForwardIterator, class Generator>
void generate
	(ForwardIterator first, ForwardIterator last, 
	Generator gen); 
template<class OutputIterator, class Size, class Generator>
void generate_n
	(OutputIterator first, Size n, Generator gen); 
template<class ForwardIterator, class T>
ForwardIterator remove
	(ForwardIterator first, ForwardIterator last, const T& value); 
template<class ForwardIterator, class Predicate>
ForwardIterator remove_if
	(ForwardIterator first, ForwardIterator last, Predicate pred); 
template<class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy
	(InputIterator first, InputIterator last,
	OutputIterator result, const T& value); 
template<class InputIterator, class OutputIterator, 
	class Predicate>
OutputIterator remove_copy_if
	(InputIterator first, InputIterator last,
	OutputIterator result, Predicate pred); 
template<class ForwardIterator>
ForwardIterator unique
	(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique
	(ForwardIterator first, ForwardIterator last, 
	BinaryPredicate pred); 
template<class InputIterator, class OutputIterator>
OutputIterator unique_copy
	(InputIterator first, InputIterator last, 
	OutputIterator result); 
template<class InputIterator, class OutputIterator, 
	class BinaryPredicate>
OutputIterator unique_copy
	(InputIterator first, InputIterator last,
	OutputIterator result, BinaryPredicate pred); 
template<class BidirectionalIterator>
void reverse
	(BidirectionalIterator first, BidirectionalIterator last);
template<class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy
	(BidirectionalIterator first, BidirectionalIterator last, 
	OutputIterator result); 
template<class ForwardIterator>
void rotate
	(ForwardIterator first, ForwardIterator middle,
	ForwardIterator last); 
template<class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy 
	(ForwardIterator first, ForwardIterator middle, 
	ForwardIterator last, OutputIterator result); 
template<class RandomAccessIterator>
void random_shuffle
	(RandomAccessIterator first,  RandomAccessIterator last); 
template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle
	(RandomAccessIterator first, RandomAccessIterator last, 
	RandomNumberGenerator& rand); 

template<class BidirectionalIterator, class Predicate>
BidirectionalIterator partition
	(BidirectionalIterator first, BidirectionalIterator last, 
	Predicate pred); 
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition
	(BidirectionalIterator first, BidirectionalIterator last, 
	Predicate pred); 

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort
	(RandomAccessIterator first, RandomAccessIterator last, 
	Compare comp); 
template<class RandomAccessIterator>
void stable_sort
	(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort
	(RandomAccessIterator first, RandomAccessIterator last,
Compare comp); 
template<class RandomAccessIterator>
void partial_sort
	(RandomAccessIterator first, RandomAccessIterator middle, 
	RandomAccessIterator last); 
template<class RandomAccessIterator, class Compare>
void partial_sort
	(RandomAccessIterator first, RandomAccessIterator middle, 
	RandomAccessIterator last, Compare comp); 
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy
	(InputIterator first, InputIterator last,
	RandomAccessIterator result_first,  
	RandomAccessIterator result_last); 
template<class InputIterator, class RandomAccessIterator, 
		class Compare>
RandomAccessIterator partial_sort_copy
	(InputIterator first, InputIterator last,
	RandomAccessIterator result_first, 
	RandomAccessIterator result_last,  Compare comp); 
template<class RandomAccessIterator>
void nth_element
	(RandomAccessIterator first, RandomAccessIterator nth,
	RandomAccessIterator last); 
template<class RandomAccessIterator, class Compare>
void nth_element
	(RandomAccessIterator first, RandomAccessIterator nth,	
	RandomAccessIterator last, Compare comp); 

template<class ForwardIterator, class T>
ForwardIterator lower_bound
	(ForwardIterator first, ForwardIterator last, const T& value); 
template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound
	(ForwardIterator first, ForwardIterator last,
	const T& value, Compare comp); 
template<class ForwardIterator, class T>
ForwardIterator upper_bound
	(ForwardIterator first, ForwardIterator last, const T& value); 
template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound
	(ForwardIterator first, ForwardIterator last,
	const T& value, Compare comp); 
template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range
	(ForwardIterator first, ForwardIterator last, const T& value); 
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range
	(ForwardIterator first, ForwardIterator last, 
	const T& value, Compare comp); 
template<class ForwardIterator, class T>
bool binary_search
	(ForwardIterator first, ForwardIterator last, const T& value); 
template<class ForwardIterator, class T, class Compare>
bool binary_search
	(ForwardIterator first, ForwardIterator last,
	const T& value, Compare comp); 

template<class InputIterator1, class InputIterator2, 
		class OutputIterator>
OutputIterator merge
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator, class Compare> 
OutputIterator merge
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2, 
OutputIterator result, Compare comp); 
template<class BidirectionalIterator>
void inplace_merge
	(BidirectionalIterator first, BidirectionalIterator middle, 
	BidirectionalIterator last); 
template<class BidirectionalIterator, 
		class Compare>
void inplace_merge
	(BidirectionalIterator first, BidirectionalIterator middle, 
	BidirectionalIterator last, Compare comp); 

template<class InputIterator1, class InputIterator2>
bool includes(
	InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2); 
template<class InputIterator1, class InputIterator2, 
		class Compare>
bool includes 
	(InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2, InputIterator2 last2, Compare comp); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator>
OutputIterator set_union
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator,		class Compare> 
OutputIterator set_union
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result, Compare comp); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator>
OutputIterator set_intersection 
	(InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator, class Compare> 
OutputIterator set_intersection 
	(InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result, Compare comp); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator>
OutputIterator set_difference 
	(InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator, class Compare> 
OutputIterator set_difference 
	(InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result, Compare comp); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator>
OutputIterator set_symmetric_difference
	(InputIterator1 first1, InputIterator1 last1,
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result); 
template<class InputIterator1, class InputIterator2, 
		class OutputIterator, class Compare> 
OutputIterator set_symmetric_difference
	(InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2, InputIterator2 last2, 
	OutputIterator result, Compare comp); 

template<class RandomAccessIterator>
void push_heap
	(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap
	(RandomAccessIterator first, 
	RandomAccessIterator last, Compare comp); 
template<class RandomAccessIterator>
void pop_heap
	(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap
	(RandomAccessIterator first, RandomAccessIterator last,
	Compare comp); 
template<class RandomAccessIterator>
void make_heap
	(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap
	(RandomAccessIterator first, RandomAccessIterator last,
	Compare comp); 
template<class RandomAccessIterator>
void sort_heap
	(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap
	(RandomAccessIterator first, RandomAccessIterator last,
	Compare comp); 

template<class T> const T& min(const T& a, const T& b); 
template<class T, class Compare>
const T& min
	(const T& a, const T& b, Compare comp); 
template<class T> const T& max(const T& a, const T& b); 
template<class T, class Compare>
const T& max
	(const T& a, const T& b, Compare comp); 
template<class ForwardIterator>
ForwardIterator min_element 
	(ForwardIterator first, ForwardIterator last); 
template<class ForwardIterator, class Compare>
ForwardIterator min_element
	(ForwardIterator first, ForwardIterator last, Compare comp); 
template<class ForwardIterator>
ForwardIterator max_element 
	(ForwardIterator first, ForwardIterator last); 
template<class ForwardIterator, class Compare>
ForwardIterator max_element
	(ForwardIterator first, ForwardIterator last, Compare comp); 
template<class InputIterator1, class InputIterator2>
bool lexicographical_compare 
	(InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2, InputIterator2 last2); 
template<class InputIterator1, class InputIterator2, 
		class Compare>
bool lexicographical_compare 
(	InputIterator1 first1, InputIterator1 last1, 
	InputIterator2 first2, InputIterator2 last2,  Compare comp); 

template<class BidirectionalIterator>
bool next_permutation
	(BidirectionalIterator first, BidirectionalIterator last); 
template<class BidirectionalIterator, class Compare>
bool next_permutation
	(BidirectionalIterator first, BidirectionalIterator last,
	Compare comp); 
template<class BidirectionalIterator>
bool prev_permutation
	(BidirectionalIterator first, BidirectionalIterator last); 
template<class BidirectionalIterator, class Compare>
bool prev_permutation
	(BidirectionalIterator first, BidirectionalIterator last, 
	Compare comp); 
}

25.1 Non-modifying Sequence Operations

Various algorithms are provided which do not modify the original object.

for_each

The function for_each is used to perform an operation for each element.

Prototype:

template<class InputIterator, class Function>

Function for_each

The function f is returned.

find

The function find searches for the first element that contains the value passed.

Prototype:

template<class InputIterator, class T>

InputIterator find

Returns the type passed.

find_if

The function find_if searches for the first element that matches the criteria passed by the predicate.

Prototype:

template<class InputIterator, class Predicate>

InputIterator find_if

Returns the iterator of the matched value.

find_end

The function find_end searches for the last occurrence of a value.

Prototype:

template<class ForwardIterator1, 

ForwardIterator1 find_end

template<class ForwardIterator1, 

ForwardIterator1 find_end

Returns the iterator to the last value or the last1 argument if none is found.

find_first_of

The function find_first_of searches for the first occurrence of a value.

Prototype:

template<class ForwardIterator1, 

ForwardIterator1 find_first_of

template<class ForwardIterator1, 

ForwardIterator1 find_first_of

Returns the iterator to the last value or the last1 argument if none is found.

adjacent_find

The function adjacent_find is used to search for two adjacent elements that are equal or equal according to the predicate argument.

Prototype:

template<class ForwardIterator>

ForwardIterator adjacent_find

template<class ForwardIterator, 

ForwardIterator adjacent_find

Returns the iterator to the first occurrence found or to last if no occurrence is found.

count

The function count is used to find the number of elements.

Prototype:

template <class InputIterator, class T>

typename iterator_traits

Returns the number of elements (iterators) as an iterator_traits diference_type.

count_if

The function count_if is used to find the number of elements that match the criteria.

Prototype:

template <class InputIterator, class Predicate>

typename iterator_traits

Returns the number of elements (iterators) as an iterator_traits diference_type.

mismatch

The function mismatch is used to find sequences that are not the same or differ according to the predicate criteria.

Prototype:

template<class InputIterator1, 

pair<InputIterator1, InputIterator2> mismatch

template<class InputIterator1, 

pair<InputIterator1, InputIterator2> mismatch

Returns a pair<iterator> that represent the beginning element and the range. If no mismatch is found the end and the corresponding range element is returned..

equal

The function equal is used to determine if a range two ranges are equal.

Prototype:

template<class InputIterator1, 

bool equal

template<class InputIterator1, 

bool equal

A boo true is returned if the values are equal or meet the criteria of the predicate.

search

The function search is used to search for the first octanes of a sub-range that meet the criteria.

Prototype:

template<class ForwardIterator1, 

ForwardIterator1 search

template<class ForwardIterator1, 

ForwardIterator1 search

An iterator to the first occurrence is returned or last1 is returned if no criteria is met.

search_n

The function search_n is used to search for a number of consecutive elements with the same properties.

Prototype:

template<class ForwardIterator, 

ForwardIterator search_n

template<class ForwardIterator,

ForwardIterator search_n

An iterator to the first occurrence is returned or last1 is returned if no criteria is met.

25.2 Mutating Sequence Operators

Various algorithms are provided that are used to modify the original object.

copy

The function copy is used to copy a range.

Prototype:

template<class InputIterator, 

OutputIterator copy(

The position of the last copied element is returned.

copy_backward

The function copy_backwards is used to copy a range starting with the last element.

Prototype:

template<class BidirectionalIterator1, 

BidirectionalIterator2 copy_backward

The position of the last copied element is returned.

swap

The function swap is used to exchange values from two locations.

Prototype:

template<class T> void swap(T& a, T& b); 

There is no return.

swap_ranges

The function swap_ranges is used swap elements of two ranges.

Prototype:

template<class ForwardIterator1, 

ForwardIterator2 swap_ranges

The position of the last swapped element is returned.

iter_swap

The function iter_swap is used to exchange two values pointed to by iterators.

Prototype:

template<class ForwardIterator1, 

void iter_swap

There is no return.

transform

The function transform is used to modify and copy elements of two ranges.

Prototype:

template<class InputIterator, 

OutputIterator transform

template<class InputIterator1, 

OutputIterator transform

The position of the last transformed element is returned.

replace

The function replace is used to replace an element with another element of different value.

Prototype:

template<class ForwardIterator, class T>

void replace

template<class ForwardIterator, 

void replace_if

There is no return.

replace_copy

The function replace_copy is used to replace specific elements while copying an entire range.

Prototype:

template<class InputIterator, 

OutputIterator replace_copy

The position of the last copied element is returned.

replace_copy_if

The function replace_copy_if is used to replace specific elements that match certain criteria while copying the entire range.

Prototype:

template<class Iterator, 

OutputIterator replace_copy_if

The position of the last copied element is returned.

fill

The function fill is used to fill a range with values.

Prototype:

template<class ForwardIterator, class T>

void fill

There is no return value.

fill_n

The function fill_n is used to fill a number of elements with a specified value.

Prototype:

template<class OutputIterator, 

void fill_n

There is no return value.

generate

The function generate is used to replace elements with the result of an operation.

Prototype:

template<class ForwardIterator, class Generator>

void generate

There is no return value.

generate_n

The function generate_n is used to replace a number of elements with the result of an operation.

Prototype:

template<class OutputIterator, 

void generate_n

There is no return value.

remove

The function remove is used to remove elements with a specified value.

Prototype:

template<class ForwardIterator, class T>

ForwardIterator remove

The end of the resulting range is returned.

remove_if

The function remove_if is used to remove elements using a specified criteria.

Prototype:

template<class ForwardIterator, class Predicate>

ForwardIterator remove_if

The end of the resulting range is returned.

remove_copy

The function remove_copy is used remove elements that do not match a value during a copy.

Prototype:

template<class InputIterator, 

OutputIterator remove_copy

The end of the resulting range is returned.

remove_copy_if

The function remove_copy_if is used to remove elements that do not match a criteria while doing a copy.

Prototype:

template<class InputIterator, 

OutputIterator remove_copy_if

The end of the resulting range is returned.

unique

The function unique is used remove all adjacent duplicates.

Prototype:

template<class ForwardIterator>

ForwardIterator unique

template<class ForwardIterator, 

ForwardIterator unique

The end of the resulting range is returned.

unique_copy

The function unique_copy is used to remove adjacent duplicates while copying.

Prototype:

template<class InputIterator, 

OutputIterator unique_copy

template<class InputIterator, 

OutputIterator unique_copy

The end of the resulting range is returned.

reverse

The function reverse is used to reverse a sequence.

Prototype:

template<class BidirectionalIterator>

void reverse

No value is returned.

reverse_copy

The function reverse_copy is used to copy the elements while reversing their order.

Prototype:

template<class BidirectionalIterator, 

OutputIterator reverse_copy

The position of the last copied element is returned.

rotate

The function rotate is used to rotate the elements within a sequence.

Prototype:

template<class ForwardIterator>

void rotate

There is no return value.

rotate_copy

The function rotate_copy is used to copy a sequence with a rotated order.

Prototype:

template<class ForwardIterator, 

OutputIterator rotate_copy

The position of the last copied element is returned.

random_shuffle

The function random_shuffle is used to exchange the order of the elements in a random fashion.

Prototype:

template<class RandomAccessIterator>

void random_shuffle

template<class RandomAccessIterator,

void random_shuffle

No value is returned.

partition

The function partition is used to change the order of the elements so that the elements that meet the criteria are first in order.

Prototype:

template<class BidirectionalIterator, 

BidirectionalIterator partition

Returns an iterator to the first position where the predicate argument is false.

stable_partition

The function stable_partition is used to change the order of the elements so that the elements meet the criteria are first in order. The relative original order is preserved.

Prototype:

template<class BidirectionalIterator, 

BidirectionalIterator stable_partition

Returns an iterator to the first position where the predicate argument is false.

25.3 Sorting And Related Operations

All of the sorting functions have two versions:, one that takes a function object for comparison and one that uses the less than operator.

sort

The function sort is used sorts the range according to the criteria.

Prototype:

template<class RandomAccessIterator>

void sort

template<class RandomAccessIterator, 

void sort(RandomAccessIterator first,

There is no return value.

stable_sort

The function stable_sort is used to sort the range but preserves the original order for equal elements.

Prototype:

template<class RandomAccessIterator>

void stable_sort

template<class RandomAccessIterator, 

void stable_sort

There is no return value.

partial_sort

The function partial_sort is used to sort a sub-range leaving the rest unsorted.

Prototype:

template<class RandomAccessIterator>

void partial_sort

template<class RandomAccessIterator, 

void partial_sort

There is no return value.

partial_sort_copy

The function partial_sort_copy is used to copy a partially sorted sequence.

Prototype:

template<class InputIterator, 

RandomAccessIterator partial_sort_copy

template<class InputIterator, 

RandomAccessIterator partial_sort_copy

The position at the end of the copied elements is returned.

nth_element

The function nth_element is used to sort based upon a specified position.

Prototype:

template<class RandomAccessIterator>

void nth_element

template<class RandomAccessIterator, 

void nth_element

There is no value returned.

lower_bound

The function lower_bound is used to find the first position that an element may be inserted without changing the order.

Prototype:

template<class ForwardIterator, class T>

ForwardIterator lower_bound

template<class ForwardIterator, 

ForwardIterator lower_bound

The position where the element can be inserted is returned.

upper_bound

The function upper_bound is used to find the last position that an element may be inserted without changing the order.

Prototype:

template<class ForwardIterator, class T>

ForwardIterator upper_bound

template<class ForwardIterator,

ForwardIterator upper_bound

The position where the element can be inserted is returned.

equal_range

The function equal_range is used to find the range as a pair where an element can be inserted without altering the order.

Prototype:

template<class ForwardIterator, class T>

pair<ForwardIterator, ForwardIterator> equal_range

template<class ForwardIterator, 

pair<ForwardIterator, ForwardIterator> equal_range

The range as a pair<> where the element can be inserted is returned.

binary_search

The function binary_search is used to see if a value is present in a range or that a value meets a criteria within that range.

Prototype:

template<class ForwardIterator, class T>

bool binary_search

template<class ForwardIterator, 

bool binary_search

The bool value true is met if any element meets the criteria.

merge

The function merge is used to combine two sorted ranges.

Prototype:

template<class InputIterator1, 

OutputIterator merge

template<class InputIterator1, 

OutputIterator merge

The position of the first element not overwritten is returned.

inplace_merge

The function replacement is used to merge consecutive sequences to the first for a concatenation.

Prototype:

template<class BidirectionalIterator>

void inplace_merge

template<class BidirectionalIterator, 

void inplace_merge

There is no value returned.

includes

The function includes is used to determine if every element meets a specified criteria.

Prototype:

template<class InputIterator1, 

bool includes

template<class InputIterator1, 

bool includes

The bool value true is retuned if all values match or false if one or more does not meet the criteria.

set_union

The function set_union is used to process the sorted union of two ranges.

Prototype:

template<class InputIterator1, 

OutputIterator set_union

template<class InputIterator1, 

OutputIterator set_union

The end of the constructed range is returned.

set_intersection

The function set_intersection is used to process the intersection of two ranges.

Prototype:

template<class InputIterator1, 

OutputIterator set_intersection

template<class InputIterator1, 

OutputIterator set_intersection

The end of the constructed range is returned.

set_difference

The function set_difference is used to process all of the elements of one range that are not part of another range.

Prototype:

template<class InputIterator1, 

OutputIterator set_difference

template<class InputIterator1, 

OutputIterator set_difference

The end of the constructed range is returned.

set_symetric_difference

The function set_symetric_difference is used to process all of the elements that are in only one of two ranges.

Prototype:

template<class InputIterator1, 

OutputIterator set_symmetric_difference

template<class InputIterator1, 

OutputIterator set_symmetric_difference

The end of the constructed range is returned.

push_heap

The function push_heap is used to add an element to a heap.

Prototype:

template<class RandomAccessIterator>

void push_heap

template<class RandomAccessIterator, 

void push_heap

There is no value returned.

pop_heap

The function pop_heap is used to remove an element from a heap.

Prototype:

template<class RandomAccessIterator>

void pop_heap

template<class RandomAccessIterator, 

void pop_heap

There is no value returned.

make_heap

The function make_heap is used to convert a range into a heap.

Prototype:

template<class RandomAccessIterator>

void make_heap

template<class RandomAccessIterator, 

void make_heap(

There is no value returned.

sort_heap

The function sort_heap is used to sort a heap.

Prototype:

template<class RandomAccessIterator>

void sort_heap

template<class RandomAccessIterator, 

void sort_heap

WARNING!

This result is not stable

There is no value returned.

min

The function min is used to determine the lesser of two objects by value or based upon a comparison.

Prototype:

template<class T> 

const T& min

template<class T, class Compare>

const T& min

The lesser of the two objects is returned.

max

The function max is used to determine the greater of two objects by value or based upon a comparison.

Prototype:

template<class T> 

const T& max

template<class T, class Compare>

const T& max

The greater of the two objects is returned.

min_element

The function min_element is used to determine the lesser element within a range based upon a value or a comparison.

Prototype:

template<class ForwardIterator>

ForwardIterator min_element

template<class ForwardIterator, class Compare>

ForwardIterator min_element

The position of the element is returned.

max_element

The function max_element is used to determine the greater element within a range based upon a value or a comparison.

Prototype:

template<class ForwardIterator>

ForwardIterator max_element

template<class ForwardIterator, class Compare>

ForwardIterator max_element

The position of the element is returned.

lexicographical_compare

The function lexicographical_compare is used to determine if a range is lexicographically less than another.

Prototype:

template<class InputIterator1, 

bool lexicographical_compare

template<class InputIterator1, 

bool lexicographical_compare

Returns true if the first argument is less than the second and false for all other conditions.

next_permutation

The function next_permutation is used to sort in an ascending order based upon lexicographical criteria.

Prototype:

template<class BidirectionalIterator>

bool next_permutation

template<class BidirectionalIterator, 

bool next_permutation

Returns true if all elements have been sorted.

prev_permutation

The function prev_permutation is used to sort in an descending order based upon lexicographical criteria.

Prototype:

template<class BidirectionalIterator>

bool prev_permutation

template<class BidirectionalIterator, 

bool prev_permutation

Returns true if all elements have been sorted.

25.4 C library algorithms

The C++ header <cstdlib> provides two variations from the standard C header stdlib.h for searching and sorting.

bsearch

The function signature of bsearch

  bsearch(const void *, const void *, size_t,   size_t, int (*)(const void *, const void *));

is replaced by

  extern "C" void *bsearch   (const void * key, const void * base,
  size_t nmemb, size_t size,
  int (* compar)(const void *, const void *));

and

  extern "C++" void *bsearch   (const void * key, const void * base,
  size_t nmemb, size_t size,
  int (* compar)(const void *, const void *));

qsort

The function signature of qsort

qsort(void *, size_t, size_t, 

is replaced by

  extern "C" void qsort   void* base, size_t nmemb, size_t size,
  int (* compar)(const void*, const void*));

and

  extern "C++" void qsort   (void* base, size_t nmemb, size_t size,
  int (* compar)(const void*, const void*));