Aleph::multiset

Referencia de la plantilla de la Clase multiset
[Árboles con raíz, Contenedores de la biblioteca estándar C++.]

Implementación Aleph del tipo estándar multiset<T> basada en árboles binarios de búsqueda con rangos. Más...

Lista de todos los miembros.

Tipos públicos

typedef multiset::iterator const_iterator
 Tipo iterador constante.
typedef const
multiset::value_type & 		const_reference
 Tipo genérico de referencia constante a elemento del conjunto.
typedef multiset::iterator const_reverse_iterator
 Tipo iterador invertido constante.
typedef T key_type
 El tipo dato de los elementos del conjunto.
typedef multiset::value_type & reference
 Tipo genérico de referencia a elemento del conjunto.
typedef multiset::iterator reverse_iterator
 Tipo iterador invertido.
typedef size_t size_type
 Tipo numérico para los tamaños (natural).
typedef T value_type
 El tipo dato de los elementos del conjunto.

Métodos públicos

iterator begin () const
 Retorna un iterador posicionado al primer elemento del multi-conjunto.
void clear ()
 Borra todos los elementos del multi-conjunto.
size_type count (const T &value) const
 Retorna la cantidad de instancias de value que hay dentro del multi-conjunto.
bool empty () const
 Retorna true si el contenedor esta vacío.
iterator end () const
 Retorna un iterador posicionado al último elemento del multi-conjunto.
