Obtaining the source
The first set of algorithms we will cover are those that are chiefly, although not exclusively, used to initialize a newly created sequence with certain values. The standard library provides several initialization algorithms. In our discussion we'll provide examples of how to apply these algorithms, and suggest how to choose one algorithm over another.
The fill() and fill_n() algorithms are used to initialize or reinitialize a sequence with a fixed value. Their declarations are as follows:
void fill (ForwardIterator first, ForwardIterator last, const T&); void fill_n (OutputIterator, Size, const T&);
Different Initialization Algorithms
The example program illustrates several uses of the algorithm:
void fill_example ()
// illustrate the use of the fill algorithm
{
// example 1, fill an array with initial values
char buffer[100], * bufferp = buffer;
fill (bufferp, bufferp + 100, '\0');
fill_n (bufferp, 10, 'x');
// example 2, use fill to initialize a list
list<string> aList(5, "nothing");
fill_n (inserter(aList, aList.begin()), 10, "empty");
// example 3, use fill to overwrite values in list
fill (aList.begin(), aList.end(), "full");
// example 4, fill in a portion of a collection
vector<int> iVec(10);
generate (iVec.begin(), iVec.end(), iotaGen(1));
vector<int>::iterator & seven =
find(iVec.begin(), iVec.end(), 7);
fill (iVec.begin(), seven, 0);
}
In example 1, an array of character values is declared. The fill() algorithm is invoked to initialize each location in this array with a null character value. The first 10 positions are then replaced with the character 'x' by using the algorithm fill_n(). Note that the fill() algorithm requires both starting and past-end iterators as arguments, whereas the fill_n() algorithm uses a starting iterator and a count.
Example 2 illustrates how, by using an insert iterator (see Chapter 2: Insert Iterators), the fill_n() algorithm can be used to initialize a variable length container, such as a list. In this case the list initially contains five elements, all holding the text "nothing". The call on fill_n() then inserts ten instances of the string "empty". The resulting list contains fifteen elements.
The third and fourth examples illustrate how fill() can be used to change the values in an existing container. In the third example each of the fifteen elements in the list created in example 2 is replaced by the string "full".
Example 4 overwrites only a portion of a list. Using the algorithm generate and the function object iotaGen, which we will describe in the next section, a vector is initialized to the values 1 2 3 ... 10. The find() algorithm (Chapter 13: Searching Operations) is then used to locate the position of the element 7, saving the location in an iterator appropriate for the vector data type. The fill() call then replaces all values up to, but not including, the 7 entry with the value 0. The resulting vector has six zero fields, followed by the values 7, 8, 9 and 10.
The fill() and fill_n() algorithm can be used with all the container classes contained in the standard library, although insert iterators must be used with ordered containers, such as a set.
Appending Several Copies
The algorithms copy() and copy_backward() are versatile functions that can be used for a number of different purposes, and are probably the most commonly executed algorithms in the standard library. The declarations for these algorithms are as follows:
OutputIterator copy (InputIterator first, InputIterator last,
OutputIterator result);
BidirectionalIterator copy_backward
(BidirectionalIterator first, BidirectionalIterator last,
BidirectionalIterator result);
Uses of the copy algorithm include:
These are illustrated in the following sample program.
void copy_example()
// illustrate the use of the copy algorithm
{
char * source = "reprise";
char * surpass = "surpass";
char buffer[120], * bufferp = buffer;
// example 1, a simple copy
copy (source, source + strlen(source) + 1, bufferp);
// example 2, self copies
copy (bufferp + 2, bufferp + strlen(buffer) + 1, bufferp);
int buflen = strlen(buffer) + 1;
copy_backward (bufferp, bufferp + buflen, bufferp + buflen + 3);
copy (surpass, surpass + 3, bufferp);
// example 3, copy to output
copy (bufferp, bufferp + strlen(buffer),
ostream_iterator<char>(cout));
cout << endl;
// example 4, use copy to convert type
list<char> char_list;
copy (bufferp, bufferp + strlen(buffer),
inserter(char_list, char_list.end()));
char * big = "big ";
copy (big, big + 4, inserter(char_list, char_list.begin()));
char buffer2 [120], * buffer2p = buffer2;
* copy (char_list.begin(), char_list.end(), buffer2p) = '\0';
cout << buffer2 << endl;
}
The first call on copy(), in example 1, simply copies the string pointed to by the variable source into a buffer, resulting in the buffer containing the text "reprise". Note that the ending position for the copy is one past the terminating null character, thus ensuring the null character is included in the copy operation.
The copy() operation is specifically designed to permit self-copies, i.e., copies of a sequence onto itself, as long as the destination iterator does not fall within the range formed by the source iterators. This is illustrated by example 2. Here the copy begins at position 2 of the buffer and extends to the end, copying characters into the beginning of the buffer. This results in the buffer holding the value "prise".
The second half of example 2 illustrates the use of the copy_backward() algorithm. This function performs the same task as the copy() algorithm, but moves elements from the end of the sequence first, progressing to the front of the sequence. (If you think of the argument as a string, characters are moved starting from the right and progressing to the left.) In this case the result will be that buffer will be assigned the value "priprise". The first three characters are then modified by another copy() operation to the values "sur", resulting in buffer holding the value "surprise".
copy_backwards
Example 3 illustrates copy() being used to move values to an output stream. (See Chapter 2: Stream Iterators). The target in this case is an ostream_iterator generated for the output stream cout. A similar mechanism can be used for input values. For example, a simple mechanism to copy every word in the input stream into a list is the following call on copy():
list<string> words; istream_iterator<string, ptrdiff_t> in_stream(cin), eof; copy(in_stream, eof, inserter(words, words.begin()));
This technique is used in the spell checking program described in Chapter 8 (Example Program - A Spelling...).
Copy can also be used to convert from one type of stream to another. For example, the call in example 4 of the sample program copies the characters held in the buffer one by one into a list of characters. The call on inserter() creates an insert iterator, used to insert values into the list. The first call on copy() places the string surprise, created in example 2, into the list. The second call on copy() inserts the values from the string "big " onto the front of the list, resulting in the list containing the characters big surprise. The final call on copy() illustrates the reverse process, copying characters from a list back into a character buffer.
A generator is a function that will return a series of values on successive invocations. Probably the generator you are most familiar with is a random number generator. However, generators can be constructed for a variety of different purposes, including initializing sequences.
Like fill() and fill_n(), the algorithms generate() and generate_n() are used to initialize or reinitialize a sequence. However, instead of a fixed argument, these algorithms draw their values from a generator. The declarations of these algorithms are as follows:
void generate (ForwardIterator, ForwardIterator, Generator); void generate_n (OutputIterator, Size, Generator);
Our example program shows several uses of the generate algorithm to initialize a sequence.
string generateLabel () {
// generate a unique label string of the form L_ddd
static int lastLabel = 0;
char labelBuffer[80];
ostrstream ost(labelBuffer, 80);
ost << "L_" << lastLabel++ << '\0';
return string(labelBuffer);
}
void generate_example ()
// illustrate the use of the generate and generate_n algorithms
{
// example 1, generate a list of label values
list<string> labelList;
generate_n (inserter(labelList, labelList.begin()),
4, generateLabel);
// example 2, generate an arithmetic progression
vector<int> iVec(10);
generate (iVec.begin(), iVec.end(), iotaGen(2));
generate_n (iVec.begin(), 5, iotaGen(7));
}
A generator can be constructed as a simple function that "remembers" information about its previous history in one or more static variables. An example is shown in the beginning of the example program, where the function generateLabel() is described. This function creates a sequence of unique string labels, such as might be needed by a compiler. Each invocation on the function generateLabel() results in a new string of the form L_ddd, each with a unique digit value. Because the variable named lastLabel is declared as static, its value is remembered from one invocation to the next. The first example of the sample program illustrates how this function might be used in combination with the generate_n() algorithm to initialize a list of four label values.
As we described in Chapter 3, in the Standard Library a function is any object that will respond to the function call operator. Using this fact, classes can easily be constructed as functions. The class iotaGen, which we described in Chapter 3 (Functions), is an example. The iotaGen function object creates a generator for an integer arithmetic sequence. In the second example in the sample program, this sequence is used to initialize a vector with the integer values 2 through 11. A call on generate_n() is then used to overwrite the first 5 positions of the vector with the values 7 through 11, resulting in the vector 7 8 9 10 11 7 8 9 10 11.
The template function swap() can be used to exchange the values of two objects of the same type. It has the following definition:
template <class T> void swap (T& a, T& b)
{
T temp(a);
a = b;
b = temp;
}
The function is generalized to iterators in the function named iter_swap(). The algorithm swap_ranges() then extends this to entire sequences. The values denoted by the first sequence are exchanged with the values denoted by a second, parallel sequence. The description of the swap_ranges() algorithm is as follows:
ForwardIterator swap_ranges
(ForwardIterator first, ForwardIterator last,
ForwardIterator first2);
Parallel Sequences
The second range is described only by a starting iterator. It is assumed (but not verified) that the second range has at least as many elements as the first range. We use both functions alone and in combination in the example program.
void swap_example ()
// illustrate the use of the algorithm swap_ranges
{
// first make two parallel sequences
int data[] = {12, 27, 14, 64}, *datap = data;
vector<int> aVec(4);
generate(aVec.begin(), aVec.end(), iotaGen(1));
// illustrate swap and iter_swap
swap(data[0], data[2]);
vector<int>::iterator last = aVec.end(); last--;
iter_swap(aVec.begin(), last);
// now swap the entire sequence
swap_ranges (aVec.begin(), aVec.end(), datap);
}