accumulate
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
accumulate - Accumulate all elements within a range into a single
value.
SYNOPSIS
#include <numeric>
template <class InputIterator, class T>
T accumulate (InputIterator first,
InputIterator last,
T init);
template <class InputIterator,
class T,
class BinaryOperation>
T accumulate (InputIterator first,
InputIterator last,
T init,
BinaryOperation binary_op);
DESCRIPTION
accumulate applies a binary operation to init and each value in the
range [first,last). The result of each operation is returned in
init. This process aggregates the result of performing the
operation on every element of the sequence into a single value.
Accumulation is done by initializing the accumulator acc with the
initial value init and then modifying it with acc = acc + *i or acc
= binary_op(acc, *i) for every iterator i in the range [first,
last) in order. If the sequence is empty, accumulate returns init.
COMPLEXITY
accumulate performs exactly last-first applications of the binary
operation (operator+ by default).
EXAMPLE
//
// accum.cpp
//
#include <numeric> //for accumulate
#include <vector> //for vector
#include <functional> //for times
#include <iostream.h>
int main()
{
//
//Typedef for vector iterators
//
typedef vector<int>::iterator iterator;
//
//Initialize a vector using an array of ints
//
int d1[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v1(d1, d1+10);
//
//Accumulate sums and products
//
int sum = accumulate(v1.begin(), v1.end(), 0);
int prod = accumulate(v1.begin(), v1.end(),
1, times<int>());
//
//Output the results
//
cout << "For the series: ";
for(iterator i = v1.begin(); i != v1.end(); i++)
cout << *i << " ";
cout << " where N = 10." << endl;
cout << "The sum = (N*N + N)/2 = " << sum << endl;
cout << "The product = N! = " << prod << endl;
return 0;
}
Output :
For the series: 1 2 3 4 5 6 7 8 9 10 where N = 10.
The sum = (N*N + N)/2 = 55
The product = N! = 3628800
WARNINGS
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
adjacent_difference
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
adjacent_difference - Outputs a sequence of the differences between
each adjacent pair of elements in a range.
SYNOPSIS
#include <numeric>
template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference (InputIterator first,
InputIterator last,
OutputIterator result);
template <class InputIterator,
class OutputIterator,
class BinaryOperation>
OutputIterator adjacent_difference (InputIterator first,
InputIterator last,
OutputIterator result,
BinaryOperation bin_op);
DESCRIPTION
Informally, adjacent_difference fills a sequence with the
differences between successive elements in a container. The result
is a sequence in which the first element is equal to the
first element of the sequence being processed, and the remaining
elements are equal to the calculated differences between
adjacent elements. For instance, applying adjacent_difference
to {1,2,3,5} will produce a result of {1,1,1,2}.
By default, subtraction is used to compute the difference, but you
can supply any binary operator. The binary operator is then applied
to adjacent elements. For example, by supplying the plus (+)
operator, the result of applying adjacent_difference to {1,2,3,5} is
the sequence {1,3,5,8}.
Formally, adjacent_difference assigns to every element referred to
by iterator i in the range [result + 1, result + (last -
first)) a value equal to the appropriate one of the
following:
*(first + (i - result)) - *(first + (i - result) - 1)
or
binary_op (*(first + (i - result)), *(first + (i - result) - 1))
result is assigned the value of *first.
adjacent_difference returns result + (last - first).
result can be equal to first. This allows you to place the results
of applying adjacent_difference into the original sequence.
COMPLEXITY
This algorithm performs exactly (last-first) - 1 applications of the
default operation (-) or binary_op.
EXAMPLE
//
// adj_diff.cpp
//
#include<numeric> //For adjacent_difference
#include<vector> //For vector
#include<functional> //For times
#include <iostream.h>
int main()
{
//
//Initialize a vector of ints from an array
//
int arr[10] = {1,1,2,3,5,8,13,21,34,55};
vector<int> v(arr,arr+10);
//
//Two uninitialized vectors for storing results
//
vector<int> diffs(10), prods(10);
//
//Calculate difference(s) using default operator (minus)
//
adjacent_difference(v.begin(),v.end(),diffs.begin());
//
//Calculate difference(s) using the times operator
//
adjacent_difference(v.begin(), v.end(), prods.begin(),
times<int>());
//
//Output the results
//
cout << "For the vector: " << endl << " ";
copy(v.begin(),v.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "The differences between adjacent elements are: "
<< endl << " ";
copy(diffs.begin(),diffs.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "The products of adjacent elements are: "
<< endl << " ";
copy(prods.begin(),prods.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
Output :
For the vector:
1 1 2 3 5 8 13 21 34 55
The differences between adjacent elements are:
1 0 1 1 2 3 5 8 13 21
The products of adjacent elements are:
1 1 2 6 15 40 104 273 714 1870
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
adjacent_find
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
adjacent_find - Find the first adjacent pair of elements in a
sequence that are equivalent.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator>
ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
DESCRIPTION
There are two versions of the adjacent_find algorithm. The first
finds equal adjacent elements in the sequence defined by iterators
first and last and returns an iterator i pointing to the first of
the equal elements. The second version lets you specify your own
binary function to test for a condition. It returns an iterator i
pointing to the first of the pair of elements that meet the
conditions of the binary function. In other words,
adjacent_find returns the first iterator i such that both i and i
+ 1 are in the range [first, last) for which one of the following
conditions holds:
*i == *(i + 1)
or
pred(*i,*(i + 1)) == true
If adjacent_find does not find a match, it returns last.
COMPLEXITY
adjacent_find performs exactly find(first,last,value) - first
applications of the corresponding predicate.
EXAMPLE
//
// find.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
typedef vector<int>::iterator iterator;
int d1[10] = {0,1,2,2,3,4,2,2,6,7};
// Set up a vector
vector<int> v1(d1,d1 + 10);
// Try find
iterator it1 = find(v1.begin(),v1.end(),3);
// Try find_if
iterator it2 =
find_if(v1.begin(),v1.end(),bind1st(equal_to<int>(),3));
// Try both adjacent_find variants
iterator it3 = adjacent_find(v1.begin(),v1.end());
iterator it4 =
adjacent_find(v1.begin(),v1.end(),equal_to<int>());
// Output results
cout << *it1 << " " << *it2 << " " << *it3 << " "
<< *it4 << endl;
return 0;
}
Output :
3 3 2 2
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> > instead of:
vector<int>
SEE ALSO
find
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
advance
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
advance - Move an iterator forward or backward (if available) by a
certain distance.
SYNOPSIS
#include <iterator>
template <class InputIterator, class Distance>
void advance (InputIterator& i, Distance n);
DESCRIPTION
The advance template function allows an iterator to be advanced
through a container by some arbitrary distance. For
bidirectional and random access iterators, this distance may be
negative. This function uses operator+ and operator- for
random access iterators, which provides a constant time
implementation. For input, forward, and bidirectional iterators,
advance uses operator++ to provide linear time implementations.
advance also uses operator-- with bidirectional iterators to
provide linear time implementations of negative distances.
If n is positive, advance increments iterator reference i by n. For
negative n, advance decrements reference i. Remember that advance
accepts a negative argument n for random access and
bidirectional iterators only.
EXAMPLE
//
// advance.cpp
//
#include<iterator>
#include<list>
#include<iostream.h>
int main()
{
//
//Initialize a list using an array
//
int arr[6] = {3,4,5,6,7,8};
list<int> l(arr,arr+6);
//
//Declare a list iterator, s.b. a ForwardIterator
//
list<int>::iterator itr = l.begin();
//
//Output the original list
//
cout << "For the list: ";
copy(l.begin(),l.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "When the iterator is initialized to l.begin(),"
<< endl << "it points to " << *itr << endl << endl;
//
// operator+ is not available for a ForwardIterator,
// so use advance.
//
advance(itr, 4);
cout << "After advance(itr,4), the iterator points to "
<< *itr << endl;
return 0;
}
Output :
For the list: 3 4 5 6 7 8
When the iterator is initialized to l.begin(),
it points to 3
After advance(itr,4), the iterator points to 7
WARNINGS
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
SEE ALSO
sequence, random_iterator, distance
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
binary_search
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
binary_search - Performs a binary search for a value on a container.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class T>
bool
binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template <class ForwardIterator, class T, class Compare>
bool
binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
DESCRIPTION
The binary_search algorithm, like other related algorithms
(equal_range, lower_bound and upper_bound) performs a binary
search on ordered containers. All binary search
algorithms have two versions. The first version uses the less
than operator (operator<) to perform the comparison, and assumes
that the sequence has been sorted using that operator. The second
version allows you to include a function object of type Compare,
which it assumes was the function used to sort the sequence.
The function object must be a binary predicate.
The binary_search algorithm returns true if a sequence contains an
element equivalent to the argument value. The first version of
binary_search returns true if the sequence contains at least one
element that is equal to the search value. The second
version of the binary_search algorithm returns true if the
sequence contains at least one element that satisfies the
conditions of the comparison function. Formally,
binary_search returns true if there is an iterator i in the
range [first, last) that satisfies the corresponding conditions:
!(*i < value) && !(value < *i)
or
comp(*i, value) == false && comp(value, *i) == false
COMPLEXITY
binary_search performs at most log(last - first) + 2 comparisons.
EXAMPLE
//
// b_search.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
typedef vector<int>::iterator iterator;
int d1[10] = {0,1,2,2,3,4,2,2,6,7};
//
// Set up a vector
//
vector<int> v1(d1,d1 + 10);
//
// Try binary_search variants
//
sort(v1.begin(),v1.end());
bool b1 = binary_search(v1.begin(),v1.end(),3);
bool b2 =
binary_search(v1.begin(),v1.end(),11,less<int>());
//
// Output results
//
cout << "In the vector: ";
copy(v1.begin(),v1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << "The number 3 was "
<< (b1 ? "FOUND" : "NOT FOUND");
cout << endl << "The number 11 was "
<< (b2 ? "FOUND" : "NOT FOUND") << endl;
return 0;
}
Output :
In the vector: 0 1 2 2 2 2 3 4 6 7
The number 3 was FOUND
The number 11 was NOT FOUND
WARNINGS
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
SEE ALSO
equal_range, lower_bound, upper_bound
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
copy
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
copy, copy_backward - Copies a range of elements
SYNOPSIS
#include <algorithm>
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
DESCRIPTION
The copy algorithm copies values from the range specified by [first
, last) to the range that specified by [result, result + (last
- first)). copy can be used to copy values from one container to
another, or to copy values from one location in a container to
another location in the same container, as long as result is not
within the range [first-last). copy returns result + (last - first).
For each non-negative integer n < (last - first), copy assigns
*(first + n) to *(result + n). The result of copy is
undefined if result is in the range [first, last).
Unless result is an insert iterator, copy assumes that at least as
many elements follow result as are in the range [first, last).
The copy_backward algorithm copies elements in the range specified
by [first, last) into the range specified by [result - (last -
first), result), starting from the end of the sequence (last-1) and
progressing to the front (first). Note that copy_backward does not
reverse the order of the elements, it simply reverses the order
of transfer. copy_backward returns result - (last - first). You
should use copy_backward instead of copy when last is in the
range [result - (last - first), result). For each positive integer
n <= (last - first), copy_backward assigns *(last - n) to
*(result - n). The result of copy_backward is undefined if
result is in the range [first, last).
Unless result is an insert iterator, copy_backward assumes that
there are at least as many elements ahead of result as are in the
range [first, last).
COMPLEXITY
Both copy and copy_backward perform exactly last - first assignments.
EXAMPLE
//
// stdlib/examples/manual.copyex.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int d1[4] = {1,2,3,4};
int d2[4] = {5,6,7,8};
// Set up three vectors
//
vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4), v3(d2,d2 + 4);
//
// Set up one empty vector
//
vector<int> v4;
//
// Copy v1 to v2
//
copy(v1.begin(),v1.end(),v2.begin());
//
// Copy backwards v1 to v3
//
copy_backward(v1.begin(),v1.end(),v3.end());
//
// Use insert iterator to copy into empty vector
//
copy(v1.begin(),v1.end(),back_inserter(v4));
//
// Copy all four to cout
//
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
copy(v3.begin(),v3.end(),out);
cout << endl;
copy(v4.begin(),v4.end(),out);
cout << endl;
return 0;
}
Output :
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector <int, allocator<int> >
instead of:
vector <int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
copy_backward
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
copy, copy_backward - Copies a range of elements
SYNOPSIS
#include <algorithm>
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
DESCRIPTION
The copy algorithm copies values from the range specified by [first
, last) to the range that specified by [result, result + (last
- first)). copy can be used to copy values from one container to
another, or to copy values from one location in a container to
another location in the same container, as long as result is not
within the range [first-last). copy returns result + (last - first).
For each non-negative integer n < (last - first), copy assigns
*(first + n) to *(result + n). The result of copy is undefined if
result is in the range [first, last).
Unless result is an insert iterator, copy assumes that at least as
many elements follow result as are in the range [first, last).
The copy_backward algorithm copies elements in the range specified
by [first, last) into the range specified by [result - (last -
first), result), starting from the end of the sequence (last-1) and
progressing to the front (first). Note that copy_backward does not
reverse the order of the elements, it simply reverses the order
of transfer. copy_backward returns result - (last - first). You
should use copy_backward instead of copy when last is in the
range [result - (last - first), result). For each positive integer
n <= (last - first), copy_backward assigns *(last - n) to
*(result - n). The result of copy_backward is undefined if
result is in the range [first, last).
Unless result is an insert iterator, copy_backward assumes that
there are at least as many elements ahead of result as are in the
range [first,last).
COMPLEXITY
Both copy and copy_backward perform exactly last - first
assignments.
//
EXAMPLE
// stdlib/examples/manual.copyex.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int d1[4] = {1,2,3,4};
int d2[4] = {5,6,7,8};
// Set up three vectors
//
vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4), v3(d2,d2 + 4);
//
// Set up one empty vector
//
vector<int> v4;
//
// Copy v1 to v2
//
copy(v1.begin(),v1.end(),v2.begin());
//
// Copy backwards v1 to v3
//
copy_backward(v1.begin(),v1.end(),v3.end());
//
// Use insert iterator to copy into empty vector
//
copy(v1.begin(),v1.end(),back_inserter(v4));
//
// Copy all four to cout
//
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
copy(v3.begin(),v3.end(),out);
cout << endl;
copy(v4.begin(),v4.end(),out);
cout << endl;
return 0;
}
Output :
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector <int, allocator<int> >
instead of:
vector <int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
count
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
count, count_if - Count the number of elements in a container that
satisfy a given condition.
SYNOPSIS
#include <algorithm>
template<class InputIterator, class T>
iterator_trait<InputIterator>::distance_type
count(InputIterator first, InputIterator last,
const T& value);
template <class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last,
const T& value, Size& n);
template<class InputIterator, class Predicate>
iterator_trait<InputIterator>::distance_type
count_if(InputIterator first, InputIterator last,
Predicate pred);
template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last,
Predicate pred, Size& n);
DESCRIPTION
The count algorithm compares value to elements in the sequence
defined by iterators first and last. The first version of count
return the number of matches. The second version
increments a counting value n each time it finds a match.
i.e., count returns (or adds to n) the number of iterators i in
the range [first, last) for which the following condition holds:
*i == value
COMPLEXITY
The count_if algorithm lets you specify a predicate, and returns the
number of times an element in the sequence satisfies the predicate
(or increments n that number of times). That is, count_if returns
(or adds to n) the number of iterators i in the range [first,
last) for which the following condition holds:
pred(*i) == true. Both count and count_if perform exactly
last-first applications of the corresponding predicate.
EXAMPLE
//
// count.cpp
//
// Does not demonstrate the partial specialization versions
// of count and count_if
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
int sequence[10] = {1,2,3,4,5,5,7,8,9,10};
int i=0,j=0,k=0;
//
// Set up a vector
//
vector<int> v(sequence,sequence + 10);
count(v.begin(),v.end(),5,i); // Count fives
count(v.begin(),v.end(),6,j); // Count sixes
//
// Count all less than 8
// I=2, j=0
//
count_if(v.begin(),v.end(),bind2nd(less<int>(),8),k);
// k = 7
cout << i << " " << j << " " << k << endl;
return 0;
}
Output : 2 0 7
WARNINGS
If your compiler does not support partial specialization then the
first version of both count and count_if (the one that returns the
count) will not be available.
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance, you'll have to write:
vector <int, allocator<int> >
instead of:
vector <int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
count_if
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
count, count_if - Count the number of elements in a container that
satisfy a given condition.
SYNOPSIS
#include <algorithm>
template<class InputIterator, class T>
iterator_trait<InputIterator>::distance_type
count(InputIterator first, InputIterator last,
const T& value);
template <class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last,
const T& value, Size& n);
template<class InputIterator, class Predicate>
iterator_trait<InputIterator>::distance_type
count_if(InputIterator first, InputIterator last,
Predicate pred);
template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last,
Predicate pred, Size& n);
DESCRIPTION
The count algorithm compares value to elements in the sequence
defined by iterators first and last. The first version of count
return the number of matches. The second version
increments a counting value n each time it finds a match.
i.e., count returns (or adds to n) the number of iterators i in
the range [first, last) for which the following condition holds:
*i == value
COMPLEXITY
The count_if algorithm lets you specify a predicate, and returns the
number of times an element in the sequence satisfies the predicate
(or increments n that number of times). That is, count_if returns
(or adds to n) the number of iterators i in the range [first,
last) for which the following condition holds:
pred(*i) == true. Both count and count_if perform exactly
last-first applications of the corresponding predicate.
EXAMPLE
//
// count.cpp
//
// Does not demonstrate the partial specialization versions
// of count and count_if
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
int sequence[10] = {1,2,3,4,5,5,7,8,9,10};
int i=0,j=0,k=0;
//
// Set up a vector
//
vector<int> v(sequence,sequence + 10);
count(v.begin(),v.end(),5,i); // Count fives
count(v.begin(),v.end(),6,j); // Count sixes
//
// Count all less than 8
// I=2, j=0
//
count_if(v.begin(),v.end(),bind2nd(less<int>(),8),k);
// k = 7
cout << i << " " << j << " " << k << endl;
return 0;
}
Output : 2 0 7
WARNINGS
If your compiler does not support partial specialization then the
first version of both count and count_if (the one that returns the
count) will not be available.
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance, you'll have to write:
vector <int, allocator<int> >
instead of:
vector <int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
compare
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
compare - A binary function or a function object that returns true
or false. compare objects are typically passed as template
parameters, and used for ordering elements within a container.
SEE ALSO
binary_function, function object
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
distance
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
distance - Computes the distance between two iterators
SYNOPSIS
#include <iterator>
template <class ForwardIterator>
iterator_traits<ForwardIterator>::distance_type
distance (ForwardIterator first,
ForwardIterator last);
template <class ForwardIterator, class Distance>
void distance (ForwardIterator first,
ForwardIterator last,
Distance& n);
DESCRIPTION
The distance template function computes the distance between two
iterator. The first version returns that value, while the
second version increments n by that value. The last iterator must
be reachable from the first iterator.
Note that the second version of this function is obsolete. It is
provided for backward compatibility and to support compilers that do
not provide partial specialization. As you may have already
deduced, the first version of the function is not available with
compilers that do not support partial specialization since it
depends on iterator_traits, which itself depends on that particular
language feature.
EXAMPLE
//
// distance.cpp
//
#include <iterator>
#include <vector>
#include <iostream.h>
int main()
{
//
//Initialize a vector using an array
//
int arr[6] = {3,4,5,6,7,8};
vector<int> v(arr,arr+6);
//
//Declare a list iterator, s.b. a ForwardIterator
//
vector<int>::iterator itr = v.begin()+3;
//
//Output the original vector
//
cout << "For the vector: ";
copy(v.begin(),v.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "When the iterator is initialized to point to "
<< *itr << endl;
//
// Use of distance
//
vector<int>::difference_type dist = 0;
distance(v.begin(), itr, dist);
cout << "The distance between the beginning and itr is "
<< dist << endl;
return 0;
}
Output :
For the vector: 3 4 5 6 7 8
When the iterator is initialized to point to 6
The distance between the beginning and itr is 3
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector <int, allocator,int> > instead of:
vector <int>
Also, if your compiler does not support partial specialization then
you will not be able to use the version of distance that returns
the distance. Instead you'll have to use the version that
increments a reference parameter.
SEE ALSO
sequence, random_iterator
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
distance_type
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
distance_type - Determine the type of distance used by an iterator.
This function is now obsolete. It is retained in order to
provide backward compatibility and support compilers that
do not provide partial specialization.
SYNOPSIS
#include <iterator>
template <class T, class Distance>
inline Distance* distance_type (const input_iterator<T,
Distance>&)
template <class T, class Distance>
inline Distance* distance_type (const forward_iterator<T,
Distance>&)
template <class T, class Distance>
inline Distance*
distance_type (const bidirectional_iterator<T, Distance>&)
template <class T, class Distance>
inline Distance*
distance_type (const random_access_iterator<T, Distance>&)
template <class T>
inline ptrdiff_t* distance_type (const T*)
DESCRIPTION
The distance_type family of function templates return a pointer to a
value that is of the same type as that used to represent a
distance between two iterators. The first four of these
take an iterator of a particular type and return a pointer to a
default value of the distance_type for that iterator. The T* form
of the function returns ptrdiff_t*.
Generic algorithms use this function to create local variables of
the correct type. The distance_type functions are typically
used like this:
template <class Iterator>
void foo(Iterator first, Iterator last)
{
__foo(begin,end,distance_type(first));
}
template <class Iterator, class Distance>
void __foo(Iterator first,Iterator last, Distance*>
{ Distance d = Distance();
distance(first,last,d);
}
The auxiliary function template allows the algorithm to extract a
distance type from the first iterator and then use that type
to perform some useful work.
SEE ALSO
Other iterator primitives: value_type, iterator_category, distance,
advance
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
equal
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
equal - Compares two ranges for equality.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template <class InputIterator1, class InputIterator2,
class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate binary_pred);
DESCRIPTION
The equal algorithm does a pairwise comparison of all of the
elements in one range with all of the elements in
another range to see if they match. The first version of equal
uses the equal operator (==) as the comparison function, and the
second version allows you to specify a binary predicate as the
comparison function. The first version returns true if all of
the corresponding elements are equal to each other. The second
version of equal returns true if for each pair of elements in
the two ranges, the result of applying the binary predicate is
true. In other words, equal returns true if both of the following
are true:
1. There are at least as many elements in the second range as in the
first;
2. For every iterator i in the range [first1, last1) the following
corresponding conditions hold:
*i == *(first2 + (i - first1))
or
binary_pred(*i, *(first2 + (i - first1))) == true
Otherwise, equal returns false.
This algorithm assumes that there are at least as many elements
available after first2 as there are in the range [first1,
last1).
COMPLEXITY
equal performs at most last1-first1 comparisons or applications of
the predicate.
EXAMPLE
//
// equal.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int d1[4] = {1,2,3,4};
int d2[4] = {1,2,4,3};
//
// Set up two vectors
//
vector<int> v1(d1+0, d1 + 4), v2(d2+0, d2 + 4);
// Check for equality
bool b1 = equal(v1.begin(),v1.end(),v2.begin());
bool b2 = equal(v1.begin(),v1.end(),
v2.begin(),equal_to<int>());
// Both b1 and b2 are false
cout << (b1 ? "TRUE" : "FALSE") << " "
<< (b2 ? "TRUE" : "FALSE") << endl;
return 0;
}
Output :
FALSE FALSE
WARNINGS
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
equal_range
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
equal_range - Find the largest subrange in a collection into which
a given value can be inserted without violating the ordering
of the collection.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const T& value);
template <class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
DESCRIPTION
The equal_range algorithm performs a binary search on an ordered
container to determine where the element value can be inserted
without violating the container's ordering. The library provides
two versions of the algorithm. The first version uses the less than
operator (operator <) to search for the valid insertion range,
and assumes that the sequence was sorted using the less than
operator. The second version allows you to specify a function
object of type Compare, and assumes that Compare was the
function used to sort the sequence. The function object must be a
binary predicate.
equal_range returns a pair of iterators, i and j that define a range
containing elements equivalent to value, i.e., the first and
last valid insertion points for value. If value is not an element
in the container, i and j are equal. Otherwise, i will
point to the first element not "less" than value, and j will
point to the first element greater than value. In the second
version, "less" is defined by the comparison object. Formally,
equal_range returns a subrange [i, j) such that value can be
inserted at any iterator k within the range. Depending upon the
version of the algorithm used, k must satisfy one of the
following conditions:
!(*k < value) && !(value < *k)
or
comp(*k,value) == false && comp(value, *k) == false
The range [first,last) is assumed to be sorted.
COMPLEXITY
equal_range performs at most 2 * log(last - first) + 1 comparisons.
EXAMPLE
//
// eqlrange.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
typedef vector<int>::iterator iterator;
int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};
//
// Set up a vector
//
vector<int> v1(d1+0, d1 + 11);
//
// Try equal_range variants
//
pair<iterator,iterator> p1 =
equal_range(v1.begin(),v1.end(),3);
// p1 = (v1.begin() + 4,v1.begin() + 5)
pair<iterator,iterator> p2 =
equal_range(v1.begin(),v1.end(),2,less<int>());
// p2 = (v1.begin() + 4,v1.begin() + 5)
// Output results
cout << endl << "The equal range for 3 is: "
<< "( " << *p1.first << " , "
<< *p1.second << " ) " << endl << endl;
cout << endl << "The equal range for 2 is: "
<< "( " << *p2.first << " , "
<< *p2.second << " ) " << endl;
return 0;
}
Output :
The equal range for 3 is: ( 3 , 4 )
The equal range for 2 is: ( 2 , 3 )
WARNINGS
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
SEE ALSO
instead of:
vector<int> binary_function, lower_bound, upper_bound
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
equal_to
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
equal_to - Binary function object that returns true if its first
argument equals its second
SYNOPSIS
#include <functional>
template <class T>
struct equal_to;
DESCRIPTION
equal_to is a binary function object. Its operator() returns true
if x is equal to y. You can pass an equal_to object to any
algorithm that requires a binary function. For example, the
transform algorithm applies a binary operation to corresponding
values in two collections and stores the result. equal_to would be
used in that algorithm in the following manner:
vector<int> vec1;
vector<int> vec2;
vector<int> vecResult;
transform(vec1.begin(), vec1.end(),
vec2.begin(), vecResult.begin(),
equal_to<int>());
After this call to transform, vecResult(n) will contain a "1" if
vec1(n) was equal to vec2(n) or a "0" if vec1(n) was not equal to
vec2(n).
INTERFACE
template <class T>
struct equal_to : binary_function<T, T, bool>
{
typedef typename binary_function<T, T, bool>::second_argument_type
second_argument_type;
typedef typename binary_function<T, T, bool>::first_argument_type
first_argument_type;
typedef typename binary_function<T, T, bool>::result_type
result_type;
SEE ALSO
bool operator() (const T&, const T&) const;
}; binary_function, function objects
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
fill
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
fill, fill_n - Initializes a range with a given value.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last,
const T& value);
template <class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& value);
DESCRIPTION
The fill and fill_n algorithms are used to assign a value to the
elements in a sequence. fill assigns the value to all the
elements designated by iterators in the range [first, last).
The fill_n algorithm assigns the value to all the elements
designated by iterators in the range [first, first + n). fill_n
assumes that there are at least n elements following first,
unless first is an insert iterator.
COMPLEXITY
fill makes exactly last - first assignments, and fill_n makes
exactly n assignments.
EXAMPLE
//
// fill.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int d1[4] = {1,2,3,4};
//
// Set up two vectors
//
vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4);
//
// Set up one empty vector
//
vector<int> v3;
//
// Fill all of v1 with 9
//
fill(v1.begin(),v1.end(),9);
//
// Fill first 3 of v2 with 7
//
fill_n(v2.begin(),3,7);
//
// Use insert iterator to fill v3 with 5 11's
//
fill_n(back_inserter(v3),5,11);
//
// Copy all three to cout
//
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
copy(v3.begin(),v3.end(),out);
cout << endl;
//
// Fill cout with 3 5's
//
fill_n(ostream_iterator<int,char>(cout," "),3,5);
cout << endl;
return 0;
}
Output :
9 9 9 9
7 7 7 4
11 11 11 11 11
5 5 5
WARNINGS
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
fill_n
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
fill, fill_n - Initializes a range with a given value.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last,
const T& value);
template <class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& value);
DESCRIPTION
The fill and fill_n algorithms are used to assign a value to the
elements in a sequence. fill assigns the value to all the
elements designated by iterators in the range [first, last).
The fill_n algorithm assigns the value to all the elements
designated by iterators in the range [first, first + n). fill_n
assumes that there are at least n elements following first,
unless first is an insert iterator.
COMPLEXITY
fill makes exactly last - first assignments, and fill_n makes
exactly n assignments.
EXAMPLE
//
// fill.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int d1[4] = {1,2,3,4};
//
// Set up two vectors
//
vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4);
//
// Set up one empty vector
//
vector<int> v3;
//
// Fill all of v1 with 9
//
fill(v1.begin(),v1.end(),9);
//
// Fill first 3 of v2 with 7
//
fill_n(v2.begin(),3,7);
//
// Use insert iterator to fill v3 with 5 11's
//
fill_n(back_inserter(v3),5,11);
//
// Copy all three to cout
//
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
copy(v3.begin(),v3.end(),out);
cout << endl;
//
// Fill cout with 3 5's
//
fill_n(ostream_iterator<int,char>(cout," "),3,5);
cout << endl;
return 0;
}
Output :
9 9 9 9
7 7 7 4
11 11 11 11 11
5 5 5
WARNINGS
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
find
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
find - Find an occurrence of value in a sequence
SYNOPSIS
#include <algorithm>
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last,
const T& value);
DESCRIPTION
The find algorithm lets you search for the first occurrence of a
particular value in a sequence. find returns the first
iterator i in the range [first, last) for which the
following condition holds:
*i == value.
If find does not find a match for value, it returns the iterator
last.
COMPLEXITY
find performs at most last-first comparisons.
EXAMPLE
//
// find.cpp
//
#include <vector>
#include <algorithm>
int main()
{
typedef vector<int>::iterator iterator;
int d1[10] = {0,1,2,2,3,4,2,2,6,7};
// Set up a vector
vector<int> v1(d1,d1 + 10);
// Try find
iterator it1 = find(v1.begin(),v1.end(),3);
// it1 = v1.begin() + 4;
// Try find_if
iterator it2 =
find_if(v1.begin(),v1.end(),bind1st(equal_to<int>(),3));
// it2 = v1.begin() + 4
// Try both adjacent_find variants
iterator it3 = adjacent_find(v1.begin(),v1.end());
// it3 = v1.begin() +2
iterator it4 =
adjacent_find(v1.begin(),v1.end(),equal_to<int>());
// v4 = v1.begin() + 2
// Output results
cout << *it1 << " " << *it2 << " " << *it3 << " "
<< *it4 << endl;
return 0;
}
Output : 3 3 2 2
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
SEE ALSO
adjacent_find, find_first_of, find_if
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
find_end
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
find_end - Finds the last occurrence of a sub-sequence in a sequence.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);
template <class Forward Iterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
BinaryPredicate pred);
DESCRIPTION
The find_end algorithm finds the last occurrence of a sub-sequence,
indicated by [first2, last2), in a sequence, [first1,last1).
The algorithm returns an iterator pointing to the first element
of the found subsequence, or last1 if no match is found.
More precisely, the find_end algorithm returns the last iterator
i in the range [first1, last1 - (last2-first2)) such that
for any non-negative integer n < (last2-first2), the
following corresponding conditions hold:
*(i+n) == *(first2+n),
pred(*(i+n),*(first2+n)) == true.
Or returns last1 if no such iterator is found.
Two versions of the algorithm exist. The first uses the equality
operator as the default binary predicate, and the second allows
you to specify a binary predicate.
COMPLEXITY
At most (last2-first2)*(last1-first1-(last2-first2)+1) applications
of the corresponding predicate are done.
EXAMPLE
//
// find_end.cpp
//
#include<vector>
#include<iterator>
#include<algorithm>
#include<iostream.h>
int main()
{
typedef vector<int>::iterator iterator;
int d1[10] = {0,1,6,5,3,2,2,6,5,7};
int d2[4] = {6,5,0,0}
//
// Set up two vectors.
//
vector<int> v1(d1+0, d1+10), v2(d2+0, d2+2);
//
// Try both find_first_of variants.
//
iterator it1 = find_first_of (v1.begin(), v1.end(), v2.begin(),
v2.end());
iterator it2 = find_first_of (v1.begin(), v1.end(), v2.begin(),
v2.end(), equal_to<int>());
//
// Try both find_end variants.
//
iterator it3 = find_end (v1.begin(), v1.end(), v2.begin(),
v2.end());
iterator it4 = find_end (v1.begin(), v1.end(), v2.begin(),
v2.end(), equal_to<int>());
//
// Output results of find_first_of.
// Iterator now points to the first element that matches one of
// a set of values
//
cout << "For the vectors: ";
copy (v1.begin(), v1.end(), ostream_iterator<int>(cout," "));
cout << " and ";
copy (v2.begin(), v2.end(), ostream_iterator<int>(cout," "));
cout<< endl ,, endl
<< "both versions of find_first_of point to: "
<< *it1 << endl << "with first_of address = " << it1
<< endl ;
//
//Output results of find_end.
// Iterator now points to the first element of the last find
//sub-sequence.
//
cout << endl << endl
<< "both versions of find_end point to: "
<< *it3 << endl << "with find_end address = " << it3
<< endl ;
return 0;
}
Output :
For the vectors: 0 1 6 5 3 2 2 6 5 7 and 6 5
both versions of find_first_of point to: 6
with first_of address = 0x100005c0
both versions of find_end point to: 6
with find_end address = 0x100005d4
WARNINGS
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int, allocator<int> >
instead of:
vector<int>
SEE ALSO
Algorithms, find, find_if, adjacent_find
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
find_first_of
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
find_first_of - Finds the first occurrence of any value from one
sequence in another sequence.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of (ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 find_first_of (ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
BinaryPredicate pred);
DESCRIPTION
The find_first_of algorithm finds a the first occurrence of a value
from a sequence, specified by first2, last2, in a sequence
specified by first1, last1. The algorithm returns an iterator in
the range [first1, last1) that points to the first matching
element. If the first sequence [first1, last1) does
not contain any of the values in the second sequence, find_first_of
returns last1.
In other words, find_first_of returns the first iterator i in the
[first1, last1)such that for some integer j in the range
[first2, last2):the following conditions hold:
*i == *j, pred(*i,*j) == true.
Or find_first_of returns last1 if no such iterator is found.
COMPLEXITY
Two versions of the algorithm exist. The first uses the equality
operator as the default binary predicate, and the second allows
you to specify a binary predicate.
At most (last1 - first1)*(last2 - first2) applications of the
corresponding predicate are done.
EXAMPLE
//
// find_f_o.cpp
//
#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream.h>
int main()
{
typedef vector<int>::iterator iterator;
int d1[10] = {0,1,2,2,3,4,2,2,6,7};
int d2[2] = {6,4};
//
// Set up two vectors
//
vector<int> v1(d1,d1 + 10), v2(d2,d2 + 2);
//
// Try both find_first_of variants
//
iterator it1 =
find_first_of(v1.begin(),v1.end(),v2.begin(),v2.end());
find_first_of(v1.begin(),v1.end(),v2.begin(),v2.end(),
equal_to<int>());
//
// Output results
//
cout << "For the vectors: ";
copy(v1.begin(),v1.end(),
ostream_iterator<int,char>(cout," " ));
cout << " and ";
copy(v2.begin(),v2.end(),
ostream_iterator<int,char>(cout," " ));
cout << endl << endl
<< "both versions of find_first_of point to: "
<< *it1;
return 0;
}
Output :
For the vectors: 0 1 2 2 3 4 2 2 6 7 and 6 4
both versions of find_first_of point to: 4
WARNINGS
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int, allocator<int> >
instead of:
vector<int>
SEE ALSO
Algorithms, adjacent_find, find, find_if, find_next, find_end
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
find_if
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
find_if - Find an occurrence of value in a sequence that satisfies
a specifed predicate.
SYNOPSIS
#include <algorithm>
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first,
InputIterator last,
Predicate pred);
DESCRIPTION
The find_if algorithm allows you to search for the first element in
a sequence that satisfies a particular condition. The
sequence is defined by iterators first and last, while the
condition is defined by the third argument: a
predicate function that returns a boolean value. find_if returns
the first iterator i in the range [first, last) for which the
following condition holds:
pred(*i) == true.
If no such iterator is found, find_if returns last.
COMPLEXITY
find_if performs at most last-first applications of the corresponding
predicate.
EXAMPLE
//
// find.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
typedef vector<int>::iterator iterator;
int d1[10] = {0,1,2,2,3,4,2,2,6,7};
// Set up a vector
vector<int> v1(d1,d1 + 10);
// Try find
iterator it1 = find(v1.begin(),v1.end(),3);
// it1 = v1.begin() + 4;
// Try find_if
iterator it2 =
find_if(v1.begin(),v1.end(),bind1st(equal_to<int>(),3));
// it2 = v1.begin() + 4
// Try both adjacent_find variants
iterator it3 = adjacent_find(v1.begin(),v1.end());
// it3 = v1.begin() +2
iterator it4 =
adjacent_find(v1.begin(),v1.end(),equal_to<int>());
// v4 = v1.begin() + 2
// Output results
cout << *it1 << " " << *it2 << " " << *it3 << " "
<< *it4 << endl;
return 0;
}
Output : 3 3 2 2
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int, allocator<int> >
instead of:
vector<int>
SEE ALSO
adjacent_find, Algorithms, find, find_end, find_first_of
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
for_each
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
for_each - Applies a function to each element in a range.
SYNOPSIS
#include <algorithm>
template <class InputIterator, class Function>
void for_each(InputIterator first, InputIterator last,
Function f);
DESCRIPTION
The for_each algorithm applies function f to all members of the
sequence in the range [first, last), where first and last are
iterators that define the sequence. Since this a non-mutating
algorithm, the function f cannot make any modifications to the
sequence, but it can achieve results through side effects (such
as copying or printing). If f returns a result, the result is
ignored.
COMPLEXITY
The function f is applied exactly last - first times.
EXAMPLE
//
// for_each.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
// Function class that outputs its argument times x
template <class Arg>
class out_times_x : private unary_function<Arg,void>
{
private:
Arg multiplier;
public:
out_times_x(const Arg& x) : multiplier(x) { }
void operator()(const Arg& x)
{ cout << x * multiplier << " " << endl; }
};
int main()
{
int sequence[5] = {1,2,3,4,5};
// Set up a vector
vector<int> v(sequence,sequence + 5);
// Setup a function object
out_times_x<int> f2(2);
for_each(v.begin(),v.end(),f2); // Apply function
return 0;
}
Output : 2 4 6 8 10
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int, allocator<int> >
instead of:
vector<int>
SEE ALSO
Algorithms, function object
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
generate
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
generate, generate_n - Initialize a container with values produced by a
value-generator class.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
Generator gen);
template <class OutputIterator, class Size, class Generator>
void generate_n(OutputIterator first, Size n, Generator gen);
DESCRIPTION
A value-generator function returns a value each time it is invoked.
The algorithms generate and generate_n initialize (or
reinitialize) a sequence by assigning the return value of the
generator function gen to all the elements designated by
iterators in the range [first, last) or [first, first + n). The
function gen takes no arguments. (gen can be a function or a class
with an operator () defined that takes no arguments.)
generate_n assumes that there are at least n elements following
first, unless first is an insert iterator.
COMPLEXITY
The generate and generate_n algorithms invoke gen and assign its
return value exactly last - first (or n) times.
EXAMPLE
//
// generate.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
// Value generator simply doubles the current value
// and returns it
template <class T>
class generate_val
{
private:
T val_;
public:
generate_val(const T& val) : val_(val) {}
T& operator()() { val_ += val_; return val_; }
};
int main()
{
int d1[4] = {1,2,3,4};
generate_val<int> gen(1);
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4);
// Set up one empty vector
vector<int> v3;
// Generate values for all of v1
generate(v1.begin(),v1.end(),gen);
// Generate values for first 3 of v2
generate_n(v2.begin(),3,gen);
// Use insert iterator to generate 5 values for v3
generate_n(back_inserter(v3),5,gen);
// Copy all three to cout
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
copy(v3.begin(),v3.end(),out);
cout << endl;
// Generate 3 values for cout
generate_n(ostream_iterator<int>(cout," "),3,gen);
cout << endl;
return 0;
}
Output :
2 4 8 16
2 4 8 4
2 4 8 16 32
2 4 8
WARNINGS
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write:
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
function objects
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
generate_n
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
generate, generate_n - Initialize a container with values produced
by a value-generator class.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
Generator gen);
template <class OutputIterator, class Size, class Generator>
void generate_n(OutputIterator first, Size n, Generator gen);
DESCRIPTION
A value-generator function returns a value each time it is invoked.
The algorithms generate and generate_n initialize (or
reinitialize) a sequence by assigning the return value of the
generator function gen to all the elements designated by
iterators in the range [first, last) or [first, first + n). The
function gen takes no arguments. (gen can be a function or a class
with an operator () defined that takes no arguments.)
generate_n assumes that there are at least n elements following
first, unless first is an insert iterator.
COMPLEXITY
The generate and generate_n algorithms invoke gen and assign its
return value exactly last - first (or n) times.
EXAMPLE
//
// generate.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
// Value generator simply doubles the current value
// and returns it
template <class T>
class generate_val
{
private:
T val_;
public:
generate_val(const T& val) : val_(val) {}
T& operator()() { val_ += val_; return val_; }
};
int main()
{
int d1[4] = {1,2,3,4};
generate_val<int> gen(1);
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4);
// Set up one empty vector
vector<int> v3;
// Generate values for all of v1
generate(v1.begin(),v1.end(),gen);
// Generate values for first 3 of v2
generate_n(v2.begin(),3,gen);
// Use insert iterator to generate 5 values for v3
generate_n(back_inserter(v3),5,gen);
// Copy all three to cout
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
copy(v3.begin(),v3.end(),out);
cout << endl;
// Generate 3 values for cout
generate_n(ostream_iterator<int>(cout," "),3,gen);
cout << endl;
return 0;
}
Output :
2 4 8 16
2 4 8 4
2 4 8 16 32
2 4 8
WARNINGS
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write:
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
function objects
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
greater
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
greater - Binary function object that returns true if its first
argument is greater than its second.
SYNOPSIS
#include <functional>
template <class T>
struct greater : binary_function<T, T, bool> {
typedef typename binary_function<T, T, bool>::second_argument_type
second_argument_type;
typedef typename binary_function<T, T, bool>::first_argument_type
first_argument_type;
typedef typename binary_function<T, T, bool>::result_type
result_type;
bool operator() (const T&, const T&) const;
};
DESCRIPTION
greater is a binary function object. Its operator() returns true if
x is greater than y. You can pass a greater object to any
algorithm that requires a binary function. For example, the
transform algorithm applies a binary operation to corresponding
values in two collections and stores the result of the
function. greater would be used in that algorithm in the following
manner:
vector<int> vec1;
vector<int> vec2;
vector<int> vecResult;
transform(vec1.begin(), vec1.end(),
vec2.begin(), vecResult.begin(), greater<int>());
WARNINGS
After this call to transform, vecResult(n) will contain a "1" if
vec1(n) was greater than vec2(n) or a "0" if vec1(n) was less than
or equal to vec2(n).
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write :
vector<int, allocator<int> >
instead of
vector<int>
SEE ALSO
function objects
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
greater_equal
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
greater_equal - Binary function object that returns true if its
first argument is greater than or equal to its second
SYNOPSIS
#include <functional>
template <class T>
struct greater_equal ; : binary_function<T, T, bool> {
typedef typename binary_function<T, T, bool>::second_argument_type
second_argument_type;
typedef typename binary_function<T, T, bool>::first_argument_type
first_argument_type;
typedef typename binary_function<T, T, bool>::result_type
result_type;
bool operator() (const T&, const T&) const;
};
DESCRIPTION
greater_equal is a binary function object. Its operator() returns
true if x is greater than or equal to y. You can pass a
greater_equal object to any algorithm that requires a binary
function. For example, the sort algorithm can accept a
binary function as an alternate comparison object to sort a
sequence. greater_equal would be used in that algorithm in
the following manner:
vector<int> vec1;
sort(vec1.begin(), vec1.end(),greater_equal<int>());
After this call to sort, vec1 will be sorted in descending order.
WARNINGS
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write :
vector<int, allocator<int> >
instead of
vector<int>
SEE ALSO
function objects
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
Heap_Operations
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
Heap_Operations
See the entries for make_heap, pop_heap, push_heap and sort_heap
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
includes
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
includes - Basic set operation for sorted sequences.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2>
bool includes (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template <class InputIterator1, class InputIterator2, class Compare>
bool includes (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
DESCRIPTION
The includes algorithm compares two sorted sequences and returns
true if every element in the range [first2, last2) is
contained in the range [first1, last1). It returns false otherwise.
include assumes that the sequences are sorted using the
default comparison operator less than (<), unless an alternative
comparison operator (comp) is provided.
COMPLEXITY
At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons
are performed.
EXAMPLE
//
// includes.cpp
//
#include <algorithm>
#include <set>
#include <iostream.h>
int main()
{
//Initialize some sets
int a1[10] = {1,2,3,4,5,6,7,8,9,10};
int a2[6] = {2,4,6,8,10,12};
int a3[4] = {3,5,7,8};
set<int, less<int> > all(a1, a1+10), even(a2, a2+6),
small(a3,a3+4);
//Demonstrate includes
cout << "The set: ";
copy(all.begin(),all.end(),
ostream_iterator<int,char>(cout," "));
bool answer = includes(all.begin(), all.end(),
small.begin(), small.end());
cout << endl
<< (answer ? "INCLUDES " : "DOES NOT INCLUDE ");
copy(small.begin(),small.end(),
ostream_iterator<int,char>(cout," "));
answer = includes(all.begin(), all.end(),
even.begin(), even.end());
cout << ", and" << endl
<< (answer ? "INCLUDES" : "DOES NOT INCLUDE ");
copy(even.begin(),even.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << endl;
return 0;
}
Output :
The set: 1 2 3 4 5 6 7 8 9 10
INCLUDES 3 5 7 8 , and
DOES NOT INCLUDE 2 4 6 8 10 12
WARNINGS
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write :
set<int, less<int>, allocator<int> >
instead of
set<int>
SEE ALSO
set, set_union, set_intersection, set_difference,
set_symmetric_difference
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
inner_product
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
inner_product - Computes the inner product A X B of two ranges A
and B.
SYNOPSIS
#include <numeric>
template <class InputIterator1, class InputIterator2,
class T>
T inner_product (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init);
template <class InputIterator1, class InputIterator2,
class T,
class BinaryOperation1,
class BinaryOperation2>
T inner_product (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init,
BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2);
DESCRIPTION
There are two versions of inner_product. The first computes an
inner product using the default multiplication and addition
operators, while the second allows you to specify binary
operations to use in place of the default operations.
The first version of the function computes its result by
initializing the accumulator acc with the initial value init and
then modifying it with:
acc = acc + ((*i1) * (*i2))
for every iterator i1 in the range [first1, last1) and iterator i2
in the range [first2, first2 + (last1 - first1)). The
algorithm returns acc.
The second version of the function initializes acc with init, then
computes the result:
acc = binary_op1(acc, binary_op2(*i1, *i2))
for every iterator i1 in the range [first1, last1) and iterator i2
in the range [first2, first2 + (last1 - first1)).
COMPLEXITY
The inner_product algorithm computes exactly (last1 - first1)
applications of either:
acc + (*i1) * (*i2)
or
binary_op1(acc, binary_op2(*i1, *i2)).
EXAMPLE
//
// inr_prod.cpp
//
#include <numeric> //For inner_product
#include <list> //For list
#include <vector> //For vectors
#include <functional> //For plus and minus
#include <iostream.h>
int main()
{
//Initialize a list and an int using arrays of ints
int a1[3] = {6, -3, -2};
int a2[3] = {-2, -3, -2};
list<int> l(a1, a1+3);
vector<int> v(a2, a2+3);
//Calculate the inner product of the two sets of values
int inner_prod =
inner_product(l.begin(), l.end(), v.begin(), 0);
//Calculate a wacky inner product using the same values
int wacky =
inner_product(l.begin(), l.end(), v.begin(), 0,
plus<int>(), minus<int>());
//Print the output
cout << "For the two sets of numbers: " << endl
<< " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << " and ";
copy(l.begin(),l.end(),ostream_iterator<int,char>(cout," "));
cout << "," << endl << endl;
cout << "The inner product is: " << inner_prod << endl;
cout << "The wacky result is: " << wacky << endl;
return 0;
}
Output :
For the two sets of numbers:
-2 -3 -2
and 6 -3 -2 ,
The inner product is: 1
The wacky result is: 8
WARNINGS
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write :
list<int, allocator<int> > and vector<int, allocator<int> >
instead of
list<int> and vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
inplace_merge
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
inplace_merge - Merge two sorted sequences into one.
SYNOPSIS
#include <algorithm>
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
DESCRIPTION
The inplace_merge algorithm merges two sorted consecutive ranges
[first, middle) and [middle, last), and puts the result of the merge
into the range [first, last). The merge is stable, that is,
if the two ranges contain equivalent elements, the elements from the
first range always precede the elements from the second.
There are two versions of the inplace_merge algorithm. The first
version uses the less than operator (operator<) as the default for
comparison, and the second version accepts a third argument that
specifies a comparison operator.
COMPLEXITY
When enough additional memory is available, inplace_merge does at
most (last - first) - 1 comparisons. If no additional memory is
available, an algorithm with O(NlogN) complexity (where N is equal
to last-first) may be used.
EXAMPLE
//
// merge.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int d1[4] = {1,2,3,4};
int d2[8] = {11,13,15,17,12,14,16,18};
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4);
// Set up four destination vectors
vector<int> v3(d2,d2 + 8),v4(d2,d2 + 8),
v5(d2,d2 + 8),v6(d2,d2 + 8);
// Set up one empty vector
vector<int> v7;
// Merge v1 with v2
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
// Now use comparator
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v4.begin(),
less<int>());
// In place merge v5
vector<int>::iterator mid = v5.begin();
advance(mid,4);
inplace_merge(v5.begin(),mid,v5.end());
// Now use a comparator on v6
mid = v6.begin();
advance(mid,4);
inplace_merge(v6.begin(),mid,v6.end(),less<int>());
// Merge v1 and v2 to empty vector using insert iterator
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),
back_inserter(v7));
// Copy all cout
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
copy(v3.begin(),v3.end(),out);
cout << endl;
copy(v4.begin(),v4.end(),out);
cout << endl;
copy(v5.begin(),v5.end(),out);
cout << endl;
copy(v6.begin(),v6.end(),out);
cout << endl;
copy(v7.begin(),v7.end(),out);
cout << endl;
// Merge v1 and v2 to cout
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output:
1 2 3 4
1 2 3 4
1 1 2 2 3 3 4 4
1 1 2 2 3 3 4 4
11 12 13 14 15 16 17 18
11 12 13 14 15 16 17 18
1 1 2 2 3 3 4 4
1 1 2 2 3 3 4 4
WARNINGS
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write :
vector<int, allocator,int> >
instead of
vector<int>
SEE ALSO
merge
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
iter_swap
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
iter_swap - Exchange values pointed at in two locations
SYNOPSIS
#include <algorithm>
template <class ForwardIterator1, class ForwardIterator2>
void iter_swap (ForwardIterator1, ForwardIterator2);
DESCRIPTION
The iter_swap algorithm exchanges the values pointed at by the two
iterators a and b.
EXAMPLE
#include <vector>
#include <algorithm>
#include <iostream.h>
int main ()
{
int d1[] = {6, 7, 8, 9, 10, 1, 2, 3, 4, 5};
//
// Set up a vector.
//
vector<int> v(d1+0, d1+10);
//
// Output original vector.
//
cout << "For the vector: ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
//
// Swap the first five elements with the last five elements.
//
swap_ranges(v.begin(), v.begin()+5, v.begin()+5);
//
// Output result.
//
cout << endl << endl
<< "Swapping the first 5 elements with the last 5 gives: "
<< endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
//
// Now an example of iter_swap -- swap first and last elements.
//
iter_swap(v.begin(), v.end()-1);
//
// Output result.
//
cout << endl << endl
<< "Swapping the first and last elements gives: "
<< endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
For the vector: 6 7 8 9 10 1 2 3 4 5
Swapping the first five elements with the last five gives:
1 2 3 4 5 6 7 8 9 10
Swapping the first and last elements gives:
10 2 3 4 5 6 7 8 9 1
WARNING
If your compiler does not support default template parameters, then
you will need to always supply the Allocator template argument. For
instance, you'll have to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
Iterators, swap, swap_ranges
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
lexicographical_compare
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
lexicographical_compare - Compares two ranges lexicographically.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2>
bool
lexicographical_compare(InputIterator1 first,
InputIterator2 last1,
InputIterator2 first2,
InputIterator last2);
template <class InputIterator1, class InputIterator2, class Compare>
bool
lexicographical_compare(InputIterator1 first,
InputIterator2 last1,
InputIterator2 first2,
InputIterator last2, Compare comp);
DESCRIPTION
The lexicographical_compare functions compare each element in the
range [first1, last1) to the corresponding element in the range
[first2, last2) using iterators i and j.
The first version of the algorithm uses operator< as the default
comparison operator. It immediately returns true if it
encounters any pair in which *i is less than *j, and immediately
returns false if *j is less than *i. If the algorithm reaches the
end of the first sequence before reaching the end of the second
sequence, it also returns true.
The second version of the function takes an argument comp that
defines a comparison function that is used in place of the default
operator<.
The lexicographical_compare functions can be used with all the
datatypes provided by the standard library.
COMPLEXITY
lexicographical_compare performs at most min((last1 - first1),
(last2 - first2)) applications of the comparison
function.
EXAMPLE
//
// lex_comp.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
int d1[5] = {1,3,5,32,64};
int d2[5] = {1,3,2,43,56};
// set up vector
vector<int> v1(d1,d1 + 5), v2(d2,d2 + 5);
// Is v1 less than v2 (I think not)
bool b1 = lexicographical_compare(v1.begin(),
v1.end(), v2.begin(), v2.end());
// Is v2 less than v1 (yup, sure is)
bool b2 = lexicographical_compare(v2.begin(),
v2.end(), v1.begin(), v1.end(), less<int>());
cout << (b1 ? "TRUE" : "FALSE") << " "
<< (b2 ? "TRUE" : "FALSE") << endl;
return 0;
}
Output:
FALSE TRUE
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you'll have to write :
vector<int, allocator<int> >
instead of :
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
lower_bound
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
lower_bound - Determine the first valid position for an element in
a sorted container.
SYNOPSIS
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last,
const T& value);
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last,
const T& value, Compare comp);
DESCRIPTION
The lower_bound algorithm compares a supplied value to elements in a
sorted container and returns the first position in the container
that value can occupy without violating the container's ordering.
There are two versions of the algorithm. The first uses the
less than operator (operator<) to perform the comparison, and
assumes that the sequence has been sorted using that operator.
The second version lets you include a function object of type
Compare, and assumes that Compare is the function used to sort
the sequence. The function object must be a binary predicate.
lower_bound's return value is the iterator for the first element in
the container that is greater than or equal to value, or, when
the comparison operator is used, the first element that does not
satisfy the comparison function. Formally, the algorithm returns
an iterator i in the range [first, last) such that for any
iterator j in the range [first, i) the following corresponding
conditions hold:
*j < value
or
comp(*j, value) == true
COMPLEXITY
lower_bound performs at most log(last - first) + 1 comparisons.
EXAMPLE
//
// ul_bound.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
typedef vector<int>::iterator iterator;
int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};
// Set up a vector
vector<int> v1(d1,d1 + 11);
// Try lower_bound variants
iterator it1 = lower_bound(v1.begin(),v1.end(),3);
// it1 = v1.begin() + 4
iterator it2 =
lower_bound(v1.begin(),v1.end(),2,less<int>());
// it2 = v1.begin() + 4
// Try upper_bound variants
iterator it3 = upper_bound(v1.begin(),v1.end(),3);
// it3 = vector + 5
iterator it4 =
upper_bound(v1.begin(),v1.end(),2,less<int>());
// it4 = v1.begin() + 5
cout << endl << endl
<< "The upper and lower bounds of 3: ( "
<< *it1 << " , " << *it3 << " ]" << endl;
cout << endl << endl
<< "The upper and lower bounds of 2: ( "
<< *it2 << " , " << *it4 << " ]" << endl;
return 0;
}
Output :
The upper and lower bounds of 3: ( 3 , 4 ]
The upper and lower bounds of 2: ( 2 , 3 ]
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
SEE ALSO
upper_bound, equal_range
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
make_heap
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
make_heap - Creates a heap.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void
make_heap(RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
make_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
DESCRIPTION
A heap is a particular organization of elements in a range between
two random access iterators [a, b). Its two key properties are:
1. *a is the largest element in the range.
2. *a may be removed by the pop_heap algorithm, or a new element can be
added by the push_heap algorithm, in O(logN) time.
These properties make heaps useful as priority queues.
The heap algorithms use less than (operator<) as the default
comparison. In all of the algorithms, an alternate comparison
operator can be specified.
The first version of the make_heap algorithm arranges the elements
in the range [first, last) into a heap using less than
(operator<) to perform comparisons. The second version uses
the comparison operator comp to perform the comparisons. Since the
only requirements for a heap are the two listed above, make_heap
is not required to do anything within the range (first, last - 1).
COMPLEXITY
This algorithm makes at most 3 * (last - first) comparisons.
EXAMPLE
//
// heap_ops.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
int d1[4] = {1,2,3,4};
int d2[4] = {1,3,2,4};
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);
// Make heaps
make_heap(v1.begin(),v1.end());
make_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Note that x, y and z represent the remaining
// values in the container (other than 4).
// The definition of the heap and heap operations
// does not require any particular ordering
// of these values.
// Copy both vectors to cout
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now let's pop
pop_heap(v1.begin(),v1.end());
pop_heap(v2.begin(),v2.end(),less<int>());
// v1 = (3,x,y,4) and v2 = (3,x,y,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// And push
push_heap(v1.begin(),v1.end());
push_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now sort those heaps
sort_heap(v1.begin(),v1.end());
sort_heap(v2.begin(),v2.end(),less<int>());
// v1 = v2 = (1,2,3,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
return 0;
}
Output :
4 2 3 1
4 3 2 1
3 2 1 4
3 1 2 4
4 3 1 2
4 3 2 1
1 2 3 4
1 2 3 4
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
SEE ALSO
pop_heap, push_heap and sort_heap
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
max
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
max - Find and return the maximum of a pair of values
SYNOPSIS
#include <algorithm>
template <class T>
const T& max(const T&, const T&);
template <class T, class Compare>
const T& max(const T&, const T&, Compare);
DESCRIPTION
The max algorithm determines and returns the maximum of a pair of
values. The optional argument Compare defines a comparison function
that can be used in place of the default operator<. This
function can be used with all the datatypes provided by
the standard library.
max returns the first argument when the arguments are equal.
EXAMPLE
//
// max.cpp
//
#include <algorithm>
#include <iostream.h>
#include <iostream.h>
int main(void)
{
double d1 = 10.0, d2 = 20.0;
// Find minimum
double val1 = min(d1, d2);
// val1 = 10.0
// the greater comparator returns the greater of the
// two values.
double val2 = min(d1, d2, greater<double>());
// val2 = 20.0;
// Find maximum
double val3 = max(d1, d2);
// val3 = 20.0;
// the less comparator returns the smaller of the two values.
// Note that, like every comparison in the STL, max is
// defined in terms of the < operator, so using less here
// is the same as using the max algorithm with a default
// comparator.
double val4 = max(d1, d2, less<double>());
// val4 = 20
cout << val1 << " " << val2 << " "
<< val3 << " " << val4 << endl;
return 0;
}
Output :
10 20 20 20
SEE ALSO
max_element, min, min_element
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
max_element
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
max_element - Finds maximum value in a range.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator>
ForwardIterator
max_element(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
ForwardIterator
max_element(ForwardIterator first, ForwardIterator last,
Compare comp);
DESCRIPTION
The max_element algorithm returns an iterator that denotes the
maximum element in a sequence. If the sequence contains more
than one copy of the element, the iterator points to its first
occurrence. The optional argument comp defines a comparison
function that can be used in place of the default operator<. This
function can be used with all the datatypes provided by the
standard library.
Algorithm max_element returns the first iterator i in the range
[first, last) such that for any iterator j in the same range the
following corresponding conditions hold:
!(*i < *j)
or
comp(*i, *j) == false.
COMPLEXITY
Exactly max((last - first) - 1, 0) applications of the corresponding
comparisons are done for max_element.
EXAMPLE
//
// max_elem.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
typedef vector<int>::iterator iterator;
int d1[5] = {1,3,5,32,64};
// set up vector
vector<int> v1(d1,d1 + 5);
// find the largest element in the vector
iterator it1 = max_element(v1.begin(), v1.end());
// it1 = v1.begin() + 4
// find the largest element in the range from
// the beginning of the vector to the 2nd to last
iterator it2 = max_element(v1.begin(), v1.end()-1,
less<int>());
// it2 = v1.begin() + 3
// find the smallest element
iterator it3 = min_element(v1.begin(), v1.end());
// it3 = v1.begin()
// find the smallest value in the range from
// the beginning of the vector plus 1 to the end
iterator it4 = min_element(v1.begin()+1, v1.end(),
less<int>());
// it4 = v1.begin() + 1
cout << *it1 << " " << *it2 << " "
<< *it3 << " " << *it4 << endl;
return 0;
}
Output :
64 32 1 3
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
SEE ALSO
max, min, min_element
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
merge
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
merge - Merge two sorted sequences into a third sequence.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
merge(InputIterator first1, InputIterator1 last1,
InputIterator2 first2, InputIterator last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator last2,
OutputIterator result, Compare comp);
DESCRIPTION
The merge algorithm merges two sorted sequences, specified by
[first1, last1) and [first2, last2), into the sequence
specified by [result, result + (last1 - first1) + (last2 -
first2)). The first version of the merge algorithm uses the
less than operator (<) to compare elements in the two sequences.
The second version uses the comparison function provided by the
function call. If a comparison function is provided, merge assumes
that both sequences were sorted using that comparison function.
The merge is stable. This means that if the two original sequences
contain equivalent elements, the elements from the first sequence
will always precede the matching elements from the second in
the resulting sequence. The size of the result of a
merge is equal to the sum of the sizes of the two argument
sequences. merge returns an iterator that points to the end of the
resulting sequence, i.e., result + (last1 - first1) + (last2
-first2). The result of merge is undefined if the resulting
range overlaps with either of the original ranges.
merge assumes that there are at least (last1 - first1) + (last2 -
first2) elements following result, unless result has been adapted by
an insert iterator.
COMPLEXITY
For merge at most (last - first1) + (last2 - first2) - 1 comparisons
are performed.
EXAMPLE
//
// merge.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int d1[4] = {1,2,3,4};
int d2[8] = {11,13,15,17,12,14,16,18};
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4);
// Set up four destination vectors
vector<int> v3(d2,d2 + 8),v4(d2,d2 + 8),
v5(d2,d2 + 8),v6(d2,d2 + 8);
// Set up one empty vector
vector<int> v7;
// Merge v1 with v2
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
// Now use comparator
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v4.begin(),
less<int>());
// In place merge v5
vector<int>::iterator mid = v5.begin();
advance(mid,4);
inplace_merge(v5.begin(),mid,v5.end());
// Now use a comparator on v6
mid = v6.begin();
advance(mid,4);
inplace_merge(v6.begin(),mid,v6.end(),less<int>());
// Merge v1 and v2 to empty vector using insert iterator
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),
back_inserter(v7));
// Copy all cout
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
copy(v3.begin(),v3.end(),out);
cout << endl;
copy(v4.begin(),v4.end(),out);
cout << endl;
copy(v5.begin(),v5.end(),out);
cout << endl;
copy(v6.begin(),v6.end(),out);
cout << endl;
copy(v7.begin(),v7.end(),out);
cout << endl;
// Merge v1 and v2 to cout
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
1 2 3 4
1 2 3 4
1 1 2 2 3 3 4 4
1 1 2 2 3 3 4 4
11 12 13 14 15 16 17 18
11 12 13 14 15 16 17 18
1 1 2 2 3 3 4 4
1 1 2 2 3 3 4 4
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
SEE ALSO
Containers, inplace_merge
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
min
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
min - Find and return the minimum of a pair of values
SYNOPSIS
#include <algorithm>
template <class T>
const T& min(const T&, const T&);
template <class T, class Compare>
const T& min(const T& a, const T&, Compare);
DESCRIPTION
The min algorithm determines and returns the minimum of a pair of
values. In the second version of the algorithm, the optional
argument Compare defines a comparison function that can be
used in place of the default operator<. This function can be
used with all the datatypes provided by the standard library.
min returns the first argument when the two arguments are equal.
EXAMPLE
//
// max.cpp
//
#include <algorithm>
#include <iostream.h>
int main(void)
{
double d1 = 10.0, d2 = 20.0;
// Find minimum
double val1 = min(d1, d2);
// val1 = 10.0
// the greater comparator returns the greater of the
// two values.
double val2 = min(d1, d2, greater<double>());
// val2 = 20.0;
// Find maximum
double val3 = max(d1, d2);
// val3 = 20.0;
// the less comparator returns the smaller of the
// two values.
// Note that, like every comparison in the STL, max is
// defined in terms of the < operator, so using less here
// is the same as using the max algorithm with a default
// comparator.
double val4 = max(d1, d2, less<double>());
// val4 = 20
cout << val1 << " " << val2 << " "
<< val3 << " " << val4 << endl;
return 0;
}
Output :
10 20 20 20
SEE ALSO
max, max_element, min_element
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
min_element
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
min_element - Finds the minimum value in a range.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator>
ForwardIterator
min_element(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
InputIterator
min_element(ForwardIterator first, ForwardIterator last,
Compare comp);
DESCRIPTION
The min_element algorithm returns an iterator that denotes the
minimum element in a sequence. If the sequence contains more
than one copy of the minimum element, the iterator points to the
first occurrence of the element. In the second version of the
function, the optional argument comp defines a comparison
function that can be used in place of the default operator<.
This function can be used with all the datatypes provided by the
standard library.
Algorithm min_element returns the first iterator i in the range
[first, last) such that for any iterator j in the range same range,
the following corresponding conditions hold:
!(*j < *i)
or
comp(*j, *i) == false.
COMPLEXITY
min_element performs exactly max((last - first) - 1, 0) applications
of the corresponding comparisons.
EXAMPLE
//
// max_elem.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
typedef vector<int>::iterator iterator;
int d1[5] = {1,3,5,32,64};
// set up vector
vector<int> v1(d1,d1 + 5);
// find the largest element in the vector
iterator it1 = max_element(v1.begin(), v1.end());
// it1 = v1.begin() + 4
// find the largest element in the range from
// the beginning of the vector to the 2nd to last
iterator it2 = max_element(v1.begin(), v1.end()-1,
less<int>());
// it2 = v1.begin() + 3
// find the smallest element
iterator it3 = min_element(v1.begin(), v1.end());
// it3 = v1.begin()
// find the smallest value in the range from
// the beginning of the vector plus 1 to the end
iterator it4 = min_element(v1.begin()+1, v1.end(),
less<int>());
// it4 = v1.begin() + 1
cout << *it1 << " " << *it2 << " "
<< *it3 << " " << *it4 << endl;
return 0;
}
Output :
64 32 1 3
WARNING
If your compiler does not support default template parameters then
you need to always supply the Allocator template argument. For
instance you'll have to write:
vector<int,allocator<int> >
instead of:
vector<int>
SEE ALSO
max, max_element, min
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
mismatch
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
mismatch - Compares elements from two sequences and returns the
first two elements that don't match each other.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2>
pair<InputIterator1,InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template <class InputIterator1, class InputIterator2,
class BinaryPredicate>
pair<InputIterator1, Inputiterator2>
mismatch(InputIterator first1, InputIterator1 last1,
InputIterator2 first2,
BinaryPredicate binary_pred);
DESCRIPTION
The mismatch algorithm compares members of two sequences and returns
two iterators (i and j) that point to the first location in each
sequence where the sequences differ from each other.
Notice that the algorithm denotes both a starting position
and an ending position for the first sequence, but denotes only a
starting position for the second sequence. mismatch assumes that
the second sequence has at least as many members as the first
sequence. If the two sequences are identical, mismatch returns a
pair of iterators that point to the end of the first sequence and
the corresponding location at which the comparison stopped in
the second sequence.
The first version of mismatch checks members of a sequence for
equality, while the second version lets you specify a
comparison function. The comparison function must be a
binary predicate.
The iterators i and j returned by mismatch are defined as follows:
j == first2 + (i - first1)
and i is the first iterator in the range [first1, last1) for which the
appropriate one of the following conditions hold:
!(*i == *(first2 + (i - first1)))
or
binary_pred(*i, *(first2 + (i - first1))) == false
If all of the members in the two sequences match, mismatch returns a
pair of last1 and first2 + (last1 - first1).
COMPLEXITY
At most last1 - first1 applications of the corresponding predicate
are done.
EXAMPLE
//
// mismatch.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
typedef vector<int>::iterator iterator;
int d1[4] = {1,2,3,4};
int d2[4] = {1,3,2,4};
// Set up two vectors
vector<int> vi1(d1,d1 + 4), vi2(d2,d2 + 4);
// p1 will contain two iterators that point to the
// first pair of elements that are different between
// the two vectors
pair<iterator, iterator> p1 = mismatch(vi1.begin(), vi1.end(),
vi2.begin());
// find the first two elements such that an element in the
// first vector is greater than the element in the second
// vector.
pair<iterator, iterator> p2 = mismatch(vi1.begin(), vi1.end(),
vi2.begin(),
less_equal<int>());
// Output results
cout << *p1.first << ", " << *p1.second << endl;
cout << *p2.first << ", " << *p2.second << endl;
return 0;
}
Output :
2, 3
3, 2
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of:
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
next_permutation
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
next_permutation - Generate successive permutations of a sequence
based on an ordering function.
SYNOPSIS
#include <algorithm>
template <class BidirectionalIterator>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
DESCRIPTION
The permutation-generating algorithms (next_permutation and
prev_permutation) assume that the set of all permutations of the
elements in a sequence is lexicographically sorted with
respect to operator< or comp. So, for example, if a sequence
includes the integers 1 2 3, that sequence has six
permutations, which, in order from first to last are: 1 2 3 , 1
3 2, 2 1 3, 2 3 1, 3 1 2, and 3 2 1.
The next_permutation algorithm takes a sequence defined by the range
[first, last) and transforms it into its next permutation, if
possible. If such a permutation does exist, the algorithm completes
the transformation and returns true. If the permutation does
not exist, next_permutation returns false, and transforms the
permutation into its "first" permutation (according to the
lexicographical ordering defined by either operator<, the default
used in the first version of the algorithm, or comp, which is
user-supplied in the second version of the algorithm.)
For example, if the sequence defined by [first, last) contains the
integers 3 2 1 (in that order), there is not a "next
permutation." Therefore, the algorithm transforms the sequence
into its first permutation (1 2 3) and returns false.
COMPLEXITY
At most (last - first)/2 swaps are performed.
EXAMPLE
//
// permute.cpp
//
#include <numeric> //for accumulate
#include <vector> //for vector
#include <functional> //for less
#include <iostream.h>
int main()
{
//Initialize a vector using an array of ints
int a1[] = {0,0,0,0,1,0,0,0,0,0};
char a2[] = "abcdefghji";
//Create the initial set and copies for permuting
vector<int> m1(a1, a1+10);
vector<int> prev_m1((size_t)10), next_m1((size_t)10);
vector<char> m2(a2, a2+10);
vector<char> prev_m2((size_t)10), next_m2((size_t)10);
copy(m1.begin(), m1.end(), prev_m1.begin());
copy(m1.begin(), m1.end(), next_m1.begin());
copy(m2.begin(), m2.end(), prev_m2.begin());
copy(m2.begin(), m2.end(), next_m2.begin());
//Create permutations
prev_permutation(prev_m1.begin(),
prev_m1.end(),less<int>());
next_permutation(next_m1.begin(),
next_m1.end(),less<int>());
prev_permutation(prev_m2.begin(),
prev_m2.end(),less<int>());
next_permutation(next_m2.begin(),
next_m2.end(),less<int>());
//Output results
cout << "Example 1: " << endl << " ";
cout << "Original values: ";
copy(m1.begin(),m1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << " ";
cout << "Previous permutation: ";
copy(prev_m1.begin(),prev_m1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl<< " ";
cout << "Next Permutation: ";
copy(next_m1.begin(),next_m1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "Example 2: " << endl << " ";
cout << "Original values: ";
copy(m2.begin(),m2.end(),
ostream_iterator<char,char>(cout," "));
cout << endl << " ";
cout << "Previous Permutation: ";
copy(prev_m2.begin(),prev_m2.end(),
ostream_iterator<char,char>(cout," "));
cout << endl << " ";
cout << "Next Permutation: ";
copy(next_m2.begin(),next_m2.end(),
ostream_iterator<char,char>(cout," "));
cout << endl << endl;
return 0;
}
Output :
Example 1:
Original values: 0 0 0 0 1 0 0 0 0 0
Previous permutation: 0 0 0 0 0 1 0 0 0 0
Next Permutation: 0 0 0 1 0 0 0 0 0 0
Example 2:
Original values: a b c d e f g h j i
Previous Permutation: a b c d e f g h i j
Next Permutation: a b c d e f g i h j
WARNING
If your compiler does not support default template parameters, the
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
prev_permutation
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
nth_element
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
nth_element - Rearranges a collection so that all elements lower in sorted
order than the nth element come before it and all elements higher in sorter
order than the nth element come after it.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void nth_element (RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void nth_element (RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last,
Compare comp);
DESCRIPTION
The nth_element algorithm rearranges a collection according to
either the default comparison operator (>) or the provided
comparison operator. After the algorithm applies, three things
are true:
+ The element that would be in the nth position if the
collection were completely sorted is in the nth position
+ All elements prior to the nth position would precede that
position in an ordered collection
+ All elements following the nth position would follow that
position in an ordered collection
That is, for any iterator i in the range [first, nth) and any
iterator j in the range [nth, last) it holds that !(*i > *j) or
comp(*i, *j) == false.
Note that the elements that precede or follow the nth position are
not necessarily sorted relative to each other. The nth_element
algorithm does not sort the entire collection.
COMPLEXITY
The algorithm is linear, on average, where N is the size of the range
[first, last).
EXAMPLE
//
// nthelem.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
template<class RandomAccessIterator>
void quik_sort(RandomAccessIterator start,
RandomAccessIterator end)
{
size_t dist = 0;
distance(start, end, dist);
//Stop condition for recursion
if(dist > 2)
{
//Use nth_element to do all the work for quik_sort
nth_element(start, start+(dist/2), end);
//Recursive calls to each remaining unsorted portion
quik_sort(start, start+(dist/2-1));
quik_sort(start+(dist/2+1), end);
}
if(dist == 2 && *end < *start)
swap(start, end);
}
int main()
{
//Initialize a vector using an array of ints
int arr[10] = {37, 12, 2, -5, 14, 1, 0, -1, 14, 32};
vector<int> v(arr, arr+10);
//Print the initial vector
cout << "The unsorted values are: " << endl << " ";
vector<int>::iterator i;
for(i = v.begin(); i != v.end(); i++)
cout << *i << ", ";
cout << endl << endl;
//Use the new sort algorithm
quik_sort(v.begin(), v.end());
//Output the sorted vector
cout << "The sorted values are: " << endl << " ";
for(i = v.begin(); i != v.end(); i++)
cout << *i << ", ";
cout << endl << endl;
return 0;
}
Output :
The unsorted values are:
37, 12, 2, -5, 14, 1, 0, -1, 14, 32,
The sorted values are:
-5, -1, 0, 1, 2, 12, 14, 14, 32, 37,
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
Algorithms
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
partial_sort
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
partial_sort - Templated algorithm for sorting collections of
entities.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void partial_sort (RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void partial_sort (RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
DESCRIPTION
The partial_sort algorithm takes the range [first,last) and places
the first middle - first values into sorted order. The result
is that the range [first, middle)is sorted like it would be if
the entire range [first,last) were sorted. The remaining
elements in the range (those in [middle, last)) are not in any
defined order. The first version of the algorithm uses less
than (operator<) as the comparison operator for the sort. The
second version uses the comparison function comp.
COMPLEXITY
partial_sort does approximately (last - first) * log(middle-first)
comparisons.
EXAMPLE
//
// partsort.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
int d1[20] = {17, 3, 5, -4, 1, 12, -10, -1, 14, 7,
-6, 8, 15, -11, 2, -2, 18, 4, -3, 0};
//
// Set up a vector.
//
vector<int> v1(d1+0, d1+20);
//
// Output original vector.
//
cout << "For the vector: ";
copy(v1.begin(), v1.end(),
ostream_iterator<int,char>(cout," "));
//
// Partial sort the first seven elements.
//
partial_sort(v1.begin(), v1.begin()+7, v1.end());
//
// Output result.
//
cout << endl << endl << "A partial_sort of seven elements
gives: "
<< endl << " ";
copy(v1.begin(), v1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
//
// A vector of ten elements.
//
vector<int> v2(10, 0);
//
// Sort the last ten elements in v1 into v2.
//
partial_sort_copy(v1.begin()+10, v1.end(), v2.begin(),
v2.end());
//
// Output result.
//
cout << endl << "A partial_sort_copy of the last ten elements
gives: "
<< endl << " ";
copy(v2.begin(), v2.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
For the vector: 17 3 5 -4 1 12 -10 -1 14 7 -6 8 15 -11 2 -2 18 4 -3 0
A partial_sort of seven elements gives:
-11 -10 -6 -4 -3 -2 -1 17 14 12 7 8 15 5 3 2 18 4 1 0
A partial_sort_copy of the last ten elements gives:
0 1 2 3 4 5 7 8 15 18
WARNING
If your compiler does not support default template parameters, then
you need to always provide the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
sort, stable_sort, partial_sort_copy
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
partial_sort_copy
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
partial_sort_copy - Templated algorithm for sorting collections of
entities.
SYNOPSIS
#include <algorithm>
template <class InputIterator,
class RandomAccessIterator>
void partial_sort_copy (InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template <class InputIterator,
class RandomAccessIterator,
class Compare>
void partial_sort_copy (InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
DESCRIPTION
The partial_sort_copy algorithm places the smaller of last - first
and result_last - result_first sorted elements from the range
[first, last) into the range beginning at result_first. (i.e., the
range: [result_first, result_first+min(last - first, result_last -
result_first)). Basically, the effect is as if the
range [first,last) were placed in a temporary buffer, sorted and
then as many elements as possible were copied into the range
[result_first, result_last).
The first version of the algorithm uses less than (operator<) as the
comparison operator for the sort. The second version uses the
comparison function comp.
COMPLEXITY
partial_sort_copy does approximately (last-first) * log(min(last-first,
result_last-result_first)) comparisons.
EXAMPLE
//
// partsort.cpp
// #include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
int d1[20] = {17, 3, 5, -4, 1, 12, -10, -1, 14, 7,
-6, 8, 15, -11, 2, -2, 18, 4, -3, 0};
//
// Set up a vector.
//
vector<int> v1(d1+0, d1+20);
//
// Output original vector.
//
cout << "For the vector: ";
copy(v1.begin(), v1.end(), ostream_iterator<int>(cout," "));
//
// Partial sort the first seven elements.
//
partial_sort(v1.begin(), v1.begin()+7, v1.end());
//
// Output result.
//
cout << endl << endl << "A partial_sort of 7 elements gives: "
<< endl << " ";
copy(v1.begin(), v1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
//
// A vector of ten elements.
//
vector<int> v2(10, 0);
//
// Sort the last ten elements in v1 into v2.
//
partial_sort_copy(v1.begin()+10, v1.end(), v2.begin(),
v2.end());
//
// Output result.
//
cout << endl << "A partial_sort_copy of the last ten elements
gives: " << endl << " ";
copy(v2.begin(), v2.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
For the vector: 17 3 5 -4 1 12 -10 -1 14 7 -6 8 15 -11 2 -2 18 4 -3 0
A partial_sort of seven elements gives:
-11 -10 -6 -4 -3 -2 -1 17 14 12 7 8 15 5 3 2 18 4 1 0
A partial_sort_copy of the last ten elements gives:
0 1 2 3 4 5 7 8 15 18
WARNING
If your compiler does not support default template parameters, then
you need to always provide the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
sort_ stable_sort, partial_sort
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
partial_sum
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
partial_sum - Calculates successive partial sums of a range of values.
SYNOPSIS
#include <numeric>
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum (InputIterator first,
InputIterator last,
OutputIterator result);
template <class InputIterator,
class OutputIterator,
class BinaryOperation>
OutputIterator partial_sum (InputIterator first,
InputIterator last,
OutputIterator result,
BinaryOperation binary_op);
DESCRIPTION
The partial_sum algorithm creates a new sequence in which every
element is formed by adding all the values of the previous elements,
or, in the second form of the algorithm, applying the operation
binary_op successively on every previous element. That is,
partial_sum assigns to every iterator i in the range [result,
result + (last - first)) a value equal to:
((...(*first + *(first + 1)) + ... ) + *(first + (i - result)))
or, in the second version of the algorithm:
binary_op(binary_op(..., binary_op (*first, *(first +
1)),...),*(first + (i - result)))
For instance, applying partial_sum to (1,2,3,4,) will yield
(1,3,6,10).
The partial_sum algorithm returns result + (last - first).
If result is equal to first, the elements of the new sequence
successively replace the elements in the original sequence,
effectively turning partial_sum into an inplace transformation.
COMPLEXITY
Exactly (last - first) - 1 applications of the default + operator or
binary_op are performed.
EXAMPLE
//
// partsum.cpp
//
#include <numeric> //for accumulate
#include <vector> //for vector
#include <functional> //for times
#include <iostream.h>
int main()
{
//Initialize a vector using an array of ints
int d1[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(d1, d1+10);
//Create an empty vectors to store results
vector<int> sums((size_t)10), prods((size_t)10);
//Compute partial_sums and partial_products
partial_sum(v.begin(), v.end(), sums.begin());
partial_sum(v.begin(), v.end(), prods.begin(), times<int>());
//Output the results
cout << "For the series: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "The partial sums: " << endl << " " ;
copy(sums.begin(),sums.end(),
ostream_iterator<int,char>(cout," "));
cout <<" should each equal (N*N + N)/2" << endl << endl;
cout << "The partial products: " << endl << " ";
copy(prods.begin(),prods.end(),
ostream_iterator<int,char>(cout," "));
cout << " should each equal N!" << endl;
return 0;
}
Output :
For the series:
1 2 3 4 5 6 7 8 9 10
The partial sums:
1 3 6 10 15 21 28 36 45 55 should each equal (N*N + N)/2
The partial products:
1 2 6 24 120 720 5040 40320 362880 3628800 should each equal N!
WARNING
If your compiler does not support default template parameters, then
you need to always provide the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
partition
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
partition - Places all of the entities that satisfy the given
predicate before all of the entities that do not.
SYNOPSIS
#include <algorithm>
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator
partition (BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
DESCRIPTION
The partition algorithm places all the elements in the range [first,
last) that satisfy pred before all the elements that do not
satisfy pred. It returns an iterator that is one past the end
of the group of elements that satisfy pred. In other
words, partition returns i such that for any itera- tor j in the
range[first, i), pred(*j) == true, and, for any iterator k in
the range [i, last), pred(*j) == false.
Note that partition does not necessarily maintain the relative order
of the elements that match and elements that do not match the
predicate. Use the algorithm stable_partition if relative order
is important.
COMPLEXITY
The partition algorithm does at most (last - first)/2 swaps, and
applies the predicate exactly last - first times.
EXAMPLE
//
// prtition.cpp
//
#include <functional>
#include <deque>
#include <algorithm>
#include <iostream.h>
//
// Create a new predicate from unary_function.
//
template<class Arg>
class is_even : public unary_function<Arg, bool>
{
public:
bool operator()(const Arg& arg1) { return (arg1 % 2) == 0; }
};
int main ()
{
//
// Initialize a deque with an array of integers.
//
int init[10] = { 1,2,3,4,5,6,7,8,9,10 };
deque<int> d1(init+0, init+10);
deque<int> d2(init+0, init+10);
//
// Print out the original values.
//
cout << "Unpartitioned values: " << "";
copy(d1.begin(), d1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
//
// A partition of the deque according to even/oddness.
//
partition(d2.begin(), d2.end(), is_even<int>());
//
// Output result of partition.
//
cout << "Partitioned values: " << "";
copy(d2.begin(), d2.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
//
// A stable partition of the deque according to even/oddness.
//
stable_partition(d1.begin(), d1.end(), is_even<int>());
//
// Output result of partition.
//
cout << "Stable partitioned values: " << "";
copy(d1.begin(), d1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
Unpartitioned values: 1 2 3 4 5 6 7 8 9 10
Partitioned values: 10 2 8 4 6 5 7 3 9 1
Stable partitioned values: 2 4 6 8 10 1 3 5 7 9
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you need to write :
deque<int, allocator<int> >
instead of :
deque<int>
SEE ALSO
stable_partition
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
permutation
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
permutation - Generate successive permutations of a sequence based
on an ordering function.
See the entries for next_permutation and prev_permutation.
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
pop_heap
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
pop_heap - Moves the largest element off the heap.
SYNOPSIS
template <class RandomAccessIterator>
void
pop_heap(RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
pop_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
DESCRIPTION
A heap is a particular organization of elements in a range between
two random access iterators [a, b). Its two key properties are:
1. *a is the largest element in the range.
2. *a may be removed by the pop_heap algorithm or a new element added
by the push_heap algorithm, in O(logN) time.
These properties make heaps useful as priority queues.
The pop_heap algorithm uses the less than (<) operator as the
default comparison. An alternate comparison operator can be
specified.
The pop_heap algorithm can be used as part of an operation to remove
the largest element from a heap. It assumes that the range
[first, last) is a valid heap (i.e., that first is the largest
element in the heap or the first element based on the alternate
comparison operator). It then swaps the value in the location first
with the value in the location last - 1 and makes [first, last
-1)back into a heap. You can then access the element in last
using the vector or deque back() member function, or remove the
element using the pop_back member function. Note that pop_heap does
not actually remove the element from the data structure, you must
use another function to do that.
COMPLEXITY
pop_heap performs at most 2 * log(last - first) comparisons.
EXAMPLE
//
// heap_ops.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
int d1[4] = {1,2,3,4};
int d2[4] = {1,3,2,4};
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);
// Make heaps
make_heap(v1.begin(),v1.end());
make_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Note that x, y and z represent the remaining
// values in the container (other than 4).
// The definition of the heap and heap operations
// does not require any particular ordering
// of these values.
// Copy both vectors to cout
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now let's pop
pop_heap(v1.begin(),v1.end());
pop_heap(v2.begin(),v2.end(),less<int>());
// v1 = (3,x,y,4) and v2 = (3,x,y,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// And push
push_heap(v1.begin(),v1.end());
push_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now sort those heaps
sort_heap(v1.begin(),v1.end());
sort_heap(v2.begin(),v2.end(),less<int>());
// v1 = v2 = (1,2,3,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
return 0;
}
Output :
4 2 3 1
4 3 2 1
3 2 1 4
3 1 2 4
4 3 1 2
4 3 2 1
1 2 3 4
1 2 3 4
WARNING
If your compiler does not support default template parameters, you
need to always supply the Allocator template argument. For
instance, you need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
make_heap, push_heap, sort_heap
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
prev_permutation
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
prev_permutation - Generate successive permutations of a sequence
based on an ordering function.
SYNOPSIS
#include <algorithm>
template <class BidirectionalIterator>
bool prev_permutation (BidirectionalIterator first,
BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
bool prev_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
DESCRIPTION
The permutation-generating algorithms (next_permutation and
prev_permutation) assume that the set of all permutations of the
elements in a sequence is lexicographically sorted with
respect to operator< or comp. So, for example, if a sequence
includes the integers 1 2 3, that sequence has six
permutations, which, in order from first to last, are: 1 2 3 ,
1 3 2, 2 1 3, 2 3 1, 3 1 2, and 3 2 1.
The prev_permutation algorithm takes a sequence defined by the range
[first, last) and transforms it into its previous permutation, if
possible. If such a permutation does exist, the algorithm
completes the transformation and returns true. If the permutation
does not exist, prev_permutation returns false, and transforms
the permutation into its "last" permutation (according to
the lexicographical ordering defined by either operator <, the
default used in the first version of the algorithm, or comp,
which is user-supplied in the second version of the
algorithm.)
For example, if the sequence defined by [first, last) contains the
integers 1 2 3 (in that order), there is not a "previous
permutation." Therefore, the algorithm transforms the
sequence into its last permutation (3 2 1) and returns false.
COMPLEXITY
At most (last - first)/2 swaps are performed.
EXAMPLE
//
// permute.cpp
//
#include <numeric> //for accumulate
#include <vector> //for vector
#include <functional> //for less
#include <iostream.h>
int main()
{
//Initialize a vector using an array of ints
int a1[] = {0,0,0,0,1,0,0,0,0,0};
char a2[] = "abcdefghji";
//Create the initial set and copies for permuting
vector<int> m1(a1, a1+10);
vector<int> prev_m1((size_t)10), next_m1((size_t)10);
vector<char> m2(a2, a2+10);
vector<char> prev_m2((size_t)10), next_m2((size_t)10);
copy(m1.begin(), m1.end(), prev_m1.begin());
copy(m1.begin(), m1.end(), next_m1.begin());
copy(m2.begin(), m2.end(), prev_m2.begin());
copy(m2.begin(), m2.end(), next_m2.begin());
//Create permutations
prev_permutation(prev_m1.begin(),
prev_m1.end(),less<int>());
next_permutation(next_m1.begin(),
next_m1.end(),less<int>());
prev_permutation(prev_m2.begin(),
prev_m2.end(),less<int>());
next_permutation(next_m2.begin(),
next_m2.end(),less<int>());
//Output results
cout << "Example 1: " << endl << " ";
cout << "Original values: ";
copy(m1.begin(),m1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << " ";
cout << "Previous permutation: ";
copy(prev_m1.begin(),prev_m1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl<< " ";
cout << "Next Permutation: ";
copy(next_m1.begin(),next_m1.end(),
ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "Example 2: " << endl << " ";
cout << "Original values: ";
copy(m2.begin(),m2.end(),
ostream_iterator<char,char>(cout," "));
cout << endl << " ";
cout << "Previous Permutation: ";
copy(prev_m2.begin(),prev_m2.end(),
ostream_iterator<char,char>(cout," "));
cout << endl << " ";
cout << "Next Permutation: ";
copy(next_m2.begin(),next_m2.end(),
ostream_iterator<char,char>(cout," "));
cout << endl << endl;
return 0;
}
Output :
Example 1:
Original values: 0 0 0 0 1 0 0 0 0 0
Previous permutation: 0 0 0 0 0 1 0 0 0 0
Next Permutation: 0 0 0 1 0 0 0 0 0 0
Example 2:
Original values: a b c d e f g h j i
Previous Permutation: a b c d e f g h i j
Next Permutation: a b c d e f g i h j
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
next_permutation
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
push_heap
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
push_heap - Places a new element into a heap.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void
push_heap(RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
push_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
DESCRIPTION
A heap is a particular organization of elements in a range between
two random access iterators [a, b). Its two key properties are:
1. *a is the largest element in the range.
2. *a may be removed by the pop_heap algorithm, or a new element
added by the push_heap algorithm, in O(logN) time.
These properties make heaps useful as priority queues.
The push_heap algorithms uses the less than (<) operator as the
default comparison. As with all of the heap manipulation
algorithms, an alternate comparison function can be specified.
The push_heap algorithm is used to add a new element to the heap.
First, a new element for the heap is added to the end of a range.
(For example, you can use the vector or deque member function
push_back()to add the element to the end of either of
those containers.) The push_heap algorithm assumes that the range
[first, last - 1) is a valid heap. It then properly posi-
tions the element in the location last - 1 into its proper position
in the heap, resulting in a heap over the range [first, last).
Note that the push_heap algorithm does not place an element into the
heap's underlying container. You must user another function to add
the element to the end of the container before applying push_heap.
COMPLEXITY
For push_heap at most log(last - first) comparisons are performed.
EXAMPLE
//
// heap_ops.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
int d1[4] = {1,2,3,4};
int d2[4] = {1,3,2,4};
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);
// Make heaps
make_heap(v1.begin(),v1.end());
make_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Note that x, y and z represent the remaining
// values in the container (other than 4).
// The definition of the heap and heap operations
// does not require any particular ordering
// of these values.
// Copy both vectors to cout
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now let's pop
pop_heap(v1.begin(),v1.end());
pop_heap(v2.begin(),v2.end(),less<int>());
// v1 = (3,x,y,4) and v2 = (3,x,y,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// And push
push_heap(v1.begin(),v1.end());
push_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now sort those heaps
sort_heap(v1.begin(),v1.end());
sort_heap(v2.begin(),v2.end(),less<int>());
// v1 = v2 = (1,2,3,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
return 0;
}
Output :
4 2 3 1
4 3 2 1
3 2 1 4
3 1 2 4
4 3 1 2
4 3 2 1
1 2 3 4
1 2 3 4
WARNING
If your compiler does not support default template parameters, you
need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
make_heap, pop_heap, sort_heap
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
random_shuffle
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
random_shuffle - Randomly shuffles elements of a collection.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void random_shuffle (RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator,
class RandomNumberGenerator>
void random_shuffle (RandomAccessIterator first,
RandomAccessIterator last,
RandomNumberGenerator& rand);
DESCRIPTION
The random_shuffle algorithm shuffles the elements in the range
[first, last) with uniform distribution. random_shuffle can take a
particular random number generating function object rand ,
where rand takes a positive argument n of distance type
of the RandomAccessIterator and returns a randomly chosen
value between 0 and n - 1.
COMPLEXITY
In the random_shuffle algorithm, (last - first) -1 swaps are done.
EXAMPLE
//
// rndshufl.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
//Initialize a vector with an array of ints
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr, arr+10);
//Print out elements in original (sorted) order
cout << "Elements before random_shuffle: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Mix them up with random_shuffle
random_shuffle(v.begin(), v.end());
//Print out the mixed up elements
cout << "Elements after random_shuffle: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
Elements before random_shuffle:
1 2 3 4 5 6 7 8 9 10
Elements after random_shuffle:
7 9 10 3 2 5 4 8 1 6
WARNING
If your compiler does not support default template parameters, you
need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
remove
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
remove - Move desired elements to the front of a container, and
return an iterator that describes where the sequence of
desired elements ends.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class T>
ForwardIterator
remove (ForwardIterator first,
ForwardIterator last,
const T& value);
DESCRIPTION
The remove algorithm eliminates all the elements referred to by
iterator i in the range [first, last) for which the following
condition holds: *i == value. remove returns an iterator that
designates the end of the resulting range. remove is
stable, that is, the relative order of the elements that are
not removed is the same as their relative order in the original
range.
remove does not actually reduce the size of the sequence. It
actually operates by: 1) copying the values that are to be retained
to the front of the sequence, and 2) returning an iterator that
describes where the sequence of retained values ends. Elements that
are after this iterator are simply the original sequence values,
left unchanged. Here's a simple example:
Say we want to remove all values of "2" from the following sequence:
354621271
Applying the remove algorithm results in the following sequence:
3546171|XX
The vertical bar represents the position of the iterator returned by
remove. Note that the elements to the left of the vertical bar are
the original sequence with the "2's" removed.
If you want to actually delete items from the container, use the
following technique:
container.erase(remove(first,last,value),container.end());
COMPLEXITY
Exactly last1 - first1 applications of the corresponding predicate are
done.
EXAMPLE
//
// remove.cpp
//
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
template<class Arg>
struct all_true : public unary_function<Arg, bool>
{
bool operator()(const Arg& x){ return 1; }
};
int main ()
{
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr, arr+10);
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
// remove the 7
vector<int>::iterator result =
remove(v.begin(), v.end(), 7);
// delete dangling elements from the vector
v.erase(result, v.end());
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
// remove everything beyond the fourth element
result = remove_if(v.begin()+4,
v.begin()+8, all_true<int>());
// delete dangling elements
v.erase(result, v.end());
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
return 0;
}
Output :
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 8 9 10
1 2 3 4
1 2 4
WARNING
If your compiler does not support default template parameters, you
need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
remove_if, remove_copy, remove_copy_if
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
remove_copy
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
remove_copy - Move desired elements to the front of a container,
and return an iterator that describes where the sequence of desired
elements ends.
SYNOPSIS
#include <algorithm>
template <class InputIterator,
class OutputIterator,
class T>
OutputIterator remove_copy (InputIterator first,
InputIterator last,
OutputIterator result,
const T& value);
DESCRIPTION
The remove_copy algorithm copies all the elements referred to by the
iterator i in the range [first, last) for which the following
corresponding condition does not hold: *i == value.
remove_copy returns the end of the resulting range.
remove_copy is stable, that is, the relative order of the elements
in the resulting range is the same as their relative order in the
original range. The elements in the original sequence are not
altered by remove_copy.
COMPLEXITY
Exactly last1 - first1 applications of the corresponding predicate are
done.
EXAMPLE
//
// remove.cpp
//
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
template<class Arg>
struct all_true : public unary_function<Arg, bool>
{
bool operator() (const Arg&) { return 1; }
};
int main ()
{
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr+0, arr+10);
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Remove the 7.
//
vector<int>::iterator result = remove(v.begin(), v.end(), 7);
//
// Delete dangling elements from the vector.
//
v.erase(result, v.end());
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Remove everything beyond the fourth element.
//
result = remove_if(v.begin()+4, v.begin()+8, all_true<int>());
//
// Delete dangling elements.
//
v.erase(result, v.end());
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Now remove all 3s on output.
//
remove_copy(v.begin(), v.end(),
ostream_iterator<int,char>(cout," "), 3);
cout << endl << endl;
//
// Now remove everything satisfying predicate on output.
// Should yield a NULL vector.
//
remove_copy_if(v.begin(), v.end(),
ostream_iterator<int,char>(cout," "),
all_true<int>());
return 0;
}
Output :
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 8 9 10
1 2 3 4
1 2 4
WARNING
If your compiler does not support default template parameters, you
need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
remove, remove_if, remove_copy_if
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
remove_copy_if
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
remove_copy_if - Move desired elements to the front of a container,
and return an iterator that describes where the sequence of desired
elements ends.
SYNOPSIS
#include <algorithm>
template <class InputIterator,
class OutputIterator,
class Predicate>
OutputIterator remove_copy_if (InputIterator first,
InputIterator last,
OutputIterator result,
Predicate pred);
DESCRIPTION
The remove_copy_if algorithm copies all the elements referred to by
the iterator i in the range [first, last) for which the
following condition does not hold: pred(*i) == true.
remove_copy_if returns the end of the resulting range.
remove_copy_if is stable, that is, the relative order of the
elements in the resulting range is the same as their relative
order in the original range.
COMPLEXITY
Exactly last1 - first1 applications of the corresponding predicate are
done.
EXAMPLE
//
// remove.cpp
//
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
template<class Arg>
struct all_true : public unary_function<Arg, bool>
{
bool operator() (const Arg&) { return 1; }
};
int main ()
{
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr+0, arr+10);
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Remove the 7.
//
vector<int>::iterator result = remove(v.begin(), v.end(), 7);
//
// Delete dangling elements from the vector.
//
v.erase(result, v.end());
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Remove everything beyond the fourth element.
//
result = remove_if(v.begin()+4, v.begin()+8, all_true<int>());
//
// Delete dangling elements.
//
v.erase(result, v.end());
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Now remove all 3s on output.
//
remove_copy(v.begin(), v.end(),
ostream_iterator<int>(cout," "), 3);
cout << endl << endl;
//
// Now remove everything satisfying predicate on output.
// Should yield a NULL vector.
//
remove_copy_if(v.begin(), v.end(),
ostream_iterator<int,char>(cout," "),
all_true<int>());
return 0;
}
Output :
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 8 9 10
1 2 3 4
1 2 4
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
remove, remove_if, remove_copy
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
remove_if
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
remove_if - Move desired elements to the front of a container, and
return an iterator that describes where the sequence of desired
elements ends.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class Predicate>
ForwardIterator remove_if (ForwardIterator first,
ForwardIterator last,
Predicate pred);
DESCRIPTION
The remove_if algorithm eliminates all the elements referred to by
iterator i in the range [first, last) for which the following
corresponding condition holds: pred(*i) == true. remove_if
returns the end of the resulting range. remove_if is stable, that
is, the relative order of the elements that are not removed is the
same as their relative order in the original range.
remove_if does not actually reduce the size of the sequence. It
actually operates by: 1) copying the values that are to be retained
to the front of the sequence, and 2) returning an iterator that
describes where the sequence of retained values ends. Elements that
are after this iterator are simply the original sequence values,
left unchanged. Here's a simple example:
Say we want to remove all even numbers from the following sequence:
123456789
Applying the remove_if algorithm results in the following sequence:
13579|XXXX
The vertical bar represents the position of the iterator returned by
remove_if. Note that the elements to the left of the vertical bar
are the original sequence with the even numbers removed. The
elements to the right of the bar are simply the untouched
original members of the original sequence.
If you want to actually delete items from the container, use the following
technique:
container.erase(remove(first,last,value),container.end());
COMPLEXITY
Exactly last1 - first1 applications of the corresponding predicate are
done.
EXAMPLE
//
// remove.cpp
//
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
template<class Arg>
struct all_true : public unary_function<Arg, bool>
{
bool operator()(const Arg& x){ return 1; }
};
int main ()
{
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr, arr+10);
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
// remove the 7
vector<int>::iterator result =
remove(v.begin(), v.end(), 7);
// delete dangling elements from the vector
v.erase(result, v.end());
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
// remove everything beyond the fourth element
result = remove_if(v.begin()+4,
v.begin()+8, all_true<int>());
// delete dangling elements
v.erase(result, v.end());
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
return 0;
}
Output :
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 8 9 10
1 2 3 4
1 2 4
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
remove, remove_copy, remove_copy_if
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
replace
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
replace - Substitutes elements stored in a collection with new
values.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class T>
void replace (ForwardIterator first,
ForwardIterator last,
const T& old_value,
const T& new_value);
DESCRIPTION
The replace algorithm replaces elements referred to by iterator i in
the range [first, last) with new_value when the following
condition holds: *i == old_value
COMPLEXITY
Exactly last - first comparisons or applications of the
corresponding predicate are done.
EXAMPLE
//
// replace.cpp
//
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
template<class Arg>
struct all_true : public unary_function<Arg, bool>
{
bool operator()(const Arg&){ return 1; }
};
int main()
{
//Initialize a vector with an array of integers
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr, arr+10);
//Print out original vector
cout << "The original list: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Replace the number 7 with 11
replace(v.begin(), v.end(), 7, 11);
// Print out vector with 7 replaced,
// s.b. 1 2 3 4 5 6 11 8 9 10
cout << "List after replace " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Replace 1 2 3 with 13 13 13
replace_if(v.begin(), v.begin()+3, all_true<int>(), 13);
// Print out the remaining vector,
// s.b. 13 13 13 4 5 6 11 8 9 10
cout << "List after replace_if " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
return 0;
}
Output :
The original list:
1 2 3 4 5 6 7 8 9 10
List after replace:
1 2 3 4 5 6 11 8 9 10
List after replace_if:
13 13 13 4 5 6 11 8 9 10
List using replace_copy to cout:
17 17 17 4 5 6 11 8 9 10
List with all elements output as 19s:
19 19 19 19 19 19 19 19 19 19
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
replace_if, replace_copy, replace_copy_if
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
replace_copy
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
replace_copy - Substitutes elements stored in a collection with new
values.
SYNOPSIS
#include <algorithm>
template <class InputIterator,
class OutputIterator,
class T>
OutputIterator replace_copy (InputIterator first,
InputIterator last,
OutputIterator result,
const T& old_value,
const T& new_value);
DESCRIPTION
The replace_copy algorithm leaves the original sequence intact and
places the revised sequence into result. The algorithm compares
elements referred to by iterator i in the range [first, last)
with old_value. If *i does not equal old_value, then the
replace_copy copies *i to result+(first-i). If *i==old_value,
then replace_copy copies new_value to result+(first-i). replace_copy
returns result+(last-first).
COMPLEXITY
Exactly last - first comparisons between values are done.
EXAMPLE
//
// replace.cpp
//
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
template<class Arg>
struct all_true : public unary_function<Arg, bool>
{
bool operator() (const Arg&) { return 1; }
};
int main ()
{
//
// Initialize a vector with an array of integers.
//
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
vector<int> v(arr+0, arr+10);
//
// Print out original vector.
//
cout << "The original list: " << endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Replace the number 7 with 11.
//
replace(v.begin(), v.end(), 7, 11);
//
// Print out vector with 7 replaced.
//
cout << "List after replace:" << endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Replace 1 2 3 with 13 13 13.
//
replace_if(v.begin(), v.begin()+3, all_true<int>(), 13);
//
// Print out the remaining vector.
//
cout << "List after replace_if:" << endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Replace those 13s with 17s on output.
//
cout << "List using replace_copy to cout:" << endl << " ";
replace_copy(v.begin(), v.end(),
ostream_iterator<int,char>(cout, " "), 13, 17);
cout << endl << endl;
//
// A simple example of replace_copy_if.
//
cout << "List w/ all elements output as 19s:" << endl << " ";
replace_copy_if(v.begin(), v.end(),
ostream_iterator<int,char>(cout, " "),
all_true<int>(), 19);
cout << endl;
return 0;
}
Output :
The original list:
1 2 3 4 5 6 7 8 9 10
List after replace:
1 2 3 4 5 6 11 8 9 10
List after replace_if:
13 13 13 4 5 6 11 8 9 10
List using replace_copy to cout:
17 17 17 4 5 6 11 8 9 10
List with all elements output as 19s:
19 19 19 19 19 19 19 19 19 19
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
replace, replace_if, replace_copy_if
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
replace_copy_if
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
replace_copy_if - Substitutes elements stored in a collection with
new values.
SYNOPSIS
#include <algorithm>
template <class InputIterator,
class OutputIterator,
class Predicate,
class T>
OutputIterator replace_copy_if (InputIterator first,
InputIterator last,
OutputIterator result,
Predicate pred,
const T& new_value);
DESCRIPTION
The replace_copy_if algorithm leaves the original sequence intact
and places a revised sequence into result. The algorithm
compares each element *i in the range [first,last) with the
conditions specified by pred. If pred(*i)==false,
replace_copy_if copies *i to result+(first-i). If pred(*i)==true,
then replace_copy copies new_value to result+(first-i).
replace_copy_if returns result+(last-first).
COMPLEXITY
Exactly last - first applications of the predicate are performed.
EXAMPLE
//
// replace.cpp
//
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
template<class Arg>
struct all_true : public unary_function<Arg, bool>
{
bool operator() (const Arg&) { return 1; }
};
int main ()
{
//
// Initialize a vector with an array of integers.
//
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
vector<int> v(arr+0, arr+10);
//
// Print out original vector.
//
cout << "The original list: " << endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Replace the number 7 with 11.
//
replace(v.begin(), v.end(), 7, 11);
//
// Print out vector with 7 replaced.
//
cout << "List after replace:" << endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Replace 1 2 3 with 13 13 13.
//
replace_if(v.begin(), v.begin()+3, all_true<int>(), 13);
//
// Print out the remaining vector.
//
cout << "List after replace_if:" << endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Replace those 13s with 17s on output.
//
cout << "List using replace_copy to cout:" << endl << " ";
replace_copy(v.begin(), v.end(),
ostream_iterator<int,char>(cout, " "), 13, 17);
cout << endl << endl;
//
// A simple example of replace_copy_if.
//
cout << "List w/ all elements output as 19s:" << endl << " ";
replace_copy_if(v.begin(), v.end(),
ostream_iterator<int,char>(cout, " "),
all_true<int>(), 19);
cout << endl;
return 0;
}
Output :
The original list:
1 2 3 4 5 6 7 8 9 10
List after replace:
1 2 3 4 5 6 11 8 9 10
List after replace_if:
13 13 13 4 5 6 11 8 9 10
List using replace_copy to cout:
17 17 17 4 5 6 11 8 9 10
List with all elements output as 19s:
19 19 19 19 19 19 19 19 19 19
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
replace, replace_if, replace_copy
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
replace_if
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
replace_if - Substitutes elements stored in a collection with new
values.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator,
class Predicate,
class T>
void replace_if (ForwardIterator first,
ForwardIterator last,
Predicate pred
const T& new_value);
DESCRIPTION
The replace_if algorithm replaces element referred to by iterator i
in the range [first, last) with new_value when the following
condition holds: pred(*i) == true.
COMPLEXITY
Exactly last - first applications of the predicate are done.
EXAMPLE
//
// replace.cpp
//
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream.h>
template<class Arg>
struct all_true : public unary_function<Arg, bool>
{
bool operator()(const Arg&){ return 1; }
};
int main()
{
//Initialize a vector with an array of integers
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr, arr+10);
//Print out original vector
cout << "The original list: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Replace the number 7 with 11
replace(v.begin(), v.end(), 7, 11);
// Print out vector with 7 replaced,
// s.b. 1 2 3 4 5 6 11 8 9 10
cout << "List after replace " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Replace 1 2 3 with 13 13 13
replace_if(v.begin(), v.begin()+3, all_true<int>(), 13);
// Print out the remaining vector,
// s.b. 13 13 13 4 5 6 11 8 9 10
cout << "List after replace_if " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
return 0;
}
Output :
The original list:
1 2 3 4 5 6 7 8 9 10
List after replace:
1 2 3 4 5 6 11 8 9 10
List after replace_if:
13 13 13 4 5 6 11 8 9 10
List using replace_copy to cout:
17 17 17 4 5 6 11 8 9 10
List with all elements output as 19s:
19 19 19 19 19 19 19 19 19 19
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
replace, replace_copy, replace_copy_if
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
reverse
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
reverse - Reverse the order of elements in a collection.
SYNOPSIS
#include <algorithm>
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first,
BidirectionalIterator last);
DESCRIPTION
The algorithm reverse reverses the elements in a sequence so that
the last element becomes the new first element, and the first
element becomes the new last. For each non-negative integer i <=
(last - first)/2 , reverse applies swap to all pairs of
iterators first + I, (last - I) - 1.
Because the iterators are assumed to be bidirectional, reverse does
not return anything.
COMPLEXITY
reverse performs exactly (last - first)/2 swaps.
EXAMPLE
//
// reverse.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
//Initialize a vector with an array of ints
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr, arr+10);
//Print out elements in original (sorted) order
cout << "Elements before reverse: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Reverse the ordering
reverse(v.begin(), v.end());
//Print out the reversed elements
cout << "Elements after reverse: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
Elements before reverse:
1 2 3 4 5 6 7 8 9 10
Elements after reverse:
10 9 8 7 6 5 4 3 2 1
A reverse_copy to cout:
1 2 3 4 5 6 7 8 9 10
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
reverse_copy, swap
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
reverse_copy
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
reverse_copy - Reverse the order of elements in a collection while
copying them to a new collecton.
SYNOPSIS
#include <algorithm>
template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy (BidirectionalIterator first,
BidirectionalIterator last,
OutputIterator result);
DESCRIPTION
The reverse_copy algorithm copies the range [first, last) to the range
[result, result + (last - first)) such that for any non-negative integer i
< (last - first), the following assignment takes place:
*(result + (last - first) -i) = *(first + i)
reverse_copy returns result + (last - first). The ranges [first, last)
and [result, result + (last - first)) must not overlap.
COMPLEXITY
reverse_copy performs exactly (last - first) assignments.
EXAMPLE
//
// reverse.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main ()
{
//
// Initialize a vector with an array of integers.
//
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
vector<int> v(arr+0, arr+10);
//
// Print out elements in original (sorted) order.
//
cout << "Elements before reverse: " << endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//
// Reverse the ordering.
//
reverse(v.begin(), v.end());
//
// Print out the reversed elements.
//
cout << "Elements after reverse: " << endl << " ";
copy(v.begin(), v.end(), ostream_iterator<int,char>(cout," "));
cout << endl << endl;
cout << "A reverse_copy to cout: " << endl << " ";
reverse_copy(v.begin(), v.end(),
ostream_iterator<int,char>(cout, " "));
cout << endl;
return 0;
}
Output :
Elements before reverse:
1 2 3 4 5 6 7 8 9 10
Elements after reverse:
10 9 8 7 6 5 4 3 2 1
A reverse_copy to cout:
1 2 3 4 5 6 7 8 9 10
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
reverse
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
rotate
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
rotate, rotate_copy - Left rotates the order of items in a
collection, placing the first item at the end, second item
first, etc., until the item pointed to by a specified
iterator is the first item in the collection.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator>
void rotate (ForwardIterator first,
ForwardIterator middle,
ForwardIterator last);
template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy (ForwardIterator first,
ForwardIterator middle,
ForwardIterator last,
OutputIterator result);
DESCRIPTION
The rotate algorithm takes three iterator arguments, first, which
defines the start of a sequence, last, which defines the end of the
sequence, and middle which defines a point within the sequence.
rotate "swaps" the segment that contains elements from first
through middle-1 with the segment that contains the elements
from middle through last. After rotate has been applied, the
element that was in position middle, is in position first, and
the other elements in that segment are in the same order relative to
each other. Similarly, the element that was in position first is
now in position last-middle +1. An example will illustrate how
rotate works:
Say that we have the sequence:
2 4 6 8 1 3 5
If we call rotate with middle = 5, the two segments are
2 4 6 8 and 1 3 5
After we apply rotate, the new sequence will be:
1 3 5 2 4 6 8
Note that the element that was in the fifth position is now in the
first position, and the element that was in the first position is
in position 4 (last - first + 1, or 8 - 5 +1 =4).
The formal description of this algorithms is: for each non-negative
integer i < (last - first), rotate places the element from the
position first + i into position first + (i + (last -
middle)) % (last - first). [first, middle) and [middle, last)
are valid ranges.
rotate_copy rotates the elements as described above, but instead of
swapping elements within the same sequence, it copies the result
of the rotation to a container specified by result.
rotate_copy copies the range [first, last) to the range [result,
result + (last - first)) such that for each non-negative integer i
< (last - first) the following assignment takes place:
*(result + (i + (last - middle)) % (last -first)) = *(first + i).
The ranges [first, last) and [result, result, + (last - first)) may not
overlap.
COMPLEXITY
For rotate at most last - first swaps are performed.
For rotate_copy last - first assignments are performed.
EXAMPLE
//
// rotate
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
//Initialize a vector with an array of ints
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr, arr+10);
//Print out elements in original (sorted) order
cout << "Elements before rotate: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Rotate the elements
rotate(v.begin(), v.begin()+4, v.end());
//Print out the rotated elements
cout << "Elements after rotate: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
Elements before rotate:
1 2 3 4 5 6 7 8 9 10
Elements after rotate:
5 6 7 8 9 10 1 2 3 4
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
rotate_copy
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
rotate, rotate_copy - Left rotates the order of items in a
collection, placing the first item at the end, second item
first, etc., until the item pointed to by a specified
iterator is the first item in the collection.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator>
void rotate (ForwardIterator first,
ForwardIterator middle,
ForwardIterator last);
template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy (ForwardIterator first,
ForwardIterator middle,
ForwardIterator last,
OutputIterator result);
DESCRIPTION
The rotate algorithm takes three iterator arguments, first, which
defines the start of a sequence, last, which defines the end of the
sequence, and middle which defines a point within the sequence.
rotate "swaps" the segment that contains elements from first
through middle-1 with the segment that contains the elements
from middle through last. After rotate has been applied, the
element that was in position middle, is in position first, and
the other elements in that segment are in the same order relative to
each other. Similarly, the element that was in position first is
now in position last-middle +1. An example will illustrate how
rotate works:
Say that we have the sequence:
2 4 6 8 1 3 5
If we call rotate with middle = 5, the two segments are
2 4 6 8 and 1 3 5
After we apply rotate, the new sequence will be:
1 3 5 2 4 6 8
Note that the element that was in the fifth position is now in the
first position, and the element that was in the first position is
in position 4 (last - first + 1, or 8 - 5 +1 =4).
The formal description of this algorithms is: for each non-negative
integer i < (last - first), rotate places the element from the
position first + i into position first + (i + (last -
middle)) % (last - first). [first, middle) and [middle, last)
are valid ranges.
rotate_copy rotates the elements as described above, but instead of
swapping elements within the same sequence, it copies the result
of the rotation to a container specified by result.
rotate_copy copies the range [first, last) to the range [result,
result + (last - first)) such that for each non-negative integer i
< (last - first) the following assignment takes place:
*(result + (i + (last - middle)) % (last -first)) = *(first + i).
The ranges [first, last) and [result, result, + (last - first))
may not overlap.
COMPLEXITY
For rotate at most last - first swaps are performed.
For rotate_copy last - first assignments are performed.
EXAMPLE
//
// rotate
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
//Initialize a vector with an array of ints
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(arr, arr+10);
//Print out elements in original (sorted) order
cout << "Elements before rotate: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Rotate the elements
rotate(v.begin(), v.begin()+4, v.end());
//Print out the rotated elements
cout << "Elements after rotate: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
cout << endl;
return 0;
}
Output :
Elements before rotate:
1 2 3 4 5 6 7 8 9 10
Elements after rotate:
5 6 7 8 9 10 1 2 3 4
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
search
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
search, search_n - Finds a sub-sequence within a sequence of values
that is element-wise equal to the values in an indicated range.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search (ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);
template <class ForwardIterator1,
class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 search (ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
BinaryPredicate binary_pred);
template <class ForwardIterator,
class Size,
class T>
ForwardIterator search_n (ForwardIterator first,
ForwardIterator last,
Size count, const T& value);
template <class ForwardIterator,
class Size,
class T,
class BinaryPredicate>
ForwardIterator search_n (ForwardIterator first,
ForwardIterator last,
Size count, const T& value,
BinaryPredicate pred)
DESCRIPTION
The search and search_n are used for searching for a sub-sequence
within a sequence. The search algorithm searches for a
sub-sequence [first2, last2) within a sequence [first1, last1), and
returns the beginning location of the sub-sequence. If it
does not find the sub-sequence, search returns last1. The first
version of search uses the equality (==) operator as a default, and
the second version allows you to specify a binary predicate to
perform the comparison.
The search_n algorithm searches for the sub-sequence composed of
count occurrences of value within a sequence [first, last), and
returns first if this sub-sequence is found. If it does not find
the sub-sequence, search_n returns last. The first version of
search_n uses the equality (==) operator as a default, and
the second version allows you to specify a binary predicate to
perform the comparison.
COMPLEXITY
search performs at most (last1 - first1)*(last2-first2) applications
of the corresponding predicate.
search_n performs at most (last - first) applications of the
corresponding predicate.
EXAMPLE
//
// search.cpp
//
#include <algorithm>
#include <list>
#include <iostream.h>
int main()
{
// Initialize a list sequence and
// sub-sequence with characters
char seq[40] = "Here's a string with a substring in it";
char subseq[10] = "substring";
list<char> sequence(seq, seq+39);
list<char> subseqnc(subseq, subseq+9);
//Print out the original sequence
cout << endl << "The sub-sequence, " << subseq
<< ", was found at the ";
cout << endl << "location identified by a '*'"
<< endl << " ";
// Create an iterator to identify the location of
// sub-sequence within sequence
list<char>::iterator place;
//Do search
place = search(sequence.begin(), sequence.end(),
subseqnc.begin(), subseqnc.end());
//Identify result by marking first character with a '*'
*place = '*';
//Output sequence to display result
for(list<char>::iterator i = sequence.begin();
i != sequence.end(); i++)
cout << *i;
cout << endl;
return 0;
}
Output :
The sub-sequence, substring, was found at the
location identified by a '*'
Here's a string with a *substring in it
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
list<char, allocator<char> >
instead of :
list<char>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
search_n
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
search, search_n - Finds a sub-sequence within a sequence of values
that is element-wise equal to the values in an indicated range.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search (ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);
template <class ForwardIterator1,
class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 search (ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
BinaryPredicate binary_pred);
template <class ForwardIterator,
class Size,
class T>
ForwardIterator search_n (ForwardIterator first,
ForwardIterator last,
Size count, const T& value);
template <class ForwardIterator,
class Size,
class T,
class BinaryPredicate>
ForwardIterator search_n (ForwardIterator first,
ForwardIterator last,
Size count, const T& value,
BinaryPredicate pred)
DESCRIPTION
The search and search_n are used for searching for a sub-sequence
within a sequence. The search algorithm searches for a
sub-sequence [first2, last2) within a sequence [first1, last1), and
returns the beginning location of the sub-sequence. If it
does not find the sub-sequence, search returns last1. The first
version of search uses the equality (==) operator as a default, and
the second version allows you to specify a binary predicate to
perform the comparison.
The search_n algorithm searches for the sub-sequence composed of
count occurrences of value within a sequence [first, last), and
returns first if this sub-sequence is found. If it does not find
the sub-sequence, search_n returns last. The first version of
search_n uses the equality (==) operator as a default, and
the second version allows you to specify a binary predicate to
perform the comparison.
COMPLEXITY
search performs at most (last1 - first1)*(last2-first2) applications of
the corresponding predicate.
search_n performs at most (last - first) applications of the corresponding
predicate.
EXAMPLE
//
// search.cpp
//
#include <algorithm>
#include <list>
#include <iostream.h>
int main()
{
// Initialize a list sequence and
// sub-sequence with characters
char seq[40] = "Here's a string with a substring in it";
char subseq[10] = "substring";
list<char> sequence(seq, seq+39);
list<char> subseqnc(subseq, subseq+9);
//Print out the original sequence
cout << endl << "The sub-sequence, " << subseq
<< ", was found at the ";
cout << endl << "location identified by a '*'"
<< endl << " ";
// Create an iterator to identify the location of
// sub-sequence within sequence
list<char>::iterator place;
//Do search
place = search(sequence.begin(), sequence.end(),
subseqnc.begin(), subseqnc.end());
//Identify result by marking first character with a '*'
*place = '*';
//Output sequence to display result
for(list<char>::iterator i = sequence.begin();
i != sequence.end(); i++)
cout << *i;
cout << endl;
return 0;
}
Output :
The sub-sequence, substring, was found at the
location identified by a '*'
Here's a string with a *substring in it
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
list<char, allocator<char> >
instead of :
list<char>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
set_difference
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
set_difference - Basic set operation for sorted sequences.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
DESCRIPTION
The set_difference algorithm constructs a sorted difference that
includes copies of the elements that are present in the range
[first1, last1) but are not present in the range [first2,
last2). It returns the end of the constructed range.
As an example, assume we have the following two sets:
1 2 3 4 5
and
3 4 5 6 7
The result of applying set_difference is the set:
1 2
The result of set_difference is undefined if the result range
overlaps with either of the original ranges.
set_difference assumes that the ranges are sorted using the default
comparison operator less than (<), unless an alternative
comparison operator (comp) is provided.
Use the set_symetric_difference algorithm to return a result that
contains all elements that are not in common between the two
sets.
COMPLEXITY
At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons
are performed.
EXAMPLE
//
// set_diff.cpp
//
#include <algorithm>
#include <set>
#include <iostream.h>
int main()
{
//Initialize some sets
int a1[10] = {1,2,3,4,5,6,7,8,9,10};
int a2[6] = {2,4,6,8,10,12};
set<int, less<int> > all(a1, a1+10), even(a2, a2+6),
odd;
//Create an insert_iterator for odd
insert_iterator<set<int, less<int> > >
odd_ins(odd, odd.begin());
//Demonstrate set_difference
cout << "The result of:" << endl << "{";
copy(all.begin(),all.end(),
ostream_iterator<int,char>(cout," "));
cout << "} - {";
copy(even.begin(),even.end(),
ostream_iterator<int,char>(cout," "));
cout << "} =" << endl << "{";
set_difference(all.begin(), all.end(),
even.begin(), even.end(), odd_ins);
copy(odd.begin(),odd.end(),
ostream_iterator<int,char>(cout," "));
cout << "}" << endl << endl;
return 0;
}
Output :
The result of:
{1 2 3 4 5 6 7 8 9 10 } - {2 4 6 8 10 12 } =
{1 3 5 7 9 }
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Compare template argument and the
Allocator template argument. For instance, you will need
to write :
set<int, less<int> allocator<int> >
instead of :
set<int>
SEE ALSO
includes, set, set_union, set_intersection, set_symmetric_difference
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
set_intersection
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
set_intersection - Basic set operation for sorted sequences.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_intersection (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_intersection (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
DESCRIPTION
The set_intersection algorithm constructs a sorted intersection of
elements from the two ranges. It returns the end of the constructed
range. When it finds an element present in both ranges,
set_intersection always copies the element from the first range into
result. This means that the result of set_intersection is
guaranteed to be stable. The result of set_intersection is
undefined if the result range overlaps with either of the
original ranges.
set_intersection assumes that the ranges are sorted using the
default comparison operator less than (<), unless an
alternative comparison operator (comp) is provided.
COMPLEXITY
At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons are per-
formed.
EXAMPLE
//
// set_intr.cpp
//
#include <algorithm>
#include <set>
#include <iostream.h>
int main()
{
//Initialize some sets
int a1[10] = {1,3,5,7,9,11};
int a3[4] = {3,5,7,8};
set<int, less<int> > odd(a1, a1+6),
result, small(a3,a3+4);
//Create an insert_iterator for result
insert_iterator<set<int, less<int> > >
res_ins(result, result.begin());
//Demonstrate set_intersection
cout << "The result of:" << endl << "{";
copy(small.begin(),small.end(),
ostream_iterator<int,char>(cout," "));
cout << "} intersection {";
copy(odd.begin(),odd.end(),
ostream_iterator<int,char>(cout," "));
cout << "} =" << endl << "{";
set_intersection(small.begin(), small.end(),
odd.begin(), odd.end(), res_ins);
copy(result.begin(),result.end(),
ostream_iterator<int,char>(cout," "));
cout << "}" << endl << endl;
return 0;
}
Output :
The result of:
{3 5 7 8 } intersection {1 3 5 7 9 11 } =
{3 5 7 }
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Compare template argument and the
Allocator template argument. For instance, you will need
to write :
set<int, less<int> allocator<int> >
instead of :
set<int>
SEE ALSO
includes, set, set_union, set_difference, set_symmetric_difference
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
set_symmetric_difference
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
set_symmetric_difference - Basic set operation for sorted sequences.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_symmetric_difference (InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_symmetric_difference (InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result, Compare comp);
DESCRIPTION
set_symmetric_difference constructs a sorted symmetric difference of
the elements from the two ranges. This means that the
constructed range includes copies of the elements that are present
in the range [first1, last1) but not present in the range [first2,
last2)and copies of the elements that are present in
the range [first2, last2) but not in the range [first1, last1).
It returns the end of the constructed range.
For example, suppose we have two sets:
1 2 3 4 5
and
3 4 5 6 7
The set_symmetric_difference of these two sets is:
1 2 6 7
The result of set_symmetric_difference is undefined if the result
range overlaps with either of the original ranges.
set_symmetric_difference assumes that the ranges are sorted using
the default comparison operator less than (<), unless an
alternative comparison operator (comp) is provided.
Use the set_symmetric_difference algorithm to return a result that
includes elements that are present in the first set and not
in the second.
COMPLEXITY
At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons
are performed.
EXAMPLE
//
// set_s_di.cpp
//
#include<algorithm>
#include<set>
#include <istream.h>
int main()
{
//Initialize some sets
int a1[] = {1,3,5,7,9,11};
int a3[] = {3,5,7,8};
set<int, less<int> > odd(a1,a1+6), result,
small(a3,a3+4);
//Create an insert_iterator for result
insert_iterator<set<int, less<int> > >
res_ins(result, result.begin());
//Demonstrate set_symmetric_difference
cout << "The symmetric difference of:" << endl << "{";
copy(small.begin(),small.end(),
ostream_iterator<int,char>(cout," "));
cout << "} with {";
copy(odd.begin(),odd.end(),
ostream_iterator<int,char>(cout," "));
cout << "} =" << endl << "{";
set_symmetric_difference(small.begin(), small.end(),
odd.begin(), odd.end(), res_ins);
copy(result.begin(),result.end(),
ostream_iterator<int,char>(cout," "));
cout << "}" << endl << endl;
return 0;
}
Output :
The symmetric difference of:
{3 5 7 8 } with {1 3 5 7 9 11 } =
{1 8 9 11 }
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Compare template argument and the
Allocator template argument. For instance, you will need
to write :
set<int, less<int>, allocator<int> >
instead of :
set<int>
SEE ALSO
includes, set, set_union, set_intersection, set_difference
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
set_union
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
set_union - Basic set operation for sorted sequences.
SYNOPSIS
#include <algorithm>
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
set_union (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_union (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
DESCRIPTION
The set_union algorithm constructs a sorted union of the elements
from the two ranges. It returns the end of the constructed range.
set_union is stable, that is, if an element is present in both
ranges, the one from the first range is copied. The result of
set_union is undefined if the result range overlaps with either
of the original ranges. Note that set_union does not merge the
two sorted sequences. If an element is present in both
sequences, only the element from the first sequence is copied to
result. (Use the merge algorithm to create an ordered merge of two
sorted sequences that contains all the elements from both
sequences.)
set_union assumes that the sequences are sorted using the default
comparison operator less than (<), unless an alternative
comparison operator (comp) is provided.
COMPLEXITY
At most ((last1 - first1) + (last2 - first2)) * 2 -1 comparisons
are performed.
EXAMPLE
//
// set_unin.cpp
//
#include <algorithm>
#include <set>
#include <iostream.h>
int main()
{
//Initialize some sets
int a2[6] = {2,4,6,8,10,12};
int a3[4] = {3,5,7,8};
set<int, less<int> > even(a2, a2+6),
result, small(a3,a3+4);
//Create an insert_iterator for result
insert_iterator<set<int, less<int> > >
res_ins(result, result.begin());
//Demonstrate set_union
cout << "The result of:" << endl << "{";
copy(small.begin(),small.end(),
ostream_iterator<int,char>(cout," "));
cout << "} union {";
copy(even.begin(),even.end(),
ostream_iterator<int,char>(cout," "));
cout << "} =" << endl << "{";
set_union(small.begin(), small.end(),
even.begin(), even.end(), res_ins);
copy(result.begin(),result.end(),
ostream_iterator<int,char>(cout," "));
cout << "}" << endl << endl;
return 0;
}
Output :
The result of:
{3 5 7 8 } union {2 4 6 8 10 12 } =
{2 3 4 5 6 7 8 10 12 }
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Compare template argument and the
Allocator template argument. For instance, you will need
to write :
set<int, less<int>, allocator<int> >
instead of :
set<int>
SEE ALSO
includes, set, set_intersection, set_difference, set_symmetric_difference
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
sort
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
sort - Templated algorithm for sorting collections of entities.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void sort (RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
DESCRIPTION
The sort algorithm sorts the elements in the range [first, last)
using either the less than (<) operator or the comparison operator
comp. If the worst case behavior is important stable_sort or
partial_sort should be used.
COMPLEXITY
sort performs approximately NlogN, where N equals last - first, comparis-
ons on the average.
EXAMPLE
//
// sort.cpp
//
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream.h>
struct associate
{
int num;
char chr;
associate(int n, char c) : num(n), chr(c){};
associate() : num(0), chr(' '){};
};
bool operator<(const associate &x, const associate &y)
{
return x.num < y.num;
}
ostream& operator<<(ostream &s, const associate &x)
{
return s << "<" << x.num << ";" << x.chr << ">";
}
int main ()
{
vector<associate>::iterator i, j, k;
associate arr[20] =
{associate(-4, ' '), associate(16, ' '),
associate(17, ' '), associate(-3, 's'),
associate(14, ' '), associate(-6, ' '),
associate(-1, ' '), associate(-3, 't'),
associate(23, ' '), associate(-3, 'a'),
associate(-2, ' '), associate(-7, ' '),
associate(-3, 'b'), associate(-8, ' '),
associate(11, ' '), associate(-3, 'l'),
associate(15, ' '), associate(-5, ' '),
associate(-3, 'e'), associate(15, ' ')};
// Set up vectors
vector<associate> v(arr, arr+20), v1((size_t)20),
v2((size_t)20);
// Copy original vector to vectors #1 and #2
copy(v.begin(), v.end(), v1.begin());
copy(v.begin(), v.end(), v2.begin());
// Sort vector #1
sort(v1.begin(), v1.end());
// Stable sort vector #2
stable_sort(v2.begin(), v2.end());
// Display the results
cout << "Original sort stable_sort" << endl;
for(i = v.begin(), j = v1.begin(), k = v2.begin();
i != v.end(); i++, j++, k++)
cout << *i << " " << *j << " " << *k << endl;
return 0;
}
Output :
Original sort stable_sort
<-4; > <-8; > <-8; >
<16; > <-7; > <-7; >
<17; > <-6; > <-6; >
<-3;s> <-5; > <-5; >
<14; > <-4; > <-4; >
<-6; > <-3;e> <-3;s>
<-1; > <-3;s> <-3;t>
<-3;t> <-3;l> <-3;a>
<23; > <-3;t> <-3;b>
<-3;a> <-3;b> <-3;l>
<-2; > <-3;a> <-3;e>
<-7; > <-2; > <-2; >
<-3;b> <-1; > <-1; >
<-8; > <11; > <11; >
<11; > <14; > <14; >
<-3;l> <15; > <15; >
<15; > <15; > <15; >
<-5; > <16; > <16; >
<-3;e> <17; > <17; >
<15; > <23; > <23; >
WARNING
If your compiler does not support default template parameters, then you
need to always supply the Allocator template argument. For instance, you
will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
stable_sort, partial_sort, partial_sort_copy
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
sort_heap
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
sort_heap - Converts a heap into a sorted collection.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void
sort_heap(RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void
sort_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
DESCRIPTION
A heap is a particular organization of elements in a range between
two random access iterators [a, b). Its two key properties are:
1. *a is the largest element in the range.
2. *a may be removed by pop_heap(), or a new element added by push_heap(),
in O(logN) time.
These properties make heaps useful as priority queues.
The sort_heap algorithm converts a heap into a sorted collection
over the range [first, last) using either the default
operator (<) or the comparison function supplied with the
algorithm. Note that sort_heap is not stable, i.e., the
elements may not be in the same relative order after sort_heap is
applied.
COMPLEXITY
sort_heap performs at most NlogN comparisons where N is equal to
last - first.
EXAMPLE
//
// heap_ops.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main(void)
{
int d1[4] = {1,2,3,4};
int d2[4] = {1,3,2,4};
// Set up two vectors
vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4);
// Make heaps
make_heap(v1.begin(),v1.end());
make_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Note that x, y and z represent the remaining
// values in the container (other than 4).
// The definition of the heap and heap operations
// does not require any particular ordering
// of these values.
// Copy both vectors to cout
ostream_iterator<int,char> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now let's pop
pop_heap(v1.begin(),v1.end());
pop_heap(v2.begin(),v2.end(),less<int>());
// v1 = (3,x,y,4) and v2 = (3,x,y,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// And push
push_heap(v1.begin(),v1.end());
push_heap(v2.begin(),v2.end(),less<int>());
// v1 = (4,x,y,z) and v2 = (4,x,y,z)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
// Now sort those heaps
sort_heap(v1.begin(),v1.end());
sort_heap(v2.begin(),v2.end(),less<int>());
// v1 = v2 = (1,2,3,4)
// Copy both vectors to cout
copy(v1.begin(),v1.end(),out);
cout << endl;
copy(v2.begin(),v2.end(),out);
cout << endl;
return 0;
}
Output :
4 2 3 1
4 3 2 1
3 2 1 4
3 1 2 4
4 3 1 2
4 3 2 1
1 2 3 4
1 2 3 4
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
make_heap, pop_heap, push_heap
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
stable_partition
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
stable_partition - Places all of the entities that satisfy the
given predicate before all of the entities that do not, while
maintaining the relative order of elements in each group.
SYNOPSIS
#include <algorithm>
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition (BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
DESCRIPTION
The stable_partition algorithm places all the elements in the range
[first, last) that satisfy pred before all the elements that do not
satisfy it. It returns an iterator i that is one past the end of
the group of elements that satisfy pred. In other words
stable_partition returns i such that for any iterator j in the
range [first, i), pred(*j) == true, and for any iterator k in
the range [i, last), pred(*j) == false. The relative order of
the elements in both groups is preserved.
The partition algorithm can be used when it is not necessary to
maintain the relative order of elements within the groups
that do and do not match the predicate.
COMPLEXITY
The stable_partition algorithm does at most (last - first) *
log(last - first) swaps. and applies the predicate exactly last
- first times.
EXAMPLE
//
// prtition.cpp
//
#include <functional>
#include <deque>
#include <algorithm>
#include <iostream.h>
//Create a new predicate from unary_function
template<class Arg>
class is_even : public unary_function<Arg, bool>
{
public:
bool operator()(const Arg& arg1)
{
return (arg1 % 2) == 0;
}
};
int main()
{
//Initialize a deque with an array of ints
int init[10] = {1,2,3,4,5,6,7,8,9,10};
deque<int> d(init, init+10);
//Print out the original values
cout << "Unpartitioned values: " << endl << " ";
copy(d.begin(),d.end(),ostream_iterator<int,char>(cout," "));
cout << endl << endl;
//Partition the deque according to even/oddness
stable_partition(d.begin(), d.end(), is_even<int>());
//Output result of partition
cout << "Partitioned values: " << endl << " ";
copy(d.begin(),d.end(),ostream_iterator<int,char>(cout," "));
return 0;
}
Output :
Unpartitioned values: 1 2 3 4 5 6 7 8 9 10
Partitioned values: 10 2 8 4 6 5 7 3 9 1
Stable partitioned values: 2 4 6 8 10 1 3 5 7 9
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
deque<int, allocator<int> >
instead of :
deque<int>
SEE ALSO
partition
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
stable_sort
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
stable_sort - Templated algorithm for sorting collections of
entities.
SYNOPSIS
#include <algorithm>
template <class RandomAccessIterator>
void stable_sort (RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void stable_sort (RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);
DESCRIPTION
The stable_sort algorithm sorts the elements in the range [first,
last). The first version of the algorithm uses less than (<) as the
comparison operator for the sort. The second version uses the
comparison function comp.
The stable_sort algorithm is considered stable because the relative
order of the equal elements is preserved.
COMPLEXITY
stable_sort does at most N(logN) **2, where N equals last -first,
comparisons; if enough extra memory is available, it is NlogN.
EXAMPLE
//
// sort.cpp
//
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream.h>
struct associate
{
int num;
char chr;
associate(int n, char c) : num(n), chr(c){};
associate() : num(0), chr(' '){};
};
bool operator<(const associate &x, const associate &y)
{
return x.num < y.num;
}
ostream& operator<<(ostream &s, const associate &x)
{
return s << "<" << x.num << ";" << x.chr << ">";
}
int main ()
{
vector<associate>::iterator i, j, k;
associate arr[20] =
{associate(-4, ' '), associate(16, ' '),
associate(17, ' '), associate(-3, 's'),
associate(14, ' '), associate(-6, ' '),
associate(-1, ' '), associate(-3, 't'),
associate(23, ' '), associate(-3, 'a'),
associate(-2, ' '), associate(-7, ' '),
associate(-3, 'b'), associate(-8, ' '),
associate(11, ' '), associate(-3, 'l'),
associate(15, ' '), associate(-5, ' '),
associate(-3, 'e'), associate(15, ' ')};
// Set up vectors
vector<associate> v(arr, arr+20), v1((size_t)20),
v2((size_t)20);
// Copy original vector to vectors #1 and #2
copy(v.begin(), v.end(), v1.begin());
copy(v.begin(), v.end(), v2.begin());
// Sort vector #1
sort(v1.begin(), v1.end());
// Stable sort vector #2
stable_sort(v2.begin(), v2.end());
// Display the results
cout << "Original sort stable_sort" << endl;
for(i = v.begin(), j = v1.begin(), k = v2.begin();
i != v.end(); i++, j++, k++)
cout << *i << " " << *j << " " << *k << endl;
return 0;
}
Output :
Original sort stable_sort
<-4; > <-8; > <-8; >
<16; > <-7; > <-7; >
<17; > <-6; > <-6; >
<-3;s> <-5; > <-5; >
<14; > <-4; > <-4; >
<-6; > <-3;e> <-3;s>
<-1; > <-3;s> <-3;t>
<-3;t> <-3;l> <-3;a>
<23; > <-3;t> <-3;b>
<-3;a> <-3;b> <-3;l>
<-2; > <-3;a> <-3;e>
<-7; > <-2; > <-2; >
<-3;b> <-1; > <-1; >
<-8; > <11; > <11; >
<11; > <14; > <14; >
<-3;l> <15; > <15; >
<15; > <15; > <15; >
<-5; > <16; > <16; >
<-3;e> <17; > <17; >
<15; > <23; > <23; >
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator>
instead of :
vector<int>
SEE ALSO
sort, partial_sort, partial_sort_copy
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
swap
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
swap - Exchange values.
SYNOPSIS
#include <algorithm>
template <class T>
void swap (T& a, T& b);
DESCRIPTION
The swap algorithm exchanges the values of a and b. The effect is:
T tmp = a
a = b
b = tmp
SEE ALSO
iter_swap, swap_ranges
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
swap_ranges
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
swap_ranges - Exchange a range of values in one location with those in
another
SYNOPSIS
#include <algorithm>
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges (ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2);
DESCRIPTION
The swap_ranges algorithm exchanges corresponding values in two
ranges, in the following manner:
For each non-negative integer n < (last - first) the function
exchanges *(first1 + n) with *(first2 + n)). After completing
all exchanges, swap_ranges returns an iterator that points to the
end of the second container, i.e., first2 + (last1
-first1). The result of swap_ranges is undefined if the
two ranges [first, last) and [first2, first2 + (last1 -
first1)) overlap.
EXAMPLE
//
// swap.cpp
//
#include <vector>
#include <algorithm>
int main()
{
int d1[] = {6, 7, 8, 9, 10, 1, 2, 3, 4, 5};
// Set up a vector
vector<int> v(d1,d1 + 10);
// Output original vector
cout << "For the vector: ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
// Swap the first five elements with the last five elements
swap_ranges(v.begin(),v.begin()+5, v.begin()+5);
// Output result
cout << endl << endl
<< "Swapping the first five elements "
<< "with the last five gives: "
<< endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
return 0;
}
Output :
For the vector: 6 7 8 9 10 1 2 3 4 5
Swapping the first five elements with the last five gives:
1 2 3 4 5 6 7 8 9 10
Swapping the first and last elements gives:
10 2 3 4 5 6 7 8 9 1
WARNING
If your compiler does not support default template parameters, you
need to always supply the Allocator template argument. For instance,
you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
iter_swap, swap
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
transform
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
transform - Applies an operation to a range of values in a
collection and stores the result.
SYNOPSIS
#include <algorithm>
template <class InputIterator,
class OutputIterator,
class UnaryOperation>
OutputIterator transform (InputIterator first,
InputIterator last,
OutputIterator result,
UnaryOperation op);
template <class InputIterator1,
class InputIterator2,
class OutputIterator,
class BinaryOperation>
OutputIterator transform (InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
OutputIterator result,
BinaryOperation binary_op);
DESCRIPTION
The transform algorithm has two forms. The first form applies unary
operation op to each element of the range [first, last), and sends
the result to the output iterator result. For example, this version
of transform, could be used to square each element in a vector. If
the output iterator (result) is the same as the input iterator used
to traverse the range, transform, performs its transformation in
place.
The second form of transform applies a binary operation, binary_op,
to corresponding elements in the range [first1, last1) and the
range that begins at first2, and sends the result to result.
For example, transform can be used to add corresponding elements in
two sequences, and store the set of sums in a third. The
algorithm assumes, but does not check, that the second sequence has
at least as many elements as the first sequence. Note that the
output iterator result can be a third sequence, or either of
the two input sequences.
Formally, transform assigns through every iterator i in the range
[result, result + (last1 - first1)) a new corresponding value equal
to:
op(*(first1 + (i - result))
or
binary_op(*(first1 + (i - result), *(first2 + (i - result)))
transform returns result + (last1 - first1). op and binary_op
must not have any side effects. result may be equal to first
in case of unary transform, or to first1 or first2 in case of
binary transform.
COMPLEXITY
Exactly last1 - first1 applications of op or binary_op are
performed.
EXAMPLE
//
// trnsform.cpp
//
#include <functional>
#include <deque>
#include <algorithm>
#include <iostream.h>
#include <iomanip.h>
int main()
{
//Initialize a deque with an array of ints
int arr1[5] = {99, 264, 126, 330, 132};
int arr2[5] = {280, 105, 220, 84, 210};
deque<int> d1(arr1, arr1+5), d2(arr2, arr2+5);
//Print the original values
cout << "The following pairs of numbers: "
<< endl << " ";
deque<int>::iterator i1;
for(i1 = d1.begin(); i1 != d1.end(); i1++)
cout << setw(6) << *i1 << " ";
cout << endl << " ";
for(i1 = d2.begin(); i1 != d2.end(); i1++)
cout << setw(6) << *i1 << " ";
// Transform the numbers in the deque to their
// factorials and store in the vector
transform(d1.begin(), d1.end(), d2.begin(),
d1.begin(), multiplies<int>());
//Display the results
cout << endl << endl;
cout << "Have the products: " << endl << " ";
for(i1 = d1.begin(); i1 != d1.end(); i1++)
cout << setw(6) << *i1 << " ";
return 0;
}
Output :
The following pairs of numbers:
99 264 126 330 132
280 105 220 84 210
Have the products:
27720 27720 27720 27720 27720
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
deque<int, allocator<int> >
instead of:
deque<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
uninitialized_copy
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
uninitialized_copy - An algorithms that uses construct to copy values from
one range to another location.
SYNOPSIS
#include <memory>
template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_copy (InputIterator first,
InputIterator last,
ForwardIterator result);
DESCRIPTION
uninitialized_copy copies all items in the range [first, last) into
the location beginning at result using the construct algorithm.
SEE ALSO
construct
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
uninitialized_fill
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
uninitialized_fill - Algorithm that uses the construct algorithm
for setting values in a collection.
SYNOPSIS
#include <memory>
template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first,
ForwardIterator last,
const T& x);
DESCRIPTION
uninitialized_fill initializes all of the items in the range [first,
last) to the value x, using the construct algorithm.
SEE ALSO
construct, uninitialized_fill_n
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
uninitialized_fill_n
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
uninitialized_fill_n - Algorithm that uses the construct algorithm for
setting values in a collection.
SYNOPSIS
#include <memory>
template <class ForwardIterator,
class Size, class T>
void uninitialized_fill_n (ForwardIterator first,
Size n, const T& x);
DESCRIPTION
unitialized_fill_n starts at the iterator first and initializes the
first n items to the value x, using the construct algorithm.
SEE ALSO
construct, uninitialized_fill
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
unique
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
unique, unique_copy - Removes consecutive duplicates from a range
of values and places the resulting unique values into the
result.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator>
ForwardIterator unique (ForwardIterator first,
ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique (ForwardIterator first,
ForwardIterator last,
BinaryPredicate binary_pred);
template <class InputIterator, class OutputIterator>
OutputIterator unique_copy (InputIterator first,
InputIterator last,
OutputIterator result);
template <class InputIterator,
class OutputIterator,
class BinaryPredicate>
OutputIterator unique_copy (InputIterator first,
InputIterator last,
OutputIterator result,
BinaryPredicate binary_pred);
DESCRIPTION
The unique algorithm moves through a sequence and eliminates all but
the first element from every consecutive group of equal
elements. There are two versions of the algorithm, one tests
for equality, and the other tests whether a binary predicate applied
to adjacent elements is true. An element is unique if it does
not meet the corresponding condition listed here:
*i == *(i - 1)
or
binary_pred(*i, *(i - 1)) == true.
If an element is unique, it is copied to the front of the sequence,
overwriting the existing elements. Once all unique elements have
been identified. The remainder of the sequence is left
unchanged, and unique returns the end of the resulting range.
The unique_copy algorithm copies the first element from every
consecutive group of equal elements, to an OutputIterator. The
unique_copy algorithm, also has two versions--one that tests for
equality and a second that tests adjacent elements against a binary
predicate.
unique_copy returns the end of the resulting range.
COMPLEXITY
Exactly (last - first) - 1 applications of the corresponding predicate are
performed.
EXAMPLE
//
// unique.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
//Initialize two vectors
int a1[20] = {4, 5, 5, 9, -1, -1, -1, 3, 7, 5,
5, 5, 6, 7, 7, 7, 4, 2, 1, 1};
vector<int> v(a1, a1+20), result;
//Create an insert_iterator for results
insert_iterator<vector<int> > ins(result,
result.begin());
//Demonstrate includes
cout << "The vector: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
//Find the unique elements
unique_copy(v.begin(), v.end(), ins);
//Display the results
cout << endl << endl
<< "Has the following unique elements:"
<< endl << " ";
copy(result.begin(),result.end(),
ostream_iterator<int,char>(cout," "));
return 0;
}
Output :
The vector:
4 5 5 9 -1 -1 -1 3 7 5 5 5 6 7 7 7 4 2 1 1
Has the following unique elements:
4 5 9 -1 3 7 5 6 7 4 2 1
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of:
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
unique_copy
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
unique, unique_copy - Removes consecutive duplicates from a range
of values and places the resulting unique values into the
result.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator>
ForwardIterator unique (ForwardIterator first,
ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique (ForwardIterator first,
ForwardIterator last,
BinaryPredicate binary_pred);
template <class InputIterator, class OutputIterator>
OutputIterator unique_copy (InputIterator first,
InputIterator last,
OutputIterator result);
template <class InputIterator,
class OutputIterator,
class BinaryPredicate>
OutputIterator unique_copy (InputIterator first,
InputIterator last,
OutputIterator result,
BinaryPredicate binary_pred);
DESCRIPTION
The unique algorithm moves through a sequence and eliminates all but
the first element from every consecutive group of equal
elements. There are two versions of the algorithm, one tests
for equality, and the other tests whether a binary predicate applied
to adjacent elements is true. An element is unique if it does
not meet the corresponding condition listed here:
*i == *(i - 1)
or
binary_pred(*i, *(i - 1)) == true.
If an element is unique, it is copied to the front of the sequence,
overwriting the existing elements. Once all unique elements have
been identified. The remainder of the sequence is left
unchanged, and unique returns the end of the resulting range.
The unique_copy algorithm copies the first element from every
consecutive group of equal elements, to an OutputIterator. The
unique_copy algorithm, also has two versions--one that tests for
equality and a second that tests adjacent elements against a binary
predicate.
unique_copy returns the end of the resulting range.
COMPLEXITY
Exactly (last - first) - 1 applications of the corresponding
predicate are performed.
EXAMPLE
//
// unique.cpp
//
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
//Initialize two vectors
int a1[20] = {4, 5, 5, 9, -1, -1, -1, 3, 7, 5,
5, 5, 6, 7, 7, 7, 4, 2, 1, 1};
vector<int> v(a1, a1+20), result;
//Create an insert_iterator for results
insert_iterator<vector<int> > ins(result,
result.begin());
//Demonstrate includes
cout << "The vector: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
//Find the unique elements
unique_copy(v.begin(), v.end(), ins);
//Display the results
cout << endl << endl
<< "Has the following unique elements:"
<< endl << " ";
copy(result.begin(),result.end(),
ostream_iterator<int,char>(cout," "));
return 0;
}
Output :
The vector:
4 5 5 9 -1 -1 -1 3 7 5 5 5 6 7 7 7 4 2 1 1
Has the following unique elements:
4 5 9 -1 3 7 5 6 7 4 2 1
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of:
vector<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
upper_bound
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
upper_bound - Determines the last valid position for a value in a
sorted container.
SYNOPSIS
#include <algorithm>
template <class ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template <class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
DESCRIPTION
The upper_bound algorithm is part of a set of binary search
algorithms. All of these algorithms perform binary searches on
ordered containers. Each algorithm has two versions. The first
version uses the less than operator (operator<) to perform the
comparison, and assumes that the sequence has been sorted using that
operator. The second version allows you to include a function
object of type Compare, and assumes that Compare is the function
used to sort the sequence. The function object must be a binary
predicate.
The upper_bound algorithm finds the last position in a container
that value can occupy without violating the container's ordering.
upper_bound's return value is the iterator for the first element in
the container that is greater than value, or, when the comparison
operator is used, the first element that does not satisfy the
comparison function. Because the algorithm is restricted to using
the less than operator or the user-defined function to perform
the search, upper_bound returns an iterator i in the range
[first, last) such that for any iterator j in the range
[first, i) the appropriate version of the following conditions
holds:
!(value < *j)
or
comp(value, *j) == false
COMPLEXITY
upper_bound performs at most log(last - first) + 1 comparisons.
EXAMPLE
//
// ul_bound.cpp
//
#include <vector>
#include <algorithm>
#include <iostream.h>
int main()
{
typedef vector<int>::iterator iterator;
int d1[11] = {0,1,2,2,3,4,2,2,2,6,7};
// Set up a vector
vector<int> v1(d1,d1 + 11);
// Try lower_bound variants
iterator it1 = lower_bound(v1.begin(),v1.end(),3);
// it1 = v1.begin() + 4
iterator it2 =
lower_bound(v1.begin(),v1.end(),2,less<int>());
// it2 = v1.begin() + 4
// Try upper_bound variants
iterator it3 = upper_bound(v1.begin(),v1.end(),3);
// it3 = vector + 5
iterator it4 =
upper_bound(v1.begin(),v1.end(),2,less<int>());
// it4 = v1.begin() + 5
cout << endl << endl
<< "The upper and lower bounds of 3: ( "
<< *it1 << " , " << *it3 << " ]" << endl;
cout << endl << endl
<< "The upper and lower bounds of 2: ( "
<< *it2 << " , " << *it4 << " ]" << endl;
return 0;
}
Output :
The upper and lower bounds of 3: ( 3 , 4 ]
The upper and lower bounds of 2: ( 2 , 3 ]
WARNING
If your compiler does not support default template parameters, then
you need to always supply the Allocator template argument. For
instance, you will need to write :
vector<int, allocator<int> >
instead of :
vector<int>
SEE ALSO
lower_bound, equal_range
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
