Skip to Main Content United States    
PRODUCTS SUPPORT SOLUTIONS SERVICES
COMPAQ SOFTWARE
cxxlstd$help.HLP

accumulate

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

accumulate - Accumulate all elements within a range into a single value.

SYNOPSIS

#include <numeric> template <class InputIterator, class T> T accumulate (InputIterator first, InputIterator last, T init);

template <class InputIterator, class T, class BinaryOperation> T accumulate (InputIterator first, InputIterator last, T init, BinaryOperation binary_op);

DESCRIPTION

accumulate applies a binary operation to init and each value in the range [first,last). The result of each operation is returned in init. This process aggregates the result of performing the operation on every element of the sequence into a single value.

Accumulation is done by initializing the accumulator acc with the initial value init and then modifying it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first, last) in order. If the sequence is empty, accumulate returns init.

COMPLEXITY

accumulate performs exactly last-first applications of the binary operation (operator+ by default).

EXAMPLE

// // accum.cpp // #include <numeric> //for accumulate #include <vector> //for vector #include <functional> //for times #include <iostream.h>

int main() { // //Typedef for vector iterators // typedef vector<int>::iterator iterator; // //Initialize a vector using an array of ints // int d1[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v1(d1, d1+10); // //Accumulate sums and products // int sum = accumulate(v1.begin(), v1.end(), 0); int prod = accumulate(v1.begin(), v1.end(), 1, times<int>()); // //Output the results // cout << "For the series: "; for(iterator i = v1.begin(); i != v1.end(); i++) cout << *i << " ";

cout << " where N = 10." << endl; cout << "The sum = (N*N + N)/2 = " << sum << endl; cout << "The product = N! = " << prod << endl; return 0; } Output : For the series: 1 2 3 4 5 6 7 8 9 10 where N = 10. The sum = (N*N + N)/2 = 55 The product = N! = 3628800

WARNINGS

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


adjacent_difference

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

adjacent_difference - Outputs a sequence of the differences between each adjacent pair of elements in a range.

SYNOPSIS

#include <numeric>

template <class InputIterator, class OutputIterator> OutputIterator adjacent_difference (InputIterator first, InputIterator last, OutputIterator result); template <class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator adjacent_difference (InputIterator first, InputIterator last, OutputIterator result, BinaryOperation bin_op);

DESCRIPTION

Informally, adjacent_difference fills a sequence with the differences between successive elements in a container. The result is a sequence in which the first element is equal to the first element of the sequence being processed, and the remaining elements are equal to the calculated differences between adjacent elements. For instance, applying adjacent_difference to {1,2,3,5} will produce a result of {1,1,1,2}.

By default, subtraction is used to compute the difference, but you can supply any binary operator. The binary operator is then applied to adjacent elements. For example, by supplying the plus (+) operator, the result of applying adjacent_difference to {1,2,3,5} is the sequence {1,3,5,8}.

Formally, adjacent_difference assigns to every element referred to by iterator i in the range [result + 1, result + (last - first)) a value equal to the appropriate one of the following:

*(first + (i - result)) - *(first + (i - result) - 1)

or

binary_op (*(first + (i - result)), *(first + (i - result) - 1))

result is assigned the value of *first.

adjacent_difference returns result + (last - first).

result can be equal to first. This allows you to place the results of applying adjacent_difference into the original sequence.

COMPLEXITY

This algorithm performs exactly (last-first) - 1 applications of the default operation (-) or binary_op.

EXAMPLE

// // adj_diff.cpp // #include<numeric> //For adjacent_difference #include<vector> //For vector #include<functional> //For times #include <iostream.h> int main() { // //Initialize a vector of ints from an array // int arr[10] = {1,1,2,3,5,8,13,21,34,55}; vector<int> v(arr,arr+10); // //Two uninitialized vectors for storing results // vector<int> diffs(10), prods(10); // //Calculate difference(s) using default operator (minus) // adjacent_difference(v.begin(),v.end(),diffs.begin()); // //Calculate difference(s) using the times operator // adjacent_difference(v.begin(), v.end(), prods.begin(), times<int>()); // //Output the results // cout << "For the vector: " << endl << " "; copy(v.begin(),v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; cout << "The differences between adjacent elements are: " << endl << " "; copy(diffs.begin(),diffs.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; cout << "The products of adjacent elements are: " << endl << " "; copy(prods.begin(),prods.end(), ostream_iterator<int,char>(cout," ")); cout << endl; return 0;

Output : For the vector: 1 1 2 3 5 8 13 21 34 55 The differences between adjacent elements are: 1 0 1 1 2 3 5 8 13 21 The products of adjacent elements are: 1 1 2 6 15 40 104 273 714 1870

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


adjacent_find

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

adjacent_find - Find the first adjacent pair of elements in a sequence that are equivalent.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

DESCRIPTION

There are two versions of the adjacent_find algorithm. The first finds equal adjacent elements in the sequence defined by iterators first and last and returns an iterator i pointing to the first of the equal elements. The second version lets you specify your own binary function to test for a condition. It returns an iterator i pointing to the first of the pair of elements that meet the conditions of the binary function. In other words, adjacent_find returns the first iterator i such that both i and i + 1 are in the range [first, last) for which one of the following conditions holds:

*i == *(i + 1)

or

pred(*i,*(i + 1)) == true

If adjacent_find does not find a match, it returns last.

COMPLEXITY

adjacent_find performs exactly find(first,last,value) - first applications of the corresponding predicate.

EXAMPLE

// // find.cpp // #include <vector> #include <algorithm> #include <iostream.h>

int main() { typedef vector<int>::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7};

// Set up a vector vector<int> v1(d1,d1 + 10);

// Try find iterator it1 = find(v1.begin(),v1.end(),3);

// Try find_if iterator it2 = find_if(v1.begin(),v1.end(),bind1st(equal_to<int>(),3));

// Try both adjacent_find variants iterator it3 = adjacent_find(v1.begin(),v1.end());

iterator it4 = adjacent_find(v1.begin(),v1.end(),equal_to<int>());

// Output results cout << *it1 << " " << *it2 << " " << *it3 << " " << *it4 << endl;

return 0; }

Output : 3 3 2 2

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> > instead of:

vector<int>

SEE ALSO

find

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


advance

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

advance - Move an iterator forward or backward (if available) by a certain distance.

SYNOPSIS

#include <iterator>

template <class InputIterator, class Distance> void advance (InputIterator& i, Distance n);

DESCRIPTION

The advance template function allows an iterator to be advanced through a container by some arbitrary distance. For bidirectional and random access iterators, this distance may be negative. This function uses operator+ and operator- for random access iterators, which provides a constant time implementation. For input, forward, and bidirectional iterators, advance uses operator++ to provide linear time implementations. advance also uses operator-- with bidirectional iterators to provide linear time implementations of negative distances.

If n is positive, advance increments iterator reference i by n. For negative n, advance decrements reference i. Remember that advance accepts a negative argument n for random access and bidirectional iterators only.

EXAMPLE

// // advance.cpp // #include<iterator> #include<list> #include<iostream.h>

int main() {

// //Initialize a list using an array // int arr[6] = {3,4,5,6,7,8}; list<int> l(arr,arr+6); // //Declare a list iterator, s.b. a ForwardIterator // list<int>::iterator itr = l.begin(); // //Output the original list // cout << "For the list: "; copy(l.begin(),l.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; cout << "When the iterator is initialized to l.begin()," << endl << "it points to " << *itr << endl << endl; // // operator+ is not available for a ForwardIterator, // so use advance. //

advance(itr, 4); cout << "After advance(itr,4), the iterator points to " << *itr << endl; return 0; }

Output : For the list: 3 4 5 6 7 8 When the iterator is initialized to l.begin(), it points to 3 After advance(itr,4), the iterator points to 7

WARNINGS

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

SEE ALSO

sequence, random_iterator, distance

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


binary_search

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

binary_search - Performs a binary search for a value on a container.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The binary_search algorithm, like other related algorithms (equal_range, lower_bound and upper_bound) performs a binary search on ordered containers. All binary search algorithms have two versions. The first version uses the less than operator (operator<) to perform the comparison, and assumes that the sequence has been sorted using that operator. The second version allows you to include a function object of type Compare, which it assumes was the function used to sort the sequence. The function object must be a binary predicate.

The binary_search algorithm returns true if a sequence contains an element equivalent to the argument value. The first version of binary_search returns true if the sequence contains at least one element that is equal to the search value. The second version of the binary_search algorithm returns true if the sequence contains at least one element that satisfies the conditions of the comparison function. Formally, binary_search returns true if there is an iterator i in the range [first, last) that satisfies the corresponding conditions:

!(*i < value) && !(value < *i)

or

comp(*i, value) == false && comp(value, *i) == false

COMPLEXITY

binary_search performs at most log(last - first) + 2 comparisons.

EXAMPLE

// // b_search.cpp // #include <vector> #include <algorithm> #include <iostream.h>

int main() { typedef vector<int>::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7}; // // Set up a vector // vector<int> v1(d1,d1 + 10); // // Try binary_search variants // sort(v1.begin(),v1.end()); bool b1 = binary_search(v1.begin(),v1.end(),3); bool b2 = binary_search(v1.begin(),v1.end(),11,less<int>()); // // Output results // cout << "In the vector: "; copy(v1.begin(),v1.end(), ostream_iterator<int,char>(cout," "));

cout << endl << "The number 3 was " << (b1 ? "FOUND" : "NOT FOUND"); cout << endl << "The number 11 was " << (b2 ? "FOUND" : "NOT FOUND") << endl; return 0; }

Output : In the vector: 0 1 2 2 2 2 3 4 6 7 The number 3 was FOUND The number 11 was NOT FOUND

WARNINGS

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

SEE ALSO

equal_range, lower_bound, upper_bound

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


copy

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

copy, copy_backward - Copies a range of elements

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The copy algorithm copies values from the range specified by [first , last) to the range that specified by [result, result + (last - first)). copy can be used to copy values from one container to another, or to copy values from one location in a container to another location in the same container, as long as result is not within the range [first-last). copy returns result + (last - first). For each non-negative integer n < (last - first), copy assigns *(first + n) to *(result + n). The result of copy is undefined if result is in the range [first, last).

Unless result is an insert iterator, copy assumes that at least as many elements follow result as are in the range [first, last).

The copy_backward algorithm copies elements in the range specified by [first, last) into the range specified by [result - (last - first), result), starting from the end of the sequence (last-1) and progressing to the front (first). Note that copy_backward does not reverse the order of the elements, it simply reverses the order of transfer. copy_backward returns result - (last - first). You should use copy_backward instead of copy when last is in the range [result - (last - first), result). For each positive integer n <= (last - first), copy_backward assigns *(last - n) to *(result - n). The result of copy_backward is undefined if result is in the range [first, last).

Unless result is an insert iterator, copy_backward assumes that there are at least as many elements ahead of result as are in the range [first, last).

COMPLEXITY

Both copy and copy_backward perform exactly last - first assignments.

EXAMPLE

// // stdlib/examples/manual.copyex.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main() { int d1[4] = {1,2,3,4}; int d2[4] = {5,6,7,8};

// Set up three vectors // vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4), v3(d2,d2 + 4); // // Set up one empty vector // vector<int> v4; // // Copy v1 to v2 // copy(v1.begin(),v1.end(),v2.begin()); // // Copy backwards v1 to v3 // copy_backward(v1.begin(),v1.end(),v3.end()); // // Use insert iterator to copy into empty vector // copy(v1.begin(),v1.end(),back_inserter(v4)); // // Copy all four to cout // ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; copy(v3.begin(),v3.end(),out); cout << endl; copy(v4.begin(),v4.end(),out); cout << endl;

return 0; }

Output : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector <int, allocator<int> >

instead of:

vector <int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


copy_backward

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

copy, copy_backward - Copies a range of elements

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The copy algorithm copies values from the range specified by [first , last) to the range that specified by [result, result + (last - first)). copy can be used to copy values from one container to another, or to copy values from one location in a container to another location in the same container, as long as result is not within the range [first-last). copy returns result + (last - first). For each non-negative integer n < (last - first), copy assigns *(first + n) to *(result + n). The result of copy is undefined if result is in the range [first, last).

Unless result is an insert iterator, copy assumes that at least as many elements follow result as are in the range [first, last).

The copy_backward algorithm copies elements in the range specified by [first, last) into the range specified by [result - (last - first), result), starting from the end of the sequence (last-1) and progressing to the front (first). Note that copy_backward does not reverse the order of the elements, it simply reverses the order of transfer. copy_backward returns result - (last - first). You should use copy_backward instead of copy when last is in the range [result - (last - first), result). For each positive integer n <= (last - first), copy_backward assigns *(last - n) to *(result - n). The result of copy_backward is undefined if result is in the range [first, last).

Unless result is an insert iterator, copy_backward assumes that there are at least as many elements ahead of result as are in the range [first,last).

COMPLEXITY

Both copy and copy_backward perform exactly last - first assignments.

//

EXAMPLE

// stdlib/examples/manual.copyex.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main() { int d1[4] = {1,2,3,4}; int d2[4] = {5,6,7,8};

// Set up three vectors // vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4), v3(d2,d2 + 4); // // Set up one empty vector // vector<int> v4; // // Copy v1 to v2 // copy(v1.begin(),v1.end(),v2.begin()); // // Copy backwards v1 to v3 // copy_backward(v1.begin(),v1.end(),v3.end()); // // Use insert iterator to copy into empty vector // copy(v1.begin(),v1.end(),back_inserter(v4)); // // Copy all four to cout // ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; copy(v3.begin(),v3.end(),out); cout << endl; copy(v4.begin(),v4.end(),out); cout << endl;

return 0; }

Output : 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector <int, allocator<int> >

instead of:

vector <int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


count

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

count, count_if - Count the number of elements in a container that satisfy a given condition.

SYNOPSIS

#include <algorithm> template<class InputIterator, class T> iterator_trait<InputIterator>::distance_type count(InputIterator first, InputIterator last, const T& value);

template <class InputIterator, class T, class Size> void count(InputIterator first, InputIterator last, const T& value, Size& n);

template<class InputIterator, class Predicate> iterator_trait<InputIterator>::distance_type count_if(InputIterator first, InputIterator last, Predicate pred);

template <class InputIterator, class Predicate, class Size> void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);

DESCRIPTION

The count algorithm compares value to elements in the sequence defined by iterators first and last. The first version of count return the number of matches. The second version increments a counting value n each time it finds a match. i.e., count returns (or adds to n) the number of iterators i in the range [first, last) for which the following condition holds:

*i == value

COMPLEXITY

The count_if algorithm lets you specify a predicate, and returns the number of times an element in the sequence satisfies the predicate (or increments n that number of times). That is, count_if returns (or adds to n) the number of iterators i in the range [first, last) for which the following condition holds:

pred(*i) == true. Both count and count_if perform exactly last-first applications of the corresponding predicate.

EXAMPLE

// // count.cpp // // Does not demonstrate the partial specialization versions // of count and count_if // #include <vector> #include <algorithm> #include <iostream.h>

int main() { int sequence[10] = {1,2,3,4,5,5,7,8,9,10}; int i=0,j=0,k=0; // // Set up a vector // vector<int> v(sequence,sequence + 10);

count(v.begin(),v.end(),5,i); // Count fives count(v.begin(),v.end(),6,j); // Count sixes // // Count all less than 8 // I=2, j=0 // count_if(v.begin(),v.end(),bind2nd(less<int>(),8),k); // k = 7

cout << i << " " << j << " " << k << endl; return 0; }

Output : 2 0 7

WARNINGS

If your compiler does not support partial specialization then the first version of both count and count_if (the one that returns the count) will not be available.

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance, you'll have to write:

vector <int, allocator<int> >

instead of:

vector <int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


count_if

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

count, count_if - Count the number of elements in a container that satisfy a given condition.

SYNOPSIS

#include <algorithm> template<class InputIterator, class T> iterator_trait<InputIterator>::distance_type count(InputIterator first, InputIterator last, const T& value);

template <class InputIterator, class T, class Size> void count(InputIterator first, InputIterator last, const T& value, Size& n);

template<class InputIterator, class Predicate> iterator_trait<InputIterator>::distance_type count_if(InputIterator first, InputIterator last, Predicate pred);

template <class InputIterator, class Predicate, class Size> void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);

DESCRIPTION

The count algorithm compares value to elements in the sequence defined by iterators first and last. The first version of count return the number of matches. The second version increments a counting value n each time it finds a match. i.e., count returns (or adds to n) the number of iterators i in the range [first, last) for which the following condition holds:

*i == value

COMPLEXITY

The count_if algorithm lets you specify a predicate, and returns the number of times an element in the sequence satisfies the predicate (or increments n that number of times). That is, count_if returns (or adds to n) the number of iterators i in the range [first, last) for which the following condition holds:

pred(*i) == true. Both count and count_if perform exactly last-first applications of the corresponding predicate.

EXAMPLE

// // count.cpp // // Does not demonstrate the partial specialization versions // of count and count_if // #include <vector> #include <algorithm> #include <iostream.h>

int main() { int sequence[10] = {1,2,3,4,5,5,7,8,9,10}; int i=0,j=0,k=0; // // Set up a vector // vector<int> v(sequence,sequence + 10);

count(v.begin(),v.end(),5,i); // Count fives count(v.begin(),v.end(),6,j); // Count sixes // // Count all less than 8 // I=2, j=0 // count_if(v.begin(),v.end(),bind2nd(less<int>(),8),k); // k = 7

cout << i << " " << j << " " << k << endl; return 0; }

Output : 2 0 7

WARNINGS

If your compiler does not support partial specialization then the first version of both count and count_if (the one that returns the count) will not be available.

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance, you'll have to write:

vector <int, allocator<int> >

instead of:

vector <int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


compare

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

compare - A binary function or a function object that returns true or false. compare objects are typically passed as template parameters, and used for ordering elements within a container.

SEE ALSO

binary_function, function object

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


distance

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

distance - Computes the distance between two iterators

SYNOPSIS

#include <iterator>

