Standard Template Library Programmer's Guide

Category: algorithms

Component type: function

template

void generate(ForwardIterator first, ForwardIterator last, Generator gen);

Generate assigns the result of invoking gen , a function object that takes no arguments, to each element in the range [first, last) . [1]

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

• ForwardIterator is a model of Forward Iterator. [2]

• ForwardIterator is mutable.

• Generator is a model of Generator.

• Generator 's result type is convertible to ForwardIterator 's value type.

Preconditions

• [first, last) is a valid range.

Complexity

Linear. Exactly last – first invocations of gen . [1]

Fill a vector with random numbers, using the standard C library function rand .

vector V;

…

generate(V.begin(), V.end(), rand);

[1] The function object gen is invoked for each iterator in the range [first, last) , as opposed to just being invoked a single time outside the loop. This distinction is important because a Generator need not return the same result each time it is invoked; it is permitted to read from a file, refer to and modify local state, and so on.

[2] The reason that generate requires its argument to be a mutable Forward Iterator, rather than just an Output Iterator, is that it uses a range [first, last) of iterators. There is no sensible way to describe a range of Output Iterators, because it is impossible to compare two Output Iterators for equality. The generate_n algorithm does have an interface that permits use of an Output Iterator.

copy , fill , fill_n , generate_n , iota

Category: algorithms

Component type: function

template

OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

Generate_n assigns the result of invoking gen , a function object that takes no arguments, to each element in the range [first, first+n) . [1] The return value is first + n .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

• OutputIterator is a model of Output Iterator.

• Size is an integral type (either signed or unsigned).

• Generator is a model of Generator.

• Generator 's result type is convertible to a type in OutputIterator 's set of value types.

• n >= 0 .

• There is enough space to hold n values. That is, [first, first+n) is a valid range.

Linear. Exactly n invocations of gen . [1]

Print 100 random numbers, using the C standard library function rand .

generate_n(ostream_iterator(cout, "\n"), 100, rand);

[1] The function object gen is invoked n times (once for each iterator in the range [first, first+n) ), as opposed to just being invoked a single time outside the loop. This distinction is important because a Generator need not return the same result each time it is invoked; it is permitted to read from a file, refer to and modify local state, and so on.

copy , fill , fill_n , generate , iota

Category: algorithms

Component type: function

template

ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

Remove removes from the range [first, last) all elements that are equal to value . That is, remove returns an iterator new_last such that the range [first, new_last) contains no elements equal to value . [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Remove is stable, meaning that the relative order of elements that are not equal to value is unchanged.

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

• ForwardIterator is a model of Forward Iterator.

• ForwardIterator is mutable.

• T is a model of Equality Comparable.

• Objects of type T can be compared for equality with objects of ForwardIterator 's value type.

• [first, last) is a valid range.

Linear. Remove performs exactly last – first comparisons for equality.

vector V;

V.push_back(3);

V.push_back(1);

V.push_back(4);

V.push_back(1);

V.push_back(5);

V.push_back(9);

copy(V.begin(), V.end(), ostream_iterator(cout, " "));

// The output is "3 1 4 1 5 9".

vector::iterator new_end = remove(V.begin(), V.end(), 1);

copy(V.begin(), new_end, ostream_iterator(cout, " "));

// The output is "3 4 5 9".

[1] The meaning of "removal" is somewhat subtle. Remove does not destroy any iterators, and does not change the distance between first and last . (There's no way that it could do anything of the sort.) So, for example, if V is a vector, remove(V.begin(), V.end(), 0) does not change V.size() : V will contain just as many elements as it did before. Remove returns an iterator that points to the end of the resulting range after elements have been removed from it; it follows that the elements after that iterator are of no interest, and may be discarded. If you are removing elements from a Sequence, you may simply erase them. That is, a reasonable way of removing elements from a Sequence is S.erase(remove(S.begin(), S.end(), x), S.end()) .