deque1 provides the same functionality as do
vectors (linear time insertion and deletion in the middle of the
container, constant time insertion and deletion at the end), and in
addition provide constant time insertion and deletion of elements at the
start of the deque. To use a deque in you program, you'll have to
include <deque>.
This is the only advantage that deque offers over
vector. You should only use them if you will definately be
performing regular insertions or deletions at the start and end, and
time is an important factor for such modifications.
There is little other difference between a vector and a deque,
other than performance. The following example is just a re-work of the example
given for vector3.cc; the only difference is that all occurrences of
vector are replaced with deque, and we've renamed
vector<Address v> to deque<Address> d.
/* deque1.cc
Compiled using g++ deque1.cc Address.cc -o deque1 */
#include <deque>
#include "AddressRepository.hh"
int main()
{
deque<Address> d;
/* Add all of the address objects to the deque: */
d.push_front(addr1);
d.push_front(addr2);
d.push_front(addr3);
d.push_front(addr4);
d.push_front(addr5);
/* Declare an iterator to work with: */
std::deque<Address>::iterator pos;
/* Loop through the deque printing out elements: */
cout << "First iteration" << endl;
for (pos=d.begin(); pos<d.end(); ++pos)
{
pos->print();
}
/* Remove the first element: */
d.pop_front();
/* Create and insert a new Address object: */
Address addr6("Reggie", "1 Card Rd.", "Hamps", 892286);
d.pop_front(addr6);
cout << "second iteration" << endl;
for (pos=d.begin() ; pos<d.end(); ++pos)
{
pos->print();
}
exit(0);
}
Example 3.8: deque1.cc
The output's a little different, because we used push_front and
pop_front instead of push_back and pop_back
respectively:
$ ./deque1
First iteration
Name: Bob, Street: 2 St. Annes Walk, City: Oxford, Phone: 303022
Name: Jane, Street: 55 Almond Terrace, City: Worcs, Phone: 242783
Name: Adam, Street: 23 Big St., City: Worcs, Phone: 443098
Name: Edith, Street: 91 Glib Terrace, City: Shrops, Phone: 858976
Name: Jane, Street: 12 Small St., City: Worcs, Phone: 225343
second iteration
Name: Reggie, Street: 1 Card Rd., City: Hamps, Phone: 892286
Name: Jane, Street: 55 Almond Terrace, City: Worcs, Phone: 242783
Name: Adam, Street: 23 Big St., City: Worcs, Phone: 443098
Name: Edith, Street: 91 Glib Terrace, City: Shrops, Phone: 858976
Name: Jane, Street: 12 Small St., City: Worcs, Phone: 225343
You'll agree that the code isn't to different from vector3.cc, but
we've already mentioned that vector and deque are
similar. Let's look at a few of the main differences between these two
containers.
Inserting elements at the front of a deque is the primary
advantage over vector. In the example above, we've demonstrated
this by using the push_front member function. By contrast
however, performing push_front operation with a vector
would have been very costly.
Insertions at the beginning or end of a deque invalidate all
(previously allocated) pointers, iterators and references. By contrast,
vector pointers, iterators and references are invalidated anytime
an element with a smaller index is inserted or removed, or the capacity
changes due to reallocation. You should consider this carefully if
you're going to use a deque; reallocating memory every time you
make a non-ended insertion or deletion could seriously slow things up,
especially for large collections of elements.
Generally, the similarities between vector and deque mean that
you should really consider using a deque over vector when
elements will be added and removed at both ends of the container, with little
insertion or removal in the middle.