Referencia de la Clase deque< T >

Vector extendible a ambos lados, almacenado en un vector circular. Más...

#include <deque.h>

Lista de todos los miembros.

Tipos públicos

typedef T value_type

Nombre estándar del objeto contenido.

typedef T * pointer

Nombre estándar del puntero al objeto contenido.

typedef T & reference

Nombre estándar de la referencia al objeto contenido.

typedef const value_type const_value_type

Nombre estándar del objeto contenido const.

typedef const T * const_pointer

Nombre estándar del puntero al objeto contenido const.

typedef const T & const_reference

Nombre estándar de la referencia al objeto contenido const.

typedef unsigned size_type

Nombre estándar del tipo retornado por size().

Métodos públicos

deque (size_type N)

Constructor: Vector extendible con capacidad para almacenar "N" valores.

~deque ()

Destructor.

bool empty () const

Retorna "true" si el vector extendible está vacía.

size_type size () const

Cantidad de valores almacenados en el vector extendible.

size_type capacity () const

Cantidad máxima de valores que se pueden almacenar en el vector extendible.

value_type & front ()

Retorna una referencia al primer valor del vector extendible.

const value_type & front () const

Retorna una referencia constante al primer valor del vector extendible.

value_type & back ()

Retorna una referencia al último valor del vector extendible.

const value_type & back () const

Retorna una referencia constante al último valor del vector extendible.

value_type & operator[] (size_type i)

Acceso al "i"-ésimo valor almacenado en el contenedor.

value_type & operator[] (size_type i) const

Acceso al "i"-ésimo valor almacenado en el contenedor ( const ).

value_type & at (size_type i)

Acceso al "i"-ésimo valor almacenado en el contenedor.

value_type & at (size_type i) const

Acceso al "i"-ésimo valor almacenado en el contenedor ( const ).

void push_front (const value_type &val)

Agrega una copia de "val" al principio del vector extendible.

void push_back (const value_type &val)

Agrega una copia de "val" al final del vector extendible.

void pop_front ()

Saca del vector extendible al valor que está al frente.

void pop_back ()

Saca del vector extendible al valor que está al frente.

Métodos privados

bool ok () const

Verifica la invariante de la clase.

value_type & at_check (size_type i)

Acceso al "i"-ésimo valor del vector extendible.

deque (const deque &)

"private" evita que el objeto sea copiado

Atributos privados

unsigned m_front

Indice del primero del vector extendible.

unsigned m_size

Cantidad de valores almacenados en el vector extendible (puede ser cero).

unsigned m_capacity

Cantidad máxima de valores que pueden estar almacenados en el vector extendible.

value_type * m_vec

Bloque de memoria para para almacenar los m_capacity valores que caben en el vector extendible.

Amigas

class test_deque

Datos de prueba para la clase.

template<class T>

std::istream & operator>> (std::istream &CIN, deque< T > &Q)

template<class T>

std::ostream & operator<< (std::ostream &COUT, const deque< T > &Q)

bool check_ok (const deque< T > &Q)

Verifica la invariante de la clase deque<T>.

Descripción detallada

template<class T>
class deque< T >

Vector extendible a ambos lados, almacenado en un vector circular.

Es posible agregar valores al principio o al final del vector extendible.
El tamaño del vector extendible no puede cambiar, pues se establece en el constructor.

Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04

Definición en la línea 27 del archivo deque.h.

Documentación de los 'Tipos Definidos' miembros de la clase

template<class T>

typedef T deque< T >::value_type

Nombre estándar del objeto contenido.

Definición en la línea 29 del archivo deque.h.

template<class T>

typedef T* deque< T >::pointer

Nombre estándar del puntero al objeto contenido.

Definición en la línea 30 del archivo deque.h.

template<class T>

typedef T& deque< T >::reference

Nombre estándar de la referencia al objeto contenido.

Definición en la línea 31 del archivo deque.h.

template<class T>

typedef const value_type deque< T >::const_value_type

Nombre estándar del objeto contenido const.

Definición en la línea 33 del archivo deque.h.

template<class T>

typedef const T* deque< T >::const_pointer

Nombre estándar del puntero al objeto contenido const.

Definición en la línea 34 del archivo deque.h.

template<class T>

typedef const T& deque< T >::const_reference

Nombre estándar de la referencia al objeto contenido const.

Definición en la línea 35 del archivo deque.h.

template<class T>

typedef unsigned deque< T >::size_type

Nombre estándar del tipo retornado por size().

Definición en la línea 37 del archivo deque.h.

Documentación del constructor y destructor

template<class T>

void deque< T >::deque ( size_type N )

Constructor: Vector extendible con capacidad para almacenar "N" valores.

Ver también:
test_deque<T>::test_deque()

Definición en la línea 116 del archivo deque.h.

