Deque

deque

Sequence

deque is a kind of sequence (See Sequences.) that, like a vector, supports random access iterators. In addition, it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time. As with vectors, storage management is handled automatically. See Reversible Container.

template  class Allocator = allocator>
class deque {
public:

// typedefs:
    typedef iterator;
    typedef const_iterator;
    typedef Allocator::pointer pointer;
    typedef Allocator::reference reference;
    typedef Allocator::const_reference const_reference;
    typedef size_type;
    typedef difference_type;
    typedef T value_type;
    typedef reverse_iterator;
    typedef const_reverse_iterator;

// allocation/deallocation:
    deque();
    deque(size_type n, const T& value = T());
    deque(const deque& x);
    template 
    deque(InputIterator first, InputIterator last);
    ~deque();
    deque& operator=(const deque& x);
    void swap(deque& x);

// accessors:
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator rend();
    size_type size() const;
    size_type max_size() const;
    bool empty() const;
    reference operator[](size_type n);
    const_reference operator[](size_type n) const;
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

// insert/erase:
    void push_front(const T& x);
    void push_back(const T& x);
    iterator insert(iterator position, const T& x = T());
    void insert (iterator position, size_type n, const T& x);
    template 
    void insert (iterator position, InputIterator first, InputIterator last);
    void pop_front();
    void pop_back();
    void erase(iterator position);
    void erase(iterator first, iterator last);
};

template 
bool operator==(const deque& x, const deque& y);

template 
bool operator<(const deque& x, const deque& y);

iterator

Typedef on deque

iterator is a random access iterator referring to T. The exact type is implementation dependent and determined by Allocator.

const_iterator

Typedef on deque

const_iterator is a constant random access iterator referring to const T. The exact type is implementation dependent and determined by Allocator. It is guaranteed that there is a constructor for const_iterator out of iterator.

size_type

Typedef on deque

size_type is an unsigned integral type. The exact type is implementation dependent and determined by Allocator.

difference_type

Typedef on deque

difference_type is a signed integral type. The exact type is implementation dependent and determined by Allocator.

insert (iterator position, const T& x = T());	Method on deque
insert (iterator position, size_type n, const T& x);	Method on deque
insert (iterator position, InputIterator first, InputIterator last);	Method on deque
push_front (const T& x);	Method on deque
push_back (const T& x);	Method on deque

insert in the middle of a deque invalidates all the iterators and references to the deque. insert and push at either end of a deque invalidate all the iterators to the deque, but have no effect on the validity of all the references to the deque. In the worst case, inserting a single element into a deque takes time linear in the minimum of the distance from the insertion point to the beginning of the deque and the distance from the insertion point to the end of the deque. Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to the copy constructor of T. That is, a deque is especially optimized for pushing and popping elements at the beginning and end.

erase (iterator position)	Method on deque
erase (iterator first, iterator last)	Method on deque
pop_front ()	Method on deque
pop_back ()	Method on deque

erase in the middle of a deque invalidates all the iterators and references to the deque. erase and pop at either end of a deque invalidate only the iterators and the references to the erased element. The number of calls to the destructor is the same as the number of elements erased, but the number of the calls to the assignment operator is equal to the minimum of the number of elements before the erased elements and the number of element after the erased elements.