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(fname);
assure(in2, fname);
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(size_t 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(size_t j = 0; j < dstrings.size(); j++) {
ostringstream ss;
ss << j;
dstrings[j] = ss.str() + ": " + dstrings[j];
}
ticks = clock() - ticks;
cout << "Indexing deque: " << 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;
ticks = clock();
copy(dstrings.begin(), dstrings.end(),
ostream_iterator<string>(tmp2, "\n"));
ticks = clock() - ticks;
cout << "Iterating deque: " << ticks << endl;
} ///:~
Knowing now what you do about the inefficiency of adding things to vector because of storage reallocation, you might expect dramatic differences between the two. However, on a 1.7MB 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 deque: 2480
Iterating vector: 2470
Iterating deque: 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 and authors) are typically 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 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, you’ll see 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 you need 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.
The following example reads objects into a deque and then converts to a vector:
//: C07:DequeConversion.cpp
// Reading into a Deque, converting to a vector
//{-bor}
#include <algorithm>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <vector>
#include "Noisy.h"
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 note 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 this is unnecessary because the constructor used for v1 determines the memory need ahead of time.
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:
//: C07:DequeOverflow.cpp
//{-bor}
// 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 <cstdlib>
#include <deque>
#include "Noisy.h"
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 have relatively few (if any) destructors called 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 of each of its data blocks. (Thus, no additional copy-constructions and destructions occur.) The deque 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. (The index block that holds the data blocks together may need to be reallocated, however.) Insertions in the middle of a deque, however, could be even messier than for vector (but not as costly).