template <class ForwardIterator> iterator_traits<ForwardIterator>::distance_type distance (ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Distance> void distance (ForwardIterator first, ForwardIterator last, Distance& n);

DESCRIPTION

The distance template function computes the distance between two iterator. The first version returns that value, while the second version increments n by that value. The last iterator must be reachable from the first iterator.

Note that the second version of this function is obsolete. It is provided for backward compatibility and to support compilers that do not provide partial specialization. As you may have already deduced, the first version of the function is not available with compilers that do not support partial specialization since it depends on iterator_traits, which itself depends on that particular language feature.

EXAMPLE

// // distance.cpp //

#include <iterator> #include <vector> #include <iostream.h> int main() { // //Initialize a vector using an array // int arr[6] = {3,4,5,6,7,8}; vector<int> v(arr,arr+6); // //Declare a list iterator, s.b. a ForwardIterator // vector<int>::iterator itr = v.begin()+3; // //Output the original vector // cout << "For the vector: "; copy(v.begin(),v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl;

cout << "When the iterator is initialized to point to " << *itr << endl; // // Use of distance // vector<int>::difference_type dist = 0; distance(v.begin(), itr, dist); cout << "The distance between the beginning and itr is " << dist << endl; return 0; }

Output : For the vector: 3 4 5 6 7 8 When the iterator is initialized to point to 6 The distance between the beginning and itr is 3

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector <int, allocator,int> > instead of:

vector <int>

Also, if your compiler does not support partial specialization then you will not be able to use the version of distance that returns the distance. Instead you'll have to use the version that increments a reference parameter.

SEE ALSO

sequence, random_iterator

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


distance_type

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

distance_type - Determine the type of distance used by an iterator. This function is now obsolete. It is retained in order to provide backward compatibility and support compilers that do not provide partial specialization.

SYNOPSIS

#include <iterator>

template <class T, class Distance> inline Distance* distance_type (const input_iterator<T, Distance>&)

template <class T, class Distance> inline Distance* distance_type (const forward_iterator<T, Distance>&)

template <class T, class Distance> inline Distance* distance_type (const bidirectional_iterator<T, Distance>&)

template <class T, class Distance> inline Distance* distance_type (const random_access_iterator<T, Distance>&)

template <class T> inline ptrdiff_t* distance_type (const T*)

DESCRIPTION

The distance_type family of function templates return a pointer to a value that is of the same type as that used to represent a distance between two iterators. The first four of these take an iterator of a particular type and return a pointer to a default value of the distance_type for that iterator. The T* form of the function returns ptrdiff_t*.

Generic algorithms use this function to create local variables of the correct type. The distance_type functions are typically used like this:

template <class Iterator> void foo(Iterator first, Iterator last) { __foo(begin,end,distance_type(first)); }

template <class Iterator, class Distance> void __foo(Iterator first,Iterator last, Distance*> { Distance d = Distance(); distance(first,last,d); }

The auxiliary function template allows the algorithm to extract a distance type from the first iterator and then use that type to perform some useful work.

SEE ALSO

Other iterator primitives: value_type, iterator_category, distance, advance

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


equal

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

equal - Compares two ranges for equality.

SYNOPSIS

#include <algorithm>

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 binary_pred);

DESCRIPTION

The equal algorithm does a pairwise comparison of all of the elements in one range with all of the elements in another range to see if they match. The first version of equal uses the equal operator (==) as the comparison function, and the second version allows you to specify a binary predicate as the comparison function. The first version returns true if all of the corresponding elements are equal to each other. The second version of equal returns true if for each pair of elements in the two ranges, the result of applying the binary predicate is true. In other words, equal returns true if both of the following are true:

1. There are at least as many elements in the second range as in the first;

2. For every iterator i in the range [first1, last1) the following corresponding conditions hold:

*i == *(first2 + (i - first1))

or

binary_pred(*i, *(first2 + (i - first1))) == true

Otherwise, equal returns false.

This algorithm assumes that there are at least as many elements available after first2 as there are in the range [first1, last1).

COMPLEXITY

equal performs at most last1-first1 comparisons or applications of the predicate.

EXAMPLE

// // equal.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main() { int d1[4] = {1,2,3,4}; int d2[4] = {1,2,4,3}; // // Set up two vectors // vector<int> v1(d1+0, d1 + 4), v2(d2+0, d2 + 4);

// Check for equality bool b1 = equal(v1.begin(),v1.end(),v2.begin()); bool b2 = equal(v1.begin(),v1.end(), v2.begin(),equal_to<int>());

// Both b1 and b2 are false cout << (b1 ? "TRUE" : "FALSE") << " " << (b2 ? "TRUE" : "FALSE") << endl; return 0; }

Output : FALSE FALSE

WARNINGS

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


equal_range

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

equal_range - Find the largest subrange in a collection into which a given value can be inserted without violating the ordering of the collection.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The equal_range algorithm performs a binary search on an ordered container to determine where the element value can be inserted without violating the container's ordering. The library provides two versions of the algorithm. The first version uses the less than operator (operator <) to search for the valid insertion range, and assumes that the sequence was sorted using the less than operator. The second version allows you to specify a function object of type Compare, and assumes that Compare was the function used to sort the sequence. The function object must be a binary predicate.

equal_range returns a pair of iterators, i and j that define a range containing elements equivalent to value, i.e., the first and last valid insertion points for value. If value is not an element in the container, i and j are equal. Otherwise, i will point to the first element not "less" than value, and j will point to the first element greater than value. In the second version, "less" is defined by the comparison object. Formally, equal_range returns a subrange [i, j) such that value can be inserted at any iterator k within the range. Depending upon the version of the algorithm used, k must satisfy one of the following conditions:

!(*k < value) && !(value < *k)

or

comp(*k,value) == false && comp(value, *k) == false

The range [first,last) is assumed to be sorted.

COMPLEXITY

equal_range performs at most 2 * log(last - first) + 1 comparisons.

EXAMPLE

// // eqlrange.cpp // #include <vector> #include <algorithm> #include <iostream.h> int main() { typedef vector<int>::iterator iterator; int d1[11] = {0,1,2,2,3,4,2,2,2,6,7}; // // Set up a vector // vector<int> v1(d1+0, d1 + 11); // // Try equal_range variants // pair<iterator,iterator> p1 = equal_range(v1.begin(),v1.end(),3); // p1 = (v1.begin() + 4,v1.begin() + 5) pair<iterator,iterator> p2 = equal_range(v1.begin(),v1.end(),2,less<int>()); // p2 = (v1.begin() + 4,v1.begin() + 5) // Output results cout << endl << "The equal range for 3 is: " << "( " << *p1.first << " , " << *p1.second << " ) " << endl << endl; cout << endl << "The equal range for 2 is: " << "( " << *p2.first << " , " << *p2.second << " ) " << endl; return 0; } Output : The equal range for 3 is: ( 3 , 4 ) The equal range for 2 is: ( 2 , 3 )

WARNINGS

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

SEE ALSO

instead of:

vector<int> binary_function, lower_bound, upper_bound

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


equal_to

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

equal_to - Binary function object that returns true if its first argument equals its second

SYNOPSIS

#include <functional>

template <class T> struct equal_to;

DESCRIPTION

equal_to is a binary function object. Its operator() returns true if x is equal to y. You can pass an equal_to object to any algorithm that requires a binary function. For example, the transform algorithm applies a binary operation to corresponding values in two collections and stores the result. equal_to would be used in that algorithm in the following manner:

vector<int> vec1; vector<int> vec2; vector<int> vecResult; transform(vec1.begin(), vec1.end(), vec2.begin(), vecResult.begin(), equal_to<int>());

After this call to transform, vecResult(n) will contain a "1" if vec1(n) was equal to vec2(n) or a "0" if vec1(n) was not equal to vec2(n).

INTERFACE

template <class T> struct equal_to : binary_function<T, T, bool> { typedef typename binary_function<T, T, bool>::second_argument_type second_argument_type; typedef typename binary_function<T, T, bool>::first_argument_type first_argument_type; typedef typename binary_function<T, T, bool>::result_type result_type;

SEE ALSO

bool operator() (const T&, const T&) const; }; binary_function, function objects

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


fill

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

fill, fill_n - Initializes a range with a given value.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The fill and fill_n algorithms are used to assign a value to the elements in a sequence. fill assigns the value to all the elements designated by iterators in the range [first, last).

The fill_n algorithm assigns the value to all the elements designated by iterators in the range [first, first + n). fill_n assumes that there are at least n elements following first, unless first is an insert iterator.

COMPLEXITY

fill makes exactly last - first assignments, and fill_n makes exactly n assignments.

EXAMPLE

// // fill.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main() { int d1[4] = {1,2,3,4}; // // Set up two vectors // vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4); // // Set up one empty vector // vector<int> v3; // // Fill all of v1 with 9 // fill(v1.begin(),v1.end(),9);

// // Fill first 3 of v2 with 7 // fill_n(v2.begin(),3,7);

// // Use insert iterator to fill v3 with 5 11's // fill_n(back_inserter(v3),5,11); // // Copy all three to cout // ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; copy(v3.begin(),v3.end(),out); cout << endl; // // Fill cout with 3 5's // fill_n(ostream_iterator<int,char>(cout," "),3,5); cout << endl;

return 0; }

Output : 9 9 9 9 7 7 7 4 11 11 11 11 11 5 5 5

WARNINGS

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


fill_n

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

fill, fill_n - Initializes a range with a given value.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The fill and fill_n algorithms are used to assign a value to the elements in a sequence. fill assigns the value to all the elements designated by iterators in the range [first, last).

The fill_n algorithm assigns the value to all the elements designated by iterators in the range [first, first + n). fill_n assumes that there are at least n elements following first, unless first is an insert iterator.

COMPLEXITY

fill makes exactly last - first assignments, and fill_n makes exactly n assignments.

EXAMPLE

// // fill.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main() { int d1[4] = {1,2,3,4}; // // Set up two vectors // vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4); // // Set up one empty vector // vector<int> v3; // // Fill all of v1 with 9 // fill(v1.begin(),v1.end(),9);

// // Fill first 3 of v2 with 7 // fill_n(v2.begin(),3,7);

// // Use insert iterator to fill v3 with 5 11's // fill_n(back_inserter(v3),5,11); // // Copy all three to cout // ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; copy(v3.begin(),v3.end(),out); cout << endl; // // Fill cout with 3 5's // fill_n(ostream_iterator<int,char>(cout," "),3,5); cout << endl;

return 0; }

Output : 9 9 9 9 7 7 7 4 11 11 11 11 11 5 5 5

WARNINGS

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


find

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

find - Find an occurrence of value in a sequence

SYNOPSIS

#include <algorithm>

template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value);

DESCRIPTION

The find algorithm lets you search for the first occurrence of a particular value in a sequence. find returns the first iterator i in the range [first, last) for which the following condition holds:

*i == value.

If find does not find a match for value, it returns the iterator last.

COMPLEXITY

find performs at most last-first comparisons.

EXAMPLE

// // find.cpp // #include <vector> #include <algorithm>

int main() { typedef vector<int>::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7};

// Set up a vector vector<int> v1(d1,d1 + 10);

// Try find iterator it1 = find(v1.begin(),v1.end(),3); // it1 = v1.begin() + 4;

// Try find_if iterator it2 = find_if(v1.begin(),v1.end(),bind1st(equal_to<int>(),3)); // it2 = v1.begin() + 4

// Try both adjacent_find variants iterator it3 = adjacent_find(v1.begin(),v1.end()); // it3 = v1.begin() +2

iterator it4 = adjacent_find(v1.begin(),v1.end(),equal_to<int>()); // v4 = v1.begin() + 2

// Output results cout << *it1 << " " << *it2 << " " << *it3 << " " << *it4 << endl;

return 0; }

Output : 3 3 2 2

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

SEE ALSO

adjacent_find, find_first_of, find_if

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


find_end

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

find_end - Finds the last occurrence of a sub-sequence in a sequence.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template <class Forward Iterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

DESCRIPTION

The find_end algorithm finds the last occurrence of a sub-sequence, indicated by [first2, last2), in a sequence, [first1,last1). The algorithm returns an iterator pointing to the first element of the found subsequence, or last1 if no match is found.

More precisely, the find_end algorithm returns the last iterator i in the range [first1, last1 - (last2-first2)) such that for any non-negative integer n < (last2-first2), the following corresponding conditions hold:

*(i+n) == *(first2+n), pred(*(i+n),*(first2+n)) == true.

Or returns last1 if no such iterator is found.

Two versions of the algorithm exist. The first uses the equality operator as the default binary predicate, and the second allows you to specify a binary predicate.

COMPLEXITY

At most (last2-first2)*(last1-first1-(last2-first2)+1) applications of the corresponding predicate are done.

EXAMPLE

// // find_end.cpp // #include<vector> #include<iterator> #include<algorithm> #include<iostream.h>

int main() { typedef vector<int>::iterator iterator; int d1[10] = {0,1,6,5,3,2,2,6,5,7}; int d2[4] = {6,5,0,0} // // Set up two vectors. // vector<int> v1(d1+0, d1+10), v2(d2+0, d2+2); // // Try both find_first_of variants. // iterator it1 = find_first_of (v1.begin(), v1.end(), v2.begin(), v2.end()); iterator it2 = find_first_of (v1.begin(), v1.end(), v2.begin(), v2.end(), equal_to<int>()); // // Try both find_end variants. // iterator it3 = find_end (v1.begin(), v1.end(), v2.begin(), v2.end()); iterator it4 = find_end (v1.begin(), v1.end(), v2.begin(), v2.end(), equal_to<int>()); // // Output results of find_first_of. // Iterator now points to the first element that matches one of // a set of values // cout << "For the vectors: "; copy (v1.begin(), v1.end(), ostream_iterator<int>(cout," ")); cout << " and "; copy (v2.begin(), v2.end(), ostream_iterator<int>(cout," ")); cout<< endl ,, endl << "both versions of find_first_of point to: " << *it1 << endl << "with first_of address = " << it1 << endl ; // //Output results of find_end. // Iterator now points to the first element of the last find //sub-sequence. // cout << endl << endl << "both versions of find_end point to: " << *it3 << endl << "with find_end address = " << it3 << endl ;

return 0; }

Output : For the vectors: 0 1 6 5 3 2 2 6 5 7 and 6 5 both versions of find_first_of point to: 6 with first_of address = 0x100005c0 both versions of find_end point to: 6 with find_end address = 0x100005d4

WARNINGS

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int, allocator<int> >

instead of:

vector<int>

SEE ALSO

Algorithms, find, find_if, adjacent_find

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


find_first_of

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

find_first_of - Finds the first occurrence of any value from one sequence in another sequence.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The find_first_of algorithm finds a the first occurrence of a value from a sequence, specified by first2, last2, in a sequence specified by first1, last1. The algorithm returns an iterator in the range [first1, last1) that points to the first matching element. If the first sequence [first1, last1) does not contain any of the values in the second sequence, find_first_of returns last1.

In other words, find_first_of returns the first iterator i in the [first1, last1)such that for some integer j in the range [first2, last2):the following conditions hold:

*i == *j, pred(*i,*j) == true.

Or find_first_of returns last1 if no such iterator is found.

COMPLEXITY

Two versions of the algorithm exist. The first uses the equality operator as the default binary predicate, and the second allows you to specify a binary predicate.

At most (last1 - first1)*(last2 - first2) applications of the corresponding predicate are done.

EXAMPLE

// // find_f_o.cpp // #include <vector> #include <iterator> #include <algorithm> #include <iostream.h>

int main() { typedef vector<int>::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7}; int d2[2] = {6,4}; // // Set up two vectors // vector<int> v1(d1,d1 + 10), v2(d2,d2 + 2); // // Try both find_first_of variants // iterator it1 = find_first_of(v1.begin(),v1.end(),v2.begin(),v2.end()); find_first_of(v1.begin(),v1.end(),v2.begin(),v2.end(), equal_to<int>()); // // Output results // cout << "For the vectors: "; copy(v1.begin(),v1.end(), ostream_iterator<int,char>(cout," " )); cout << " and "; copy(v2.begin(),v2.end(), ostream_iterator<int,char>(cout," " )); cout << endl << endl << "both versions of find_first_of point to: " << *it1;

return 0; }

Output : For the vectors: 0 1 2 2 3 4 2 2 6 7 and 6 4 both versions of find_first_of point to: 4

WARNINGS

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int, allocator<int> >

instead of:

vector<int>

SEE ALSO

Algorithms, adjacent_find, find, find_if, find_next, find_end

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


find_if

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

find_if - Find an occurrence of value in a sequence that satisfies a specifed predicate.

SYNOPSIS

#include <algorithm>

template <class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

DESCRIPTION

The find_if algorithm allows you to search for the first element in a sequence that satisfies a particular condition. The sequence is defined by iterators first and last, while the condition is defined by the third argument: a predicate function that returns a boolean value. find_if returns the first iterator i in the range [first, last) for which the following condition holds:

pred(*i) == true.

If no such iterator is found, find_if returns last.

COMPLEXITY

find_if performs at most last-first applications of the corresponding predicate.

EXAMPLE

// // find.cpp // #include <vector> #include <algorithm> #include <iostream.h>

int main() { typedef vector<int>::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7};

// Set up a vector vector<int> v1(d1,d1 + 10);

// Try find iterator it1 = find(v1.begin(),v1.end(),3); // it1 = v1.begin() + 4;

// Try find_if iterator it2 = find_if(v1.begin(),v1.end(),bind1st(equal_to<int>(),3)); // it2 = v1.begin() + 4

// Try both adjacent_find variants iterator it3 = adjacent_find(v1.begin(),v1.end()); // it3 = v1.begin() +2

iterator it4 = adjacent_find(v1.begin(),v1.end(),equal_to<int>()); // v4 = v1.begin() + 2

// Output results cout << *it1 << " " << *it2 << " " << *it3 << " " << *it4 << endl;

return 0; }

Output : 3 3 2 2

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int, allocator<int> >

instead of:

vector<int>

SEE ALSO

adjacent_find, Algorithms, find, find_end, find_first_of

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


for_each

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

for_each - Applies a function to each element in a range.

SYNOPSIS

#include <algorithm>

template <class InputIterator, class Function> void for_each(InputIterator first, InputIterator last, Function f);

DESCRIPTION

The for_each algorithm applies function f to all members of the sequence in the range [first, last), where first and last are iterators that define the sequence. Since this a non-mutating algorithm, the function f cannot make any modifications to the sequence, but it can achieve results through side effects (such as copying or printing). If f returns a result, the result is ignored.

COMPLEXITY

The function f is applied exactly last - first times.

EXAMPLE

// // for_each.cpp // #include <vector> #include <algorithm> #include <iostream.h>

// Function class that outputs its argument times x template <class Arg> class out_times_x : private unary_function<Arg,void> { private: Arg multiplier;

