deque c++ reference

A deque (pronounced "deck") is very similar to a vector. It manages its elements with a dynamic array, provides random access, and has almost the same interface as a vector. The difference is that with a deque the dynamic array is open at both ends. Thus, a deque is fast for insertions and deletions at both the end and the beginning (figure below).

Figure: Logical Structure of a Deque

To provide this ability, the deque is implemented typically as a bunch of individual blocks, with the first block growing in one direction and the last block growing in the opposite direction (figure below).

Figure: Internal Structure of a Deque

To use a deque, you must include the header file <deque>:

#include <deque>

There, the type is defined as a template class inside namespace std:

namespace std { template <class T, class Allocator = allocator<T> > class deque; }

As with vectors, the type of the elements is passed as a first template parameter and may be of any type that is assignable and copyable. The optional second template argument is the memory model, with allocator as the default.

Abilities of Deques

Deques have the following differences compared with the abilities of vectors:

• Inserting and removing elements is fast both at the beginning and at the end (for vectors it is only fast at the end). These operations are done in amortized constant time.
• The internal structure has one more indirection to access the elements, so element access and iterator movement of deques are usually a bit slower.
• Iterators must be smart pointers of a special type rather than ordinary pointers because they must jump between different blocks.
• In systems that have size limitations for blocks of memory (for example, some PC systems), a deque might contain more elements because it uses more than one block of memory. Thus, max_size() might be larger for deques.
• Deques provide no support to control the capacity and the moment of reallocation. In particular, any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque. However, reallocation may perform better than for vectors, because according to their typical internal structure, deques don't have to copy all elements on reallocation.
• Blocks of memory might get freed when they are no longer used, so the memory size of a deque might shrink (however, whether and how this happens is implementation specific).

The following features of vectors also apply to deques:

• Inserting and deleting elements in the middle is relatively slow because all elements up to either of both ends may be moved to make room or to fill a gap.
• Iterators are random access iterators.

In summary, you should prefer a deque if the following is true:

• You insert and remove elements at both ends (this is the classic case for a queue).
• You don't refer to elements of the container.
• It is important that the container frees memory when it is no longer used (however, the standard does not guarantee that this happens).

The interface of vectors and deques is almost the same, so trying both is very easy when no special feature of a vector or a deque is necessary.

Deque Operations

Table a through Table c list all operations provided for deques.

Table a:- Constructors and Destructor of Deques
Operation	Effect
deque<Elem> c	Creates an empty deque without any elements
deque<Elem> c1(c2)	Creates a copy of another deque of the same type (all elements are copied)
deque<Elem> c(n)	Creates a deque with n elements that are created by the default constructor
deque<Elem> c(n,elem)	Creates a deque initialized with n copies of element elem
deque<Elem> c(beg,end)	Creates a deque initialized with the elements of the range [beg,end)
c.~deque<Elem>()	Destroys all elements and frees the memory

Table b:- Nonmodifying Operations of Deques
Operation	Effect
c.size()	Returns the actual number of elements
c.empty ()	Returns whether the container is empty (equivalent to size()==0, but might be faster)
c.max_size()	Returns the maximum number of elements possible
c1 == c2	Returns whether c1 is equal to c2
c1 != c2	Returns whether c1 is not equal to c2 (equivalent to ! (c1==c2))
c1 < c2	Returns whether c1 is less than c2
c1 > c2	Returns whether c1 is greater than c2 (equivalent to c2<c1)
c1 <= c2	Returns whether c1 is less than or equal to c2 (equivalent to ! (c2<c1) )
c1 >= c2	Returns whether c1 is greater than or equal to c2 (equivalent to ! (c1<c2) )
c.at(idx)	Returns the element with index idx (throws range error exception if idx is out of range)
c[idx]	Returns the element with index idx (no range checking)
c.front()	Returns the first element (no check whether a first element exists)
c.back()	Returns the last element (no check whether a last element exists)
c.begin()	Returns a random access iterator for the first element
c.end()	Returns a random access iterator for the position after the last element
c.rbegin()	Returns a reverse iterator for the first element of a reverse iteration
c.rend()	Returns a reverse iterator for the position after the last element of a reverse iteration

Table c:- Modifying Operations of Deques
Operation	Effect
c1 = c2	Assigns all elements of c2 to c1
c.assign (n,elem)	Assigns n copies of element elem
c.assign (beg,end)	Assigns the elements of the range [beg,end)
c1.swap(c2)	Swaps the data of c1 and c2
swap(c1,c2)	Same (as global function)
c.insert (pos,elem)	Inserts at iterator position pos a copy of elem and returns the position of the new element
c. insert (pos,n,elem)	Inserts at iterator position pos n copies of elem (returns nothing)
c.insert (pos,beg,end)	Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing)
c.push_back (elem)	Appends a copy of elem at the end
c.pop_back()	Removes the last element (does not return it)
c.push_front (elem)	Inserts a copy of elem at the beginning
c.pop_front()	Removes the first element (does not return it)
c.erase(pos)	Removes the element at iterator position pos and returns the position of the next element
c.erase (beg,end)	Removes all elements of the range [beg,end) and returns the position of the next element
c. resize (num)	Changes the number of elements to num (if size () grows, new elements are created by their default constructor)
c.resize (num, elem)	Changes the number of elements to num (if size () grows, new elements are copies of elem)
c.clear()	Removes all elements (makes the container empty)

Deque operations differ from vector operations only as follows:

1. Deques do not provide the functions for capacity (capacity () and reserve ()).
2. Deques do provide direct functions to insert and to delete the first element (push_front () and pop_front()).

Because the other operations are the same, they are not reexplained here. Note that you still must consider the following:

1. No member functions for element access (except at ()) check whether an index or an iterator isvalid.
2. An insertion or deletion of elements might cause a reallocation. Thus, any insertion or deletioninvalidates all pointers, references, and iterators that refer to other elements of the deque. Theexception is when elements are inserted at the front or the back. In this case, references andpointers to elements stay valid (but iterators don't).

Exception Handling

In principle, deques provide the same support for exception handing as do vectors. The additional operations push_front() and pop_front() behave according to push_back() and pop_back () respectively. Thus, the C++ standard library provides the following behavior:

• If an element gets inserted with push_back () or push_front () and an exception occurs, these functions have no effect.
• Neither pop_back () nor pop_front () throw any exceptions.

Examples of Using Deques

The following program is a simple example that shows the abilities of deques:

#include <iostream> #include <deque> #include <string> #include <algorithm> using namespace std; int main() { //create empty deque of strings deque<string> coll; //insert several elements coll.assign (3, string("string")); coll.push_back ("last string"); coll.push_front ("first string"); //print elements separated by newlines copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n")); cout << endl; //remove first and last element coll.pop_front(); coll.pop_back(); //insert ''another'' into every element but the first for (int i=1; i<coll.size(); ++i) { coll[i] = "another " + coll [i]; } //change size to four elements coll.resize (4, "resized string"); //print elements separated by newlines copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n")); }

The program has the following output:

first string string string string last string string another string another string resized string

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

• Complete Tutorial of C++ Template's
• Standard Template Library Tutorial
• Inter Process Communication Tutorial
• Advance Programming in C & C++

-----------------------------------------------------------------

The Art of Learning with Innovation,
eLearning Courses for C and C++ Programming Language - The Most appreciated course !!!

Copyright © ccplusplus.com