then it would have to reallocate storage). When an object is erased from the vector, the assignment operator is once again used to move everything up to cover the place that is being erased (notice that this requires that the assignment operator properly cleans up the lvalue). Lastly, the object on the end of the array is deleted.

You can imagine how enormous the overhead can become if objects are inserted and removed from the middle of a vector if the number of elements is large and the objects are complicated. It’s obviously a practice to avoid.

deque

The deque (double-ended-queue, pronounced “deck”) is the basic sequence container optimized for adding and removing elements from either end. It also allows for reasonably fast random access – it has an operator[ ] like vector. However, it does not have vector’s constraint of keeping everything in a single sequential block of memory. Instead, deque uses multiple blocks of sequential storage (keeping track of all the blocks and their order in a mapping structure). For this reason the overhead for a deque to add or remove elements at either end is very low. In addition, it never needs to copy and destroy contained objects during a new storage allocation (like vector does) so it is far more efficient than vector if you are adding an unknown quantity of objects. This means that vector is the best choice only if you have a pretty good idea of how many objects you need. In addition, many of the programs shown earlier in this book that use vector and push_back( ) might be more efficient with a deque. The interface to deque is only slightly different from a vector (deque has a push_front( ) and pop_front( ) while vector does not, for example) so converting code from using vector to using deque is almost trivial. Consider StringVector.cpp, which can be changed to use deque by replacing the word “vector” with “deque” everywhere. The following program adds parallel deque operations to the vector operations in StringVector.cpp, and performs timing comparisons:

//: C04:StringDeque.cpp

// Converted from StringVector.cpp #include "../require.h"

#include <string> #include <deque> #include <vector> #include <fstream> #include <iostream> #include <iterator> #include <sstream> #include <ctime> using namespace std;

int main(int argc, char* argv[]) { requireArgs(argc, 1);

Chapter 15: Multiple Inheritance

179

ifstream in(argv[1]); assure(in, argv[1]); vector<string> vstrings; deque<string> dstrings; string line;

//Time reading into vector: clock_t ticks = clock(); while(getline(in, line))

vstrings.push_back(line); ticks = clock() - ticks;

cout << "Read into vector: " << ticks << endl;

//Repeat for deque:

ifstream in2(argv[1]); assure(in2, argv[1]); ticks = clock(); while(getline(in2, line))

dstrings.push_back(line); ticks = clock() - ticks;

cout << "Read into deque: " << ticks << endl; // Now compare indexing:

ticks = clock();

for(int i = 0; i < vstrings.size(); i++) { ostringstream ss;

ss << i;

vstrings[i] = ss.str() + ": " + vstrings[i];

}

ticks = clock() - ticks;

cout << "Indexing vector: " << ticks << endl; ticks = clock();

for(int j = 0; j < dstrings.size(); j++) { ostringstream ss;

ss << j;

dstrings[j] = ss.str() + ": " + dstrings[j];

}

ticks = clock() - ticks;

cout << "Indexing deqeue: " << ticks << endl; // Compare iteration

ofstream tmp1("tmp1.tmp"), tmp2("tmp2.tmp"); ticks = clock();

copy(vstrings.begin(), vstrings.end(), ostream_iterator<string>(tmp1, "\n"));

ticks = clock() - ticks;

cout << "Iterating vector: " << ticks << endl;

Chapter 15: Multiple Inheritance

180

ticks = clock(); copy(dstrings.begin(), dstrings.end(),

ostream_iterator<string>(tmp2, "\n")); ticks = clock() - ticks;

cout << "Iterating deqeue: " << ticks << endl; } ///:~

Knowing now what you do about the inefficiency of adding things to vector because of storage reallocation, you may expect dramatic differences between the two. However, on a 1.7 Megabyte text file one compiler’s program produced the following (measured in platform/compiler specific clock ticks, not seconds):

Read into vector: 8350

Read into deque: 7690

Indexing vector: 2360

Indexing deqeue: 2480

Iterating vector: 2470

Iterating deqeue: 2410

A different compiler and platform roughly agreed with this. It’s not so dramatic, is it? This points out some important issues:

1.We (programmers) are typically very bad at guessing where inefficiencies occur in our programs.