public: out_times_x(const Arg& x) : multiplier(x) { } void operator()(const Arg& x) { cout << x * multiplier << " " << endl; } };

int main() { int sequence[5] = {1,2,3,4,5};

// Set up a vector vector<int> v(sequence,sequence + 5);

// Setup a function object out_times_x<int> f2(2);

for_each(v.begin(),v.end(),f2); // Apply function

return 0; }

Output : 2 4 6 8 10

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int, allocator<int> >

instead of:

vector<int>

SEE ALSO

Algorithms, function object

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


generate

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

generate, generate_n - Initialize a container with values produced by a value-generator class.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

A value-generator function returns a value each time it is invoked. The algorithms generate and generate_n initialize (or reinitialize) a sequence by assigning the return value of the generator function gen to all the elements designated by iterators in the range [first, last) or [first, first + n). The function gen takes no arguments. (gen can be a function or a class with an operator () defined that takes no arguments.)

generate_n assumes that there are at least n elements following first, unless first is an insert iterator.

COMPLEXITY

The generate and generate_n algorithms invoke gen and assign its return value exactly last - first (or n) times.

EXAMPLE

// // generate.cpp // #include <algorithm> #include <vector> #include <iostream.h>

// Value generator simply doubles the current value // and returns it template <class T> class generate_val { private: T val_; public: generate_val(const T& val) : val_(val) {} T& operator()() { val_ += val_; return val_; } };

int main() { int d1[4] = {1,2,3,4}; generate_val<int> gen(1);

// Set up two vectors vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4); // Set up one empty vector vector<int> v3;

// Generate values for all of v1 generate(v1.begin(),v1.end(),gen);

// Generate values for first 3 of v2 generate_n(v2.begin(),3,gen);

// Use insert iterator to generate 5 values for v3 generate_n(back_inserter(v3),5,gen);

// Copy all three to cout ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; copy(v3.begin(),v3.end(),out); cout << endl;

// Generate 3 values for cout generate_n(ostream_iterator<int>(cout," "),3,gen); cout << endl;

return 0; }

Output : 2 4 8 16 2 4 8 4 2 4 8 16 32 2 4 8

WARNINGS

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write:

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

function objects

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


generate_n

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

generate, generate_n - Initialize a container with values produced by a value-generator class.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

A value-generator function returns a value each time it is invoked. The algorithms generate and generate_n initialize (or reinitialize) a sequence by assigning the return value of the generator function gen to all the elements designated by iterators in the range [first, last) or [first, first + n). The function gen takes no arguments. (gen can be a function or a class with an operator () defined that takes no arguments.)

generate_n assumes that there are at least n elements following first, unless first is an insert iterator.

COMPLEXITY

The generate and generate_n algorithms invoke gen and assign its return value exactly last - first (or n) times.

EXAMPLE

// // generate.cpp // #include <algorithm> #include <vector> #include <iostream.h>

// Value generator simply doubles the current value // and returns it template <class T> class generate_val { private: T val_; public: generate_val(const T& val) : val_(val) {} T& operator()() { val_ += val_; return val_; } };

int main() { int d1[4] = {1,2,3,4}; generate_val<int> gen(1);

// Set up two vectors vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4); // Set up one empty vector vector<int> v3;

// Generate values for all of v1 generate(v1.begin(),v1.end(),gen);

// Generate values for first 3 of v2 generate_n(v2.begin(),3,gen);

// Use insert iterator to generate 5 values for v3 generate_n(back_inserter(v3),5,gen);

// Copy all three to cout ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; copy(v3.begin(),v3.end(),out); cout << endl;

// Generate 3 values for cout generate_n(ostream_iterator<int>(cout," "),3,gen); cout << endl;

return 0; }

Output : 2 4 8 16 2 4 8 4 2 4 8 16 32 2 4 8

WARNINGS

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write:

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

function objects

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


greater

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

greater - Binary function object that returns true if its first argument is greater than its second.

SYNOPSIS

#include <functional>

template <class T> struct greater : binary_function<T, T, bool> { typedef typename binary_function<T, T, bool>::second_argument_type second_argument_type; typedef typename binary_function<T, T, bool>::first_argument_type first_argument_type; typedef typename binary_function<T, T, bool>::result_type result_type; bool operator() (const T&, const T&) const; };

DESCRIPTION

greater is a binary function object. Its operator() returns true if x is greater than y. You can pass a greater object to any algorithm that requires a binary function. For example, the transform algorithm applies a binary operation to corresponding values in two collections and stores the result of the function. greater would be used in that algorithm in the following manner:

vector<int> vec1; vector<int> vec2; vector<int> vecResult; transform(vec1.begin(), vec1.end(), vec2.begin(), vecResult.begin(), greater<int>());

WARNINGS

After this call to transform, vecResult(n) will contain a "1" if vec1(n) was greater than vec2(n) or a "0" if vec1(n) was less than or equal to vec2(n).

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write :

vector<int, allocator<int> >

instead of

vector<int>

SEE ALSO

function objects

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


greater_equal

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

greater_equal - Binary function object that returns true if its first argument is greater than or equal to its second

SYNOPSIS

#include <functional>

template <class T> struct greater_equal ; : binary_function<T, T, bool> { typedef typename binary_function<T, T, bool>::second_argument_type second_argument_type; typedef typename binary_function<T, T, bool>::first_argument_type first_argument_type; typedef typename binary_function<T, T, bool>::result_type result_type; bool operator() (const T&, const T&) const; };

DESCRIPTION

greater_equal is a binary function object. Its operator() returns true if x is greater than or equal to y. You can pass a greater_equal object to any algorithm that requires a binary function. For example, the sort algorithm can accept a binary function as an alternate comparison object to sort a sequence. greater_equal would be used in that algorithm in the following manner:

vector<int> vec1; sort(vec1.begin(), vec1.end(),greater_equal<int>());

After this call to sort, vec1 will be sorted in descending order.

WARNINGS

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write :

vector<int, allocator<int> >

instead of

vector<int>

SEE ALSO

function objects

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


Heap_Operations

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

Heap_Operations

See the entries for make_heap, pop_heap, push_heap and sort_heap

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


includes

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

includes - Basic set operation for sorted sequences.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The includes algorithm compares two sorted sequences and returns true if every element in the range [first2, last2) is contained in the range [first1, last1). It returns false otherwise. include assumes that the sequences are sorted using the default comparison operator less than (<), unless an alternative comparison operator (comp) is provided.

COMPLEXITY

At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons are performed.

EXAMPLE

// // includes.cpp // #include <algorithm> #include <set> #include <iostream.h>

int main() {

//Initialize some sets int a1[10] = {1,2,3,4,5,6,7,8,9,10}; int a2[6] = {2,4,6,8,10,12}; int a3[4] = {3,5,7,8}; set<int, less<int> > all(a1, a1+10), even(a2, a2+6), small(a3,a3+4);

//Demonstrate includes cout << "The set: "; copy(all.begin(),all.end(), ostream_iterator<int,char>(cout," ")); bool answer = includes(all.begin(), all.end(), small.begin(), small.end()); cout << endl << (answer ? "INCLUDES " : "DOES NOT INCLUDE "); copy(small.begin(),small.end(), ostream_iterator<int,char>(cout," ")); answer = includes(all.begin(), all.end(), even.begin(), even.end()); cout << ", and" << endl << (answer ? "INCLUDES" : "DOES NOT INCLUDE "); copy(even.begin(),even.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl;

return 0; }

Output : The set: 1 2 3 4 5 6 7 8 9 10 INCLUDES 3 5 7 8 , and DOES NOT INCLUDE 2 4 6 8 10 12

WARNINGS

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write :

set<int, less<int>, allocator<int> >

instead of

set<int>

SEE ALSO

set, set_union, set_intersection, set_difference, set_symmetric_difference

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


inner_product

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

inner_product - Computes the inner product A X B of two ranges A and B.

SYNOPSIS

#include <numeric> template <class InputIterator1, class InputIterator2, class T> T inner_product (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); template <class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> T inner_product (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);

DESCRIPTION

There are two versions of inner_product. The first computes an inner product using the default multiplication and addition operators, while the second allows you to specify binary operations to use in place of the default operations.

The first version of the function computes its result by initializing the accumulator acc with the initial value init and then modifying it with:

acc = acc + ((*i1) * (*i2))

for every iterator i1 in the range [first1, last1) and iterator i2 in the range [first2, first2 + (last1 - first1)). The algorithm returns acc.

The second version of the function initializes acc with init, then computes the result:

acc = binary_op1(acc, binary_op2(*i1, *i2))

for every iterator i1 in the range [first1, last1) and iterator i2 in the range [first2, first2 + (last1 - first1)).

COMPLEXITY

The inner_product algorithm computes exactly (last1 - first1) applications of either:

acc + (*i1) * (*i2) or

binary_op1(acc, binary_op2(*i1, *i2)).

EXAMPLE

// // inr_prod.cpp // #include <numeric> //For inner_product #include <list> //For list #include <vector> //For vectors #include <functional> //For plus and minus #include <iostream.h> int main() { //Initialize a list and an int using arrays of ints int a1[3] = {6, -3, -2}; int a2[3] = {-2, -3, -2}; list<int> l(a1, a1+3); vector<int> v(a2, a2+3); //Calculate the inner product of the two sets of values int inner_prod = inner_product(l.begin(), l.end(), v.begin(), 0); //Calculate a wacky inner product using the same values int wacky = inner_product(l.begin(), l.end(), v.begin(), 0, plus<int>(), minus<int>()); //Print the output cout << "For the two sets of numbers: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << " and "; copy(l.begin(),l.end(),ostream_iterator<int,char>(cout," ")); cout << "," << endl << endl; cout << "The inner product is: " << inner_prod << endl; cout << "The wacky result is: " << wacky << endl; return 0; } Output : For the two sets of numbers: -2 -3 -2 and 6 -3 -2 , The inner product is: 1 The wacky result is: 8

WARNINGS

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write :

list<int, allocator<int> > and vector<int, allocator<int> >

instead of

list<int> and vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


inplace_merge

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

inplace_merge - Merge two sorted sequences into one.

SYNOPSIS

#include <algorithm> 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);

DESCRIPTION

The inplace_merge algorithm merges two sorted consecutive ranges [first, middle) and [middle, last), and puts the result of the merge into the range [first, last). The merge is stable, that is, if the two ranges contain equivalent elements, the elements from the first range always precede the elements from the second.

There are two versions of the inplace_merge algorithm. The first version uses the less than operator (operator<) as the default for comparison, and the second version accepts a third argument that specifies a comparison operator.

COMPLEXITY

When enough additional memory is available, inplace_merge does at most (last - first) - 1 comparisons. If no additional memory is available, an algorithm with O(NlogN) complexity (where N is equal to last-first) may be used.

EXAMPLE

// // merge.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main() { int d1[4] = {1,2,3,4}; int d2[8] = {11,13,15,17,12,14,16,18};

// Set up two vectors vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4);

// Set up four destination vectors vector<int> v3(d2,d2 + 8),v4(d2,d2 + 8), v5(d2,d2 + 8),v6(d2,d2 + 8); // Set up one empty vector vector<int> v7; // Merge v1 with v2 merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin()); // Now use comparator merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v4.begin(), less<int>()); // In place merge v5 vector<int>::iterator mid = v5.begin(); advance(mid,4); inplace_merge(v5.begin(),mid,v5.end()); // Now use a comparator on v6 mid = v6.begin(); advance(mid,4); inplace_merge(v6.begin(),mid,v6.end(),less<int>()); // Merge v1 and v2 to empty vector using insert iterator merge(v1.begin(),v1.end(),v2.begin(),v2.end(), back_inserter(v7)); // Copy all cout ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; copy(v3.begin(),v3.end(),out); cout << endl; copy(v4.begin(),v4.end(),out); cout << endl; copy(v5.begin(),v5.end(),out); cout << endl; copy(v6.begin(),v6.end(),out); cout << endl; copy(v7.begin(),v7.end(),out); cout << endl;

// Merge v1 and v2 to cout merge(v1.begin(),v1.end(),v2.begin(),v2.end(), ostream_iterator<int,char>(cout," ")); cout << endl; return 0; }

Output: 1 2 3 4 1 2 3 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 11 12 13 14 15 16 17 18 11 12 13 14 15 16 17 18 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4

WARNINGS

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write :

vector<int, allocator,int> >

instead of

vector<int>

SEE ALSO

merge

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


iter_swap

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

iter_swap - Exchange values pointed at in two locations

SYNOPSIS

#include <algorithm>

template <class ForwardIterator1, class ForwardIterator2> void iter_swap (ForwardIterator1, ForwardIterator2);

DESCRIPTION

The iter_swap algorithm exchanges the values pointed at by the two iterators a and b.

EXAMPLE

#include <vector> #include <algorithm> #include <iostream.h>

int main () { int d1[] = {6, 7, 8, 9, 10, 1, 2, 3, 4, 5}; // // Set up a vector. // vector<int> v(d1+0, d1+10); // // Output original vector. // cout << "For the vector: "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); // // Swap the first five elements with the last five elements. // swap_ranges(v.begin(), v.begin()+5, v.begin()+5); // // Output result. // cout << endl << endl << "Swapping the first 5 elements with the last 5 gives: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); // // Now an example of iter_swap -- swap first and last elements. // iter_swap(v.begin(), v.end()-1); // // Output result. // cout << endl << endl << "Swapping the first and last elements gives: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl;

return 0; }

Output : For the vector: 6 7 8 9 10 1 2 3 4 5 Swapping the first five elements with the last five gives: 1 2 3 4 5 6 7 8 9 10 Swapping the first and last elements gives: 10 2 3 4 5 6 7 8 9 1

WARNING

If your compiler does not support default template parameters, then you will need to always supply the Allocator template argument. For instance, you'll have to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

Iterators, swap, swap_ranges

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


lexicographical_compare

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

lexicographical_compare - Compares two ranges lexicographically.

SYNOPSIS

#include <algorithm>

template <class InputIterator1, class InputIterator2> bool lexicographical_compare(InputIterator1 first, InputIterator2 last1, InputIterator2 first2, InputIterator last2);

template <class InputIterator1, class InputIterator2, class Compare> bool lexicographical_compare(InputIterator1 first, InputIterator2 last1, InputIterator2 first2, InputIterator last2, Compare comp);

DESCRIPTION

The lexicographical_compare functions compare each element in the range [first1, last1) to the corresponding element in the range [first2, last2) using iterators i and j.

The first version of the algorithm uses operator< as the default comparison operator. It immediately returns true if it encounters any pair in which *i is less than *j, and immediately returns false if *j is less than *i. If the algorithm reaches the end of the first sequence before reaching the end of the second sequence, it also returns true.

The second version of the function takes an argument comp that defines a comparison function that is used in place of the default operator<.

The lexicographical_compare functions can be used with all the datatypes provided by the standard library.

COMPLEXITY

lexicographical_compare performs at most min((last1 - first1), (last2 - first2)) applications of the comparison function.

EXAMPLE

// // lex_comp.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main(void) { int d1[5] = {1,3,5,32,64}; int d2[5] = {1,3,2,43,56};

// set up vector vector<int> v1(d1,d1 + 5), v2(d2,d2 + 5);

// Is v1 less than v2 (I think not) bool b1 = lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end());

// Is v2 less than v1 (yup, sure is) bool b2 = lexicographical_compare(v2.begin(), v2.end(), v1.begin(), v1.end(), less<int>()); cout << (b1 ? "TRUE" : "FALSE") << " " << (b2 ? "TRUE" : "FALSE") << endl;

return 0; }

Output: FALSE TRUE

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write :

vector<int, allocator<int> >

instead of :

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


lower_bound

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

lower_bound - Determine the first valid position for an element in a sorted container.

SYNOPSIS

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);

DESCRIPTION

The lower_bound algorithm compares a supplied value to elements in a sorted container and returns the first position in the container that value can occupy without violating the container's ordering. There are two versions of the algorithm. The first uses the less than operator (operator<) to perform the comparison, and assumes that the sequence has been sorted using that operator. The second version lets you include a function object of type Compare, and assumes that Compare is the function used to sort the sequence. The function object must be a binary predicate.

lower_bound's return value is the iterator for the first element in the container that is greater than or equal to value, or, when the comparison operator is used, the first element that does not satisfy the comparison function. Formally, the algorithm returns an iterator i in the range [first, last) such that for any iterator j in the range [first, i) the following corresponding conditions hold:

*j < value

or

comp(*j, value) == true

COMPLEXITY

lower_bound performs at most log(last - first) + 1 comparisons.

EXAMPLE

// // ul_bound.cpp // #include <vector> #include <algorithm> #include <iostream.h>

int main() { typedef vector<int>::iterator iterator; int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};

// Set up a vector vector<int> v1(d1,d1 + 11);

// Try lower_bound variants iterator it1 = lower_bound(v1.begin(),v1.end(),3); // it1 = v1.begin() + 4

iterator it2 = lower_bound(v1.begin(),v1.end(),2,less<int>()); // it2 = v1.begin() + 4

// Try upper_bound variants iterator it3 = upper_bound(v1.begin(),v1.end(),3); // it3 = vector + 5

iterator it4 = upper_bound(v1.begin(),v1.end(),2,less<int>()); // it4 = v1.begin() + 5

cout << endl << endl << "The upper and lower bounds of 3: ( " << *it1 << " , " << *it3 << " ]" << endl;

cout << endl << endl << "The upper and lower bounds of 2: ( " << *it2 << " , " << *it4 << " ]" << endl;

return 0; }

Output : The upper and lower bounds of 3: ( 3 , 4 ] The upper and lower bounds of 2: ( 2 , 3 ]

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

SEE ALSO

upper_bound, equal_range

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


make_heap

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

make_heap - Creates a heap.

SYNOPSIS

#include <algorithm>

template <class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last);

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

DESCRIPTION

A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties are:

1. *a is the largest element in the range.

2. *a may be removed by the pop_heap algorithm, or a new element can be added by the push_heap algorithm, in O(logN) time.

These properties make heaps useful as priority queues.

The heap algorithms use less than (operator<) as the default comparison. In all of the algorithms, an alternate comparison operator can be specified.

The first version of the make_heap algorithm arranges the elements in the range [first, last) into a heap using less than (operator<) to perform comparisons. The second version uses the comparison operator comp to perform the comparisons. Since the only requirements for a heap are the two listed above, make_heap is not required to do anything within the range (first, last - 1).

