| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
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 {-bor}
// Reading into a Deque, converting to a vector.
//{L} Noisy
#include <algorithm>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#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 requirement
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.
//{L} Noisy
#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 << endl;
} ///:~
Here you will have relatively few (if any) destructors
called before the words cleaning up appear in the output. 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).
Because of deque s clever storage management,
an existing iterator is not invalidated after you add new things to either end
of a deque, as it was demonstrated to do with vector (in VectorCoreDump.cpp).
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.
| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
