| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
Among other things, the generic algorithms in the standard
library provide a vocabulary with which to describe solutions. 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 need 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 what 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 <algorithm>
#include <cassert>
#include <cstddef> // 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(size_t 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 copy any kind of sequence. The
following example copies string objects:
//: C06:CopyStrings.cpp
// Copies strings.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <string>
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. If you think that the implementation of copy( )
looks like the following, you re almost right:
template<typename T> void copy(T* begin, T* end,
T* dest) {
while(begin != end)
*dest++ = *begin++;
}
We say almost because copy( ) can process
sequences delimited by anything that acts like a pointer, such as an iterator.
In this way, copy( ) can be used to duplicate a vector:
//: C06:CopyVector.cpp
// Copies the contents of a vector.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <vector>
using namespace std;
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
vector<int> v1(a, a + SIZE);
vector<int> 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 establish the size of the output vector, v2,
ahead of time:
//: C06:InsertVector.cpp
// Appends the contents of a vector to another.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <vector>
using namespace std;
int main() {
int a[] = { 10, 20, 30 };
const size_t SIZE = sizeof a / sizeof a[0];
vector<int> v1(a, a + SIZE);
vector<int> v2; // v2 is empty here
copy(v1.begin(), v1.end(), back_inserter(v2));
assert(equal(v1.begin(), v1.end(), v2.begin()));
} ///:~
The back_inserter( ) function is defined in the <iterator>
header. We ll explain how insert iterators work in depth in the next chapter.
Since iterators are identical to pointers in all essential
ways, you can write the algorithms in the standard library in such a way as to
allow both pointer and iterator arguments. For this reason, the implementation
of copy( ) looks more like the following code:
template<typename Iterator>
void copy(Iterator begin, Iterator end, Iterator dest)
{
while(begin != end)
*begin++ = *dest++;
}
Whichever argument type you use in the call, copy( )
assumes it properly implements the indirection and increment operators. If it
doesn t, you ll get a compile-time error.
| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