iterator erase (iterator beg, const iterator &end)
 Borra del multi-conjunto el rango comprendido por [beg.
void erase (iterator pos)
 Borra del multi-conjunto el valor actual del iterador pos.
size_type erase (const T &value)
 Borra del multi-conjunto todas las instancias de value.
iterator find (const T &value) const
 Retorna un iterador posicionado sobre la primera instancia del elemento value en el multi-conjunto.
template<typename Itor>
void insert (Itor beg, const Itor &end)
 Inserta en el multi-conjunto los elementos de un contenedor comprendidos en el rango [beg.
iterator insert (iterator pos, const T &value)
 Inserta value en el multi-conjunto a partir del iterador pos.
iterator insert (const T &value)
 Inserta value en el multi-conjunto.
iterator lower_bound (const T &value) const
 Retorna un iterador posicionado sobre la primera instancia de value dentro de multi-conjunto.
template<typename Itor>
 multiset (Itor beg, Itor end)
 Instancia un multi-conjunto con los elementos comprendidos en el rango [beg.
 multiset (const multiset &c)
 Instancia una copia del multi-conjunto c.
 multiset ()
 Constructor vacío de un multi-conjunto.
bool operator!= (const multiset &c) const
 Retorna true si el multi-conjunto this no contiene exactamente los mismos elementos del multi-conjunto c.
bool operator< (const multiset &c) const
 Retorna true si los elementos ordenados del multi-conjunto this son menores que los del multi-conjunto c.
bool operator<= (const multiset &c) const
 Retorna true si los elementos ordenados del multi-conjunto this son menores o iguales que los del multi-conjunto c.
multiset & operator= (const multiset &c)
 Asigna todo el contenido de c a this.
bool operator== (const multiset &c) const
 Retorna true si el multi-conjunto this tiene exactamente los mismos elementos del multi-conjunto c.
bool operator> (const multiset &c) const
 Retorna true si los elementos ordenados del multi-conjunto this son mayores que los del multi-conjunto c.
bool operator>= (const multiset &c) const
 Retorna true si los elementos ordenados del multi-conjunto this son mayores o iguales que los del multi-conjunto c.
size_type size () const
 Retorna la cantidad de elementos que contiene el multi-conjunto.
void swap (multiset &c)
 Intercambia en tiempo constante todos los elementos de this con los de c.
iterator upper_bound (const T &value) const
 Retorna un iterador posicionado sobre la última instancia de value dentro de multi-conjunto.
 ~multiset ()
 Destructor; todos los elementos son eliminados y la memoria es liberada.

Clases

class  iterator
 Iterador sobre un multi-conjunto (multiset). Más...

Descripción detallada

template<class T, class Compare = Aleph::less<T>, template< class, class > class Tree = Treap_Rk_Vtl>
class Aleph::multiset< T, Compare, Tree >

Esta es una implantación parcial de la clase estándar C++ multiset<T> basada en árboles binarios de búsqueda con rangos. Por omisión se emplea la clase Treap_Rk, con la cual, en medidas de rendimiento, ha probado ser más rápida que sus contrapartes gnu y Boost.

multiset<T> implanta un conjunto de claves de tipo T en el cual se permiten repitencias.

Parámetros:
T el tipo de dato que almacenará el conjunto.
Compare el criterio de comparación entre los elementos de tipo T. Por omisión se implanta T::operator<(const T&).
Tree la clase de árbol binario de búsqueda con rangos que instrumentará el conjunto. Por omisión si usa Treap_Rk
Ver también:
Treap_Rk set map multimap

Definición en la línea 83 del archivo Multiset.H.

Documentación del constructor y destructor

multiset ( Itor  beg,
Itor  end 
) [inline]

.end).

Este constructor instancia un multi-conjunto con elementos iniciales copiados del contenedor asociado los iteradores beg y end.

Parámetros:
[in] beg iterador posicionado en el primer elemento del contenedor a copiar.
[in] end iterador posicionado en el último más un elemento del contenedor a copiar.
Excepciones:
domain_error si los iteradores beg y end no están asociados al mismo contenedor.
bad_alloc si no hay suficiente memoria.
Nota:
El elemento posicionado por el iterador end no se incluye.

Definición en la línea 539 del archivo Multiset.H.

Hace referencia a multiset::insert().

Documentación de las funciones miembro

size_type count ( const T &  value  )  const [inline]

Parámetros:
[in] value valor de clave a buscar.
Devuelve:
cantidad de instancias del valor de clave value que contiene el multi-conjunto.

Definición en la línea 661 del archivo Multiset.H.

iterator erase ( iterator  beg,
const iterator &  end 
) [inline]

.end).

erase(beg,end) borra eficientemente todos los elementos del multi-conjunto delimitados por los iteradores beg y end.

Parámetros:
[in] beg iterador posicionado sobre el elemento inicio del rango.
[in] end iterador posicionado sobre el último más un elemento del rango.
Excepciones:
domain_error si los iteradores beg y end no están asociados a this.
Nota:
El elemento posicionado por el iterador end no se incluye.

Definición en la línea 1018 del archivo Multiset.H.

void erase ( iterator  pos  )  [inline]

erase(pos) borra del conjunto el elemento correspondiente al valor actual del iterador pos.

Parámetros:
[in] pos iterador cuyo valor actual será borrado.
Excepciones:
domain_error si el iterador no está asociado al conjunto this.
underflow_error si el iterador está desbordado por la izquierda.
overflow_error si el iterador está desbordado por la derecha.

Definición en la línea 969 del archivo Multiset.H.

Hace referencia a Dlink::del(), Dnode::get_data(), KEY, multiset::iterator::list_itor, y multiset::iterator::tree_itor.

size_type erase ( const T &  value  )  [inline]

erase(value) borra del multi-conjunto todas las instancias el elemento value.

Parámetros:
[in] value valor del elemento a borrar.
Devuelve:
cantidad de instancias de value que fueron borradas.

Definición en la línea 940 del archivo Multiset.H.

iterator find ( const T &  value  )  const [inline]

find(value) busca el elemento value en el multi-conjunto. Si éste es encontrado, entonces se retorna un iterador posicionado sobre el primer elemento del multi-conjunto con el valor en cuestión; de lo contrario, se retorna un iterador al elemento que antecedería a value si éste fuese insertado. Nótese que en este caso el elemento antecesor es el último entre los repetidos.

Parámetros:
[in] value valor a buscar dentro del multi-conjunto.
Devuelve:
iterador posicionado sobre el primer elemento con valor value si éste se encuentra en el multi-conjunto o un iterador al último elemento que antecedería a value si éste se insertase en el multi-conjunto.

Definición en la línea 688 del archivo Multiset.H.

Hace referencia a multiset::end(), multiset::iterator::list_itor, y multiset::iterator::tree_itor.

void insert ( Itor  beg,
const Itor &  end 
) [inline]

.end).

