|
VMS Help CXXLSTD, Algorithms *Conan The Librarian |
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
Algorithms - Generic algorithms for performing various operations
on containers and sequences.
SYNOPSIS
#include <algorithm>
The synopsis of each algorithm appears in its entry in the reference
guide.
DESCRIPTION
The Standard C++ Library provides a very flexible framework for
applying generic algorithms to containers. The library also
provides a rich set of these algorithms for searching, sorting,
merging, transforming, scanning, and much more.
Each algorithm can be applied to a variety of containers, including
those defined by a user of the library. The following design
features make algorithms generic:
+ Generic algorithms access the collection through iterators
+ Algorithms are templatized on iterator types
+ Each algorithm is designed to require the least number of
services from the iterators it uses
In addition to requiring certain iterator capabilities, algorithms
may require a container to be in a specific state. For example,
some algorithms can only work on previously sorted containers.
Because most algorithms rely on iterators to gain access to data,
they can be grouped according to the type of iterator they require,
as is done in the Algorithms by Iterator section below. They can
also be grouped according to the type of operation they perform.
ALGORITHMS BY MUTATING/NON-MUTATING FUNCTION
The broadest categorization groups algorithms into two main types:
mutating and non-mutating. Algorithms that alter (or mutate) the
contents of a container fall into the mutating group. All
others are considered non-mutating. For example, both fill and
sort are mutating algorithms, while find and for_each are
non-mutating.
Non-mutating operations
accumulate find_end max element
adjacent_find find_first_of min
binary_search find_if min_element
count_min for_each mismatch
count_if includes nth_element
equal lexicographical_compare search
equal_range lower_bound search_n
find max
Mutating operations
copy remove_if
copy_backward replace
fill replace_copy
fill_n replace_copy_if
generate replace_if
generate_n reverse
inplace_merge reverse_copy
iter_swap rotate
make_heap rotate_copy
merge set_difference
nth_element set_symmetric_difference
next_permutation set_intersection
partial_sort set_union
partial_sort_copy sort
partition sort_heap
prev_permutation stable_partition
push_heap stable_sort
pop_heap swap
random_shuffle swap_ranges
remove transform
remove_copy unique
remove_copy_if unique_copy
Note that the library provides both in place and copy versions of
many algorithms, such as replace and replace_copy. The library
also provides versions of algorithms that allow the use of default
comparators and comparators supplied by the user. Often these
functions are overloaded, but in some cases (where
overloading proved impractical or impossible) the names differ
(e.g., replace, which will use equality to determine replacement,
and replace_if, which accesses a user provided compare
function).
ALGORITHMS BY OPERATION
We can further distinguish algorithms by the kind of operations they
perform. The following lists all algorithms by loosely
grouping them into similar operations.
Initializing operations
fill generate
fill_n generate_n
Search operations
adjacent_find find_end search_n
count find_if
count_if find_first_of
find search
Binary search operations (Elements must be sorted)
binary_search lower_bound
equal_range upper_bound
Compare operations
equal mismatch
lexicographical_compare
Copy operations
copy copy_backward
Transforming operations
partition reverse
random_shuffle reverse_copy
replace rotate
replace_copy rotate_copy
replace_copy_if stable_partition
replace_if transform
Swap operations
swap swap_ranges
Scanning operations
accumulate for_each
Remove operations
remove remove_if
remove_copy unique
remove_copy_if unique_copy
Sorting operations
nth_element sort
partial_sort stable_sort
partial_sort_copy
Merge operations (Elements must be sorted)
inplace_merge merge
Set operations (Elements must be sorted)
includes set_symmetric_difference
set_difference set_union
set_intersection
Heap operations
make_heap push_heap
pop_heap sort_heap
Minimum and maximum
max min
max_element min_element
Permutation generators
next_permutation prev_permutation
ALGORITHMS BY CATEGORY
Each algorithm requires certain kinds of iterators (for a
description of the iterators and their capabilities see the
Iterator entry in this manual). The following set of lists
groups the algorithms according to the types of iterators they
require.
Algorithms that use no iterators:
max min swap
Algorithms that require only input iterators:
accumulate find mismatch
count find_if
count_if includes
equal inner_product
for_each lexicographical_compare
Algorithms that require only output iterators:
fill_n generate_n
Algorithms that read from input iterators and write to output
iterators:
adjacent_difference replace_copy transform
copy replace_copy_if unique_copy
merge set_difference
partial_sum set_intersedtion
remove_copy set_symmetric_difference
remove_copy_if set_union
Algorithms that require forward iterators:
adjacent_find iter_swap replace_if
binary_search lower_bound rotate
equal_range max_element search
fill min_element search_n
find_end remove swap_ranges
find_first_of remove_if unique
generate replace upper_bound
Algorithms that read from forward iterators and write to output
iterators:
rotate_copy
Algorithms that require bidirectional iterators
copy_backward partition
inplace_merge prev_permutation
next_permutation reverse
stable_permutation
Algorithms that read from bidirectional iterators and write to output
iterators:
reverse_copy
Algorithms that require random access iterators:
make_heap pop_heap sort
nth_element push_heap sort_heap
partial_sort random_shuffle stable_sort
Algorithms that read from input iterators and write to random access
iterators:
partial_sort_copy
COMPLEXITY
The complexity for each of these algorithms is given in the manual
page for that algorithm.
SEE ALSO
Manual pages for each of the algorithms named in the lists above.
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
Additional Information (explode) :
|
|