template<class T>

deque< T >::~deque ( ) [inline]

Destructor.

Definición en la línea 41 del archivo deque.h.

template<class T>

deque< T >::deque ( const deque< T > & ) [explicit, private]

"private" evita que el objeto sea copiado

Documentación de las funciones miembro

template<class T>

bool deque< T >::empty ( ) const [inline]

Retorna "true" si el vector extendible está vacía.

Ver también:
test_deque<T>::test_empty()

Definición en la línea 44 del archivo deque.h.

template<class T>

size_type deque< T >::size ( ) const [inline]

Cantidad de valores almacenados en el vector extendible.

Ver también:
test_deque<T>::test_size()

Definición en la línea 47 del archivo deque.h.

template<class T>

size_type deque< T >::capacity ( ) const [inline]

Cantidad máxima de valores que se pueden almacenar en el vector extendible.

Ver también:
test_deque<T>::test_capacity()

Definición en la línea 49 del archivo deque.h.

template<class T>

value_type& deque< T >::front ( ) [inline]

Retorna una referencia al primer valor del vector extendible.

El primero valor es el que está "al frente" en el vector extendible.
Precondición:
!empty()

Ver también:
test_deque<T>::test_front()

Definición en la línea 55 del archivo deque.h.

template<class T>

const value_type& deque< T >::front ( ) const [inline]

Retorna una referencia constante al primer valor del vector extendible.

El primero valor es el que está "al frente" en el vector extendible.
Precondición:
!empty()

Ver también:
test_deque<T>::test_front_const()

Definición en la línea 61 del archivo deque.h.

template<class T>

value_type& deque< T >::back ( ) [inline]

Retorna una referencia al último valor del vector extendible.

El úlimo valor es el que está "al final" en el vector extendible.
Precondición:
!empty()

Ver también:
test_deque<T>::test_back()

Definición en la línea 68 del archivo deque.h.

template<class T>

const value_type& deque< T >::back ( ) const [inline]

Retorna una referencia constante al último valor del vector extendible.

El úlimo valor es el que está "al final" en el vector extendible.
Precondición:
!empty()

Ver también:
test_deque<T>::test_back_const()

Definición en la línea 74 del archivo deque.h.

template<class T>

value_type& deque< T >::operator[] ( size_type i ) [inline]

Acceso al "i"-ésimo valor almacenado en el contenedor.

No levanta ninguna excepción si "i" está fuera del rango válido.

Definición en la línea 78 del archivo deque.h.

template<class T>

value_type& deque< T >::operator[] ( size_type i ) const [inline]

Acceso al "i"-ésimo valor almacenado en el contenedor ( const ).

No levanta ninguna excepción si "i" está fuera del rango válido.

Definición en la línea 85 del archivo deque.h.

template<class T>

value_type& deque< T >::at ( size_type i ) [inline]

Acceso al "i"-ésimo valor almacenado en el contenedor.

Levanta la excepción std::out_of_range si "i" está fuera del rango válido.

Definición en la línea 89 del archivo deque.h.

template<class T>

value_type& deque< T >::at ( size_type i ) const [inline]

Acceso al "i"-ésimo valor almacenado en el contenedor ( const ).

Levanta la excepción std::out_of_range si "i" está fuera del rango válido.

Definición en la línea 92 del archivo deque.h.

template<class T>

void deque< T >::push_front ( const value_type & val )

Agrega una copia de "val" al principio del vector extendible.

Precondición:
size() < m_capacity

Ver también:
test_deque<T>::test_push_front()

Definición en la línea 188 del archivo deque.h.

template<class T>

void deque< T >::push_back ( const value_type & val )

Agrega una copia de "val" al final del vector extendible.

Precondición:
size() < m_capacity

Ver también:
test_deque<T>::test_push_back()

Definición en la línea 171 del archivo deque.h.

template<class T>

void deque< T >::pop_front ( ) [inline]

Saca del vector extendible al valor que está al frente.

Precondición:
!empty()

Ver también:
test_deque<T>::test_pop_front()

Definición en la línea 203 del archivo deque.h.

template<class T>

void deque< T >::pop_back ( ) [inline]

Saca del vector extendible al valor que está al frente.

Precondición:
!empty()

Ver también:
test_deque<T>::test_pop_back()

Definición en la línea 223 del archivo deque.h.

template<class T>

bool deque< T >::ok ( ) const [private]

Verifica la invariante de la clase.

Implementación para check_ok( const deque<T>& Q ).
Ver también:
check_ok( const deque<T>& Q)

Comentarios:

