On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

## A first look

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

 Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire