Algorithms

Various operations can be defined for container classes. Those that are specific to the container are defined with the container class. Those that are common to all containers are contained in a library called algorithm.

These generic algorithms either look only at the elements in the container, move the elements in the container, or perform specific calculations.

There are 4 types of algorithms:

A nonmodifying algorithm is one that does not modify the elements of the container, it simply examines the elements.

adjacent_find find_end max
binary_search find_first_of max_element
count find_if min
count_if for_each min_element
equal includes search
equal_range lower_bound search_n
find mismatch upper_bound

A modifying algorithm is one that modifies the elements of the container by rearranging, removing, or changing the values of the elements.

copy prev_permutation rotate_copy
copy_backward random_shuffle set_difference
fill remove set_intersection
fill_n remove_copy set_symmetric_difference
generate remove_copy_if set_union
generate_n remove_if sort
inplace_merge replace stable_partition
iter_swap replace_copy stable_sort
merge replace_copy_if swap
next_permutation replace_if swap_ranges
nth_element reverse transform
partial_sort reverse_copy unique
partial_sort_copy rotate unique_copy
partition    

A numeric algorithm is one that performs a numeric calculation on the elements of a container.

accumulate inner_product
adjacent_difference partial_sum

The STL algorithms take advantage of function overloading to allow the user to specify the manipulating criteria for the data rather than relying on the default action. This is accomplished by using a function object, which is simply any object that can be called as if it is a function. An ordinary function is a function object, and so is a function pointer; more generally, so is an object of a class that defines operator().

Arithmetic Function Objects

Function Object Name Use
plus<type> plus<int> addNum;

int sum = addNum( 12, 35 );
minus<type> minus<int> subtractNum;

int difference = subtractNum( 56, 35 );
multiplies<type> multiplies<int> multiplyNum;

int product = multiplyNum( 6, 3 );
divides<type> divides<int> divideNum;

int quotient = divideNum( 16, 3 );
modulus<type> modulus<int> remainder;

int remain = remainder( 16, 7 );
negate<type> negate<int> num;

int opposite = num( -25 );

Relational Function Objects

Function Object Name Use
equal_to<type> returns a boolean value indicating whether two arguments are equal

equal_to<int> compare;

bool isEqual = compare( 12, 35 );
not_equal_to<type> returns a boolean value indicating whether two arguments are not equal

not_equal_to<int> compare;

bool isEqual = compare( 20, 30 );
greater<type> returns a boolean value indicating whether the first argument is greater than the second argument

greater<int> compare;

bool isGreater = compare( 8, 5 );
greater_equal<type> returns a boolean value indicating whether the first argument is greater than or equal to the second argument

greater_equal<int> compare;

bool isGreaterEqaul = compare( 34, 21 );
less<type> returns a boolean value indicating whether the first argument is less than the second argument

less<int> compare;

bool isLess = compare( 3, 5 );
less_equal<type> returns a boolean value indicating whether the first argument is less than or equal to the second argument

less_equal<int> compare;

bool isLessEqual = compare( 8, 15 );

Logical Function Objects

Function Object Name Use
logical_not<type> returns true if its operand evaluates to false; otherwise it returns false

This is a unary function object
logical_and<type> returns true if both of its operands evaluate to true; otherwise it returns false

This is a binary function object
logical_or<type> returns true if at least one of its operands evaluates to true; otherwise it returns false

This is a binary function object

copy function

Function prototype:    iterator copy( first, last, destination );

The copy function will copy all of the elements in the range [first, last) to destination and returns an iterator indicating the end of the range of copied elements.

One of the common uses for this function is to output the elements of a container:

ostream_iterator<int> screen( cout, ", " );

copy( vecList.begin(), vecList.end(), screen );

copy( vecList.begin() + 1, vecList.end(), vecList.begin() );