insert(beg,end) toma un rango de elementos de un contenedor (set, map, multiset, multimap, list o vector) asociados a los iteradores beg y end e inserta todos los elementos del rango en el conjunto this.

Parámetros:
[in] beg iterador posicionado sobre el elemento inicio del rango.
[in] end iterador posicionado sobre el último más un elemento final del rango.
Excepciones:
domain_error si los iteradores beg y end no están asociados al mismo contenedor.
bad_alloc si no hay suficiente memoria.
Nota:
El elemento posicionado por el iterador end no se incluye.

Definición en la línea 924 del archivo Multiset.H.

Hace referencia a multiset::insert().

iterator insert ( iterator  pos,
const T &  value 
) [inline]

insert(pos, value) inserta en el multi-conjunto this, a partir del elemento posicionado por el iterador pos.

Según el estándar, pos debe ser considerado una ayuda a la inserción que ahorre eventuales búsquedas. Esto es correcto en el caso de Aleph si el valor del elemento actual de pos es igual a value; en este caso, la inserción toma $O(1)$ y value queda exactamente después del elemento actual de pos .

Si el valor del elemento actual de pos no es igual a value, entonces es inevitable una búsqueda -que toma $O(\lg n)$- de value en el multi-conjunto. Si value ya se encuentra, entonces value se inserta al final de los elementos repetidos. mismo que value, entonces la inserción se realiza en

Parámetros:
[in] pos iterador a partir del cual se desea realizar la inserción.
[in] value valor a insertar en el multi-conjunto.
Devuelve:
un iterador posicionado sobre el elemento recién insertado.
Excepciones:
bad_alloc si no hay suficiente memoria.

Definición en la línea 864 del archivo Multiset.H.

Hace referencia a multiset::insert(), KEY, multiset::iterator::list_itor, y multiset::iterator::tree_itor.

iterator insert ( const T &  value  )  [inline]

insert(value) inserta en el multi-conjunto this una copia del elemento value y iterador posicionado en el elemento recién insertado.

A menos que no halla suficiente memoria, esta operación no falla.

Parámetros:
[in] value valor a insertar en el multi-conjunto.
Devuelve:
un iterador posicionado sobre el elemento recién insertado
Excepciones:
bad_alloc si no hay suficiente memoria.

Definición en la línea 799 del archivo Multiset.H.

Referenciado por multiset::insert(), y multiset::multiset().

iterator lower_bound ( const T &  value  )  const [inline]

lower_bound(value) busca el elemento value en el multi-conjunto. Si éste es encontrado, entonces se retorna un iterador posicionado sobre el primer elemento del multi-conjunto con el valor en cuestión; de lo contrario, se retorna un iterador desbordado al final del conjunto.

Parámetros:
[in] value valor a buscar dentro del multi-conjunto.
Devuelve:
iterador posicionado sobre el primer elemento con valor value si éste se encuentra en el multi-conjunto o un iterador desbordado si value no se encuentra en el multi-conjunto.

Definición en la línea 718 del archivo Multiset.H.

Hace referencia a multiset::end(), y multiset::size().

iterator upper_bound ( const T &  value  )  const [inline]

upper_bound(value) busca el elemento value en el multi-conjunto. Si éste es encontrado, entonces se retorna un iterador posicionado sobre el último elemento del multi-conjunto con el valor en cuestión; de lo contrario, se retorna un iterador desbordado al final del conjunto.

Parámetros:
[in] value valor a buscar dentro del multi-conjunto.
Devuelve:
iterador posicionado sobre el último elemento con valor value si éste se encuentra en el multi-conjunto o un iterador desbordado si value no se encuentra en el multi-conjunto.

Definición en la línea 746 del archivo Multiset.H.

Hace referencia a multiset::end(), multiset::iterator::list_itor, y multiset::size().

La documentación para esta clase fue generada a partir del siguiente fichero:
Leandro R. León