COMPLEXITY

This algorithm makes at most 3 * (last - first) comparisons.

EXAMPLE

// // heap_ops.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4};

// Set up two vectors vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);

// Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z) // Note that x, y and z represent the remaining // values in the container (other than 4). // The definition of the heap and heap operations // does not require any particular ordering // of these values.

// Copy both vectors to cout ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// Now let's pop pop_heap(v1.begin(),v1.end()); pop_heap(v2.begin(),v2.end(),less<int>()); // v1 = (3,x,y,4) and v2 = (3,x,y,4)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// And push push_heap(v1.begin(),v1.end()); push_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// Now sort those heaps sort_heap(v1.begin(),v1.end()); sort_heap(v2.begin(),v2.end(),less<int>()); // v1 = v2 = (1,2,3,4)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

return 0; } Output : 4 2 3 1 4 3 2 1 3 2 1 4 3 1 2 4 4 3 1 2 4 3 2 1 1 2 3 4 1 2 3 4

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

SEE ALSO

pop_heap, push_heap and sort_heap

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


max

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

max - Find and return the maximum of a pair of values

SYNOPSIS

#include <algorithm>

template <class T> const T& max(const T&, const T&);

template <class T, class Compare> const T& max(const T&, const T&, Compare);

DESCRIPTION

The max algorithm determines and returns the maximum of a pair of values. The optional argument Compare defines a comparison function that can be used in place of the default operator<. This function can be used with all the datatypes provided by the standard library.

max returns the first argument when the arguments are equal.

EXAMPLE

// // max.cpp // #include <algorithm> #include <iostream.h> #include <iostream.h>

int main(void) { double d1 = 10.0, d2 = 20.0;

// Find minimum double val1 = min(d1, d2); // val1 = 10.0

// the greater comparator returns the greater of the // two values. double val2 = min(d1, d2, greater<double>()); // val2 = 20.0;

// Find maximum double val3 = max(d1, d2); // val3 = 20.0;

// the less comparator returns the smaller of the two values. // Note that, like every comparison in the STL, max is // defined in terms of the < operator, so using less here // is the same as using the max algorithm with a default // comparator. double val4 = max(d1, d2, less<double>()); // val4 = 20

cout << val1 << " " << val2 << " " << val3 << " " << val4 << endl;

return 0; }

Output : 10 20 20 20

SEE ALSO

max_element, min, min_element

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


max_element

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

max_element - Finds maximum value in a range.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator> ForwardIterator max_element(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Compare> ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);

DESCRIPTION

The max_element algorithm returns an iterator that denotes the maximum element in a sequence. If the sequence contains more than one copy of the element, the iterator points to its first occurrence. The optional argument comp defines a comparison function that can be used in place of the default operator<. This function can be used with all the datatypes provided by the standard library.

Algorithm max_element returns the first iterator i in the range [first, last) such that for any iterator j in the same range the following corresponding conditions hold:

!(*i < *j)

or

comp(*i, *j) == false.

COMPLEXITY

Exactly max((last - first) - 1, 0) applications of the corresponding comparisons are done for max_element.

EXAMPLE

// // max_elem.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main(void) { typedef vector<int>::iterator iterator; int d1[5] = {1,3,5,32,64};

// set up vector vector<int> v1(d1,d1 + 5);

// find the largest element in the vector iterator it1 = max_element(v1.begin(), v1.end()); // it1 = v1.begin() + 4

// find the largest element in the range from // the beginning of the vector to the 2nd to last iterator it2 = max_element(v1.begin(), v1.end()-1, less<int>()); // it2 = v1.begin() + 3

// find the smallest element iterator it3 = min_element(v1.begin(), v1.end()); // it3 = v1.begin()

// find the smallest value in the range from // the beginning of the vector plus 1 to the end iterator it4 = min_element(v1.begin()+1, v1.end(), less<int>()); // it4 = v1.begin() + 1

cout << *it1 << " " << *it2 << " " << *it3 << " " << *it4 << endl;

return 0; }

Output : 64 32 1 3

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

SEE ALSO

max, min, min_element

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


merge

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

merge - Merge two sorted sequences into a third sequence.

SYNOPSIS

#include <algorithm>

template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator first1, InputIterator1 last1, InputIterator2 first2, InputIterator last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator last2, OutputIterator result, Compare comp);

DESCRIPTION

The merge algorithm merges two sorted sequences, specified by [first1, last1) and [first2, last2), into the sequence specified by [result, result + (last1 - first1) + (last2 - first2)). The first version of the merge algorithm uses the less than operator (<) to compare elements in the two sequences. The second version uses the comparison function provided by the function call. If a comparison function is provided, merge assumes that both sequences were sorted using that comparison function.

The merge is stable. This means that if the two original sequences contain equivalent elements, the elements from the first sequence will always precede the matching elements from the second in the resulting sequence. The size of the result of a merge is equal to the sum of the sizes of the two argument sequences. merge returns an iterator that points to the end of the resulting sequence, i.e., result + (last1 - first1) + (last2 -first2). The result of merge is undefined if the resulting range overlaps with either of the original ranges.

merge assumes that there are at least (last1 - first1) + (last2 - first2) elements following result, unless result has been adapted by an insert iterator.

COMPLEXITY

For merge at most (last - first1) + (last2 - first2) - 1 comparisons are performed.

EXAMPLE

// // merge.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main() { int d1[4] = {1,2,3,4}; int d2[8] = {11,13,15,17,12,14,16,18};

// Set up two vectors vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4); // Set up four destination vectors vector<int> v3(d2,d2 + 8),v4(d2,d2 + 8), v5(d2,d2 + 8),v6(d2,d2 + 8); // Set up one empty vector vector<int> v7;

// Merge v1 with v2 merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin()); // Now use comparator merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v4.begin(), less<int>());

// In place merge v5 vector<int>::iterator mid = v5.begin(); advance(mid,4); inplace_merge(v5.begin(),mid,v5.end()); // Now use a comparator on v6 mid = v6.begin(); advance(mid,4); inplace_merge(v6.begin(),mid,v6.end(),less<int>());

// Merge v1 and v2 to empty vector using insert iterator merge(v1.begin(),v1.end(),v2.begin(),v2.end(), back_inserter(v7));

// Copy all cout ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; copy(v3.begin(),v3.end(),out); cout << endl; copy(v4.begin(),v4.end(),out); cout << endl; copy(v5.begin(),v5.end(),out); cout << endl; copy(v6.begin(),v6.end(),out); cout << endl; copy(v7.begin(),v7.end(),out); cout << endl;

// Merge v1 and v2 to cout merge(v1.begin(),v1.end(),v2.begin(),v2.end(), ostream_iterator<int,char>(cout," ")); cout << endl;

return 0; }

Output : 1 2 3 4 1 2 3 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 11 12 13 14 15 16 17 18 11 12 13 14 15 16 17 18 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

SEE ALSO

Containers, inplace_merge

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


min

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

min - Find and return the minimum of a pair of values

SYNOPSIS

#include <algorithm>

template <class T> const T& min(const T&, const T&);

template <class T, class Compare> const T& min(const T& a, const T&, Compare);

DESCRIPTION

The min algorithm determines and returns the minimum of a pair of values. In the second version of the algorithm, the optional argument Compare defines a comparison function that can be used in place of the default operator<. This function can be used with all the datatypes provided by the standard library.

min returns the first argument when the two arguments are equal.

EXAMPLE

// // max.cpp // #include <algorithm> #include <iostream.h>

int main(void) { double d1 = 10.0, d2 = 20.0;

// Find minimum double val1 = min(d1, d2); // val1 = 10.0

// the greater comparator returns the greater of the // two values. double val2 = min(d1, d2, greater<double>()); // val2 = 20.0;

// Find maximum double val3 = max(d1, d2); // val3 = 20.0;

// the less comparator returns the smaller of the // two values. // Note that, like every comparison in the STL, max is // defined in terms of the < operator, so using less here // is the same as using the max algorithm with a default // comparator. double val4 = max(d1, d2, less<double>()); // val4 = 20

cout << val1 << " " << val2 << " " << val3 << " " << val4 << endl;

return 0; }

Output : 10 20 20 20

SEE ALSO

max, max_element, min_element

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


min_element

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

min_element - Finds the minimum value in a range.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator> ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Compare> InputIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);

DESCRIPTION

The min_element algorithm returns an iterator that denotes the minimum element in a sequence. If the sequence contains more than one copy of the minimum element, the iterator points to the first occurrence of the element. In the second version of the function, the optional argument comp defines a comparison function that can be used in place of the default operator<. This function can be used with all the datatypes provided by the standard library.

Algorithm min_element returns the first iterator i in the range [first, last) such that for any iterator j in the range same range, the following corresponding conditions hold:

!(*j < *i)

or

comp(*j, *i) == false.

COMPLEXITY

min_element performs exactly max((last - first) - 1, 0) applications of the corresponding comparisons.

EXAMPLE

// // max_elem.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main(void) { typedef vector<int>::iterator iterator; int d1[5] = {1,3,5,32,64};

// set up vector vector<int> v1(d1,d1 + 5);

// find the largest element in the vector iterator it1 = max_element(v1.begin(), v1.end()); // it1 = v1.begin() + 4

// find the largest element in the range from // the beginning of the vector to the 2nd to last iterator it2 = max_element(v1.begin(), v1.end()-1, less<int>()); // it2 = v1.begin() + 3

// find the smallest element iterator it3 = min_element(v1.begin(), v1.end()); // it3 = v1.begin()

// find the smallest value in the range from // the beginning of the vector plus 1 to the end iterator it4 = min_element(v1.begin()+1, v1.end(), less<int>()); // it4 = v1.begin() + 1

cout << *it1 << " " << *it2 << " " << *it3 << " " << *it4 << endl;

return 0; }

Output : 64 32 1 3

WARNING

If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:

vector<int,allocator<int> >

instead of:

vector<int>

SEE ALSO

max, max_element, min

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


mismatch

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

mismatch - Compares elements from two sequences and returns the first two elements that don't match each other.

SYNOPSIS

#include <algorithm>

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(InputIterator first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);

DESCRIPTION

The mismatch algorithm compares members of two sequences and returns two iterators (i and j) that point to the first location in each sequence where the sequences differ from each other. Notice that the algorithm denotes both a starting position and an ending position for the first sequence, but denotes only a starting position for the second sequence. mismatch assumes that the second sequence has at least as many members as the first sequence. If the two sequences are identical, mismatch returns a pair of iterators that point to the end of the first sequence and the corresponding location at which the comparison stopped in the second sequence.

The first version of mismatch checks members of a sequence for equality, while the second version lets you specify a comparison function. The comparison function must be a binary predicate.

The iterators i and j returned by mismatch are defined as follows:

j == first2 + (i - first1)

and i is the first iterator in the range [first1, last1) for which the appropriate one of the following conditions hold:

!(*i == *(first2 + (i - first1)))

or

binary_pred(*i, *(first2 + (i - first1))) == false

If all of the members in the two sequences match, mismatch returns a pair of last1 and first2 + (last1 - first1).

COMPLEXITY

At most last1 - first1 applications of the corresponding predicate are done.

EXAMPLE

// // mismatch.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main(void) { typedef vector<int>::iterator iterator; int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4};

// Set up two vectors vector<int> vi1(d1,d1 + 4), vi2(d2,d2 + 4);

// p1 will contain two iterators that point to the // first pair of elements that are different between // the two vectors pair<iterator, iterator> p1 = mismatch(vi1.begin(), vi1.end(), vi2.begin());

// find the first two elements such that an element in the // first vector is greater than the element in the second // vector. pair<iterator, iterator> p2 = mismatch(vi1.begin(), vi1.end(), vi2.begin(), less_equal<int>());

// Output results cout << *p1.first << ", " << *p1.second << endl; cout << *p2.first << ", " << *p2.second << endl;

return 0; } Output : 2, 3 3, 2

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of:

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


next_permutation

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

next_permutation - Generate successive permutations of a sequence based on an ordering function.

SYNOPSIS

#include <algorithm>

template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

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

DESCRIPTION

The permutation-generating algorithms (next_permutation and prev_permutation) assume that the set of all permutations of the elements in a sequence is lexicographically sorted with respect to operator< or comp. So, for example, if a sequence includes the integers 1 2 3, that sequence has six permutations, which, in order from first to last are: 1 2 3 , 1 3 2, 2 1 3, 2 3 1, 3 1 2, and 3 2 1.

The next_permutation algorithm takes a sequence defined by the range [first, last) and transforms it into its next permutation, if possible. If such a permutation does exist, the algorithm completes the transformation and returns true. If the permutation does not exist, next_permutation returns false, and transforms the permutation into its "first" permutation (according to the lexicographical ordering defined by either operator<, the default used in the first version of the algorithm, or comp, which is user-supplied in the second version of the algorithm.)

For example, if the sequence defined by [first, last) contains the integers 3 2 1 (in that order), there is not a "next permutation." Therefore, the algorithm transforms the sequence into its first permutation (1 2 3) and returns false.

COMPLEXITY

At most (last - first)/2 swaps are performed.

EXAMPLE

// // permute.cpp // #include <numeric> //for accumulate #include <vector> //for vector #include <functional> //for less #include <iostream.h>

int main() { //Initialize a vector using an array of ints int a1[] = {0,0,0,0,1,0,0,0,0,0}; char a2[] = "abcdefghji"; //Create the initial set and copies for permuting vector<int> m1(a1, a1+10); vector<int> prev_m1((size_t)10), next_m1((size_t)10); vector<char> m2(a2, a2+10); vector<char> prev_m2((size_t)10), next_m2((size_t)10); copy(m1.begin(), m1.end(), prev_m1.begin()); copy(m1.begin(), m1.end(), next_m1.begin()); copy(m2.begin(), m2.end(), prev_m2.begin()); copy(m2.begin(), m2.end(), next_m2.begin()); //Create permutations prev_permutation(prev_m1.begin(), prev_m1.end(),less<int>()); next_permutation(next_m1.begin(), next_m1.end(),less<int>()); prev_permutation(prev_m2.begin(), prev_m2.end(),less<int>()); next_permutation(next_m2.begin(), next_m2.end(),less<int>()); //Output results cout << "Example 1: " << endl << " "; cout << "Original values: "; copy(m1.begin(),m1.end(), ostream_iterator<int,char>(cout," ")); cout << endl << " "; cout << "Previous permutation: "; copy(prev_m1.begin(),prev_m1.end(), ostream_iterator<int,char>(cout," ")); cout << endl<< " "; cout << "Next Permutation: "; copy(next_m1.begin(),next_m1.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; cout << "Example 2: " << endl << " "; cout << "Original values: "; copy(m2.begin(),m2.end(), ostream_iterator<char,char>(cout," ")); cout << endl << " "; cout << "Previous Permutation: "; copy(prev_m2.begin(),prev_m2.end(), ostream_iterator<char,char>(cout," ")); cout << endl << " "; cout << "Next Permutation: "; copy(next_m2.begin(),next_m2.end(), ostream_iterator<char,char>(cout," ")); cout << endl << endl;

return 0; }

Output : Example 1: Original values: 0 0 0 0 1 0 0 0 0 0 Previous permutation: 0 0 0 0 0 1 0 0 0 0 Next Permutation: 0 0 0 1 0 0 0 0 0 0 Example 2: Original values: a b c d e f g h j i Previous Permutation: a b c d e f g h i j Next Permutation: a b c d e f g i h j

WARNING

If your compiler does not support default template parameters, the you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

prev_permutation

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


nth_element

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

nth_element - Rearranges a collection so that all elements lower in sorted order than the nth element come before it and all elements higher in sorter order than the nth element come after it.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The nth_element algorithm rearranges a collection according to either the default comparison operator (>) or the provided comparison operator. After the algorithm applies, three things are true:

+ The element that would be in the nth position if the collection were completely sorted is in the nth position

+ All elements prior to the nth position would precede that position in an ordered collection

+ All elements following the nth position would follow that position in an ordered collection

That is, for any iterator i in the range [first, nth) and any iterator j in the range [nth, last) it holds that !(*i > *j) or comp(*i, *j) == false.

Note that the elements that precede or follow the nth position are not necessarily sorted relative to each other. The nth_element algorithm does not sort the entire collection.

COMPLEXITY

The algorithm is linear, on average, where N is the size of the range [first, last).

EXAMPLE

// // nthelem.cpp // #include <algorithm> #include <vector> #include <iostream.h>

template<class RandomAccessIterator> void quik_sort(RandomAccessIterator start, RandomAccessIterator end) { size_t dist = 0; distance(start, end, dist);

//Stop condition for recursion if(dist > 2) { //Use nth_element to do all the work for quik_sort nth_element(start, start+(dist/2), end);

//Recursive calls to each remaining unsorted portion quik_sort(start, start+(dist/2-1)); quik_sort(start+(dist/2+1), end); }

if(dist == 2 && *end < *start) swap(start, end); }

int main() { //Initialize a vector using an array of ints int arr[10] = {37, 12, 2, -5, 14, 1, 0, -1, 14, 32}; vector<int> v(arr, arr+10);

//Print the initial vector cout << "The unsorted values are: " << endl << " "; vector<int>::iterator i; for(i = v.begin(); i != v.end(); i++) cout << *i << ", "; cout << endl << endl;

//Use the new sort algorithm quik_sort(v.begin(), v.end());

//Output the sorted vector cout << "The sorted values are: " << endl << " "; for(i = v.begin(); i != v.end(); i++) cout << *i << ", "; cout << endl << endl;

return 0; }

Output : The unsorted values are: 37, 12, 2, -5, 14, 1, 0, -1, 14, 32, The sorted values are: -5, -1, 0, 1, 2, 12, 14, 14, 32, 37,

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

Algorithms

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


partial_sort

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

partial_sort - Templated algorithm for sorting collections of entities.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The partial_sort algorithm takes the range [first,last) and places the first middle - first values into sorted order. The result is that the range [first, middle)is sorted like it would be if the entire range [first,last) were sorted. The remaining elements in the range (those in [middle, last)) are not in any defined order. The first version of the algorithm uses less than (operator<) as the comparison operator for the sort. The second version uses the comparison function comp.

COMPLEXITY

partial_sort does approximately (last - first) * log(middle-first) comparisons.

EXAMPLE

// // partsort.cpp // #include <vector> #include <algorithm> #include <iostream.h>

