deque

Overview

The standard library provides double ended array with random access deque.

Details

deque are basically resizable, double ended, sequence of elements with random access. New elements can be added at both the ends and inserted in the middle. Note that unlike vector, deque does not offer contiguous sequence of elements.

Syntax

The syntax is as below. Template parameter T represents the datatype to store and Alloc represents the allocator used for storage.

template < class T, class Alloc = allocator<T> > 
class deque;

Members

 It defines following types

Name	Description
value_type	The first template parameter (T)
allocator_type	The second template parameter (Alloc)
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer
const_pointer	allocator_traits<allocator_type>::const_pointer
iterator	a random access iterator to value_type convertible to const_iterator
const_iterator	a random access iterator to const value_type
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
difference_type	a signed integral type
size_type	an unsigned integral type

Operation

deque can be graphically represented as below.

Elements can be added at both the ends and can also be accessed randomly.

Complexity

The complexity of random access operation is O(1). Insertion or removal at the front and end is O(1). Insertion or removal at the middle is O(n) size().

Functionality

Constructors

In following constructors use default allocator. Custom allocators can be used by passing them as an additional argument.

Name	Description
deque ()	Default Constructor. Example: //v:{} deque<int> v;
deque (size_type n)	Constructs a container with n elements initialized with T(). Example: //v:{0,0,0,0,0} deque<int> v(5);
deque (size_type n, const value_type& val)	Constructs a container with n elements initialized with with val. Example: //v:{10,10,10,10,10} deque<int> v(5,10);
deque (InputIterator first, InputIterator last)	Constructs a container and copies the elements in the range. Example: int a[5]{1,2,3,4,5}; //v:{1,2,3,4,5} deque<int> v(begin(a),end(a));
deque (const deque & x)	copy constructor.
deque (deque && x)	move constructor.
deque (initializer_list<value_type> il)	initializer_list constructor. Example: //v:{1,2,3,4,5} deque<int> v{1,2,3,4,5};

Iterator

Name	Description
iterator begin() iterator end()	Returns iterator to beginning and end. Example: deque<int> v{1,2,3,4,5}; //prints 1 2 3 4 5 for (auto itr=v.begin(); itr!=v.end(); ++itr) cout << *itr << ' ';
reverse_iterator rbegin() reverse_iterator rend()	Returns reverse_iterator  to reverse beginning and reverse end. Example: deque<int> v{1,2,3,4,5}; //prints 5 4 3 2 1 for (auto itr=v.rbegin(); itr!=v.rend(); ++itr) cout << *itr << ' ';
const_iterator cbegin const_iterator cend()	Returns const_iterator to beginning and end. Example: deque<int> v{1,2,3,4,5}; //prints 1 2 3 4 5 for (auto itr=v.cbegin(); itr!=v.cend(); ++itr) cout << *itr << ' ';
const_reverse_iterator crbegin() const_reverse_iterator crend()	Returns const_reverse_iterator  to reverse beginning and reverse end. Example: deque<int> v{1,2,3,4,5}; //prints 5 4 3 2 1 for (auto itr=v.crbegin(); itr!=v.crend(); ++itr) cout << *itr << ' ';

Capacity

Name	Description
size_type size()	Returns the number of elements. Example: deque<int> v{1,2,3,4,5}; //prints 5 cout << v.size();
size_type max_size()	Returns maximum  possible number of elements possible. A very large number.
void resize (size_type n) void resize (size_type n, const value_type& val )	Size is changed to n. New elements are initialized to default value.  Size is changed to n. New elements are initialized to val.
Example deque<int> v{1,2,3}; //(1) //v:{1,2,3,0,0} v.resize(5); //prints 5 cout << v.size() ; //(2) //v:{1,2,3,0,0,9,9,9} v.resize(8,9); //prints 8 cout << v.size();
bool empty()	Tests whether size is 0.
void shrink_to_fit()	Reduces memory usage by freeing unused memory.
Example: template<class Tp> struct NAlloc { typedef Tp value_type; int MemAllocated=0; NAlloc() = default; template<class T> NAlloc(const NAlloc<T>&) {} Tp* allocate(std::size_t n) { n *= sizeof(Tp); MemAllocated+=n; return static_cast<Tp*>(::operator new(n)); } void deallocate(Tp* p, std::size_t n) { MemAllocated-=n; ::operator delete(p); } }; template<class T, class U> bool operator==(const NAlloc<T>&, const NAlloc<U>&) { return true; } template<class T, class U> bool operator!=(const NAlloc<T>&, const NAlloc<U>&) { return false; } //size=10 MemAllocated=4096 deque<int,NAlloc<int>> v(10); //size=4000 MemAllocated=16384 v.resize(4000); //size=10 MemAllocated=14336 v.resize(10); //size=10 MemAllocated=13312 v.shrink_to_fit();