2.Efficiency comes from a combination of effects – here, reading the lines in and converting them to strings may dominate over the cost of the vector vs. deque.

3.The string class is probably fairly well-designed in terms of efficiency.

Of course, this doesn’t mean you shouldn’t use a deque rather than a vector when you know that an uncertain number of objects will be pushed onto the end of the container. On the contrary, you should – when you’re tuning for performance. But you should also be aware that performance issues are usually not where you think they are, and the only way to know for sure where your bottlenecks are is by testing. Later in this chapter there will be a more “pure” comparison of performance between vector, deque and list.

Converting between sequences

Sometimes you need the behavior or efficiency of one kind of container for one part of your program, and a different container’s behavior or efficiency in another part of the program. For example, you may need the efficiency of a deque when adding objects to the container but the efficiency of a vector when indexing them. Each of the basic sequence containers (vector, deque and list) has a two-iterator constructor (indicating the beginning and ending of the sequence to read from when creating a new object) and an assign( ) member function to read into an existing container, so you can easily move objects from one sequence container to another.

Chapter 15: Multiple Inheritance

181

The following example reads objects into a deque and then converts to a vector:

//: C04:DequeConversion.cpp

// Reading into a Deque, converting to a vector #include "Noisy.h"

#include <deque> #include <vector> #include <iostream> #include <algorithm> #include <cstdlib> using namespace std;

int main(int argc, char* argv[]) { int size = 25;

if(argc >= 2) size = atoi(argv[1]); deque<Noisy> d;

generate_n(back_inserter(d), size, NoisyGen()); cout << "\n Converting to a vector(1)" << endl; vector<Noisy> v1(d.begin(), d.end());

cout << "\n Converting to a vector(2)" << endl; vector<Noisy> v2;

v2.reserve(d.size()); v2.assign(d.begin(), d.end()); cout << "\n Cleanup" << endl;

} ///:~

You can try various sizes, but you should see that it makes no difference – the objects are simply copy-constructed into the new vectors. What’s interesting is that v1 does not cause multiple allocations while building the vector, no matter how many elements you use. You might initially think that you must follow the process used for v2 and preallocate the storage to prevent messy reallocations, but the constructor used for v1 determines the memory need ahead of time so this is unnecessary.

Cost of overflowing allocated storage

It’s illuminating to see what happens with a deque when it overflows a block of storage, in contrast with VectorOverflow.cpp:

//: C04:DequeOverflow.cpp

//A deque is much more efficient than a vector

//when pushing back a lot of elements, since it

//doesn't require copying and destroying. #include "Noisy.h"

#include <deque> #include <cstdlib>

Chapter 15: Multiple Inheritance

182

using namespace std;

int main(int argc, char* argv[]) { int size = 1000;

if(argc >= 2) size = atoi(argv[1]); deque<Noisy> dn;

Noisy n;

for(int i = 0; i < size; i++) dn.push_back(n);

cout << "\n cleaning up \n"; } ///:~

Here you will never see any destructors before the words “cleaning up” appear. Since the deque allocates all its storage in blocks instead of a contiguous array like vector, it never needs to move existing storage (thus no additional copy-constructions and destructions occur). It simply allocates a new block. For the same reason, the deque can just as efficiently add elements to the beginning of the sequence, since if it runs out of storage it (again) just allocates a new block for the beginning. Insertions in the middle of a deque, however, could be even messier than for vector (but not as costly).

Because a deque never moves its storage, a held iterator never becomes invalid when you add new things to either end of a deque, as it was demonstrated to do with vector (in VectorCoreDump.cpp). However, it’s still possible (albeit harder) to do bad things:

//: C04:DequeCoreDump.cpp

// How to break a program using a deque #include <queue>

#include <iostream> using namespace std;

int main() {

deque<int> di(100, 0);

//No problem iterating from beginning to end,

//even though it spans multiple blocks: copy(di.begin(), di.end(),

ostream_iterator<int>(cout, " ")); deque<int>::iterator i = // In the middle:

di.begin() + di.size() / 2;;

//Walk the iterator forward as you perform

//a lot of insertions in the middle:

for(int j = 0; j < 1000; j++) { cout << j << endl;

di.insert(i++, 1); // Eventually breaks

}

} ///:~

Chapter 15: Multiple Inheritance

183