Desafortunadamente no fue posible lograr que el compilador aceptara una implementación directa para check_ok( const deque<T>& Q )
El ligador (linker) emite el error LNK2019. El truco para lidiar con este problema (work arount) es implementar ok()
Es mejor que check_ok() sea una función para evitarle al programador usuario la obligación de implementar el método ok()
http://www.di-mare.com/adolfo/binder/c04.htm#sc11
http://www.google.com/search?num=100&as_q=LNK2019+template+c%2B%2B
http://search.yahoo.com/search?n=100&p=LNK2019+template+c%2B%2B

- Invariante: ningún objeto puede estar almacenado en la posición nula.
- Invariante: La capacidad m_capacity debe ser mayor que cero.
- Invariante: El índice m_front no puede exceder m_capacity.
- Invariante: El índice m_size no puede exceder m_capacity.
- Invariante: La cantidad de valores almanenados size() no puede exceder m_capacity.
- Invariante: El vector m_vec[] debe existir en memoria dinámica.

Invariante: Todos los valores almacenados en el contenedor deben cumplir con su propia invariante

Definición en la línea 309 del archivo deque.h.

template<class T>

T & deque< T >::at_check ( size_type i ) [private]

Acceso al "i"-ésimo valor del vector extendible.

Si (i=>m_capacity) retorna el valor m_vec[i-m_capacity].
Verifica que el valor de "i" esté en el rango válido.
Está implementado de manera que el índice de at(m_front+m_size-1) siempre esté en el rango válido.
Funciona como si los índices que están a partir de m_capacity estuvieran en un vector, a la par de m_vec[].
Rango válido para "i": [[ m_front ==> m_front + m_size - 1 ]].
Levanta la excepción std::out_of_range si "i" está fuera del rango válido.
m_vec[] m_capacity==7 || \/ m_front==<5> <6> +---+---+---+---+---+---+---+ - at_check(<5>) es m_vec[5] | 5 | 6 | _ | _ | _ | 3 | 4 | - at_check(<6>) es m_vec[6] +---+---+---+---+---+---+---+ - at_check(<7>) es m_vec[0] +-------+ |-------+ - at_check(<8>) es m_vec[1] | #3 #4 m_front---+ #2 | | | - Sólo estos accesos son válidos +-<-<-----------------------<-<-+ - los demás levantan \c std::out_of_range m_size == 4

Definición en la línea 155 del archivo deque.h.

Documentación de las funciones relacionadas y clases amigas

template<class T>

friend class test_deque [friend]

Datos de prueba para la clase.

Definición en la línea 107 del archivo deque.h.

template<class T>

template<class T>

std::istream& operator>> ( std::istream & CIN,

deque< T > & Q

) [friend]

template<class T>

template<class T>

std::ostream& operator<< ( std::ostream & COUT,

const deque< T > & Q

) [friend]

template<class T>

bool check_ok ( const deque< T > & Q ) [friend]

Verifica la invariante de la clase deque<T>.

Regresa "true" si "*this" contiene un valor correcto.
Podría retornar "true" aún cuando "*this" tenga su valor corrupto.
Podría no retornar si "*this" tiene su valor corrupto.
http://www.di-mare.com/adolfo/binder/c04.htm#sc11
Ver también:
deque<T>::ok( )

Rep: Diagrama de la clase
+-------------------------------+ +-----------------------------------+ | m_vec[] | | m_vec[] m_capacity==7 | | || | | || | | \/ <1> <2>==m_front <6> | | \/ m_front==<5> <6> | | +---+---+---+---+---+---+---+ | | +---+---+---+---+---+---+---+ | | | _ | _ | 3 | 9 | 5 | 6 | _ | | | | 5 | 6 | _ | _ | _ | 3 | 9 | | | +---+---+---+---+---+---+---+ | | +---+---+---+---+---+---+---+ | | <0> |-----------+ | | +-------+ |-------+ | | m_front---+ #2 #3 #4 | | | #3 #4 m_front---+ #2 | | | | | | | | | m_size == 4 | | +-<-<-----------------------<-<-+ | +-------------------------------+ +-----------------------------------+

Rep: http://www.di-mare.com/adolfo/binder/c03.htm#k1-Rep

Rep: Descripción en palabras

Los valores del vector extendible están almacenados en memoria dinámica, consecutivamente, en el vector "m_vec[]" cuyo tamaño no puede cambiar pues queda definido cómo "deque<T>::m_capacity" cuando el objeto es construido.
El primer valor del vector extendible siempre está almacenado en "m_vec[m_front]".
El último valor del vector extendible siempre está almacenado en "m_vec[ (m_front+m_size-1) % m_capacity ]".
En el diagrama se muestran 2 formas en que puede estar almacenado el valor de una cola Q = [3,9,5,6] con "3" al frente y "6" al final.
En esta implementación del vector extendible se usa un vector circular en donde los valores están almacenados desde el índice "m_front" de "m_vec[]".
Como siempre el "frente" del vector extendible debe estar "antes" que el "final", cuando el valor de "m_front" no es "0", porque no apunta al principio del vector, lo que ocurre es que el vector extendible está almacenado llegando al final del vector y luego volviendo al principio (wrap-around).
La otra forma de almacenar el vector extendible en un vector circular es usar los campos "m_front" y "m_back", pero esta implementación tiene el problema de que es necesario desperdiciar uno de los campos del vector "m_vec[]" pues de otra manera no es posible determinar si el vector extendible está lleno o vacío.