int main() { int d1[20] = {17, 3, 5, -4, 1, 12, -10, -1, 14, 7, -6, 8, 15, -11, 2, -2, 18, 4, -3, 0}; // // Set up a vector. // vector<int> v1(d1+0, d1+20); // // Output original vector. // cout << "For the vector: "; copy(v1.begin(), v1.end(), ostream_iterator<int,char>(cout," ")); // // Partial sort the first seven elements. // partial_sort(v1.begin(), v1.begin()+7, v1.end()); // // Output result. // cout << endl << endl << "A partial_sort of seven elements gives: " << endl << " "; copy(v1.begin(), v1.end(), ostream_iterator<int,char>(cout," ")); cout << endl; // // A vector of ten elements. // vector<int> v2(10, 0); // // Sort the last ten elements in v1 into v2. // partial_sort_copy(v1.begin()+10, v1.end(), v2.begin(), v2.end()); // // Output result. // cout << endl << "A partial_sort_copy of the last ten elements gives: " << endl << " "; copy(v2.begin(), v2.end(), ostream_iterator<int,char>(cout," ")); cout << endl;

return 0; }

Output : For the vector: 17 3 5 -4 1 12 -10 -1 14 7 -6 8 15 -11 2 -2 18 4 -3 0 A partial_sort of seven elements gives: -11 -10 -6 -4 -3 -2 -1 17 14 12 7 8 15 5 3 2 18 4 1 0 A partial_sort_copy of the last ten elements gives: 0 1 2 3 4 5 7 8 15 18

WARNING

If your compiler does not support default template parameters, then you need to always provide the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

sort, stable_sort, partial_sort_copy

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


partial_sort_copy

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

partial_sort_copy - Templated algorithm for sorting collections of entities.

SYNOPSIS

#include <algorithm>

template <class InputIterator, class RandomAccessIterator> void partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template <class InputIterator, class RandomAccessIterator, class Compare> void partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

DESCRIPTION

The partial_sort_copy algorithm places the smaller of last - first and result_last - result_first sorted elements from the range [first, last) into the range beginning at result_first. (i.e., the range: [result_first, result_first+min(last - first, result_last - result_first)). Basically, the effect is as if the range [first,last) were placed in a temporary buffer, sorted and then as many elements as possible were copied into the range [result_first, result_last).

The first version of the algorithm uses less than (operator<) as the comparison operator for the sort. The second version uses the comparison function comp.

COMPLEXITY

partial_sort_copy does approximately (last-first) * log(min(last-first, result_last-result_first)) comparisons.

EXAMPLE

// // partsort.cpp // #include <vector> #include <algorithm> #include <iostream.h> int main() { int d1[20] = {17, 3, 5, -4, 1, 12, -10, -1, 14, 7, -6, 8, 15, -11, 2, -2, 18, 4, -3, 0}; // // Set up a vector. // vector<int> v1(d1+0, d1+20); // // Output original vector. // cout << "For the vector: "; copy(v1.begin(), v1.end(), ostream_iterator<int>(cout," ")); // // Partial sort the first seven elements. // partial_sort(v1.begin(), v1.begin()+7, v1.end()); // // Output result. // cout << endl << endl << "A partial_sort of 7 elements gives: " << endl << " "; copy(v1.begin(), v1.end(), ostream_iterator<int,char>(cout," ")); cout << endl; // // A vector of ten elements. // vector<int> v2(10, 0); // // Sort the last ten elements in v1 into v2. // partial_sort_copy(v1.begin()+10, v1.end(), v2.begin(), v2.end()); // // Output result. // cout << endl << "A partial_sort_copy of the last ten elements gives: " << endl << " "; copy(v2.begin(), v2.end(), ostream_iterator<int,char>(cout," ")); cout << endl; return 0; } Output : For the vector: 17 3 5 -4 1 12 -10 -1 14 7 -6 8 15 -11 2 -2 18 4 -3 0 A partial_sort of seven elements gives: -11 -10 -6 -4 -3 -2 -1 17 14 12 7 8 15 5 3 2 18 4 1 0 A partial_sort_copy of the last ten elements gives: 0 1 2 3 4 5 7 8 15 18

WARNING

If your compiler does not support default template parameters, then you need to always provide the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

sort_ stable_sort, partial_sort

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


partial_sum

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

partial_sum - Calculates successive partial sums of a range of values.

SYNOPSIS

#include <numeric>

template <class InputIterator, class OutputIterator> OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result);

template <class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);

DESCRIPTION

The partial_sum algorithm creates a new sequence in which every element is formed by adding all the values of the previous elements, or, in the second form of the algorithm, applying the operation binary_op successively on every previous element. That is, partial_sum assigns to every iterator i in the range [result, result + (last - first)) a value equal to:

((...(*first + *(first + 1)) + ... ) + *(first + (i - result)))

or, in the second version of the algorithm:

binary_op(binary_op(..., binary_op (*first, *(first + 1)),...),*(first + (i - result)))

For instance, applying partial_sum to (1,2,3,4,) will yield (1,3,6,10).

The partial_sum algorithm returns result + (last - first).

If result is equal to first, the elements of the new sequence successively replace the elements in the original sequence, effectively turning partial_sum into an inplace transformation.

COMPLEXITY

Exactly (last - first) - 1 applications of the default + operator or binary_op are performed.

EXAMPLE

// // partsum.cpp // #include <numeric> //for accumulate #include <vector> //for vector #include <functional> //for times #include <iostream.h>

int main() { //Initialize a vector using an array of ints int d1[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(d1, d1+10);

//Create an empty vectors to store results vector<int> sums((size_t)10), prods((size_t)10);

//Compute partial_sums and partial_products partial_sum(v.begin(), v.end(), sums.begin()); partial_sum(v.begin(), v.end(), prods.begin(), times<int>());

//Output the results cout << "For the series: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

cout << "The partial sums: " << endl << " " ; copy(sums.begin(),sums.end(), ostream_iterator<int,char>(cout," ")); cout <<" should each equal (N*N + N)/2" << endl << endl;

cout << "The partial products: " << endl << " "; copy(prods.begin(),prods.end(), ostream_iterator<int,char>(cout," ")); cout << " should each equal N!" << endl;

return 0; }

Output : For the series: 1 2 3 4 5 6 7 8 9 10

The partial sums: 1 3 6 10 15 21 28 36 45 55 should each equal (N*N + N)/2 The partial products: 1 2 6 24 120 720 5040 40320 362880 3628800 should each equal N!

WARNING

If your compiler does not support default template parameters, then you need to always provide the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


partition

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

partition - Places all of the entities that satisfy the given predicate before all of the entities that do not.

SYNOPSIS

#include <algorithm>

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

DESCRIPTION

The partition algorithm places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy pred. It returns an iterator that is one past the end of the group of elements that satisfy pred. In other words, partition returns i such that for any itera- tor j in the range[first, i), pred(*j) == true, and, for any iterator k in the range [i, last), pred(*j) == false.

Note that partition does not necessarily maintain the relative order of the elements that match and elements that do not match the predicate. Use the algorithm stable_partition if relative order is important.

COMPLEXITY

The partition algorithm does at most (last - first)/2 swaps, and applies the predicate exactly last - first times.

EXAMPLE

// // prtition.cpp // #include <functional> #include <deque> #include <algorithm> #include <iostream.h>

// // Create a new predicate from unary_function. // template<class Arg> class is_even : public unary_function<Arg, bool> { public: bool operator()(const Arg& arg1) { return (arg1 % 2) == 0; } };

int main () { // // Initialize a deque with an array of integers. // int init[10] = { 1,2,3,4,5,6,7,8,9,10 }; deque<int> d1(init+0, init+10); deque<int> d2(init+0, init+10); // // Print out the original values. // cout << "Unpartitioned values: " << ""; copy(d1.begin(), d1.end(), ostream_iterator<int,char>(cout," ")); cout << endl; // // A partition of the deque according to even/oddness. // partition(d2.begin(), d2.end(), is_even<int>()); // // Output result of partition. // cout << "Partitioned values: " << ""; copy(d2.begin(), d2.end(), ostream_iterator<int,char>(cout," ")); cout << endl; // // A stable partition of the deque according to even/oddness. // stable_partition(d1.begin(), d1.end(), is_even<int>()); // // Output result of partition. // cout << "Stable partitioned values: " << ""; copy(d1.begin(), d1.end(), ostream_iterator<int,char>(cout," ")); cout << endl;

return 0; }

Output : Unpartitioned values: 1 2 3 4 5 6 7 8 9 10 Partitioned values: 10 2 8 4 6 5 7 3 9 1 Stable partitioned values: 2 4 6 8 10 1 3 5 7 9

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you need to write :

deque<int, allocator<int> >

instead of :

deque<int>

SEE ALSO

stable_partition

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


permutation

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

permutation - Generate successive permutations of a sequence based on an ordering function.

See the entries for next_permutation and prev_permutation.

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


pop_heap

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

pop_heap - Moves the largest element off the heap.

SYNOPSIS

template <class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

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

DESCRIPTION

A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties are:

1. *a is the largest element in the range.

2. *a may be removed by the pop_heap algorithm or a new element added by the push_heap algorithm, in O(logN) time.

These properties make heaps useful as priority queues.

The pop_heap algorithm uses the less than (<) operator as the default comparison. An alternate comparison operator can be specified.

The pop_heap algorithm can be used as part of an operation to remove the largest element from a heap. It assumes that the range [first, last) is a valid heap (i.e., that first is the largest element in the heap or the first element based on the alternate comparison operator). It then swaps the value in the location first with the value in the location last - 1 and makes [first, last -1)back into a heap. You can then access the element in last using the vector or deque back() member function, or remove the element using the pop_back member function. Note that pop_heap does not actually remove the element from the data structure, you must use another function to do that.

COMPLEXITY

pop_heap performs at most 2 * log(last - first) comparisons.

EXAMPLE

// // heap_ops.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4};

// Set up two vectors vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);

// Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z) // Note that x, y and z represent the remaining // values in the container (other than 4). // The definition of the heap and heap operations // does not require any particular ordering // of these values.

// Copy both vectors to cout ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// Now let's pop pop_heap(v1.begin(),v1.end()); pop_heap(v2.begin(),v2.end(),less<int>()); // v1 = (3,x,y,4) and v2 = (3,x,y,4)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// And push push_heap(v1.begin(),v1.end()); push_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// Now sort those heaps sort_heap(v1.begin(),v1.end()); sort_heap(v2.begin(),v2.end(),less<int>()); // v1 = v2 = (1,2,3,4)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

return 0; }

Output : 4 2 3 1 4 3 2 1 3 2 1 4 3 1 2 4 4 3 1 2 4 3 2 1 1 2 3 4 1 2 3 4

WARNING

If your compiler does not support default template parameters, you need to always supply the Allocator template argument. For instance, you need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

make_heap, push_heap, sort_heap

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


prev_permutation

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

prev_permutation - Generate successive permutations of a sequence based on an ordering function.

SYNOPSIS

#include <algorithm>

template <class BidirectionalIterator> bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last);

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

DESCRIPTION

The permutation-generating algorithms (next_permutation and prev_permutation) assume that the set of all permutations of the elements in a sequence is lexicographically sorted with respect to operator< or comp. So, for example, if a sequence includes the integers 1 2 3, that sequence has six permutations, which, in order from first to last, are: 1 2 3 , 1 3 2, 2 1 3, 2 3 1, 3 1 2, and 3 2 1.

The prev_permutation algorithm takes a sequence defined by the range [first, last) and transforms it into its previous permutation, if possible. If such a permutation does exist, the algorithm completes the transformation and returns true. If the permutation does not exist, prev_permutation returns false, and transforms the permutation into its "last" permutation (according to the lexicographical ordering defined by either operator <, the default used in the first version of the algorithm, or comp, which is user-supplied in the second version of the algorithm.)

For example, if the sequence defined by [first, last) contains the integers 1 2 3 (in that order), there is not a "previous permutation." Therefore, the algorithm transforms the sequence into its last permutation (3 2 1) and returns false.

COMPLEXITY

At most (last - first)/2 swaps are performed.

EXAMPLE

// // permute.cpp // #include <numeric> //for accumulate #include <vector> //for vector #include <functional> //for less #include <iostream.h>

int main() { //Initialize a vector using an array of ints int a1[] = {0,0,0,0,1,0,0,0,0,0}; char a2[] = "abcdefghji";

//Create the initial set and copies for permuting vector<int> m1(a1, a1+10); vector<int> prev_m1((size_t)10), next_m1((size_t)10); vector<char> m2(a2, a2+10); vector<char> prev_m2((size_t)10), next_m2((size_t)10);

copy(m1.begin(), m1.end(), prev_m1.begin()); copy(m1.begin(), m1.end(), next_m1.begin()); copy(m2.begin(), m2.end(), prev_m2.begin()); copy(m2.begin(), m2.end(), next_m2.begin());

//Create permutations prev_permutation(prev_m1.begin(), prev_m1.end(),less<int>()); next_permutation(next_m1.begin(), next_m1.end(),less<int>()); prev_permutation(prev_m2.begin(), prev_m2.end(),less<int>()); next_permutation(next_m2.begin(), next_m2.end(),less<int>()); //Output results cout << "Example 1: " << endl << " "; cout << "Original values: "; copy(m1.begin(),m1.end(), ostream_iterator<int,char>(cout," ")); cout << endl << " "; cout << "Previous permutation: "; copy(prev_m1.begin(),prev_m1.end(), ostream_iterator<int,char>(cout," "));

cout << endl<< " "; cout << "Next Permutation: "; copy(next_m1.begin(),next_m1.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl;

cout << "Example 2: " << endl << " "; cout << "Original values: "; copy(m2.begin(),m2.end(), ostream_iterator<char,char>(cout," ")); cout << endl << " "; cout << "Previous Permutation: "; copy(prev_m2.begin(),prev_m2.end(), ostream_iterator<char,char>(cout," ")); cout << endl << " ";

cout << "Next Permutation: "; copy(next_m2.begin(),next_m2.end(), ostream_iterator<char,char>(cout," ")); cout << endl << endl;

return 0; }

Output : Example 1: Original values: 0 0 0 0 1 0 0 0 0 0 Previous permutation: 0 0 0 0 0 1 0 0 0 0 Next Permutation: 0 0 0 1 0 0 0 0 0 0 Example 2: Original values: a b c d e f g h j i Previous Permutation: a b c d e f g h i j Next Permutation: a b c d e f g i h j

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

next_permutation

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


push_heap

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

push_heap - Places a new element into a heap.

SYNOPSIS

#include <algorithm>

template <class RandomAccessIterator> void push_heap(RandomAccessIterator first, RandomAccessIterator last);

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

DESCRIPTION

A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties are:

1. *a is the largest element in the range.

2. *a may be removed by the pop_heap algorithm, or a new element added by the push_heap algorithm, in O(logN) time.

These properties make heaps useful as priority queues.

The push_heap algorithms uses the less than (<) operator as the default comparison. As with all of the heap manipulation algorithms, an alternate comparison function can be specified.

The push_heap algorithm is used to add a new element to the heap. First, a new element for the heap is added to the end of a range. (For example, you can use the vector or deque member function push_back()to add the element to the end of either of those containers.) The push_heap algorithm assumes that the range [first, last - 1) is a valid heap. It then properly posi- tions the element in the location last - 1 into its proper position in the heap, resulting in a heap over the range [first, last).

Note that the push_heap algorithm does not place an element into the heap's underlying container. You must user another function to add the element to the end of the container before applying push_heap.

COMPLEXITY

For push_heap at most log(last - first) comparisons are performed.

EXAMPLE

// // heap_ops.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4};

// Set up two vectors vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);

// Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z) // Note that x, y and z represent the remaining // values in the container (other than 4). // The definition of the heap and heap operations // does not require any particular ordering // of these values.

// Copy both vectors to cout ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// Now let's pop pop_heap(v1.begin(),v1.end()); pop_heap(v2.begin(),v2.end(),less<int>()); // v1 = (3,x,y,4) and v2 = (3,x,y,4)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// And push push_heap(v1.begin(),v1.end()); push_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// Now sort those heaps sort_heap(v1.begin(),v1.end()); sort_heap(v2.begin(),v2.end(),less<int>()); // v1 = v2 = (1,2,3,4)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

return 0; }

Output : 4 2 3 1 4 3 2 1 3 2 1 4 3 1 2 4 4 3 1 2 4 3 2 1 1 2 3 4 1 2 3 4

WARNING

If your compiler does not support default template parameters, you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

make_heap, pop_heap, sort_heap

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


random_shuffle

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

random_shuffle - Randomly shuffles elements of a collection.

SYNOPSIS

#include <algorithm>

template <class RandomAccessIterator> void random_shuffle (RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle (RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);

DESCRIPTION

The random_shuffle algorithm shuffles the elements in the range [first, last) with uniform distribution. random_shuffle can take a particular random number generating function object rand , where rand takes a positive argument n of distance type of the RandomAccessIterator and returns a randomly chosen value between 0 and n - 1.

COMPLEXITY

In the random_shuffle algorithm, (last - first) -1 swaps are done.

EXAMPLE

// // rndshufl.cpp // #include <algorithm> #include <vector> #include <iostream.h> int main() { //Initialize a vector with an array of ints int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr, arr+10); //Print out elements in original (sorted) order cout << "Elements before random_shuffle: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; //Mix them up with random_shuffle random_shuffle(v.begin(), v.end()); //Print out the mixed up elements cout << "Elements after random_shuffle: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl;

return 0; }

Output : Elements before random_shuffle: 1 2 3 4 5 6 7 8 9 10 Elements after random_shuffle: 7 9 10 3 2 5 4 8 1 6

WARNING

If your compiler does not support default template parameters, you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


remove

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

remove - Move desired elements to the front of a container, and return an iterator that describes where the sequence of desired elements ends.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator, class T> ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& value);

DESCRIPTION

The remove algorithm eliminates all the elements referred to by iterator i in the range [first, last) for which the following condition holds: *i == value. remove returns an iterator that designates the end of the resulting range. remove is stable, that is, the relative order of the elements that are not removed is the same as their relative order in the original range.

remove does not actually reduce the size of the sequence. It actually operates by: 1) copying the values that are to be retained to the front of the sequence, and 2) returning an iterator that describes where the sequence of retained values ends. Elements that are after this iterator are simply the original sequence values, left unchanged. Here's a simple example:

Say we want to remove all values of "2" from the following sequence:

