| United States |
|
|
|
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
|
