Deque< T > Class Template Reference

Deque template. More...

#include <deque.hh>

Public Types
enum	{ RESERVE_GROW = (size_type) -1 }
	Constant passed to reserve() to grow the deque. More...
typedef T	value_type
	Value type.
typedef T &	reference
	Reference to value type.
typedef const T &	const_reference
	Const reference to value type.
typedef T *	pointer
	Pointer to value type.
typedef const T *	const_pointer
	Pointer to const value type.
typedef fast_argument< T >::type	value_argument_type
	Type used for value arguments (either T or const T &).
typedef const T &	const_access_type
typedef int	size_type
	Type of sizes (size()).
typedef Deque_iterator< T >	iterator
	Iterator type.
typedef Deque_const_iterator< T >	const_iterator
	Const iterator type.

Public Member Functions
	Deque ()
	Construct an empty deque.
	Deque (size_type n, value_argument_type v)
	Construct a deque containing n copies of v.
	Deque (const Deque< T > &x)
	Construct a deque as a copy of x.
Deque< T > &	operator= (const Deque< T > &x)
	Replace this deque's contents with a copy of x.
Deque< T > &	assign (size_type n, value_argument_type v=T())
	Replace this deque's contents with n copies of v.
iterator	begin ()
	Return an iterator for the first element in the deque.
iterator	end ()
	Return an iterator for the end of the deque.
const_iterator	begin () const
const_iterator	end () const
const_iterator	cbegin () const
	Return a const_iterator for the beginning of the deque.
const_iterator	cend () const
	Return a const_iterator for the end of the deque.
size_type	size () const
	Return the number of elements.
size_type	capacity () const
	Return the deque's capacity.
bool	empty () const
	Test if the deque is empty (size() == 0).
void	resize (size_type n, value_argument_type v=T())
	Resize the deque to contain n elements.
bool	reserve (size_type n)
	Reserve space for at least n more elements.
T &	operator[] (size_type i)
	Return a reference to the ith element.
const T &	operator[] (size_type i) const
T &	at (size_type i)
	Return a reference to the ith element.
const T &	at (size_type i) const
T &	front ()
	Return a reference to the first element.
const T &	front () const
T &	back ()
	Return a reference to the last element (number size()-1).
const T &	back () const
T &	unchecked_at (size_type i)
	Return a reference to the ith element.
const T &	unchecked_at (size_type i) const
T &	at_u (size_type i)
const T &	at_u (size_type i) const
void	push_back (value_argument_type v)
	Append v to the end of the deque.
void	pop_back ()
	Remove the last element.
void	push_front (value_argument_type v)
	Prepend element v.
void	pop_front ()
	Remove the first element.
iterator	insert (iterator it, value_argument_type v)
	Insert v before position it.
iterator	erase (iterator it)
	Remove the element at position it.
iterator	erase (iterator a, iterator b)
	Remove the elements in [a, b).
void	clear ()
	Remove all elements.
void	swap (Deque< T > &x)
	Swap the contents of this deque and x.

Detailed Description

template<typename T>
class Deque< T >

Deque template.

Deque implements a double-ended queue: a growable array that can efficiently add and remove elements at both ends (see push_back(), pop_back(), push_front(), and pop_front()). Its interface should be compatible with C++'s std::deque, although that type has more methods. Deque elements are accessed with operator[] like arrays.

Deque is implemented using a circular buffer of elements. This makes its operations slightly slower than those of Vector. If you only need to push elements to the end of an array, prefer Vector.

Example code:

Deque<int> d;
printf("%d\n", d.size());         // prints "0"
 
d.push_back(1);
d.push_back(2);
printf("%d\n", d.size());         // prints "2"
printf("%d %d\n", d[0], d[1]);    // prints "1 2"
 
d.push_front(0);
d.push_front(-1);
printf("%d\n", d.size());         // prints "4"
printf("%d %d %d %d\n", d[0], d[1], d[2], d[3]);
                                  // prints "-1 0 1 2"
 
d.pop_front();
d.pop_back();
printf("%d\n", d.size());         // prints "2"
printf("%d %d\n", d[0], d[1]);    // prints "0 1"

Member Typedef Documentation

value_type

template<typename T >

typedef T Deque< T >::value_type

Value type.

reference

template<typename T >

typedef T& Deque< T >::reference

Reference to value type.

const_reference

template<typename T >

typedef const T& Deque< T >::const_reference

Const reference to value type.

pointer

template<typename T >

typedef T* Deque< T >::pointer

Pointer to value type.

const_pointer

template<typename T >

typedef const T* Deque< T >::const_pointer

Pointer to const value type.

value_argument_type

template<typename T >

typedef fast_argument<T>::type Deque< T >::value_argument_type

Type used for value arguments (either T or const T &).

size_type

template<typename T >

typedef int Deque< T >::size_type

Type of sizes (size()).

iterator

template<typename T >

typedef Deque_iterator<T> Deque< T >::iterator

Iterator type.

const_iterator

template<typename T >

typedef Deque_const_iterator<T> Deque< T >::const_iterator

Const iterator type.

Member Enumeration Documentation

anonymous enum

template<typename T >

anonymous enum

Constant passed to reserve() to grow the deque.

Constructor & Destructor Documentation

Deque() [1/3]

template<typename T >

Deque< T >::Deque ( )

inlineexplicit

Construct an empty deque.

Deque() [2/3]

template<typename T >

Deque< T >::Deque ( size_type  n, value_argument_type  v  )