354621271

Applying the remove algorithm results in the following sequence:

3546171|XX

The vertical bar represents the position of the iterator returned by remove. Note that the elements to the left of the vertical bar are the original sequence with the "2's" removed.

If you want to actually delete items from the container, use the following technique:

container.erase(remove(first,last,value),container.end());

COMPLEXITY

Exactly last1 - first1 applications of the corresponding predicate are done.

EXAMPLE

// // remove.cpp // #include <algorithm> #include <vector> #include <iterator> #include <iostream.h> template<class Arg> struct all_true : public unary_function<Arg, bool> { bool operator()(const Arg& x){ return 1; } }; int main () { int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr, arr+10); copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // remove the 7 vector<int>::iterator result = remove(v.begin(), v.end(), 7); // delete dangling elements from the vector v.erase(result, v.end()); copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // remove everything beyond the fourth element result = remove_if(v.begin()+4, v.begin()+8, all_true<int>()); // delete dangling elements v.erase(result, v.end()); copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; return 0; } Output : 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 8 9 10 1 2 3 4 1 2 4

WARNING

If your compiler does not support default template parameters, you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

remove_if, remove_copy, remove_copy_if

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


remove_copy

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

remove_copy - Move desired elements to the front of a container, and return an iterator that describes where the sequence of desired elements ends.

SYNOPSIS

#include <algorithm>

template <class InputIterator, class OutputIterator, class T> OutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, const T& value);

DESCRIPTION

The remove_copy algorithm copies all the elements referred to by the iterator i in the range [first, last) for which the following corresponding condition does not hold: *i == value. remove_copy returns the end of the resulting range. remove_copy is stable, that is, the relative order of the elements in the resulting range is the same as their relative order in the original range. The elements in the original sequence are not altered by remove_copy.

COMPLEXITY

Exactly last1 - first1 applications of the corresponding predicate are done.

EXAMPLE

// // remove.cpp // #include <algorithm> #include <vector> #include <iterator> #include <iostream.h>

template<class Arg> struct all_true : public unary_function<Arg, bool> { bool operator() (const Arg&) { return 1; } };

int main () { int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr+0, arr+10);

copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Remove the 7. // vector<int>::iterator result = remove(v.begin(), v.end(), 7); // // Delete dangling elements from the vector. // v.erase(result, v.end());

copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Remove everything beyond the fourth element. // result = remove_if(v.begin()+4, v.begin()+8, all_true<int>()); // // Delete dangling elements. // v.erase(result, v.end());

copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Now remove all 3s on output. // remove_copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "), 3); cout << endl << endl; // // Now remove everything satisfying predicate on output. // Should yield a NULL vector. // remove_copy_if(v.begin(), v.end(), ostream_iterator<int,char>(cout," "), all_true<int>());

return 0; }

Output : 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 8 9 10 1 2 3 4 1 2 4

WARNING

If your compiler does not support default template parameters, you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

remove, remove_if, remove_copy_if

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


remove_copy_if

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

remove_copy_if - Move desired elements to the front of a container, and return an iterator that describes where the sequence of desired elements ends.

SYNOPSIS

#include <algorithm>

template <class InputIterator, class OutputIterator, class Predicate> OutputIterator remove_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

DESCRIPTION

The remove_copy_if algorithm copies all the elements referred to by the iterator i in the range [first, last) for which the following condition does not hold: pred(*i) == true. remove_copy_if returns the end of the resulting range. remove_copy_if is stable, that is, the relative order of the elements in the resulting range is the same as their relative order in the original range.

COMPLEXITY

Exactly last1 - first1 applications of the corresponding predicate are done.

EXAMPLE

// // remove.cpp // #include <algorithm> #include <vector> #include <iterator> #include <iostream.h>

template<class Arg> struct all_true : public unary_function<Arg, bool> { bool operator() (const Arg&) { return 1; } };

int main () { int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr+0, arr+10);

copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Remove the 7. // vector<int>::iterator result = remove(v.begin(), v.end(), 7); // // Delete dangling elements from the vector. // v.erase(result, v.end());

copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Remove everything beyond the fourth element. // result = remove_if(v.begin()+4, v.begin()+8, all_true<int>()); // // Delete dangling elements. // v.erase(result, v.end());

copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Now remove all 3s on output. // remove_copy(v.begin(), v.end(), ostream_iterator<int>(cout," "), 3); cout << endl << endl; // // Now remove everything satisfying predicate on output. // Should yield a NULL vector. // remove_copy_if(v.begin(), v.end(), ostream_iterator<int,char>(cout," "), all_true<int>());

return 0; } Output : 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 8 9 10 1 2 3 4 1 2 4

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

remove, remove_if, remove_copy

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


remove_if

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

remove_if - Move desired elements to the front of a container, and return an iterator that describes where the sequence of desired elements ends.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator, class Predicate> ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, Predicate pred);

DESCRIPTION

The remove_if algorithm eliminates all the elements referred to by iterator i in the range [first, last) for which the following corresponding condition holds: pred(*i) == true. remove_if returns the end of the resulting range. remove_if is stable, that is, the relative order of the elements that are not removed is the same as their relative order in the original range.

remove_if does not actually reduce the size of the sequence. It actually operates by: 1) copying the values that are to be retained to the front of the sequence, and 2) returning an iterator that describes where the sequence of retained values ends. Elements that are after this iterator are simply the original sequence values, left unchanged. Here's a simple example:

Say we want to remove all even numbers from the following sequence:

123456789

Applying the remove_if algorithm results in the following sequence:

13579|XXXX

The vertical bar represents the position of the iterator returned by remove_if. Note that the elements to the left of the vertical bar are the original sequence with the even numbers removed. The elements to the right of the bar are simply the untouched original members of the original sequence.

If you want to actually delete items from the container, use the following technique:

container.erase(remove(first,last,value),container.end());

COMPLEXITY

Exactly last1 - first1 applications of the corresponding predicate are done.

EXAMPLE

// // remove.cpp // #include <algorithm> #include <vector> #include <iterator> #include <iostream.h> template<class Arg> struct all_true : public unary_function<Arg, bool> { bool operator()(const Arg& x){ return 1; } }; int main () { int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr, arr+10); copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // remove the 7 vector<int>::iterator result = remove(v.begin(), v.end(), 7); // delete dangling elements from the vector v.erase(result, v.end()); copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; // remove everything beyond the fourth element result = remove_if(v.begin()+4, v.begin()+8, all_true<int>()); // delete dangling elements v.erase(result, v.end()); copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl; return 0; } Output : 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 8 9 10 1 2 3 4 1 2 4

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

remove, remove_copy, remove_copy_if

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


replace

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

replace - Substitutes elements stored in a collection with new values.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator, class T> void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

DESCRIPTION

The replace algorithm replaces elements referred to by iterator i in the range [first, last) with new_value when the following condition holds: *i == old_value

COMPLEXITY

Exactly last - first comparisons or applications of the corresponding predicate are done.

EXAMPLE

// // replace.cpp // #include <algorithm> #include <vector> #include <iterator> #include <iostream.h>

template<class Arg> struct all_true : public unary_function<Arg, bool> { bool operator()(const Arg&){ return 1; } };

int main() {

//Initialize a vector with an array of integers int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr, arr+10);

//Print out original vector cout << "The original list: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

//Replace the number 7 with 11 replace(v.begin(), v.end(), 7, 11);

// Print out vector with 7 replaced, // s.b. 1 2 3 4 5 6 11 8 9 10 cout << "List after replace " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

//Replace 1 2 3 with 13 13 13 replace_if(v.begin(), v.begin()+3, all_true<int>(), 13);

// Print out the remaining vector, // s.b. 13 13 13 4 5 6 11 8 9 10 cout << "List after replace_if " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

return 0; }

Output : The original list: 1 2 3 4 5 6 7 8 9 10 List after replace: 1 2 3 4 5 6 11 8 9 10 List after replace_if: 13 13 13 4 5 6 11 8 9 10 List using replace_copy to cout: 17 17 17 4 5 6 11 8 9 10 List with all elements output as 19s: 19 19 19 19 19 19 19 19 19 19

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

replace_if, replace_copy, replace_copy_if

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


replace_copy

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

replace_copy - Substitutes elements stored in a collection with new values.

SYNOPSIS

#include <algorithm>

template <class InputIterator, class OutputIterator, class T> OutputIterator replace_copy (InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);

DESCRIPTION

The replace_copy algorithm leaves the original sequence intact and places the revised sequence into result. The algorithm compares elements referred to by iterator i in the range [first, last) with old_value. If *i does not equal old_value, then the replace_copy copies *i to result+(first-i). If *i==old_value, then replace_copy copies new_value to result+(first-i). replace_copy returns result+(last-first).

COMPLEXITY

Exactly last - first comparisons between values are done.

EXAMPLE

// // replace.cpp // #include <algorithm> #include <vector> #include <iterator> #include <iostream.h>

template<class Arg> struct all_true : public unary_function<Arg, bool> { bool operator() (const Arg&) { return 1; } };

int main () { // // Initialize a vector with an array of integers. // int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; vector<int> v(arr+0, arr+10); // // Print out original vector. // cout << "The original list: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Replace the number 7 with 11. // replace(v.begin(), v.end(), 7, 11); // // Print out vector with 7 replaced. // cout << "List after replace:" << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Replace 1 2 3 with 13 13 13. // replace_if(v.begin(), v.begin()+3, all_true<int>(), 13); // // Print out the remaining vector. // cout << "List after replace_if:" << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Replace those 13s with 17s on output. // cout << "List using replace_copy to cout:" << endl << " "; replace_copy(v.begin(), v.end(), ostream_iterator<int,char>(cout, " "), 13, 17); cout << endl << endl; // // A simple example of replace_copy_if. // cout << "List w/ all elements output as 19s:" << endl << " "; replace_copy_if(v.begin(), v.end(), ostream_iterator<int,char>(cout, " "), all_true<int>(), 19); cout << endl;

return 0; } Output : The original list: 1 2 3 4 5 6 7 8 9 10 List after replace: 1 2 3 4 5 6 11 8 9 10 List after replace_if: 13 13 13 4 5 6 11 8 9 10 List using replace_copy to cout: 17 17 17 4 5 6 11 8 9 10 List with all elements output as 19s: 19 19 19 19 19 19 19 19 19 19

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

replace, replace_if, replace_copy_if

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


replace_copy_if

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

replace_copy_if - Substitutes elements stored in a collection with new values.

SYNOPSIS

#include <algorithm> template <class InputIterator, class OutputIterator, class Predicate, class T> OutputIterator replace_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);

DESCRIPTION

The replace_copy_if algorithm leaves the original sequence intact and places a revised sequence into result. The algorithm compares each element *i in the range [first,last) with the conditions specified by pred. If pred(*i)==false, replace_copy_if copies *i to result+(first-i). If pred(*i)==true, then replace_copy copies new_value to result+(first-i). replace_copy_if returns result+(last-first).

COMPLEXITY

Exactly last - first applications of the predicate are performed.

EXAMPLE

// // replace.cpp // #include <algorithm> #include <vector> #include <iterator> #include <iostream.h>

template<class Arg> struct all_true : public unary_function<Arg, bool> { bool operator() (const Arg&) { return 1; } };

int main () { // // Initialize a vector with an array of integers. // int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; vector<int> v(arr+0, arr+10); // // Print out original vector. // cout << "The original list: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Replace the number 7 with 11. // replace(v.begin(), v.end(), 7, 11); // // Print out vector with 7 replaced. // cout << "List after replace:" << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Replace 1 2 3 with 13 13 13. // replace_if(v.begin(), v.begin()+3, all_true<int>(), 13); // // Print out the remaining vector. // cout << "List after replace_if:" << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Replace those 13s with 17s on output. // cout << "List using replace_copy to cout:" << endl << " "; replace_copy(v.begin(), v.end(), ostream_iterator<int,char>(cout, " "), 13, 17); cout << endl << endl; // // A simple example of replace_copy_if. // cout << "List w/ all elements output as 19s:" << endl << " "; replace_copy_if(v.begin(), v.end(), ostream_iterator<int,char>(cout, " "), all_true<int>(), 19); cout << endl;

return 0; } Output : The original list: 1 2 3 4 5 6 7 8 9 10 List after replace: 1 2 3 4 5 6 11 8 9 10 List after replace_if: 13 13 13 4 5 6 11 8 9 10 List using replace_copy to cout: 17 17 17 4 5 6 11 8 9 10 List with all elements output as 19s: 19 19 19 19 19 19 19 19 19 19

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

replace, replace_if, replace_copy

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


replace_if

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

replace_if - Substitutes elements stored in a collection with new values.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator, class Predicate, class T> void replace_if (ForwardIterator first, ForwardIterator last, Predicate pred const T& new_value);

DESCRIPTION

The replace_if algorithm replaces element referred to by iterator i in the range [first, last) with new_value when the following condition holds: pred(*i) == true.

COMPLEXITY

Exactly last - first applications of the predicate are done.

EXAMPLE

// // replace.cpp // #include <algorithm> #include <vector> #include <iterator> #include <iostream.h>

template<class Arg> struct all_true : public unary_function<Arg, bool> { bool operator()(const Arg&){ return 1; } };

int main() {

//Initialize a vector with an array of integers int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr, arr+10);

//Print out original vector cout << "The original list: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

//Replace the number 7 with 11 replace(v.begin(), v.end(), 7, 11);

// Print out vector with 7 replaced, // s.b. 1 2 3 4 5 6 11 8 9 10 cout << "List after replace " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

//Replace 1 2 3 with 13 13 13 replace_if(v.begin(), v.begin()+3, all_true<int>(), 13);

// Print out the remaining vector, // s.b. 13 13 13 4 5 6 11 8 9 10 cout << "List after replace_if " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

return 0; }

Output : The original list: 1 2 3 4 5 6 7 8 9 10 List after replace: 1 2 3 4 5 6 11 8 9 10 List after replace_if: 13 13 13 4 5 6 11 8 9 10 List using replace_copy to cout: 17 17 17 4 5 6 11 8 9 10 List with all elements output as 19s: 19 19 19 19 19 19 19 19 19 19

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

replace, replace_copy, replace_copy_if

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


reverse

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

reverse - Reverse the order of elements in a collection.

SYNOPSIS

#include <algorithm>

template <class BidirectionalIterator> void reverse (BidirectionalIterator first, BidirectionalIterator last);

DESCRIPTION

The algorithm reverse reverses the elements in a sequence so that the last element becomes the new first element, and the first element becomes the new last. For each non-negative integer i <= (last - first)/2 , reverse applies swap to all pairs of iterators first + I, (last - I) - 1.

Because the iterators are assumed to be bidirectional, reverse does not return anything.

COMPLEXITY

reverse performs exactly (last - first)/2 swaps.

EXAMPLE

// // reverse.cpp // #include <algorithm> #include <vector> #include <iostream.h> int main() { //Initialize a vector with an array of ints int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr, arr+10);

//Print out elements in original (sorted) order cout << "Elements before reverse: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

//Reverse the ordering reverse(v.begin(), v.end());

//Print out the reversed elements cout << "Elements after reverse: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl;

return 0; }

Output : Elements before reverse: 1 2 3 4 5 6 7 8 9 10 Elements after reverse: 10 9 8 7 6 5 4 3 2 1 A reverse_copy to cout: 1 2 3 4 5 6 7 8 9 10

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

reverse_copy, swap

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


reverse_copy

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

reverse_copy - Reverse the order of elements in a collection while copying them to a new collecton.

SYNOPSIS

#include <algorithm>

template <class BidirectionalIterator, class OutputIterator> OutputIterator reverse_copy (BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

DESCRIPTION

The reverse_copy algorithm copies the range [first, last) to the range [result, result + (last - first)) such that for any non-negative integer i < (last - first), the following assignment takes place:

*(result + (last - first) -i) = *(first + i)

reverse_copy returns result + (last - first). The ranges [first, last) and [result, result + (last - first)) must not overlap.

COMPLEXITY

reverse_copy performs exactly (last - first) assignments.

EXAMPLE

// // reverse.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main () { // // Initialize a vector with an array of integers. // int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; vector<int> v(arr+0, arr+10); // // Print out elements in original (sorted) order. // cout << "Elements before reverse: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl; // // Reverse the ordering. // reverse(v.begin(), v.end()); // // Print out the reversed elements. // cout << "Elements after reverse: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," ")); cout << endl << endl;

cout << "A reverse_copy to cout: " << endl << " "; reverse_copy(v.begin(), v.end(), ostream_iterator<int,char>(cout, " ")); cout << endl;

return 0; }

Output : Elements before reverse: 1 2 3 4 5 6 7 8 9 10 Elements after reverse: 10 9 8 7 6 5 4 3 2 1 A reverse_copy to cout: 1 2 3 4 5 6 7 8 9 10

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

reverse

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


rotate

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

rotate, rotate_copy - Left rotates the order of items in a collection, placing the first item at the end, second item first, etc., until the item pointed to by a specified iterator is the first item in the collection.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The rotate algorithm takes three iterator arguments, first, which defines the start of a sequence, last, which defines the end of the sequence, and middle which defines a point within the sequence. rotate "swaps" the segment that contains elements from first through middle-1 with the segment that contains the elements from middle through last. After rotate has been applied, the element that was in position middle, is in position first, and the other elements in that segment are in the same order relative to each other. Similarly, the element that was in position first is now in position last-middle +1. An example will illustrate how rotate works:

Say that we have the sequence:

2 4 6 8 1 3 5

If we call rotate with middle = 5, the two segments are

2 4 6 8 and 1 3 5

After we apply rotate, the new sequence will be:

1 3 5 2 4 6 8

Note that the element that was in the fifth position is now in the first position, and the element that was in the first position is in position 4 (last - first + 1, or 8 - 5 +1 =4).

The formal description of this algorithms is: for each non-negative integer i < (last - first), rotate places the element from the position first + i into position first + (i + (last - middle)) % (last - first). [first, middle) and [middle, last) are valid ranges.

rotate_copy rotates the elements as described above, but instead of swapping elements within the same sequence, it copies the result of the rotation to a container specified by result. rotate_copy copies the range [first, last) to the range [result, result + (last - first)) such that for each non-negative integer i < (last - first) the following assignment takes place:

*(result + (i + (last - middle)) % (last -first)) = *(first + i).

The ranges [first, last) and [result, result, + (last - first)) may not overlap.

