United States
 cxxlstd\$help.HLP ```accumulate Standard C++ Library Copyright 1996, Rogue Wave Software, Inc. NAME accumulate - Accumulate all elements within a range into a single value. SYNOPSIS #include template T accumulate (InputIterator first, InputIterator last, T init); template 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 //for accumulate #include //for vector #include //for times #include int main() { // //Typedef for vector iterators // typedef vector::iterator iterator; // //Initialize a vector using an array of ints // int d1[10] = {1,2,3,4,5,6,7,8,9,10}; vector 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()); // //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 > instead of: vector 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 template OutputIterator adjacent_difference (InputIterator first, InputIterator last, OutputIterator result); template 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 //For adjacent_difference #include //For vector #include //For times #include int main() { // //Initialize a vector of ints from an array // int arr[10] = {1,1,2,3,5,8,13,21,34,55}; vector v(arr,arr+10); // //Two uninitialized vectors for storing results // vector 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()); // //Output the results // cout << "For the vector: " << endl << " "; copy(v.begin(),v.end(), ostream_iterator(cout," ")); cout << endl << endl; cout << "The differences between adjacent elements are: " << endl << " "; copy(diffs.begin(),diffs.end(), ostream_iterator(cout," ")); cout << endl << endl; cout << "The products of adjacent elements are: " << endl << " "; copy(prods.begin(),prods.end(), ostream_iterator(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 > instead of: vector 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 template ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last); template 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 #include #include int main() { typedef vector::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7}; // Set up a vector vector 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(),3)); // Try both adjacent_find variants iterator it3 = adjacent_find(v1.begin(),v1.end()); iterator it4 = adjacent_find(v1.begin(),v1.end(),equal_to()); // 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 > instead of: vector 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 template 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 #include #include int main() { // //Initialize a list using an array // int arr[6] = {3,4,5,6,7,8}; list l(arr,arr+6); // //Declare a list iterator, s.b. a ForwardIterator // list::iterator itr = l.begin(); // //Output the original list // cout << "For the list: "; copy(l.begin(),l.end(), ostream_iterator(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 > instead of: vector 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 template bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template 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 #include #include int main() { typedef vector::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7}; // // Set up a vector // vector 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()); // // Output results // cout << "In the vector: "; copy(v1.begin(),v1.end(), ostream_iterator(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 > instead of: vector 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 template OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); template 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 #include #include int main() { int d1[4] = {1,2,3,4}; int d2[4] = {5,6,7,8}; // Set up three vectors // vector v1(d1,d1 + 4), v2(d2,d2 + 4), v3(d2,d2 + 4); // // Set up one empty vector // vector 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 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 > instead of: vector 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 template OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); template 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 #include #include int main() { int d1[4] = {1,2,3,4}; int d2[4] = {5,6,7,8}; // Set up three vectors // vector v1(d1,d1 + 4), v2(d2,d2 + 4), v3(d2,d2 + 4); // // Set up one empty vector // vector 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 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 > instead of: vector 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 template iterator_trait::distance_type count(InputIterator first, InputIterator last, const T& value); template void count(InputIterator first, InputIterator last, const T& value, Size& n); template iterator_trait::distance_type count_if(InputIterator first, InputIterator last, Predicate pred); template 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 #include #include 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 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(),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 > instead of: vector 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 template iterator_trait::distance_type count(InputIterator first, InputIterator last, const T& value); template void count(InputIterator first, InputIterator last, const T& value, Size& n); template iterator_trait::distance_type count_if(InputIterator first, InputIterator last, Predicate pred); template 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 #include #include 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 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(),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 > instead of: vector 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 template iterator_traits::distance_type distance (ForwardIterator first, ForwardIterator last); template 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 #include #include int main() { // //Initialize a vector using an array // int arr[6] = {3,4,5,6,7,8}; vector v(arr,arr+6); // //Declare a list iterator, s.b. a ForwardIterator // vector::iterator itr = v.begin()+3; // //Output the original vector // cout << "For the vector: "; copy(v.begin(),v.end(), ostream_iterator(cout," ")); cout << endl << endl; cout << "When the iterator is initialized to point to " << *itr << endl; // // Use of distance // vector::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 > instead of: vector 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 template inline Distance* distance_type (const input_iterator&) template inline Distance* distance_type (const forward_iterator&) template inline Distance* distance_type (const bidirectional_iterator&) template inline Distance* distance_type (const random_access_iterator&) template 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 void foo(Iterator first, Iterator last) { __foo(begin,end,distance_type(first)); } template 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 template bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template 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 #include #include int main() { int d1[4] = {1,2,3,4}; int d2[4] = {1,2,4,3}; // // Set up two vectors // vector 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()); // 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 > instead of: vector 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 template pair equal_range(ForwardIterator first, ForwardIterator last, const T& value); template pair 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 #include #include int main() { typedef vector::iterator iterator; int d1[11] = {0,1,2,2,3,4,2,2,2,6,7}; // // Set up a vector // vector v1(d1+0, d1 + 11); // // Try equal_range variants // pair p1 = equal_range(v1.begin(),v1.end(),3); // p1 = (v1.begin() + 4,v1.begin() + 5) pair p2 = equal_range(v1.begin(),v1.end(),2,less()); // 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 > SEE ALSO instead of: vector 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 template 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 vec1; vector vec2; vector vecResult; transform(vec1.begin(), vec1.end(), vec2.begin(), vecResult.begin(), equal_to()); 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 struct equal_to : binary_function { typedef typename binary_function::second_argument_type second_argument_type; typedef typename binary_function::first_argument_type first_argument_type; typedef typename binary_function::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 template void fill(ForwardIterator first, ForwardIterator last, const T& value); template 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 #include #include int main() { int d1[4] = {1,2,3,4}; // // Set up two vectors // vector v1(d1,d1 + 4), v2(d1,d1 + 4); // // Set up one empty vector // vector 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 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(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 > instead of: vector 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 template void fill(ForwardIterator first, ForwardIterator last, const T& value); template 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 #include #include int main() { int d1[4] = {1,2,3,4}; // // Set up two vectors // vector v1(d1,d1 + 4), v2(d1,d1 + 4); // // Set up one empty vector // vector 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 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(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 > instead of: vector 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 template 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 #include int main() { typedef vector::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7}; // Set up a vector vector 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(),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()); // 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 > instead of: vector 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 template ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template 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 #include #include #include int main() { typedef vector::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 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()); // // 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()); // // 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(cout," ")); cout << " and "; copy (v2.begin(), v2.end(), ostream_iterator(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 > instead of: vector 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 template ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template 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 #include #include #include int main() { typedef vector::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 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()); // // Output results // cout << "For the vectors: "; copy(v1.begin(),v1.end(), ostream_iterator(cout," " )); cout << " and "; copy(v2.begin(),v2.end(), ostream_iterator(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 > instead of: vector 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 template 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 #include #include int main() { typedef vector::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7}; // Set up a vector vector 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(),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()); // 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 > instead of: vector 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 template 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 #include #include // Function class that outputs its argument times x template class out_times_x : private unary_function { 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 v(sequence,sequence + 5); // Setup a function object out_times_x 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 > instead of: vector 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 template void generate(ForwardIterator first, ForwardIterator last, Generator gen); template 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 #include #include // Value generator simply doubles the current value // and returns it template 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 gen(1); // Set up two vectors vector v1(d1,d1 + 4), v2(d1,d1 + 4); // Set up one empty vector vector 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 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(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 > instead of : vector 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 template void generate(ForwardIterator first, ForwardIterator last, Generator gen); template 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 #include #include // Value generator simply doubles the current value // and returns it template 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 gen(1); // Set up two vectors vector v1(d1,d1 + 4), v2(d1,d1 + 4); // Set up one empty vector vector 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 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(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 > instead of : vector 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 template struct greater : binary_function { typedef typename binary_function::second_argument_type second_argument_type; typedef typename binary_function::first_argument_type first_argument_type; typedef typename binary_function::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 vec1; vector vec2; vector vecResult; transform(vec1.begin(), vec1.end(), vec2.begin(), vecResult.begin(), greater()); 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 > instead of vector 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 template struct greater_equal ; : binary_function { typedef typename binary_function::second_argument_type second_argument_type; typedef typename binary_function::first_argument_type first_argument_type; typedef typename binary_function::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 vec1; sort(vec1.begin(), vec1.end(),greater_equal()); 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 > instead of vector 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 template bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template 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 #include #include 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 > all(a1, a1+10), even(a2, a2+6), small(a3,a3+4); //Demonstrate includes cout << "The set: "; copy(all.begin(),all.end(), ostream_iterator(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(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(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, allocator > instead of set 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 template T inner_product (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); template 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 //For inner_product #include //For list #include //For vectors #include //For plus and minus #include 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 l(a1, a1+3); vector 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(), minus()); //Print the output cout << "For the two sets of numbers: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(cout," ")); cout << endl << " and "; copy(l.begin(),l.end(),ostream_iterator(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 > and vector > instead of list and vector 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 template void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template 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 #include #include 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 v1(d1,d1 + 4), v2(d1,d1 + 4); // Set up four destination vectors vector v3(d2,d2 + 8),v4(d2,d2 + 8), v5(d2,d2 + 8),v6(d2,d2 + 8); // Set up one empty vector vector 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()); // In place merge v5 vector::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()); // 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 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(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 > instead of vector 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 template void iter_swap (ForwardIterator1, ForwardIterator2); DESCRIPTION The iter_swap algorithm exchanges the values pointed at by the two iterators a and b. EXAMPLE #include #include #include int main () { int d1[] = {6, 7, 8, 9, 10, 1, 2, 3, 4, 5}; // // Set up a vector. // vector v(d1+0, d1+10); // // Output original vector. // cout << "For the vector: "; copy(v.begin(), v.end(), ostream_iterator(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(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(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 > instead of : vector 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 template bool lexicographical_compare(InputIterator1 first, InputIterator2 last1, InputIterator2 first2, InputIterator last2); template 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 #include #include int main(void) { int d1[5] = {1,3,5,32,64}; int d2[5] = {1,3,2,43,56}; // set up vector vector 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()); 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 > instead of : vector 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 ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); template 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 #include #include int main() { typedef vector::iterator iterator; int d1[11] = {0,1,2,2,3,4,2,2,2,6,7}; // Set up a vector vector 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()); // 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()); // 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 > instead of: vector 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 template void make_heap(RandomAccessIterator first, RandomAccessIterator last); template 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 #include #include int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4}; // Set up two vectors vector v1(d1,d1 + 4), v2(d2,d2 + 4); // Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less()); // 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 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()); // 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()); // 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()); // 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 > instead of: vector 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 template const T& max(const T&, const T&); template 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 #include #include 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()); // 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()); // 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 template ForwardIterator max_element(ForwardIterator first, ForwardIterator last); template 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 #include #include int main(void) { typedef vector::iterator iterator; int d1[5] = {1,3,5,32,64}; // set up vector vector 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()); // 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()); // 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 > instead of: vector 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 template OutputIterator merge(InputIterator first1, InputIterator1 last1, InputIterator2 first2, InputIterator last2, OutputIterator result); template 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 #include #include 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 v1(d1,d1 + 4), v2(d1,d1 + 4); // Set up four destination vectors vector v3(d2,d2 + 8),v4(d2,d2 + 8), v5(d2,d2 + 8),v6(d2,d2 + 8); // Set up one empty vector vector 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()); // In place merge v5 vector::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()); // 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 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(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 > instead of: vector 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 template const T& min(const T&, const T&); template 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 #include 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()); // 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()); // 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 template ForwardIterator min_element(ForwardIterator first, ForwardIterator last); template 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 #include #include int main(void) { typedef vector::iterator iterator; int d1[5] = {1,3,5,32,64}; // set up vector vector 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()); // 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()); // 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 > instead of: vector 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 template pair mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template pair 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 #include #include int main(void) { typedef vector::iterator iterator; int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4}; // Set up two vectors vector 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 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 p2 = mismatch(vi1.begin(), vi1.end(), vi2.begin(), less_equal()); // 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 > instead of: vector 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 template bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); template 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 //for accumulate #include //for vector #include //for less #include 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 m1(a1, a1+10); vector prev_m1((size_t)10), next_m1((size_t)10); vector m2(a2, a2+10); vector 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()); next_permutation(next_m1.begin(), next_m1.end(),less()); prev_permutation(prev_m2.begin(), prev_m2.end(),less()); next_permutation(next_m2.begin(), next_m2.end(),less()); //Output results cout << "Example 1: " << endl << " "; cout << "Original values: "; copy(m1.begin(),m1.end(), ostream_iterator(cout," ")); cout << endl << " "; cout << "Previous permutation: "; copy(prev_m1.begin(),prev_m1.end(), ostream_iterator(cout," ")); cout << endl<< " "; cout << "Next Permutation: "; copy(next_m1.begin(),next_m1.end(), ostream_iterator(cout," ")); cout << endl << endl; cout << "Example 2: " << endl << " "; cout << "Original values: "; copy(m2.begin(),m2.end(), ostream_iterator(cout," ")); cout << endl << " "; cout << "Previous Permutation: "; copy(prev_m2.begin(),prev_m2.end(), ostream_iterator(cout," ")); cout << endl << " "; cout << "Next Permutation: "; copy(next_m2.begin(),next_m2.end(), ostream_iterator(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 > instead of : vector 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 template void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template 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 #include #include template 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 v(arr, arr+10); //Print the initial vector cout << "The unsorted values are: " << endl << " "; vector::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 > instead of : vector 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 template void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template 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 #include #include 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 v1(d1+0, d1+20); // // Output original vector. // cout << "For the vector: "; copy(v1.begin(), v1.end(), ostream_iterator(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(cout," ")); cout << endl; // // A vector of ten elements. // vector 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(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 > instead of : vector 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 template void partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template 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 #include #include 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 v1(d1+0, d1+20); // // Output original vector. // cout << "For the vector: "; copy(v1.begin(), v1.end(), ostream_iterator(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(cout," ")); cout << endl; // // A vector of ten elements. // vector 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(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 > instead of : vector 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 template OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result); template 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 //for accumulate #include //for vector #include //for times #include int main() { //Initialize a vector using an array of ints int d1[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(d1, d1+10); //Create an empty vectors to store results vector 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()); //Output the results cout << "For the series: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(cout," ")); cout << endl << endl; cout << "The partial sums: " << endl << " " ; copy(sums.begin(),sums.end(), ostream_iterator(cout," ")); cout <<" should each equal (N*N + N)/2" << endl << endl; cout << "The partial products: " << endl << " "; copy(prods.begin(),prods.end(), ostream_iterator(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 > instead of : vector 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 template 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 #include #include #include // // Create a new predicate from unary_function. // template class is_even : public unary_function { 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 d1(init+0, init+10); deque d2(init+0, init+10); // // Print out the original values. // cout << "Unpartitioned values: " << ""; copy(d1.begin(), d1.end(), ostream_iterator(cout," ")); cout << endl; // // A partition of the deque according to even/oddness. // partition(d2.begin(), d2.end(), is_even()); // // Output result of partition. // cout << "Partitioned values: " << ""; copy(d2.begin(), d2.end(), ostream_iterator(cout," ")); cout << endl; // // A stable partition of the deque according to even/oddness. // stable_partition(d1.begin(), d1.end(), is_even()); // // Output result of partition. // cout << "Stable partitioned values: " << ""; copy(d1.begin(), d1.end(), ostream_iterator(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 > instead of : deque 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 void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template 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 #include #include int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4}; // Set up two vectors vector v1(d1,d1 + 4), v2(d2,d2 + 4); // Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less()); // 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 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()); // 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()); // 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()); // 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 > instead of : vector 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 template bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last); template 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 //for accumulate #include //for vector #include //for less #include 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 m1(a1, a1+10); vector prev_m1((size_t)10), next_m1((size_t)10); vector m2(a2, a2+10); vector 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()); next_permutation(next_m1.begin(), next_m1.end(),less()); prev_permutation(prev_m2.begin(), prev_m2.end(),less()); next_permutation(next_m2.begin(), next_m2.end(),less()); //Output results cout << "Example 1: " << endl << " "; cout << "Original values: "; copy(m1.begin(),m1.end(), ostream_iterator(cout," ")); cout << endl << " "; cout << "Previous permutation: "; copy(prev_m1.begin(),prev_m1.end(), ostream_iterator(cout," ")); cout << endl<< " "; cout << "Next Permutation: "; copy(next_m1.begin(),next_m1.end(), ostream_iterator(cout," ")); cout << endl << endl; cout << "Example 2: " << endl << " "; cout << "Original values: "; copy(m2.begin(),m2.end(), ostream_iterator(cout," ")); cout << endl << " "; cout << "Previous Permutation: "; copy(prev_m2.begin(),prev_m2.end(), ostream_iterator(cout," ")); cout << endl << " "; cout << "Next Permutation: "; copy(next_m2.begin(),next_m2.end(), ostream_iterator(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 > instead of : vector 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 template void push_heap(RandomAccessIterator first, RandomAccessIterator last); template 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 #include #include int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4}; // Set up two vectors vector v1(d1,d1 + 4), v2(d2,d2 + 4); // Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less()); // 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 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()); // 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()); // 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()); // 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 > instead of : vector 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 template void random_shuffle (RandomAccessIterator first, RandomAccessIterator last); template 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 #include #include int main() { //Initialize a vector with an array of ints int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(arr, arr+10); //Print out elements in original (sorted) order cout << "Elements before random_shuffle: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(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(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 > instead of : vector 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 template 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 #include #include #include template struct all_true : public unary_function { bool operator()(const Arg& x){ return 1; } }; int main () { int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(arr, arr+10); copy(v.begin(),v.end(),ostream_iterator(cout," ")); cout << endl << endl; // remove the 7 vector::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(cout," ")); cout << endl << endl; // remove everything beyond the fourth element result = remove_if(v.begin()+4, v.begin()+8, all_true()); // delete dangling elements v.erase(result, v.end()); copy(v.begin(),v.end(),ostream_iterator(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 > instead of : vector 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 template 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 #include #include #include template struct all_true : public unary_function { bool operator() (const Arg&) { return 1; } }; int main () { int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(arr+0, arr+10); copy(v.begin(),v.end(),ostream_iterator(cout," ")); cout << endl << endl; // // Remove the 7. // vector::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(cout," ")); cout << endl << endl; // // Remove everything beyond the fourth element. // result = remove_if(v.begin()+4, v.begin()+8, all_true()); // // Delete dangling elements. // v.erase(result, v.end()); copy(v.begin(),v.end(),ostream_iterator(cout," ")); cout << endl << endl; // // Now remove all 3s on output. // remove_copy(v.begin(), v.end(), ostream_iterator(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(cout," "), all_true()); 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 > instead of : vector 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 template 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 #include #include #include template struct all_true : public unary_function { bool operator() (const Arg&) { return 1; } }; int main () { int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(arr+0, arr+10); copy(v.begin(),v.end(),ostream_iterator(cout," ")); cout << endl << endl; // // Remove the 7. // vector::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(cout," ")); cout << endl << endl; // // Remove everything beyond the fourth element. // result = remove_if(v.begin()+4, v.begin()+8, all_true()); // // Delete dangling elements. // v.erase(result, v.end()); copy(v.begin(),v.end(),ostream_iterator(cout," ")); cout << endl << endl; // // Now remove all 3s on output. // remove_copy(v.begin(), v.end(), ostream_iterator(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(cout," "), all_true()); 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 > instead of : vector 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 template 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 #include #include #include template struct all_true : public unary_function { bool operator()(const Arg& x){ return 1; } }; int main () { int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(arr, arr+10); copy(v.begin(),v.end(),ostream_iterator(cout," ")); cout << endl << endl; // remove the 7 vector::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(cout," ")); cout << endl << endl; // remove everything beyond the fourth element result = remove_if(v.begin()+4, v.begin()+8, all_true()); // delete dangling elements v.erase(result, v.end()); copy(v.begin(),v.end(),ostream_iterator(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 > instead of : vector 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 template 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 #include #include #include template struct all_true : public unary_function { 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 v(arr, arr+10); //Print out original vector cout << "The original list: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(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(cout," ")); cout << endl << endl; //Replace 1 2 3 with 13 13 13 replace_if(v.begin(), v.begin()+3, all_true(), 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(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 > instead of : vector 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 template 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 #include #include #include template struct all_true : public unary_function { 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 v(arr+0, arr+10); // // Print out original vector. // cout << "The original list: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator(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(cout," ")); cout << endl << endl; // // Replace 1 2 3 with 13 13 13. // replace_if(v.begin(), v.begin()+3, all_true(), 13); // // Print out the remaining vector. // cout << "List after replace_if:" << endl << " "; copy(v.begin(), v.end(), ostream_iterator(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(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(cout, " "), all_true(), 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 > instead of : vector 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 template 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 #include #include #include template struct all_true : public unary_function { 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 v(arr+0, arr+10); // // Print out original vector. // cout << "The original list: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator(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(cout," ")); cout << endl << endl; // // Replace 1 2 3 with 13 13 13. // replace_if(v.begin(), v.begin()+3, all_true(), 13); // // Print out the remaining vector. // cout << "List after replace_if:" << endl << " "; copy(v.begin(), v.end(), ostream_iterator(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(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(cout, " "), all_true(), 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 > instead of : vector 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 template 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 #include #include #include template struct all_true : public unary_function { 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 v(arr, arr+10); //Print out original vector cout << "The original list: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(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(cout," ")); cout << endl << endl; //Replace 1 2 3 with 13 13 13 replace_if(v.begin(), v.begin()+3, all_true(), 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(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 > instead of : vector 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 template 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 #include #include int main() { //Initialize a vector with an array of ints int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(arr, arr+10); //Print out elements in original (sorted) order cout << "Elements before reverse: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(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(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 > instead of : vector 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 template 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 #include #include int main () { // // Initialize a vector with an array of integers. // int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; vector v(arr+0, arr+10); // // Print out elements in original (sorted) order. // cout << "Elements before reverse: " << endl << " "; copy(v.begin(), v.end(), ostream_iterator(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(cout," ")); cout << endl << endl; cout << "A reverse_copy to cout: " << endl << " "; reverse_copy(v.begin(), v.end(), ostream_iterator(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 > instead of : vector 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 template void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last); template 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 #include #include int main() { //Initialize a vector with an array of ints int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(arr, arr+10); //Print out elements in original (sorted) order cout << "Elements before rotate: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(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(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 > instead of : vector 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 template void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last); template 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 #include #include int main() { //Initialize a vector with an array of ints int arr[10] = {1,2,3,4,5,6,7,8,9,10}; vector v(arr, arr+10); //Print out elements in original (sorted) order cout << "Elements before rotate: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(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(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 > instead of : vector 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 template ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred); template ForwardIterator search_n (ForwardIterator first, ForwardIterator last, Size count, const T& value); template 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 #include #include 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 sequence(seq, seq+39); list 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::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::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 > instead of : list 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 template ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred); template ForwardIterator search_n (ForwardIterator first, ForwardIterator last, Size count, const T& value); template 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 #include #include 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 sequence(seq, seq+39); list 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::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::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 > instead of : list 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 template OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template 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 #include #include 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 > all(a1, a1+10), even(a2, a2+6), odd; //Create an insert_iterator for odd insert_iterator > > odd_ins(odd, odd.begin()); //Demonstrate set_difference cout << "The result of:" << endl << "{"; copy(all.begin(),all.end(), ostream_iterator(cout," ")); cout << "} - {"; copy(even.begin(),even.end(), ostream_iterator(cout," ")); cout << "} =" << endl << "{"; set_difference(all.begin(), all.end(), even.begin(), even.end(), odd_ins); copy(odd.begin(),odd.end(), ostream_iterator(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 allocator > instead of : set 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 template OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator last2, OutputIterator result); template 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 #include #include int main() { //Initialize some sets int a1[10] = {1,3,5,7,9,11}; int a3[4] = {3,5,7,8}; set > odd(a1, a1+6), result, small(a3,a3+4); //Create an insert_iterator for result insert_iterator > > res_ins(result, result.begin()); //Demonstrate set_intersection cout << "The result of:" << endl << "{"; copy(small.begin(),small.end(), ostream_iterator(cout," ")); cout << "} intersection {"; copy(odd.begin(),odd.end(), ostream_iterator(cout," ")); cout << "} =" << endl << "{"; set_intersection(small.begin(), small.end(), odd.begin(), odd.end(), res_ins); copy(result.begin(),result.end(), ostream_iterator(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 allocator > instead of : set 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 template OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template 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 #include #include int main() { //Initialize some sets int a1[] = {1,3,5,7,9,11}; int a3[] = {3,5,7,8}; set > odd(a1,a1+6), result, small(a3,a3+4); //Create an insert_iterator for result insert_iterator > > res_ins(result, result.begin()); //Demonstrate set_symmetric_difference cout << "The symmetric difference of:" << endl << "{"; copy(small.begin(),small.end(), ostream_iterator(cout," ")); cout << "} with {"; copy(odd.begin(),odd.end(), ostream_iterator(cout," ")); cout << "} =" << endl << "{"; set_symmetric_difference(small.begin(), small.end(), odd.begin(), odd.end(), res_ins); copy(result.begin(),result.end(), ostream_iterator(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, allocator > instead of : set 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 template OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template 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 #include #include int main() { //Initialize some sets int a2[6] = {2,4,6,8,10,12}; int a3[4] = {3,5,7,8}; set > even(a2, a2+6), result, small(a3,a3+4); //Create an insert_iterator for result insert_iterator > > res_ins(result, result.begin()); //Demonstrate set_union cout << "The result of:" << endl << "{"; copy(small.begin(),small.end(), ostream_iterator(cout," ")); cout << "} union {"; copy(even.begin(),even.end(), ostream_iterator(cout," ")); cout << "} =" << endl << "{"; set_union(small.begin(), small.end(), even.begin(), even.end(), res_ins); copy(result.begin(),result.end(), ostream_iterator(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, allocator > instead of : set 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 template void sort (RandomAccessIterator first, RandomAccessIterator last); template 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 #include #include #include 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::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 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 > instead of : vector 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 template void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template 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 #include #include int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4}; // Set up two vectors vector v1(d1,d1 + 4), v2(d2,d2 + 4); // Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less()); // 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 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()); // 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()); // 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()); // 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 > instead of : vector 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 template 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 #include #include #include //Create a new predicate from unary_function template class is_even : public unary_function { 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 d(init, init+10); //Print out the original values cout << "Unpartitioned values: " << endl << " "; copy(d.begin(),d.end(),ostream_iterator(cout," ")); cout << endl << endl; //Partition the deque according to even/oddness stable_partition(d.begin(), d.end(), is_even()); //Output result of partition cout << "Partitioned values: " << endl << " "; copy(d.begin(),d.end(),ostream_iterator(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 > instead of : deque 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 template void stable_sort (RandomAccessIterator first, RandomAccessIterator last); template 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 #include #include #include 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::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 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 instead of : vector 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 template 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 template 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 #include int main() { int d1[] = {6, 7, 8, 9, 10, 1, 2, 3, 4, 5}; // Set up a vector vector v(d1,d1 + 10); // Output original vector cout << "For the vector: "; copy(v.begin(),v.end(),ostream_iterator(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(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 > instead of : vector 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 template OutputIterator transform (InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); template 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 #include #include #include #include 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 d1(arr1, arr1+5), d2(arr2, arr2+5); //Print the original values cout << "The following pairs of numbers: " << endl << " "; deque::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()); //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 > instead of: deque 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 template 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 template 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 template 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 template ForwardIterator unique (ForwardIterator first, ForwardIterator last); template ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred); template OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result); template 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 #include #include 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 v(a1, a1+20), result; //Create an insert_iterator for results insert_iterator > ins(result, result.begin()); //Demonstrate includes cout << "The vector: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(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(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 > instead of: vector 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 template ForwardIterator unique (ForwardIterator first, ForwardIterator last); template ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred); template OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result); template 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 #include #include 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 v(a1, a1+20), result; //Create an insert_iterator for results insert_iterator > ins(result, result.begin()); //Demonstrate includes cout << "The vector: " << endl << " "; copy(v.begin(),v.end(),ostream_iterator(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(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 > instead of: vector 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 template ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); template 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 #include #include int main() { typedef vector::iterator iterator; int d1[11] = {0,1,2,2,3,4,2,2,2,6,7}; // Set up a vector vector 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()); // 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()); // 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 > instead of : vector SEE ALSO lower_bound, equal_range STANDARDS CONFORMANCE ANSI X3J16/ISO WG21 Joint C++ Committee ```