inlineexplicit

Construct a deque containing n copies of v.

Deque() [3/3]

template<typename T >

Deque< T >::Deque ( const Deque< T > &  x )

inline

Construct a deque as a copy of x.

Member Function Documentation

operator=()

template<typename T >

Deque< T > & Deque< T >::operator= ( const Deque< T > &  x )

inline

Replace this deque's contents with a copy of x.

assign()

template<typename T >

Deque< T > & Deque< T >::assign ( size_type  n, value_argument_type  v = T()  )

inline

Replace this deque's contents with n copies of v.

Postcondition

size() == n

begin() [1/2]

template<typename T >

Deque< T >::iterator Deque< T >::begin ( )

inline

Return an iterator for the first element in the deque.

end() [1/2]

template<typename T >

Deque< T >::iterator Deque< T >::end ( )

inline

Return an iterator for the end of the deque.

Invariant

end() == begin() + size()

begin() [2/2]

template<typename T >

Deque< T >::const_iterator Deque< T >::begin ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

end() [2/2]

template<typename T >

Deque< T >::const_iterator Deque< T >::end ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

cbegin()

template<typename T >

Deque< T >::const_iterator Deque< T >::cbegin ( ) const

inline

Return a const_iterator for the beginning of the deque.

cend()

template<typename T >

Deque< T >::const_iterator Deque< T >::cend ( ) const

inline

Return a const_iterator for the end of the deque.

Invariant

end() == begin() + size()

size()

template<typename T >

Deque< T >::size_type Deque< T >::size ( ) const

inline

Return the number of elements.

capacity()

template<typename T >

Deque< T >::size_type Deque< T >::capacity ( ) const

inline

Return the deque's capacity.

The capacity is greater than or equal to the size(). Functions such as resize(n) will not allocate new memory for the deque if n <= capacity().

empty()

template<typename T >

bool Deque< T >::empty ( ) const

inline

Test if the deque is empty (size() == 0).

resize()

template<typename T >

void Deque< T >::resize ( size_type  n, value_argument_type  v = T()  )

inline

Resize the deque to contain n elements.

never

Parameters

n	new size
v	value used to fill new elements

reserve()

template<typename T >

bool Deque< T >::reserve ( size_type  n )

inline

Reserve space for at least n more elements.

Returns

true iff reserve succeeded.

This function changes the deque's capacity(), not its size(). If reserve(n) succeeds, then any succeeding call to resize(m) with m < n will succeed without allocating deque memory.

operator[]() [1/2]

template<typename T >

T & Deque< T >::operator[] ( size_type  i )

inline

Return a reference to the ith element.

Precondition

0 <= i < size()

operator[]() [2/2]

template<typename T >

const T & Deque< T >::operator[] ( size_type  i ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

at() [1/2]

template<typename T >

T & Deque< T >::at ( size_type  i )

inline

Return a reference to the ith element.

Precondition

0 <= i < size()

See also

operator[]()

at() [2/2]

template<typename T >

const T & Deque< T >::at ( size_type  i ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

front() [1/2]

template<typename T >

T & Deque< T >::front ( )

inline

Return a reference to the first element.

Precondition

!empty()

front() [2/2]

template<typename T >

const T & Deque< T >::front ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

back() [1/2]

template<typename T >

T & Deque< T >::back ( )

inline

Return a reference to the last element (number size()-1).

Precondition

!empty()

back() [2/2]

template<typename T >

const T & Deque< T >::back ( ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

unchecked_at() [1/2]

template<typename T >

T & Deque< T >::unchecked_at ( size_type  i )

inline

Return a reference to the ith element.

Precondition

0 <= i < size()

Unlike operator[]() and at(), this function does not check bounds, even if assertions are enabled. Use with caution.

unchecked_at() [2/2]

template<typename T >

const T & Deque< T >::unchecked_at ( size_type  i ) const

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

push_back()

template<typename T >

void Deque< T >::push_back ( value_argument_type  v )

inline

Append v to the end of the deque.

A copy of v is added to position size(). Takes amortized O(1) time.

pop_back()

template<typename T >

void Deque< T >::pop_back ( )

inline

Remove the last element.

Takes O(1) time.

push_front()

template<typename T >

void Deque< T >::push_front ( value_argument_type  v )

inline

Prepend element v.

A copy of v is added to position 0. Other elements are shifted one position forward. Takes amortized O(1) time.

pop_front()

template<typename T >

void Deque< T >::pop_front ( )

inline

Remove the first element.

Other elements are shifted one position backward. Takes O(1) time.

insert()

template<typename T >

Deque< T >::iterator Deque< T >::insert ( iterator  it, value_argument_type  v  )

inline

Insert v before position it.

Returns

An iterator pointing at the new element.

erase() [1/2]

template<typename T >

Deque< T >::iterator Deque< T >::erase ( iterator  it )

inline

Remove the element at position it.

Returns

An iterator pointing at the element following it.

erase() [2/2]

template<typename T >

Deque< T >::iterator Deque< T >::erase ( iterator  a, iterator  b  )

inline

Remove the elements in [a, b).

Returns

An iterator corresponding to b.

clear()

template<typename T >

void Deque< T >::clear ( )

inline

Remove all elements.

Postcondition

size() == 0

swap()

template<typename T >

void Deque< T >::swap ( Deque< T > &  x )

inline

Swap the contents of this deque and x.

---

The documentation for this class was generated from the following file:

• include/click/deque.hh