Element Access

Name	Description
reference operator[](size_type n)	Returns reference  to the element at position n. No bounds check is done. Example: deque<int> v{1,2,3,4,5}; //prints 2 0. no exception checks cout << v[1] << " " << v[100];
reference at(size_type n)	Returns reference to the element at position n. Exception is thrown for invalid input. Example: deque<int> v{1,2,3,4,5}; //prints 2. exception is thrown. cout << v.at(1) << " " << v.at(100);
reference front()	Returns reference to the first element.  Exception is thrown for invalid input. Example: deque<int> v{1,2,3,4,5}; //prints 1. cout << v.front();
reference back()	Returns reference  to the last element.  Exception is thrown for invalid input. Example: vector<int> v{1,2,3,4,5}; //prints 5. cout << v.back();

Modifiers

Name	Description
void assign(InputIterator first, InputIterator last) void assign(size_type n, const value_type& val) void assign(initializer_list<value_type> il)	Replace deque content with the  elements in the range. Replace deque content  with n elements initialized with with val. Replace deque content with the contents of il.
Example: int a[]{1,2,3,4,5}; deque<int> v{}; //(1) //v:{3,4,5} v.assign(begin(a)+2,end(a)); //(2) //v:{10,10,10,10,10} v.assign(5,10); //(3) //v:{1,2,3} v.assign({1,2,3});
void push_back(const value_type& val)	Adds element at the end. Example: deque<int> v{}; //v:{1} v.push_back(1);
void pop_back()	Delete the last element. Example: vector<int> v{1}; //v:{} v.pop_back();
void push_front(const value_type& val)	Adds element at the end. Example: deque<int> v{}; //v:{1} v.push_front(1);
void pop_front()	Delete the last element. Example: deque<int> v{1}; //v:{} v.pop_front();
iterator insert(const_iterator pos, InputIterator first, InputIterator last) iterator insert(const_iterator pos, size_type n, const value_type& val) iterator  insert(const_iterator pos, const value_type& val) iterator  insert(const_iterator pos, const value_type&& val) iterator  insert(const_iterator pos,, initializer_list<value_type> il)	At pos, insert the  elements in the range. At pos, insert n elements initialized with with val. At pos, insert an element with value val. At pos, insert an element with value val moved. At pos, insert an element with the contents of initializer_list. All these returns an iterator to the first inserted element.
Example: int a[]{1,2,3,4,5}; deque<int> v{}; deque<int>::iterator itr; //(1) //v:{1,2,3,4,5} //itr = begin(v) itr = v.insert(cbegin(v),begin(a),end(a)); //(2) //v:{1,2,3,4,5,6} //itr = begin(v)+5 itr = v.insert(cend(v),1,6); //(3) //v:{1,2,3,4,5,6,7} //itr = begin(v)+6 itr = v.insert(cend(v),7); //(4) //v:{1,2,3,4,5,6,7,8} //itr = begin(v)+7 itr = v.insert(cend(v),move(8)); //(5) //v:{1,2,3,4,5,6,7,8,9,10} //itr = begin(v)+8 itr = v.insert(cend(v),{9,10});
iterator erase(const_iterator pos) iterator erase(const_iterator first, const_iterator last)	Erases element at pos Erase elements in the range Returns an iterator that points to the element that was  located after the last erased element.
Example: deque<int> v{1,2,3,4,5}; deque<int>::iterator itr; //(1) // v:{2,3,4,5} // itr = begin(v) itr = v.erase(cbegin(v)); //(2) // v:{2,3} // itr = begin(v)+2 itr = v.erase(cbegin(v)+2,cend(v));
void swap(deque & v)	Swap content with v. Note T has to be same. Example: deque<int> v{1,2,3,4,5}; deque<int> v2{5,4,3,2,1}; //v2:{1,2,3,4,5} //v:{1,2,3,4,5} v2.swap(v);
void clear()	Clears the contents. Example: deque<int> v{1,2,3,4,5}; //v:{} v.clear();
iterator emplace(const_iterator pos, Args ...arg)	Construct and insert element in place using arg. Returns an iterator to the first element inserted. Example: deque<int> v{1,2,3,5}; //v:{1,2,3,4,5} //itr=begin()+3 auto itr = v.emplace(cbegin(v)+3,4);
void emplace_front(Args ...arg)	Construct and insert element at the end using arg. Example: vector<int> v{2,3,4,5}; //v:{1,2,3,4,5} v.emplace_front(1);
void emplace_back(Args ...arg)	Construct and insert element at the end using arg. Example: vector<int> v{1,2,3,4}; //v:{1,2,3,4,5} v.emplace_back(5);