COMPLEXITY

For rotate at most last - first swaps are performed.

For rotate_copy last - first assignments are performed.

EXAMPLE

// // rotate // #include <algorithm> #include <vector> #include <iostream.h>

int main() { //Initialize a vector with an array of ints int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr, arr+10);

//Print out elements in original (sorted) order cout << "Elements before rotate: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

//Rotate the elements rotate(v.begin(), v.begin()+4, v.end());

//Print out the rotated elements cout << "Elements after rotate: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl;

return 0; }

Output : Elements before rotate: 1 2 3 4 5 6 7 8 9 10 Elements after rotate: 5 6 7 8 9 10 1 2 3 4

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


rotate_copy

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

rotate, rotate_copy - Left rotates the order of items in a collection, placing the first item at the end, second item first, etc., until the item pointed to by a specified iterator is the first item in the collection.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The rotate algorithm takes three iterator arguments, first, which defines the start of a sequence, last, which defines the end of the sequence, and middle which defines a point within the sequence. rotate "swaps" the segment that contains elements from first through middle-1 with the segment that contains the elements from middle through last. After rotate has been applied, the element that was in position middle, is in position first, and the other elements in that segment are in the same order relative to each other. Similarly, the element that was in position first is now in position last-middle +1. An example will illustrate how rotate works:

Say that we have the sequence:

2 4 6 8 1 3 5

If we call rotate with middle = 5, the two segments are

2 4 6 8 and 1 3 5

After we apply rotate, the new sequence will be:

1 3 5 2 4 6 8

Note that the element that was in the fifth position is now in the first position, and the element that was in the first position is in position 4 (last - first + 1, or 8 - 5 +1 =4).

The formal description of this algorithms is: for each non-negative integer i < (last - first), rotate places the element from the position first + i into position first + (i + (last - middle)) % (last - first). [first, middle) and [middle, last) are valid ranges.

rotate_copy rotates the elements as described above, but instead of swapping elements within the same sequence, it copies the result of the rotation to a container specified by result. rotate_copy copies the range [first, last) to the range [result, result + (last - first)) such that for each non-negative integer i < (last - first) the following assignment takes place:

*(result + (i + (last - middle)) % (last -first)) = *(first + i).

The ranges [first, last) and [result, result, + (last - first)) may not overlap.

COMPLEXITY

For rotate at most last - first swaps are performed.

For rotate_copy last - first assignments are performed.

EXAMPLE

// // rotate // #include <algorithm> #include <vector> #include <iostream.h>

int main() { //Initialize a vector with an array of ints int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector<int> v(arr, arr+10);

//Print out elements in original (sorted) order cout << "Elements before rotate: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

//Rotate the elements rotate(v.begin(), v.begin()+4, v.end());

//Print out the rotated elements cout << "Elements after rotate: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); cout << endl;

return 0; }

Output : Elements before rotate: 1 2 3 4 5 6 7 8 9 10 Elements after rotate: 5 6 7 8 9 10 1 2 3 4

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


search

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

search, search_n - Finds a sub-sequence within a sequence of values that is element-wise equal to the values in an indicated range.

SYNOPSIS

#include <algorithm>

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 binary_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> ForwardIterator search_n (ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred)

DESCRIPTION

The search and search_n are used for searching for a sub-sequence within a sequence. The search algorithm searches for a sub-sequence [first2, last2) within a sequence [first1, last1), and returns the beginning location of the sub-sequence. If it does not find the sub-sequence, search returns last1. The first version of search uses the equality (==) operator as a default, and the second version allows you to specify a binary predicate to perform the comparison.

The search_n algorithm searches for the sub-sequence composed of count occurrences of value within a sequence [first, last), and returns first if this sub-sequence is found. If it does not find the sub-sequence, search_n returns last. The first version of search_n uses the equality (==) operator as a default, and the second version allows you to specify a binary predicate to perform the comparison.

COMPLEXITY

search performs at most (last1 - first1)*(last2-first2) applications of the corresponding predicate.

search_n performs at most (last - first) applications of the corresponding predicate.

EXAMPLE

// // search.cpp // #include <algorithm> #include <list> #include <iostream.h>

int main() { // Initialize a list sequence and // sub-sequence with characters char seq[40] = "Here's a string with a substring in it"; char subseq[10] = "substring"; list<char> sequence(seq, seq+39); list<char> subseqnc(subseq, subseq+9);

//Print out the original sequence cout << endl << "The sub-sequence, " << subseq << ", was found at the "; cout << endl << "location identified by a '*'" << endl << " ";

// Create an iterator to identify the location of // sub-sequence within sequence list<char>::iterator place;

//Do search place = search(sequence.begin(), sequence.end(), subseqnc.begin(), subseqnc.end());

//Identify result by marking first character with a '*' *place = '*';

//Output sequence to display result for(list<char>::iterator i = sequence.begin(); i != sequence.end(); i++) cout << *i; cout << endl;

return 0; }

Output : The sub-sequence, substring, was found at the location identified by a '*' Here's a string with a *substring in it

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

list<char, allocator<char> >

instead of :

list<char>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


search_n

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

search, search_n - Finds a sub-sequence within a sequence of values that is element-wise equal to the values in an indicated range.

SYNOPSIS

#include <algorithm>

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 binary_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> ForwardIterator search_n (ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred)

DESCRIPTION

The search and search_n are used for searching for a sub-sequence within a sequence. The search algorithm searches for a sub-sequence [first2, last2) within a sequence [first1, last1), and returns the beginning location of the sub-sequence. If it does not find the sub-sequence, search returns last1. The first version of search uses the equality (==) operator as a default, and the second version allows you to specify a binary predicate to perform the comparison.

The search_n algorithm searches for the sub-sequence composed of count occurrences of value within a sequence [first, last), and returns first if this sub-sequence is found. If it does not find the sub-sequence, search_n returns last. The first version of search_n uses the equality (==) operator as a default, and the second version allows you to specify a binary predicate to perform the comparison.

COMPLEXITY

search performs at most (last1 - first1)*(last2-first2) applications of the corresponding predicate.

search_n performs at most (last - first) applications of the corresponding predicate.

EXAMPLE

// // search.cpp // #include <algorithm> #include <list> #include <iostream.h>

int main() { // Initialize a list sequence and // sub-sequence with characters char seq[40] = "Here's a string with a substring in it"; char subseq[10] = "substring"; list<char> sequence(seq, seq+39); list<char> subseqnc(subseq, subseq+9);

//Print out the original sequence cout << endl << "The sub-sequence, " << subseq << ", was found at the "; cout << endl << "location identified by a '*'" << endl << " ";

// Create an iterator to identify the location of // sub-sequence within sequence list<char>::iterator place;

//Do search place = search(sequence.begin(), sequence.end(), subseqnc.begin(), subseqnc.end());

//Identify result by marking first character with a '*' *place = '*';

//Output sequence to display result for(list<char>::iterator i = sequence.begin(); i != sequence.end(); i++) cout << *i; cout << endl;

return 0; }

Output : The sub-sequence, substring, was found at the location identified by a '*' Here's a string with a *substring in it

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

list<char, allocator<char> >

instead of :

list<char>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


set_difference

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

set_difference - Basic set operation for sorted sequences.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The set_difference algorithm constructs a sorted difference that includes copies of the elements that are present in the range [first1, last1) but are not present in the range [first2, last2). It returns the end of the constructed range.

As an example, assume we have the following two sets:

1 2 3 4 5

and

3 4 5 6 7

The result of applying set_difference is the set:

1 2

The result of set_difference is undefined if the result range overlaps with either of the original ranges.

set_difference assumes that the ranges are sorted using the default comparison operator less than (<), unless an alternative comparison operator (comp) is provided.

Use the set_symetric_difference algorithm to return a result that contains all elements that are not in common between the two sets.

COMPLEXITY

At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons are performed.

EXAMPLE

// // set_diff.cpp // #include <algorithm> #include <set> #include <iostream.h> int main() { //Initialize some sets int a1[10] = {1,2,3,4,5,6,7,8,9,10}; int a2[6] = {2,4,6,8,10,12}; set<int, less<int> > all(a1, a1+10), even(a2, a2+6), odd; //Create an insert_iterator for odd insert_iterator<set<int, less<int> > > odd_ins(odd, odd.begin());

//Demonstrate set_difference cout << "The result of:" << endl << "{"; copy(all.begin(),all.end(), ostream_iterator<int,char>(cout," ")); cout << "} - {"; copy(even.begin(),even.end(), ostream_iterator<int,char>(cout," ")); cout << "} =" << endl << "{"; set_difference(all.begin(), all.end(), even.begin(), even.end(), odd_ins); copy(odd.begin(),odd.end(), ostream_iterator<int,char>(cout," ")); cout << "}" << endl << endl; return 0; } Output : The result of: {1 2 3 4 5 6 7 8 9 10 } - {2 4 6 8 10 12 } = {1 3 5 7 9 }

WARNING

If your compiler does not support default template parameters, then you need to always supply the Compare template argument and the Allocator template argument. For instance, you will need to write :

set<int, less<int> allocator<int> >

instead of :

set<int>

SEE ALSO

includes, set, set_union, set_intersection, set_symmetric_difference

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


set_intersection

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

set_intersection - Basic set operation for sorted sequences.

SYNOPSIS

#include <algorithm>

template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator 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);

DESCRIPTION

The set_intersection algorithm constructs a sorted intersection of elements from the two ranges. It returns the end of the constructed range. When it finds an element present in both ranges, set_intersection always copies the element from the first range into result. This means that the result of set_intersection is guaranteed to be stable. The result of set_intersection is undefined if the result range overlaps with either of the original ranges.

set_intersection assumes that the ranges are sorted using the default comparison operator less than (<), unless an alternative comparison operator (comp) is provided.

COMPLEXITY

At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons are per- formed.

EXAMPLE

// // set_intr.cpp // #include <algorithm> #include <set> #include <iostream.h> int main() {

//Initialize some sets int a1[10] = {1,3,5,7,9,11}; int a3[4] = {3,5,7,8}; set<int, less<int> > odd(a1, a1+6), result, small(a3,a3+4);

//Create an insert_iterator for result insert_iterator<set<int, less<int> > > res_ins(result, result.begin());

//Demonstrate set_intersection cout << "The result of:" << endl << "{"; copy(small.begin(),small.end(), ostream_iterator<int,char>(cout," ")); cout << "} intersection {"; copy(odd.begin(),odd.end(), ostream_iterator<int,char>(cout," ")); cout << "} =" << endl << "{"; set_intersection(small.begin(), small.end(), odd.begin(), odd.end(), res_ins); copy(result.begin(),result.end(), ostream_iterator<int,char>(cout," ")); cout << "}" << endl << endl;

return 0; }

Output : The result of: {3 5 7 8 } intersection {1 3 5 7 9 11 } = {3 5 7 }

WARNING

If your compiler does not support default template parameters, then you need to always supply the Compare template argument and the Allocator template argument. For instance, you will need to write :

set<int, less<int> allocator<int> >

instead of :

set<int>

SEE ALSO

includes, set, set_union, set_difference, set_symmetric_difference

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


set_symmetric_difference

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

set_symmetric_difference - Basic set operation for sorted sequences.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

set_symmetric_difference constructs a sorted symmetric difference of the elements from the two ranges. This means that the constructed range includes copies of the elements that are present in the range [first1, last1) but not present in the range [first2, last2)and copies of the elements that are present in the range [first2, last2) but not in the range [first1, last1). It returns the end of the constructed range.

For example, suppose we have two sets:

1 2 3 4 5

and

3 4 5 6 7

The set_symmetric_difference of these two sets is:

1 2 6 7

The result of set_symmetric_difference is undefined if the result range overlaps with either of the original ranges.

set_symmetric_difference assumes that the ranges are sorted using the default comparison operator less than (<), unless an alternative comparison operator (comp) is provided.

Use the set_symmetric_difference algorithm to return a result that includes elements that are present in the first set and not in the second.

COMPLEXITY

At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons are performed.

EXAMPLE

// // set_s_di.cpp // #include<algorithm> #include<set> #include <istream.h>

int main() {

//Initialize some sets int a1[] = {1,3,5,7,9,11}; int a3[] = {3,5,7,8}; set<int, less<int> > odd(a1,a1+6), result, small(a3,a3+4);

//Create an insert_iterator for result insert_iterator<set<int, less<int> > > res_ins(result, result.begin());

//Demonstrate set_symmetric_difference cout << "The symmetric difference of:" << endl << "{"; copy(small.begin(),small.end(), ostream_iterator<int,char>(cout," ")); cout << "} with {"; copy(odd.begin(),odd.end(), ostream_iterator<int,char>(cout," ")); cout << "} =" << endl << "{"; set_symmetric_difference(small.begin(), small.end(), odd.begin(), odd.end(), res_ins); copy(result.begin(),result.end(), ostream_iterator<int,char>(cout," ")); cout << "}" << endl << endl;

return 0; }

Output : The symmetric difference of: {3 5 7 8 } with {1 3 5 7 9 11 } = {1 8 9 11 }

WARNING

If your compiler does not support default template parameters, then you need to always supply the Compare template argument and the Allocator template argument. For instance, you will need to write :

set<int, less<int>, allocator<int> >

instead of :

set<int>

SEE ALSO

includes, set, set_union, set_intersection, set_difference

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


set_union

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

set_union - Basic set operation for sorted sequences.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The set_union algorithm constructs a sorted union of the elements from the two ranges. It returns the end of the constructed range. set_union is stable, that is, if an element is present in both ranges, the one from the first range is copied. The result of set_union is undefined if the result range overlaps with either of the original ranges. Note that set_union does not merge the two sorted sequences. If an element is present in both sequences, only the element from the first sequence is copied to result. (Use the merge algorithm to create an ordered merge of two sorted sequences that contains all the elements from both sequences.)

set_union assumes that the sequences are sorted using the default comparison operator less than (<), unless an alternative comparison operator (comp) is provided.

COMPLEXITY

At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons are performed.

EXAMPLE

// // set_unin.cpp // #include <algorithm> #include <set> #include <iostream.h>

int main() {

//Initialize some sets int a2[6] = {2,4,6,8,10,12}; int a3[4] = {3,5,7,8}; set<int, less<int> > even(a2, a2+6), result, small(a3,a3+4);

//Create an insert_iterator for result insert_iterator<set<int, less<int> > > res_ins(result, result.begin());

//Demonstrate set_union cout << "The result of:" << endl << "{"; copy(small.begin(),small.end(), ostream_iterator<int,char>(cout," ")); cout << "} union {"; copy(even.begin(),even.end(), ostream_iterator<int,char>(cout," ")); cout << "} =" << endl << "{"; set_union(small.begin(), small.end(), even.begin(), even.end(), res_ins); copy(result.begin(),result.end(), ostream_iterator<int,char>(cout," ")); cout << "}" << endl << endl;

return 0; }

Output : The result of: {3 5 7 8 } union {2 4 6 8 10 12 } = {2 3 4 5 6 7 8 10 12 }

WARNING

If your compiler does not support default template parameters, then you need to always supply the Compare template argument and the Allocator template argument. For instance, you will need to write :

set<int, less<int>, allocator<int> >

instead of :

set<int>

SEE ALSO

includes, set, set_intersection, set_difference, set_symmetric_difference

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


sort

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

sort - Templated algorithm for sorting collections of entities.

SYNOPSIS

#include <algorithm>

template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

DESCRIPTION

The sort algorithm sorts the elements in the range [first, last) using either the less than (<) operator or the comparison operator comp. If the worst case behavior is important stable_sort or partial_sort should be used.

COMPLEXITY

sort performs approximately NlogN, where N equals last - first, comparis- ons on the average.

EXAMPLE

// // sort.cpp // #include <vector> #include <algorithm> #include <functional> #include <iostream.h>

struct associate { int num; char chr;

associate(int n, char c) : num(n), chr(c){}; associate() : num(0), chr(' '){}; };

bool operator<(const associate &x, const associate &y) { return x.num < y.num; }

ostream& operator<<(ostream &s, const associate &x) { return s << "<" << x.num << ";" << x.chr << ">"; }

int main () { vector<associate>::iterator i, j, k;

associate arr[20] = {associate(-4, ' '), associate(16, ' '), associate(17, ' '), associate(-3, 's'), associate(14, ' '), associate(-6, ' '), associate(-1, ' '), associate(-3, 't'), associate(23, ' '), associate(-3, 'a'), associate(-2, ' '), associate(-7, ' '), associate(-3, 'b'), associate(-8, ' '), associate(11, ' '), associate(-3, 'l'), associate(15, ' '), associate(-5, ' '), associate(-3, 'e'), associate(15, ' ')};

// Set up vectors vector<associate> v(arr, arr+20), v1((size_t)20), v2((size_t)20);

// Copy original vector to vectors #1 and #2 copy(v.begin(), v.end(), v1.begin()); copy(v.begin(), v.end(), v2.begin());

// Sort vector #1 sort(v1.begin(), v1.end());

// Stable sort vector #2 stable_sort(v2.begin(), v2.end());

// Display the results cout << "Original sort stable_sort" << endl; for(i = v.begin(), j = v1.begin(), k = v2.begin(); i != v.end(); i++, j++, k++) cout << *i << " " << *j << " " << *k << endl;

return 0; }

Output : Original sort stable_sort <-4; > <-8; > <-8; > <16; > <-7; > <-7; > <17; > <-6; > <-6; > <-3;s> <-5; > <-5; > <14; > <-4; > <-4; > <-6; > <-3;e> <-3;s> <-1; > <-3;s> <-3;t> <-3;t> <-3;l> <-3;a> <23; > <-3;t> <-3;b> <-3;a> <-3;b> <-3;l> <-2; > <-3;a> <-3;e> <-7; > <-2; > <-2; > <-3;b> <-1; > <-1; > <-8; > <11; > <11; > <11; > <14; > <14; > <-3;l> <15; > <15; > <15; > <15; > <15; > <-5; > <16; > <16; > <-3;e> <17; > <17; > <15; > <23; > <23; >

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

stable_sort, partial_sort, partial_sort_copy

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


sort_heap

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

sort_heap - Converts a heap into a sorted collection.

SYNOPSIS

#include <algorithm>

template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

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

DESCRIPTION

A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties are:

1. *a is the largest element in the range.

2. *a may be removed by pop_heap(), or a new element added by push_heap(), in O(logN) time.

These properties make heaps useful as priority queues.

