The first set of algorithms we cover are used chiefly, although not exclusively, to initialize a newly created sequence with certain values. The C++ Standard Library provides several initialization algorithms. The initialization algorithms all overwrite every element in a container. The difference between the algorithms is the source for the values used in initialization. The std::fill() algorithm repeats a single value, the std::copy() algorithm reads values from a second container, and the std::generate() algorithm invokes a function for each new value. In our discussion we provide examples of how to apply these algorithms, and suggest how to choose one algorithm over another.
NOTE -- The sample programs described in the following sections are in the file alg1.cpp. We generally omit output statements from the descriptions of the programs provided here, although they are included in the compete versions.
The std::fill() and std::fill_n() algorithms are used to initialize or reinitialize a sequence with a fixed value. Their declarations are as follows:
namespace std {
void fill(ForwardIterator first,
ForwardIterator last, const T&);
void fill_n(OutputIterator, Size, const T&);
}
The example program illustrates several uses of the algorithm:
void fill_example ()
// illustrates the use of the fill algorithm
// see alg1.cpp for complete source code
{
// example 1, fill an array with initial values
char buffer[100], *bufferp = buffer;
std::fill(bufferp, bufferp + 100, '\0');
std::fill_n(bufferp, 10, 'x');
// example 2, use fill_n to initialize a list
std::list<string> aList(5, "nothing");
std::fill_n(inserter(aList, aList.begin()), 10, "empty");
// example 3, use fill to overwrite values in list
std::fill(aList.begin(), aList.end(), "full");
// example 4, fill in a portion of a collection
std::vector<int> iVec(10);
std::generate(iVec.begin(), iVec.end(), iotaGen(1));
std::vector<int>::iterator& seven =
std::find(iVec.begin(), iVec.end(), 7);
std::fill(iVec.begin(), seven, 0);
}
In example 1, an array of character values is declared. The std::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 std::fill_n(). Note that the std::fill() algorithm requires both starting and past-end iterators as arguments, whereas the std::fill_n() algorithm uses a starting iterator and a count.
By applying an insert iterator (Section 2.4), example 2 illustrates how the std::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 std::fill_n() then inserts ten instances of the string "empty". The resulting list contains fifteen elements.
Examples 3 and 4 illustrate how std::fill() can be used to change the values in an existing container. In example 3 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 generic algorithm std::generate() and the function object iotaGen (see Section 3.2 and Section 13.2.3), a vector is initialized to the values 1 2 3... 10. The std::find() algorithm (see Section 13.3.1) is used to locate the position of the element 7, saving the location in an iterator appropriate for the vector datatype. The std::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 std::fill() and std::fill_n() algorithm can be used with all the container classes contained in the C++ Standard Library, although insert iterators must be used with ordered containers, such as sets.
The algorithms std::copy() and std::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 C++ Standard Library. The declarations for these algorithms are as follows:
namespace std {
OutputIterator copy (InputIterator first, InputIterator last,
OutputIterator result);
BidirectionalIterator copy_backward
(BidirectionalIterator first, BidirectionalIterator last,
BidirectionalIterator result);
}
The result returned by the copy() function is a pointer to the end of the copied sequence. However, the result of one copy() operation can be used as a starting iterator in a subsequent copy() to make a catenation of values.
Uses of the copy algorithm include:
Duplicating an entire sequence by copying into a new sequence
Creating sub-sequences of an existing sequence
Adding elements into a sequence
Copying a sequence from input or to output
Converting a sequence from one form into another
The uses of the copy algorithm are illustrated in the following sample program:
void copy_example()
// illustrates the use of the copy algorithm
// see alg1.cpp for complete source code
{
char *source = "reprise";
char *surpass = "surpass";
char buffer[120], *bufferp = buffer;
// example 1, a simple copy
std::copy(source, source + strlen(source) + 1, bufferp);
// example 2, self copies
std::copy(bufferp + 2, bufferp + strlen(buffer) + 1, bufferp);
int buflen = strlen(buffer) + 1;
std::copy_backward(bufferp, bufferp + buflen,
bufferp + buflen + 3);
std::copy(surpass, surpass + 3, bufferp);
// example 3, copy to output
std::copy(bufferp, bufferp + strlen(buffer),
std::ostream_iterator<char,char>(std::cout));
std::cout << std::endl;
// example 4, use copy to convert type
std::list<char> char_list;
std::copy (bufferp, bufferp + strlen(buffer),
std::inserter(char_list, char_list.end()));
char *big = "big ";
std::copy(big, big + 4,
std::inserter(char_list, char_list.begin()));
char buffer2[120], *buffer2p = buffer2;
*std::copy(char_list.begin(), char_list.end(), buffer2p) = '\0';
std::cout << buffer2 << std::endl;
}
In example 1, the first call on std::copy() 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 std::copy() operation is specifically designed to permit self-copies, which are 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 std::copy_backward() algorithm. This function performs the same task as the std::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 is that buffer is assigned the value "priprise". The first three characters are then modified by another std::copy() operation to the values "sur", resulting in buffer holding the value "surprise".
NOTE -- In the copy_backwards algorithm, note that it is the order of transfer that is backwards, not the elements themselves; the relative placement of moved values in the target is the same as in the source.
Example 3 illustrates std::copy() being used to move values to an output stream (see Section 2.3.2). The target in this case is an ostream_iterator generated for the output stream std::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():
std::list<std::string> words;
std::istream_iterator<std::string, char> in_stream(std::cin), eof;
std::copy(in_stream, eof, std::inserter(words,
words.begin()));
This technique is used in the spell checking program described in Section 8.3.
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 std::inserter() creates an insert iterator, used to insert values into the list. The first call on std::copy() places the string surprise, created in example 2, into the list. The second call on std::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 std::copy() illustrates the reverse process, copying characters from a list back into a character buffer.
A generator is a function that returns 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 std::fill() and std::fill_n(), the algorithms std::generate() and std::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:
namespace std {
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
// see alg1.cpp for complete source code
static int lastLabel = 0;
char labelBuffer[80];
std::ostrstream ost(labelBuffer, 80);
ost << "L_" << lastLabel++ << '\0';
return std::string(labelBuffer);
}
void generate_example ()
// illustrate the use of the generate and generate_n algorithms
{
// example 1, generate a list of label values
std::list<std::string> labelList;
std::generate_n(std::inserter(labelList, labelList.begin()),
4, generateLabel);
// example 2, generate an arithmetic progression
std::vector<int> iVec(10);
std::generate(iVec.begin(), iVec.end(), iotaGen(2));
std::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 illustrates how this function might be used in combination with the std::generate_n() algorithm to initialize a list of four label values.
As we described in Chapter 3, a function is any object that will respond to the function call operator. Using this definition, classes can easily be constructed as functions. The class iotaGen, is an example (see Section 3.2). 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 std::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 std::swap() can be used to exchange the values of two objects of the same type. It has the following definition:
namespace std {
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 std::iter_swap(). The algorithm std::swap_ranges() 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 std::swap_ranges() algorithm is as follows:
namespace std {
ForwardIterator swap_ranges
(ForwardIterator first, ForwardIterator last,
ForwardIterator first2);
}
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.
NOTE -- A number of algorithms operate on two parallel sequences. In most cases, the second sequence is identified using only a starting iterator, not a starting and ending iterator pair. It is assumed, but never verified, that the second sequence is at least as large as the first. Errors will occur if this condition is not satisfied.
In the example program, both std::swap() and std::iter_swap() are used separately and in combination:
void swap_example ()
// illustrates the use of the algorithm swap_ranges
// see alg1.cpp for complete source code
{
// first make two parallel sequences
int data[] = {12, 27, 14, 64}, *datap = data;
std::vector<int> aVec(4);
std::generate(aVec.begin(), aVec.end(), iotaGen(1));
// illustrate swap and iter_swap
std::swap(data[0], data[2]);
std::vector<int>::iterator last = aVec.end();
last--;
std::iter_swap(aVec.begin(), last);
// now swap the entire sequence
std::swap_ranges(aVec.begin(), aVec.end(), datap);
}