Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
The deque container is a basic sequence 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, a typical implementation of 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 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 at either end. This means that vector is the
best choice only if you have a 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 have been more efficient had we used a deque
instead. The interface to deque differs only slightly from 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 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:
//: C07:StringDeque.cpp
// Converted from StringVector.cpp.
#include <cstddef>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
#include "../require.h"
using namespace std;
int main(int argc, char* argv[]) {
char* fname = "StringDeque.cpp";
if(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
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(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.7 MB 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 vector
vs. deque.
3. The string class is probably fairly well designed in terms
of efficiency.
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.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |