Referencia de la plantilla de la Clase Aleph::DynArray< T >

#include <tpl_dynArray.H>

Diagrama de herencias de Aleph::DynArray< T >

Clases
class	Iterator

Tipos públicos
typedef T	Item_Type
typedef T	Key_Type

Métodos públicos
size_t	get_dir_size () const
	Retorna tamaño del directorio.
size_t	get_seg_size () const
	Retorna tamaño del segmento.
size_t	get_block_size () const
	Retorna tamaño del bloque.
size_t	size () const
	Retorna dimensión actual (más lejano índice escrito)
size_t	max_size () const
	Retorna máxima dimensión permitida.
size_t	get_num_blocks () const
	Retorna la cantidad de bloques actualmente apartados.
void	set_default_initial_value (const T &value)
void	set_default_initial_value (T &&value=T())
	DynArray (size_t _pow_dir, size_t _pow_seg, size_t _pow_block) throw (std::exception, std::bad_alloc, std::length_error, std::overflow_error)
	DynArray (const size_t dim=0) throw (std::exception, std::bad_alloc, std::length_error, std::overflow_error)
	DynArray (const DynList< T > &list)
	~DynArray ()
	Destructor que libera toda la memoria ocupada.
void	copy_array (const DynArray< T > &src_array)
	DynArray (const DynArray< T > &array) throw (std::exception, std::bad_alloc)
DynArray< T > &	operator= (const DynArray< T > &array) throw (std::exception, std::bad_alloc)
void	swap (DynArray< T > &array)
	DynArray (DynArray &&other)
DynArray &	operator= (DynArray &&other)
T &	access (const size_t i)
T &	operator() (const size_t i)
const T &	access (const size_t i) const
const T &	operator() (const size_t i) const
bool	exist (const size_t i) const throw (std::exception, std::out_of_range)
T *	test (const size_t i) const
T &	touch (const size_t i) throw (std::exception, std::bad_alloc, std::out_of_range)
void	reserve (const size_t l, const size_t r) throw (std::exception, std::bad_alloc, std::domain_error, std::length_error)
void	reserve (const size_t dim)
void	cut (const size_t new_dim=0) throw (std::exception, std::domain_error)
void	empty ()
Proxy	operator[] (const size_t i) const throw (std::exception, std::bad_alloc, std::length_error, std::invalid_argument)
Proxy	operator[] (const size_t i) throw (std::exception, std::length_error, std::invalid_argument, std::bad_alloc)
T &	append ()
T &	append (const T &data)
T &	append (T &&data)
void	push (const T &data)
	Inserta como en una pila un elemento al final del arreglo.
T &	push ()
	Aparta un elemento al final del arrreglo.
bool	is_empty ()
T	pop ()
	Elimina el último elemento del arreglo como si fuese una pila.
T &	top ()
	Retorna el último elemento del arreglo como si fuese una pila.
T &	get_first ()
	Retorna el último elemento del arreglo como si fuese una cola.
T &	get_last ()
	Retorna el primer elemento del arreglo como si fuese una cola.
template<class Operation >
bool	traverse (Operation &operation) const
template<class Operation >
bool	traverse (Operation &operation)
template<class Operation >
bool	traverse (Operation &&operation=Operation()) const
template<class Operation >
bool	traverse (Operation &&operation=Operation())
	Functional_Methods (T)

Métodos públicos estáticos
static void	compute_sizes (const size_t n, size_t &d, size_t &s, size_t &b)

Atributos públicos estáticos
static const size_t	Default_Pow_Dir = 6
static const size_t	Default_Pow_Seg = 8
static const size_t	Default_Pow_Block = 12
static const size_t	Max_Bits_Allowed = 8 * sizeof(size_t)
static const unsigned long long	Max_Dim_Allowed

Descripción detallada

template<typename T>
class Aleph::DynArray< T >

Arreglo dinámico perezoso.

Esta clase implementa arreglo dinámicos perezosos. Por dinámico se entiende que la memoria es automáticamente apartada en función de la dimensión. Por perezoso se entiende que la memoria puede apartarse en tiempo de escritura.

Parámetros

T	El tipo de dato del arreglo.

Un arreglo dinámico maneja tres valores muy importantes que determinan su dinamismo. Estos valores son llamados:

• block_size: Idealmente, un arreglo dinámico puede verse como una agrupación de bloques de tamaño block_size. Inicialmente, el arreglo dinámico no tiene ningún bloque apartado. Cuando por primera vez se escribe una entrada b[i], se aparta un bloque que albergará a b[i] y sus entradas aledañas. A medida que el valor de block_size sea mayor, se requerirá apelar menos al manejador de memoria y se aprovechará más la localidad de referencia dada por el cache de hardware, pero como el bloque es continuo la probabilidad de falla por memoria aumenta. Un valor pequeño hace más probable apartar memoria
• seg_size: los bloques se indizan mediante un arreglo llamado segmento.
• dir_size: a su vez, los segmentos se indizan en otro arreglo llamado directorio.

Para lograr un acceso constante lo más eficiente posible, estos tamaños son potencias exactas de dos.

Un arreglo dinámico recién inicializado sólo ocupa un arreglo continuo correspondiente al directorio.

La máxima dimensión del arreglo dinámico está limitada por dir_size x seg_size x block_size elementos.

El arreglo dinámico maneja una dimensión actual, la cual se especifica en tiempo de construcción y que se expande automáticamente si se escriben entradas por encima de la dimensión actual.

Los elementos pueden accederse de diversas formas. Siendo la principal mediante el tradicional operador [], la cual realiza todas las verificaciones de rango, aparta automáticamente la memoria y puede expandir la dimensión.

Puesto que la unidad de apartado de memoria es el bloque, no hay garantía de que una entrada leída se corresponda con una ya escrita.

Documentación del constructor y destructor

template<typename T>

Aleph::DynArray< T >::DynArray ( size_t  _pow_dir, size_t  _pow_seg, size_t  _pow_block  ) throw ( std::exception, std::bad_alloc, std::length_error, std::overflow_error )

inline

Constructor especializado.

Define un arreglo dinámico con tamaños de directorio, segmento y bloque.

Parámetros

[in]	_pow_dir	Potencia de dos tamaño del directorio.
[in]	_pow_seg	Potencia de dos tamaño del segmento.
[in]	_pow_block	Potencia de dos tamaño del bloque.

Excepciones

bad_alloc	si no hay memoria para apartar el directorio. Esto puede ocurrir porque es demasiado grande o porque hay muy poca memoria disponible.
length_error	Si los tamaños seleccionados exceden la máxima dimensión posible
overflow_error	Si ocurre overflow de con las operaciones de bits.

template<typename T>

Aleph::DynArray< T >::DynArray ( const size_t  dim = 0 ) throw ( std::exception, std::bad_alloc, std::length_error, std::overflow_error )

inline

Constructor por omisión.

Este es el constructor por omisión en el cual se especifica una dimensión. Los tamaños de directorio, segmento y bloque son seleccionados automáticamente.

Parámetros

[in]

dim

dimensión inicial del arreglo (puede expandirse automáticamente si se escribe más allá de ella)

Excepciones

bad_alloc	si no hay memoria para apartar el directorio. Esto puede ocurrir porque es demasiado grande o porque hay muy poca memoria disponible.
length_error	Si los tamaños seleccionados exceden la máxima dimensión posible
overflow_error	Si ocurre overflow de con las operaciones de bits.

template<typename T>

Aleph::DynArray< T >::DynArray ( const DynArray< T > &  array ) throw ( std::exception, std::bad_alloc )

inline

Constructor copia.

