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:
//: C20: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);
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;
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
A
different compiler and platform roughly agreed with this. It’s not so
dramatic, is it? This points out some important issues:
- We
(programmers) are typically very bad at guessing where inefficiencies occur in
our programs.
- 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.
- 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.
The
following example reads objects into a
deque
and then converts to a
vector:
//: C20: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:
//: C20: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>
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:
//: C20: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
}Of
course, there are two things here that you wouldn’t normally do with a
deque:
first, elements are inserted in the middle, which
deque
allows but isn’t designed for. Second, calling
insert( )
repeatedly with the same iterator would not ordinarily cause an access
violation, but the iterator is walked forward after each insertion. I’m
guessing it eventually walks off the end of a block, but I’m not sure
what actually causes the problem.
If
you stick to what
deque
is best at – insertions and removals from either end, reasonably rapid
traversals and fairly fast random-access using
operator[
]
– you’ll be in good shape.
Checked
random-access
Both
vector
and
deque
provide two ways to perform random access of their elements: the
operator[
]
,
which you’ve seen already, and
at( ),
which checks the boundaries of the container that’s being indexed and
throws an exception if you go out of bounds. It does cost more to use
at( ):
//: C20:IndexingVsAt.cpp
// Comparing "at()" to operator[]
#include "../require.h"
#include <vector>
#include <deque>
#include <iostream>
#include <ctime>
using namespace std;
int main(int argc, char* argv[]) {
requireMinArgs(argc, 1);
long count = 1000;
int sz = 1000;
if(argc >= 2) count = atoi(argv[1]);
if(argc >= 3) sz = atoi(argv[2]);
vector<int> vi(sz);
clock_t ticks = clock();
for(int i1 = 0; i1 < count; i1++)
for(int j = 0; j < sz; j++)
vi[j];
cout << "vector[]" << clock() - ticks << endl;
ticks = clock();
for(int i2 = 0; i2 < count; i2++)
for(int j = 0; j < sz; j++)
vi.at(j);
cout << "vector::at()" << clock()-ticks <<endl;
deque<int> di(sz);
ticks = clock();
for(int i3 = 0; i3 < count; i3++)
for(int j = 0; j < sz; j++)
di[j];
cout << "deque[]" << clock() - ticks << endl;
ticks = clock();
for(int i4 = 0; i4 < count; i4++)
for(int j = 0; j < sz; j++)
di.at(j);
cout << "deque::at()" << clock()-ticks <<endl;
// Demonstrate at() when you go out of bounds:
di.at(vi.size() + 1);As
you’ll learn in the exception-handling chapter, different systems may
handle the uncaught exception in different ways, but you’ll know one way
or another that something went wrong with the program when using
at( ),
whereas it’s possible to go blundering ahead using
operator[
]
.
Contact: webmaster@codeguru.com
CodeGuru - the website for developers.