Deque

deque¹ 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.