Referencia del Archivo deque.h

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

#include <exception>
#include <iostream>

Ir al código fuente de este archivo.

Namespaces
namespace	std
Funciones
template<class T>
bool	check_ok (const deque< T > &Q)
	Verifica la invariante de la clase deque<T>.

---

Descripción detallada

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

Autor:

Adolfo Di Mare <[email protected]>

Fecha:

2006

Definición en el archivo deque.h.

---

Documentación de las funciones

template<class T> bool check_ok (  const deque< T > &  Q  )

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.

---

Hosted by www.Geocities.ws