[ новости /+++ | форум | теги | ]

                       Standard C++ Library
             Copyright 1998, 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 allows you to apply  generic  algo-
     rithms  to  containers, and it supplies a set of these algo-
     rithms for searching, sorting, merging, transforming,  scan-
     ning, and more.

     Each algorithm can be applied to a  variety  of  containers,
     including  those  defined by a user of the library. The fol-
     lowing design features make algorithms generic:



     o    Generic algorithms access the collection through itera-
          tors

     o    Algorithms are templatized on iterator types

     o    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  previ-
     ously 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  sec-
     tion  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 has place and copy  versions  of  many
     algorithms,  such  as  replace and replace_copy. The library
     also has 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 (for example, replace, which uses  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  opera-
     tions  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  out-
     put iterators:


     adjacent_difference    replace_copy        transform
     copy                   replace_copy_if     unique_copy
     merge                  set_difference
     partial_sum            set_intersection
     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          stable_permutation
     inplace_merge          prev_permutation
     next_permutation       reverse

     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  ran-
     dom 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.

Партнёры:

Хостинг: