Deque
deque (usually pronounced like "deck") is an irregular acronym of double-ended queue. Double-ended queues are a kind of sequence containers. As such, their elements are ordered following a strict linear sequence.
Deques may be implemented by specific libraries in different ways, but in all cases they allow for the individual elements to be accessed through random access iterators, with storage always handled automatically (expanding and contracting as needed).
Deque sequences have the following properties:
Individual elements can be accessed by their position index.
Iteration over the elements can be performed in any order.
Elements can be efficiently added and removed from any of its ends (either the beginning or the end of the sequence).
Therefore they provide a similar functionality as the one provided by vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence and not only at its end. On the drawback side, unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.
Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.
For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists.
Global comparison operator functions
These overloaded global operator functions perform the appropriate comparison operation between deque containers x and y.
Operations == and != are performed by comparing the elements using algorithm equal.
Operations <, >, <= and >= are performed by using algorithm lexicographical_compare, which requires that the type of the elements (T) has the < operation (less-than) defined between two objects of that type.
These operators are overloaded in header <deque>.
// constructing deques
#include <iostream>#include <deque>using namespace std; void construct()
{
unsigned int i; // constructors used in the same order as described above: deque<int> first; // empty deque of ints deque<int> second (4,100); // four ints with value 100 deque<int> third (second.begin(),second.end()); // iterating through second deque<int> fourth (third); // a copy of third
fourth.clear(); if(true == fourth.empty())
cout << "Non Empty";
// the iterator constructor can also be used to construct from arrays: int myints[] = {16,2,77,29}; deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
deque<int>::iterator it; it=second.begin()+1; first.assign (it,second.end()-1); // the 2 central values of second, last iterator not included
first.at(3) = 50;
// cout << first.at(6); // exception thrown
// cout << first[6]; // memory corruption
cout << first.back(); // 50
first.erase(first.begin()+1);
first.erase(first.begin()+1, first.end()); // erase 3 elements
first.front() = 40;
}