Standard C++ LibraryCopyright 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



privacy and legal statement