Читаем Thinking In C++. Volume 2: Practical Programming полностью

Thinking In C++. Volume 2: Practical Programming

Among other things, the generic algorithms in the standard library provide a vocabulary with which to describe solutions. That is, once you become familiar with the algorithms, you’ll have a new set of words with which to discuss what you’re doing, and these words are at a higher level than what you had before. You don’t have to say, "This loop moves through and assigns from here to there … oh, I see, it’s copying!" Instead, you just say copy( ). This is the kind of thing we’ve been doing in computer programming from the beginning—creating high-level abstractions to express what you’re doing and spending less time saying how you’re doing it. The how has been solved once and for all and is hidden in the algorithm’s code, ready to be reused on demand^.

Here’s an example of how to use the copy algorithm:

//: C06:CopyInts.cpp

// Copies ints without an explicit loop

#include

#include // For size_t

using namespace std;

int main() {

int a[] = {10, 20, 30};

const size_t SIZE = sizeof a / sizeof a[0];

int b[SIZE];

copy(a, a + SIZE, b);

for (int i = 0; i < SIZE; ++i)

assert(a[i] == b[i]);

} ///:~^.

The copy algorithm’s first two parameters represent the range of the input sequence—in this case the array a. Ranges are denoted by a pair of pointers. The first points to the first element of the sequence, and the second points one position past the end of the array (right after the last element). This may seem strange at first, but it is an old C idiom that comes in quite handy. For example, the difference of these two pointers yields the number of elements in the sequence. More important, in implementing copy( ), the second pointer can act as a sentinel to stop the iteration through the sequence. The third argument refers to the beginning of the output sequence, which is the array b in this example. It is assumed that the array that b represents has enough space to receive the copied elements^.

The copy( ) algorithm wouldn’t be very exciting if it could only process integers. It can in fact copy any sequence. The following example copies string objects^.

//: C06:CopyStrings.cpp

// Copies strings

#include

using namespace std;

int main() {

string a[] = {"read", "my", "lips"};

const size_t SIZE = sizeof a / sizeof a[0];

string b[SIZE];

copy(a, a + SIZE, b);

assert(equal(a, a + SIZE, b));

} ///:~^.

This example introduces another algorithm, equal( ), which returns true only if each element in the first sequence is equal (using its operator==( )) to the corresponding element in the second sequence. This example traverses each sequence twice, once for the copy, and once for the comparison, without a single explicit loop!^.

Generic algorithms achieve this flexibility because they are function templates, of course. If you guessed that the implementation of copy( ) looked something like the following, you’d be "almost" right^.

template

void copy(T* begin, T* end, T* dest) {

while (begin != end)

*dest++ = *begin++;

}^.

We say "almost," because copy( ) can actually process sequences delimited by anything that acts like a pointer, such as an iterator. In this way, copy( ) can duplicate a vector, as in the following example^.

//: C06:CopyVector.cpp

// Copies the contents of a vector

#include

using namespace std;

int main() {

int a[] = {10, 20, 30};

const size_t SIZE = sizeof a / sizeof a[0];

vector v1(a, a + SIZE);

vector v2(SIZE);

copy(v1.begin(), v1.end(), v2.begin());

assert(equal(v1.begin(), v1.end(), v2.begin()));

} ///:~^.

The first vector, v1, is initialized from the sequence of integers in the array a. The definition of the vector v2 uses a different vector constructor that makes room for SIZE elements, initialized to zero (the default value for integers).

As with the array example earlier, it’s important that v2 have enough space to receive a copy of the contents of v1. For convenience, a special library function, back_inserter( ), returns a special type of iterator that inserts elements instead of overwriting them, so memory is expanded automatically by the container as needed. The following example uses back_inserter( ), so it doesn’t have to expand the size of the output vector, v2, ahead of time^.

//: C06:InsertVector.cpp

// Appends the contents of a vector to another

#include

using namespace std;

int main() {

int a[] = {10, 20, 30};

const size_t SIZE = sizeof a / sizeof a[0];

vector v1(a, a + SIZE);

vector v2; // v2 is empty here

copy(v1.begin(), v1.end(), back_inserter(v2));

assert(equal(v1.begin(), v1.end(), v2.begin()));

} ///:~