The sort_heap algorithm converts a heap into a sorted collection over the range [first, last) using either the default operator (<) or the comparison function supplied with the algorithm. Note that sort_heap is not stable, i.e., the elements may not be in the same relative order after sort_heap is applied.

COMPLEXITY

sort_heap performs at most NlogN comparisons where N is equal to last - first.

EXAMPLE

// // heap_ops.cpp // #include <algorithm> #include <vector> #include <iostream.h>

int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4};

// Set up two vectors vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);

// Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z) // Note that x, y and z represent the remaining // values in the container (other than 4). // The definition of the heap and heap operations // does not require any particular ordering // of these values.

// Copy both vectors to cout ostream_iterator<int,char> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// Now let's pop pop_heap(v1.begin(),v1.end()); pop_heap(v2.begin(),v2.end(),less<int>()); // v1 = (3,x,y,4) and v2 = (3,x,y,4)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// And push push_heap(v1.begin(),v1.end()); push_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

// Now sort those heaps sort_heap(v1.begin(),v1.end()); sort_heap(v2.begin(),v2.end(),less<int>()); // v1 = v2 = (1,2,3,4)

// Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl;

return 0; }

Output : 4 2 3 1 4 3 2 1 3 2 1 4 3 1 2 4 4 3 1 2 4 3 2 1 1 2 3 4 1 2 3 4

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

make_heap, pop_heap, push_heap

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


stable_partition

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

stable_partition - Places all of the entities that satisfy the given predicate before all of the entities that do not, while maintaining the relative order of elements in each group.

SYNOPSIS

#include <algorithm>

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

DESCRIPTION

The stable_partition algorithm places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it. It returns an iterator i that is one past the end of the group of elements that satisfy pred. In other words stable_partition returns i such that for any iterator j in the range [first, i), pred(*j) == true, and for any iterator k in the range [i, last), pred(*j) == false. The relative order of the elements in both groups is preserved.

The partition algorithm can be used when it is not necessary to maintain the relative order of elements within the groups that do and do not match the predicate.

COMPLEXITY

The stable_partition algorithm does at most (last - first) * log(last - first) swaps. and applies the predicate exactly last - first times.

EXAMPLE

// // prtition.cpp // #include <functional> #include <deque> #include <algorithm> #include <iostream.h>

//Create a new predicate from unary_function template<class Arg> class is_even : public unary_function<Arg, bool> { public: bool operator()(const Arg& arg1) { return (arg1 % 2) == 0; } };

int main() { //Initialize a deque with an array of ints int init[10] = {1,2,3,4,5,6,7,8,9,10}; deque<int> d(init, init+10);

//Print out the original values cout << "Unpartitioned values: " << endl << " "; copy(d.begin(),d.end(),ostream_iterator<int,char>(cout," ")); cout << endl << endl;

//Partition the deque according to even/oddness stable_partition(d.begin(), d.end(), is_even<int>());

//Output result of partition cout << "Partitioned values: " << endl << " "; copy(d.begin(),d.end(),ostream_iterator<int,char>(cout," "));

return 0; }

Output : Unpartitioned values: 1 2 3 4 5 6 7 8 9 10 Partitioned values: 10 2 8 4 6 5 7 3 9 1 Stable partitioned values: 2 4 6 8 10 1 3 5 7 9

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

deque<int, allocator<int> >

instead of :

deque<int>

SEE ALSO

partition

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


stable_sort

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

stable_sort - Templated algorithm for sorting collections of entities.

SYNOPSIS

#include <algorithm>

template <class RandomAccessIterator> void stable_sort (RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare> void stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

DESCRIPTION

The stable_sort algorithm sorts the elements in the range [first, last). The first version of the algorithm uses less than (<) as the comparison operator for the sort. The second version uses the comparison function comp.

The stable_sort algorithm is considered stable because the relative order of the equal elements is preserved.

COMPLEXITY

stable_sort does at most N(logN) **2, where N equals last -first, comparisons; if enough extra memory is available, it is NlogN.

EXAMPLE

// // sort.cpp // #include <vector> #include <algorithm> #include <functional> #include <iostream.h>

struct associate { int num; char chr;

associate(int n, char c) : num(n), chr(c){}; associate() : num(0), chr(' '){}; };

bool operator<(const associate &x, const associate &y) { return x.num < y.num; }

ostream& operator<<(ostream &s, const associate &x) { return s << "<" << x.num << ";" << x.chr << ">"; }

int main () { vector<associate>::iterator i, j, k;

associate arr[20] = {associate(-4, ' '), associate(16, ' '), associate(17, ' '), associate(-3, 's'), associate(14, ' '), associate(-6, ' '), associate(-1, ' '), associate(-3, 't'), associate(23, ' '), associate(-3, 'a'), associate(-2, ' '), associate(-7, ' '), associate(-3, 'b'), associate(-8, ' '), associate(11, ' '), associate(-3, 'l'), associate(15, ' '), associate(-5, ' '), associate(-3, 'e'), associate(15, ' ')};

// Set up vectors vector<associate> v(arr, arr+20), v1((size_t)20), v2((size_t)20);

// Copy original vector to vectors #1 and #2 copy(v.begin(), v.end(), v1.begin()); copy(v.begin(), v.end(), v2.begin());

// Sort vector #1 sort(v1.begin(), v1.end());

// Stable sort vector #2 stable_sort(v2.begin(), v2.end());

// Display the results cout << "Original sort stable_sort" << endl; for(i = v.begin(), j = v1.begin(), k = v2.begin(); i != v.end(); i++, j++, k++) cout << *i << " " << *j << " " << *k << endl;

return 0; }

Output : Original sort stable_sort <-4; > <-8; > <-8; > <16; > <-7; > <-7; > <17; > <-6; > <-6; > <-3;s> <-5; > <-5; > <14; > <-4; > <-4; > <-6; > <-3;e> <-3;s> <-1; > <-3;s> <-3;t> <-3;t> <-3;l> <-3;a> <23; > <-3;t> <-3;b> <-3;a> <-3;b> <-3;l> <-2; > <-3;a> <-3;e> <-7; > <-2; > <-2; > <-3;b> <-1; > <-1; > <-8; > <11; > <11; > <11; > <14; > <14; > <-3;l> <15; > <15; > <15; > <15; > <15; > <-5; > <16; > <16; > <-3;e> <17; > <17; > <15; > <23; > <23; >

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator>

instead of :

vector<int>

SEE ALSO

sort, partial_sort, partial_sort_copy

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


swap

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

swap - Exchange values.

SYNOPSIS

#include <algorithm>

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

DESCRIPTION

The swap algorithm exchanges the values of a and b. The effect is:

T tmp = a a = b b = tmp

SEE ALSO

iter_swap, swap_ranges

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


swap_ranges

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

swap_ranges - Exchange a range of values in one location with those in another

SYNOPSIS

#include <algorithm>

template <class ForwardIterator1, class ForwardIterator2> ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);

DESCRIPTION

The swap_ranges algorithm exchanges corresponding values in two ranges, in the following manner:

For each non-negative integer n < (last - first) the function exchanges *(first1 + n) with *(first2 + n)). After completing all exchanges, swap_ranges returns an iterator that points to the end of the second container, i.e., first2 + (last1 -first1). The result of swap_ranges is undefined if the two ranges [first, last) and [first2, first2 + (last1 - first1)) overlap.

EXAMPLE

// // swap.cpp // #include <vector> #include <algorithm>

int main() { int d1[] = {6, 7, 8, 9, 10, 1, 2, 3, 4, 5};

// Set up a vector vector<int> v(d1,d1 + 10);

// Output original vector cout << "For the vector: "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));

// Swap the first five elements with the last five elements swap_ranges(v.begin(),v.begin()+5, v.begin()+5);

// Output result cout << endl << endl << "Swapping the first five elements " << "with the last five gives: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));

return 0; }

Output : For the vector: 6 7 8 9 10 1 2 3 4 5 Swapping the first five elements with the last five gives: 1 2 3 4 5 6 7 8 9 10 Swapping the first and last elements gives: 10 2 3 4 5 6 7 8 9 1

WARNING

If your compiler does not support default template parameters, you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

iter_swap, swap

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


transform

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

transform - Applies an operation to a range of values in a collection and stores the result.

SYNOPSIS

#include <algorithm>

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);

DESCRIPTION

The transform algorithm has two forms. The first form applies unary operation op to each element of the range [first, last), and sends the result to the output iterator result. For example, this version of transform, could be used to square each element in a vector. If the output iterator (result) is the same as the input iterator used to traverse the range, transform, performs its transformation in place.

The second form of transform applies a binary operation, binary_op, to corresponding elements in the range [first1, last1) and the range that begins at first2, and sends the result to result. For example, transform can be used to add corresponding elements in two sequences, and store the set of sums in a third. The algorithm assumes, but does not check, that the second sequence has at least as many elements as the first sequence. Note that the output iterator result can be a third sequence, or either of the two input sequences.

Formally, transform assigns through every iterator i in the range [result, result + (last1 - first1)) a new corresponding value equal to:

op(*(first1 + (i - result))

or

binary_op(*(first1 + (i - result), *(first2 + (i - result)))

transform returns result + (last1 - first1). op and binary_op must not have any side effects. result may be equal to first in case of unary transform, or to first1 or first2 in case of binary transform.

COMPLEXITY

Exactly last1 - first1 applications of op or binary_op are performed.

EXAMPLE

// // trnsform.cpp // #include <functional> #include <deque> #include <algorithm> #include <iostream.h> #include <iomanip.h> int main() { //Initialize a deque with an array of ints int arr1[5] = {99, 264, 126, 330, 132}; int arr2[5] = {280, 105, 220, 84, 210}; deque<int> d1(arr1, arr1+5), d2(arr2, arr2+5); //Print the original values cout << "The following pairs of numbers: " << endl << " "; deque<int>::iterator i1; for(i1 = d1.begin(); i1 != d1.end(); i1++) cout << setw(6) << *i1 << " "; cout << endl << " "; for(i1 = d2.begin(); i1 != d2.end(); i1++) cout << setw(6) << *i1 << " "; // Transform the numbers in the deque to their // factorials and store in the vector transform(d1.begin(), d1.end(), d2.begin(), d1.begin(), multiplies<int>()); //Display the results cout << endl << endl; cout << "Have the products: " << endl << " "; for(i1 = d1.begin(); i1 != d1.end(); i1++) cout << setw(6) << *i1 << " "; return 0; }

Output : The following pairs of numbers: 99 264 126 330 132 280 105 220 84 210 Have the products: 27720 27720 27720 27720 27720

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

deque<int, allocator<int> >

instead of:

deque<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


uninitialized_copy

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

uninitialized_copy - An algorithms that uses construct to copy values from one range to another location.

SYNOPSIS

#include <memory>

template <class InputIterator, class ForwardIterator> ForwardIterator uninitialized_copy (InputIterator first, InputIterator last, ForwardIterator result);

DESCRIPTION

uninitialized_copy copies all items in the range [first, last) into the location beginning at result using the construct algorithm.

SEE ALSO

construct

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


uninitialized_fill

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

uninitialized_fill - Algorithm that uses the construct algorithm for setting values in a collection.

SYNOPSIS

#include <memory>

template <class ForwardIterator, class T> void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

DESCRIPTION

uninitialized_fill initializes all of the items in the range [first, last) to the value x, using the construct algorithm.

SEE ALSO

construct, uninitialized_fill_n

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


uninitialized_fill_n

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

uninitialized_fill_n - Algorithm that uses the construct algorithm for setting values in a collection.

SYNOPSIS

#include <memory>

template <class ForwardIterator, class Size, class T> void uninitialized_fill_n (ForwardIterator first, Size n, const T& x);

DESCRIPTION

unitialized_fill_n starts at the iterator first and initializes the first n items to the value x, using the construct algorithm.

SEE ALSO

construct, uninitialized_fill

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


unique

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

unique, unique_copy - Removes consecutive duplicates from a range of values and places the resulting unique values into the result.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator> ForwardIterator unique (ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate> ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_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 binary_pred);

DESCRIPTION

The unique algorithm moves through a sequence and eliminates all but the first element from every consecutive group of equal elements. There are two versions of the algorithm, one tests for equality, and the other tests whether a binary predicate applied to adjacent elements is true. An element is unique if it does not meet the corresponding condition listed here:

*i == *(i - 1)

or

binary_pred(*i, *(i - 1)) == true.

If an element is unique, it is copied to the front of the sequence, overwriting the existing elements. Once all unique elements have been identified. The remainder of the sequence is left unchanged, and unique returns the end of the resulting range.

The unique_copy algorithm copies the first element from every consecutive group of equal elements, to an OutputIterator. The unique_copy algorithm, also has two versions--one that tests for equality and a second that tests adjacent elements against a binary predicate.

unique_copy returns the end of the resulting range.

COMPLEXITY

Exactly (last - first) - 1 applications of the corresponding predicate are performed.

EXAMPLE

// // unique.cpp // #include <algorithm> #include <vector> #include <iostream.h> int main() { //Initialize two vectors int a1[20] = {4, 5, 5, 9, -1, -1, -1, 3, 7, 5, 5, 5, 6, 7, 7, 7, 4, 2, 1, 1}; vector<int> v(a1, a1+20), result; //Create an insert_iterator for results insert_iterator<vector<int> > ins(result, result.begin()); //Demonstrate includes cout << "The vector: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); //Find the unique elements unique_copy(v.begin(), v.end(), ins); //Display the results cout << endl << endl << "Has the following unique elements:" << endl << " "; copy(result.begin(),result.end(), ostream_iterator<int,char>(cout," ")); return 0; } Output : The vector: 4 5 5 9 -1 -1 -1 3 7 5 5 5 6 7 7 7 4 2 1 1 Has the following unique elements: 4 5 9 -1 3 7 5 6 7 4 2 1

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of:

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


unique_copy

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

unique, unique_copy - Removes consecutive duplicates from a range of values and places the resulting unique values into the result.

SYNOPSIS

#include <algorithm>

template <class ForwardIterator> ForwardIterator unique (ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate> ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_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 binary_pred);

DESCRIPTION

The unique algorithm moves through a sequence and eliminates all but the first element from every consecutive group of equal elements. There are two versions of the algorithm, one tests for equality, and the other tests whether a binary predicate applied to adjacent elements is true. An element is unique if it does not meet the corresponding condition listed here:

*i == *(i - 1)

or

binary_pred(*i, *(i - 1)) == true.

If an element is unique, it is copied to the front of the sequence, overwriting the existing elements. Once all unique elements have been identified. The remainder of the sequence is left unchanged, and unique returns the end of the resulting range.

The unique_copy algorithm copies the first element from every consecutive group of equal elements, to an OutputIterator. The unique_copy algorithm, also has two versions--one that tests for equality and a second that tests adjacent elements against a binary predicate.

unique_copy returns the end of the resulting range.

COMPLEXITY

Exactly (last - first) - 1 applications of the corresponding predicate are performed.

EXAMPLE

// // unique.cpp // #include <algorithm> #include <vector> #include <iostream.h> int main() { //Initialize two vectors int a1[20] = {4, 5, 5, 9, -1, -1, -1, 3, 7, 5, 5, 5, 6, 7, 7, 7, 4, 2, 1, 1}; vector<int> v(a1, a1+20), result; //Create an insert_iterator for results insert_iterator<vector<int> > ins(result, result.begin()); //Demonstrate includes cout << "The vector: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," ")); //Find the unique elements unique_copy(v.begin(), v.end(), ins); //Display the results cout << endl << endl << "Has the following unique elements:" << endl << " "; copy(result.begin(),result.end(), ostream_iterator<int,char>(cout," ")); return 0; } Output : The vector: 4 5 5 9 -1 -1 -1 3 7 5 5 5 6 7 7 7 4 2 1 1 Has the following unique elements: 4 5 9 -1 3 7 5 6 7 4 2 1

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of:

vector<int>

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee


upper_bound

Standard C++ Library Copyright 1996, Rogue Wave Software, Inc.

NAME

upper_bound - Determines the last valid position for a value in a sorted container.

SYNOPSIS

#include <algorithm> 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);

DESCRIPTION

The upper_bound algorithm is part of a set of binary search algorithms. All of these algorithms perform binary searches on ordered containers. Each algorithm has two versions. The first version uses the less than operator (operator<) to perform the comparison, and assumes that the sequence has been sorted using that operator. The second version allows you to include a function object of type Compare, and assumes that Compare is the function used to sort the sequence. The function object must be a binary predicate.

The upper_bound algorithm finds the last position in a container that value can occupy without violating the container's ordering. upper_bound's return value is the iterator for the first element in the container that is greater than value, or, when the comparison operator is used, the first element that does not satisfy the comparison function. Because the algorithm is restricted to using the less than operator or the user-defined function to perform the search, upper_bound returns an iterator i in the range [first, last) such that for any iterator j in the range [first, i) the appropriate version of the following conditions holds:

!(value < *j)

or

comp(value, *j) == false

COMPLEXITY

upper_bound performs at most log(last - first) + 1 comparisons.

EXAMPLE

// // ul_bound.cpp // #include <vector> #include <algorithm> #include <iostream.h>

int main() { typedef vector<int>::iterator iterator; int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};

// Set up a vector vector<int> v1(d1,d1 + 11);

// Try lower_bound variants iterator it1 = lower_bound(v1.begin(),v1.end(),3); // it1 = v1.begin() + 4

iterator it2 = lower_bound(v1.begin(),v1.end(),2,less<int>()); // it2 = v1.begin() + 4

// Try upper_bound variants iterator it3 = upper_bound(v1.begin(),v1.end(),3); // it3 = vector + 5

iterator it4 = upper_bound(v1.begin(),v1.end(),2,less<int>()); // it4 = v1.begin() + 5

cout << endl << endl << "The upper and lower bounds of 3: ( " << *it1 << " , " << *it3 << " ]" << endl;

cout << endl << endl << "The upper and lower bounds of 2: ( " << *it2 << " , " << *it4 << " ]" << endl;

return 0; }

Output : The upper and lower bounds of 3: ( 3 , 4 ] The upper and lower bounds of 2: ( 2 , 3 ]

WARNING

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator<int> >

instead of :

vector<int>

SEE ALSO

lower_bound, equal_range

STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee

Buy Online or Call 1.800.888.0220      privacy statement and legal notices 
STORES CONTACT US SEARCH PRODUCTS SOLUTIONS OPTIONS DEVELOPERS