Definición en la línea 103 del archivo deque.h.

Documentación de los datos miembro

template<class T>

unsigned deque< T >::m_front [private]

Indice del primero del vector extendible.

Definición en la línea 109 del archivo deque.h.

template<class T>

unsigned deque< T >::m_size [private]

Cantidad de valores almacenados en el vector extendible (puede ser cero).

Definición en la línea 110 del archivo deque.h.

template<class T>

unsigned deque< T >::m_capacity [private]

Cantidad máxima de valores que pueden estar almacenados en el vector extendible.

Definición en la línea 111 del archivo deque.h.

template<class T>

value_type* deque< T >::m_vec [private]

Bloque de memoria para para almacenar los m_capacity valores que caben en el vector extendible.

Definición en la línea 112 del archivo deque.h.

La documentación para esta clase fué generada a partir de los siguientes archivos:

Generado el Tue Aug 21 14:45:39 2007 para Contenedor deque: por

1.4.1

Hosted by www.Geocities.ws


Tipos públicos
typedef T	value_type
	Nombre estándar del objeto contenido.
typedef T *	pointer
	Nombre estándar del puntero al objeto contenido.
typedef T &	reference
	Nombre estándar de la referencia al objeto contenido.
typedef const value_type	const_value_type
	Nombre estándar del objeto contenido `const`.
typedef const T *	const_pointer
	Nombre estándar del puntero al objeto contenido `const`.
typedef const T &	const_reference
	Nombre estándar de la referencia al objeto contenido `const`.
typedef unsigned	size_type
	Nombre estándar del tipo retornado por `size()`.
Métodos públicos
	deque (size_type N)
	Constructor: Vector extendible con capacidad para almacenar `"N"` valores.
	~deque ()
	Destructor.
bool	empty () const
	Retorna `"true"` si el vector extendible está vacía.
size_type	size () const
	Cantidad de valores almacenados en el vector extendible.
size_type	capacity () const
	Cantidad máxima de valores que se pueden almacenar en el vector extendible.
value_type &	front ()
	Retorna una referencia al primer valor del vector extendible.
const value_type &	front () const
	Retorna una referencia constante al primer valor del vector extendible.
value_type &	back ()
	Retorna una referencia al último valor del vector extendible.
const value_type &	back () const
	Retorna una referencia constante al último valor del vector extendible.
value_type &	operator[] (size_type i)
	Acceso al `"i"-ésimo` valor almacenado en el contenedor.
value_type &	operator[] (size_type i) const
	Acceso al `"i"-ésimo` valor almacenado en el contenedor ( `const` ).
value_type &	at (size_type i)
	Acceso al `"i"-ésimo` valor almacenado en el contenedor.
value_type &	at (size_type i) const
	Acceso al `"i"-ésimo` valor almacenado en el contenedor ( `const` ).
void	push_front (const value_type &val)
	Agrega una copia de `"val"` al principio del vector extendible.
void	push_back (const value_type &val)
	Agrega una copia de `"val"` al final del vector extendible.
void	pop_front ()
	Saca del vector extendible al valor que está al frente.
void	pop_back ()
	Saca del vector extendible al valor que está al frente.
Métodos privados
bool	ok () const
	Verifica la invariante de la clase.
value_type &	at_check (size_type i)
	Acceso al `"i"-ésimo` valor del vector extendible.
	deque (const deque &)
	`"private"` evita que el objeto sea copiado
Atributos privados
unsigned	m_front
	Indice del primero del vector extendible.
unsigned	m_size
	Cantidad de valores almacenados en el vector extendible (puede ser cero).
unsigned	m_capacity
	Cantidad máxima de valores que pueden estar almacenados en el vector extendible.
value_type *	m_vec
	Bloque de memoria para para almacenar los `m_capacity` valores que caben en el vector extendible.
Amigas
class	test_deque
	Datos de prueba para la clase.
template<class T>
std::istream &	operator>> (std::istream &CIN, deque< T > &Q)
template<class T>
std::ostream &	operator<< (std::ostream &COUT, const deque< T > &Q)
bool	check_ok (const deque< T > &Q)
	Verifica la invariante de la clase `deque<T>`.

Referencia de la Clase deque< T >

Tipos públicos

Métodos públicos

Métodos privados

Atributos privados

Amigas