STL Deque


The deque (short form for double-ended queue) is similar to a vector. It has random access capability using subscripts but does not have the limitation of needing contiguous memory. Memory for a deque is allocated in terms of many storage blocks. Deque is efficient in insertions and deletions at its front and back. Unlike a vector it has the member functions push_front( ) and pop_front( ).

It does not have the capacity( ) and reserve( ) functions available in vectors. The reserve( ) function in vectors can be used to specify how many elements you will store in the vector (this will reduce the amount of reallocations in a vector). Generally a vector is advisable if you have an idea about the number of elements you will need to store. A deque is efficient in situations where you need to do frequent insertions and deletions at the front.

There are no exclusive deque member functions. All of the member functions are available in other containers (unlike the list container which has exclusive functions).


Let’s take a look at a simple program to illustrate a deque.

//Program to use the deque STL container

#include <iostream>
#include <deque>
using namespace std;

void display(deque<int> &deq)
{
deque<int>::iterator ptr;
for (ptr=deq.begin( );ptr!=deq.end( );ptr++)
{
    cout<<" "<<*ptr;
}
}

int main( )
{
deque<int> deqint;
deque<int>::reverse_iterator rptr;

for (int i=1;i<5;i++)
{
    deqint.push_front(i);
}
cout<<endl<<"Deque contains: ";
display(deqint);

cout<<endl<<"The first element is : "<<deqint[0];

deqint.at(2)=99;
cout<<endl<<"Deque contains: ";
display(deqint);

//using a reverse iterator to display contents
cout<<endl<<"Deque contents in reverse: ";
for (rptr=deqint.rbegin( ); rptr!=deqint.rend( ); rptr++)
{
    cout<<" "<<*rptr;
}

return 0;
}

The output will be:

Deque contains : 4 3 2 1

The first element is : 4

Deque contains : 4 3 99 1

Deque contents in reverse : 1 99 3 4

The functions are pretty much the same as we have seen earlier. We have used the reverse iterator to illustrate its working. Basically the reverse iterator can be used to pass through a container from the back to the front.

rbegin( ) will position the iterator at the end of the container. Whenever the reverse iterator is incremented it will move towards the beginning.


Learn about Associative Containers

Go back to Contents page 2.


Copyright © 2004 Sethu Subramanian All rights reserved.