Copia elemento a elemento el arreglo array a this. Los tamaños de directorio, segmento y bloque de this serán los mismo que los de array.

Parámetros

[in]

array

arreglo fuente de la copia.

Excepciones

bad_alloc

si no hay suficiente memoria.

Documentación de las funciones miembro

template<typename T>

T& Aleph::DynArray< T >::access ( const size_t  i )

inline

Acceso rápido sin validación.

Esta rutina accede al i-ésimo elemento del arreglo de la manera más rápida posible en detrimento de verificar si la entrada existe, bien sea porque no ha sido escrita o porque está fuera de rango.

El fin de esta función es realizar un acceso a la velocidad máxima bajo la certitud de utilización.

Independientemente que el acceso sea o no válido, esta fuunción actualiza la dimensión actual del arreglo en caso de que el índice i sea mayor.

Parámetros

[in]

i

índice de la entrada de acceso.

Nota

Úsese con extremo cuidado. Si la entrada no tiene un bloque apartado, entonces, en el mejor de los casos, habrá una falla de memoria con su correspondiente excepción del sistema operativo. De lo contrario, entonces el acceso será realizado pero ello no implica que sea correcto.

Ver también

exist

Referenciado por Aleph::binary_search(), Aleph::bubble_sort(), Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks(), Aleph::DynArray< pthread_mutex_t >::copy_array(), Aleph::heapsort(), Aleph::insertion_sort(), Aleph::kosaraju_connected_components(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::load(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::load_in_text_mode(), Aleph::Matrix_Graph< GT, SA >::operator()(), Aleph::BitArray::read(), DynArray_Set< T, Equal >::remove(), Aleph::BitArray::save(), Aleph::BitArray::save_in_array_of_chars(), DynArray_Set< T, Equal >::search(), Aleph::search_cycle(), Aleph::search_extreme(), Aleph::selection_sort(), Aleph::sequential_search(), Aleph::shellsort() y Aleph::BitArray::write().

Gráfico de llamadas a esta función:

template<typename T>

const T& Aleph::DynArray< T >::access ( const size_t  i ) const

inline

Acceso rápido sin validación a arreglo constante.

Esta rutina accede al i-ésimo elemento del arreglo de la manera más rápida posible en detrimento de verificar si la entrada existe, bien sea porque no ha sido escrita o porque está fuera de rango.

El fin de esta función es realizar un acceso a la velocidad máxima bajo la certitud de utilización.

Parámetros

[in]

i

índice de la entrada de acceso.

Nota

Úsese con extremo cuidado. Si la entrada no tiene un bloque apartado, entonces, en el mejor de los casos, habrá una falla de memoria con su correspondiente excepción del sistema operativo. De lo contrario, entonces el acceso será realizado pero ello no implica que sea correcto.

Ver también

exist

template<typename T>

T& Aleph::DynArray< T >::append ( )

inline

Aparta un elemento al final del arrreglo. Retotna referencia a la entrada apartada

Referenciado por DynArray_Set< T, Equal >::put().

Gráfico de llamadas a esta función:

template<typename T>

T& Aleph::DynArray< T >::append ( const T &  data )

inline

Escribe un elemento al final del arreglo. Retorna referencia al lugar del arreglo donde el elemento fue escrito

template<typename T>

static void Aleph::DynArray< T >::compute_sizes ( const size_t  n, size_t &  d, size_t &  s, size_t &  b  )

inlinestatic

Propone potencias de dos para directorio, segmento y bloques que sean suficientes para albergar un arreglo de dimensión n.

Referenciado por Aleph::DynMatrix< long >::set_dimension().

Gráfico de llamadas a esta función:

template<typename T>

void Aleph::DynArray< T >::copy_array ( const DynArray< T > &  src_array )

inline

Copia de elemento a elemento.

Copia todos los elementos de src_array a this. La copia se realiza elemento por elemento de entre los escritos en src_array.

Nota

Los tamaños de directorio, segmento y bloque son independientes.

Parámetros

[in]

src_array

arreglo fuente de la copia

template<typename T>

void Aleph::DynArray< T >::cut ( const size_t  new_dim = 0 ) throw ( std::exception, std::domain_error )

inline

Corta un arreglo; reduce su dimensión.

cut(dim) reduce la dimensión del arreglo al valor de dim. Para que el método tenga sentido, dim debe ser menor que la dimensión actual. Después de la operación, la memoria ocupada por los bloques superiores a la nueva dimensión han sido liberados.

En general, cut() se utiliza para liberar memoria.

Parámetros

new_dim

valor de la nueva dimensión. Por omisión, este valor es cero, en cuyo caso se liberan todos los bloques.

Excepciones

domain_error

si la new_dim es mayor que la dimensión actual.

Referenciado por Aleph::Map_Matrix_Graph< GT, SA >::copy_list_graph(), Aleph::BitArray::empty(), Aleph::BitArray::load(), Aleph::BitArray::load_from_array_of_chars(), Aleph::Bellman_Ford< GT, Distance, SA >::paint_spanning_tree(), Aleph::BitArray::pop(), DynArray_Set< T, Equal >::remove() y Aleph::BitArray::set_size().

Gráfico de llamadas a esta función:

template<typename T>

void Aleph::DynArray< T >::empty ( )

inline

Libera toda la memoria ocupada por el arreglo. La dimensión queda en cero.

template<typename T>

bool Aleph::DynArray< T >::exist ( const size_t  i ) const throw ( std::exception, std::out_of_range )

inline

Retorna true si existe la entrada i.

El método verifica si la entrada i está presente en memoria; es decir, si puede leerse con seguridad de que existe un bloque apartado para la entrada.

El que el método retorne true no necesariamente implica que la entrada fue previamente escrita (podría tratarse de una entrada no escrita pero aledaña a una escrita que comparte el mismo bloque.

Parámetros

[in]

i

índice de la entrada que se desea verificar.

Excepciones

out_of_range

si i excede la máxima dimensión.

Referenciado por Aleph::DynArray< pthread_mutex_t >::copy_array(), Aleph::Matrix_Graph< GT, SA >::operator()(), Aleph::BitArray::save(), Aleph::BitArray::save_in_array_of_chars() y Aleph::sequential_search().

Gráfico de llamadas a esta función:

template<typename T>

DynArray<T>& Aleph::DynArray< T >::operator= ( const DynArray< T > &  array ) throw ( std::exception, std::bad_alloc )

inline

Asignación.

Asigna a this todos los elementos existentes de array.

Parámetros

[in]

array

arreglo fuente de la copia.

Excepciones

bad_alloc

si no hay suficiente memoria.

template<typename T>

void Aleph::DynArray< T >::reserve ( const size_t  l, const size_t  r  ) throw ( std::exception, std::bad_alloc, std::domain_error, std::length_error )

inline

Reserva un rango de memoria.

reserve(l, r) verifica el rango de entradas del arreglo comprendido entre l y r y asegura que haya memoria.

Parámetros

[in]	l	índice inferior
[in]	r	índice superior

Excepciones

std::bad_alloc	si no hay suficiente memoria. En ese caso, no hay manera precisa de saber hasta donde ha sido apartada la memoria. Si l es mayor que la antigua dimensión, entonces el valor de la dimensión actual estará modificado hasta el último bloque apartado.
domain_error	si l es mayor que r
length_error	si r es mayor que la máxima dimensión.

Referenciado por Aleph::Compute_Cut_Nodes< GT, SA >::compute_blocks(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::load(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::load_in_text_mode() y Aleph::BitArray::reserve().

Gráfico de llamadas a esta función:

template<typename T>

void Aleph::DynArray< T >::reserve ( const size_t  dim )

inline

Reserva un rango de memoria.

reerve(dim) verifica todas las de entradas del arreglo comprendido entre 0 y dim - 1 y asegura que haya memoria.

Es una sobrecarga del método reserve(l,r).

Parámetros

[in]

dim

índice superior

Excepciones

std::bad_alloc	si no hay suficiente memoria. En ese caso, no hay manera precisa de saber hasta donde ha sido apartada la memoria. Si l es mayor que la antigua dimensión, entonces el valor de la dimensión actual estará modificado hasta el último bloque apartado.
length_error	si dim es mayor que la máxima dimensión.

template<typename T>

void Aleph::DynArray< T >::set_default_initial_value ( const T &  value )

inline

Configura el valor por omisión que debe tener una nueva entrada

Normalmente, cuando se aparta un nuevo bloque, el valor inicial de sus elementos está dado por el valor asignado por el constructor por omisión T::T(). Esta primitiva coloca el valor a colocar en cada elemento de un nuevo bloque al valor value.

Parámetros

[in]

value

el valor por omisión que deben tomar las entradas del bloque.

Referenciado por Aleph::BitArray::BitArray() y Aleph::BitArray::dyn_right_shift().

Gráfico de llamadas a esta función:

template<typename T>

void Aleph::DynArray< T >::swap ( DynArray< T > &  array )

inline

Intercambio rapidísimo entre arreglos.

swap intercambia todos los elementos del arreglo array con los del arreglo this en un muy rápido tiempo constante.

Parámetros

[in]

array

arreglo a intercambiar con this

Nota

Los tamaños de directorio, segmento y bloque también son intercambiados.

template<typename T>

T* Aleph::DynArray< T >::test ( const size_t  i ) const

inline

Verifica si existe una entrada en un aareglo dinámico.

test(i) examina el arreglo dinámico this y, en caso de que la celda exista, es decir, que su memoria haya sido apartada, retorna un puntero al elemento correspondiente a la posición i. De lo contrario, la rutina retorna un puntero nulo.

El uso principal de esta rutina es verificar por la existencia de la entrada y a la vez obtener su dirección encaso de que la misma exista.

Parámetros

[in]

i

índice de la entrada a probar.

Devuelve

un puntero a la entrada i del arreglo o NULL en caso de que ésta no exista.

template<typename T>

T& Aleph::DynArray< T >::touch ( const size_t  i ) throw ( std::exception, std::bad_alloc, std::out_of_range )

inline

Toca que la i-ésima entrada de manera de asegurar que haya memoria.

touch(i) verifica si el bloque albergante de la entrada i ha sido apartado y, en caso de no existir bloque, aparta la correspondiente memoria.

Parámetros

[in]

i

índice de la entrada a tocar.

Excepciones

bad_alloc	si no hay memoria para apartar el bloque
out_of_range	si i es mayor que la máxima dimensión

Ver también

cut

Referenciado por Aleph::BitArray::load(), Aleph::BitArray::load_from_array_of_chars(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_list_graph(), Aleph::Ady_Mat< GT, __Entry_Type, SA >::operate_all_arcs_matrix(), Aleph::Matrix_Graph< GT, SA >::operator()() y Aleph::BitArray::write_bit().

Gráfico de llamadas a esta función:

template<typename T>

template<class Operation >

bool Aleph::DynArray< T >::traverse ( Operation &  operation ) const

inline

Traverse all the set of pairs and for eah pair executes operation.

Operation must have the signature

bool operation(T & item)

If

operation() 

returns false then the traversal is aborted; otherwise the the routine advance and so on

Parámetros

[in]

operation

Devuelve

true if all items are traversed; false otherwise

Documentación de los datos miembro

template<typename T>

const unsigned long long Aleph::DynArray< T >::Max_Dim_Allowed

static

Valor inicial:

= 
      256*1024*1024*1024ull

---

La documentación para esta clase fue generada a partir del siguiente fichero:

• tpl_dynArray.H