#include <Multiset.H>

Clases
class	iterator

Tipos públicos
typedef T	value_type
	El tipo dato de los elementos del conjunto.

typedef multiset::value_type &	reference
	Tipo genérico de referencia a elemento del conjunto.

typedef const multiset::value_type &	const_reference
	Tipo genérico de referencia constante a elemento del conjunto.

typedef size_t	size_type
	Tipo numérico para los tamaños (natural).

typedef T	key_type
	El tipo dato de los elementos del conjunto.

typedef multiset::iterator	const_iterator
	Tipo iterador constante.

typedef multiset::iterator	reverse_iterator
	Tipo iterador invertido.

typedef multiset::iterator	const_reverse_iterator
	Tipo iterador invertido constante.

Métodos públicos
	multiset ()
	Constructor vacío de un multi-conjunto.

	multiset (const multiset &c)
	Instancia una copia del multi-conjunto c.

template<typename Itor >
	multiset (Itor beg, const Itor &end)

	~multiset ()

multiset &	operator= (const multiset &c)
	Asigna todo el contenido de c a this.

size_type	size () const
	Retorna la cantidad de elementos que contiene el multi-conjunto.

bool	empty () const
	Retorna true si el contenedor esta vacío.

bool	operator== (const multiset &c) const

bool	operator!= (const multiset &c) const

bool	operator< (const multiset &c) const

bool	operator> (const multiset &c) const

bool	operator<= (const multiset &c) const

bool	operator>= (const multiset &c) const

size_type	count (const T &value) const

iterator	find (const T &value) const

iterator	lower_bound (const T &value) const

iterator	upper_bound (const T &value) const

void	swap (multiset &c)

iterator	begin () const

iterator	end () const

iterator	insert (const T &value)

iterator	insert (iterator pos, const T &value)

template<typename Itor >
void	insert (Itor beg, const Itor &end)

size_type	erase (const T &value)

void	erase (iterator pos)

iterator	erase (iterator beg, const iterator &end)

void	clear ()
	Borra todos los elementos del multi-conjunto.

Descripción detallada

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

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

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 Rand_Tree set map multimap

Documentación del constructor y destructor

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

template<typename Itor >

Aleph::multiset< T, Compare, Tree >::multiset	(	Itor	beg,
		const Itor &	end
	)

inline

Instancia un multi-conjunto con los elementos comprendidos en el rango [beg..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.

Hace referencia a Aleph::multiset< T, Compare, Tree >::insert().

Gráfico de llamadas para esta función:

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

Aleph::multiset< T, Compare, Tree >::~multiset ( )

inline

Destructor; todos los elementos son eliminados y la memoria es liberada.

Hace referencia a Aleph::destroyRec().

Gráfico de llamadas para esta función:

Documentación de las funciones miembro

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

iterator Aleph::multiset< T, Compare, Tree >::begin ( ) const

inline

Retorna un iterador posicionado al primer elemento del multi-conjunto.

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

size_type Aleph::multiset< T, Compare, Tree >::count ( const T & value ) const

inline

Retorna la cantidad de instancias de value que hay dentro del multi-conjunto.

Parámetros

[in] value valor de clave a buscar.

Devuelve: cantidad de instancias del valor de clave value que contiene el multi-conjunto.

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

iterator Aleph::multiset< T, Compare, Tree >::end ( ) const

inline

Retorna un iterador posicionado al último elemento del multi-conjunto.

Referenciado por Aleph::multiset< T, Compare, Tree >::find(), Aleph::multiset< T, Compare, Tree >::lower_bound() y Aleph::multiset< T, Compare, Tree >::upper_bound().

Gráfico de llamadas a esta función:

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

size_type Aleph::multiset< T, Compare, Tree >::erase ( const T & value )

inline

Borra del multi-conjunto todas las instancias de value.

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.

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

void Aleph::multiset< T, Compare, Tree >::erase ( iterator pos )

inline

Borra del multi-conjunto el valor actual del iterador pos.

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.

Hace referencia a KEY.

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

iterator Aleph::multiset< T, Compare, Tree >::erase	(	iterator	beg,
		const iterator &	end
	)

inline

Borra del multi-conjunto el rango comprendido por [beg..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.

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

iterator Aleph::multiset< T, Compare, Tree >::find ( const T & value ) const

inline

Retorna un iterador posicionado sobre la primera instancia del elemento value en el multi-conjunto.

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.

Hace referencia a Aleph::multiset< T, Compare, Tree >::end().

Gráfico de llamadas para esta función:

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

iterator Aleph::multiset< T, Compare, Tree >::insert ( const T & value )

inline

Inserta value en el multi-conjunto.

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

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.

Referenciado por Aleph::multiset< T, Compare, Tree >::insert() y Aleph::multiset< T, Compare, Tree >::multiset().

Gráfico de llamadas a esta función:

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

iterator Aleph::multiset< T, Compare, Tree >::insert	(	iterator	pos,
		const T &	value
	)

inline

Inserta value en el multi-conjunto a partir del iterador pos.

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.
overflow_error	si el iter

Hace referencia a Aleph::multiset< T, Compare, Tree >::insert() y KEY.

Gráfico de llamadas para esta función:

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

template<typename Itor >

void Aleph::multiset< T, Compare, Tree >::insert	(	Itor	beg,
		const Itor &	end
	)

inline

Inserta en el multi-conjunto los elementos de un contenedor comprendidos en el rango [beg..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.

Hace referencia a Aleph::multiset< T, Compare, Tree >::insert().

Gráfico de llamadas para esta función:

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

iterator Aleph::multiset< T, Compare, Tree >::lower_bound ( const T & value ) const

inline

Retorna un iterador posicionado sobre la primera instancia de value dentro de multi-conjunto.

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.

Hace referencia a Aleph::multiset< T, Compare, Tree >::end() y Aleph::multiset< T, Compare, Tree >::size().

Gráfico de llamadas para esta función:

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

bool Aleph::multiset< T, Compare, Tree >::operator!= ( const multiset< T, Compare, Tree > & c ) const

inline

Retorna true si el multi-conjunto this no contiene exactamente los mismos elementos del multi-conjunto c.

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

bool Aleph::multiset< T, Compare, Tree >::operator< ( const multiset< T, Compare, Tree > & c ) const

inline

Retorna true si los elementos ordenados del multi-conjunto this son menores que los del multi-conjunto c.

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

bool Aleph::multiset< T, Compare, Tree >::operator<= ( const multiset< T, Compare, Tree > & c ) const

inline

Retorna true si los elementos ordenados del multi-conjunto this son menores o iguales que los del multi-conjunto c.

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

bool Aleph::multiset< T, Compare, Tree >::operator== ( const multiset< T, Compare, Tree > & c ) const

inline

Retorna true si el multi-conjunto this tiene exactamente los mismos elementos del multi-conjunto c.

Hace referencia a KEY y Aleph::multiset< T, Compare, Tree >::size().

Gráfico de llamadas para esta función:

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

bool Aleph::multiset< T, Compare, Tree >::operator> ( const multiset< T, Compare, Tree > & c ) const

inline

Retorna true si los elementos ordenados del multi-conjunto this son mayores que los del multi-conjunto c.

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

bool Aleph::multiset< T, Compare, Tree >::operator>= ( const multiset< T, Compare, Tree > & c ) const

inline

Retorna true si los elementos ordenados del multi-conjunto this son mayores o iguales que los del multi-conjunto c.

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

void Aleph::multiset< T, Compare, Tree >::swap ( multiset< T, Compare, Tree > & c )

inline

Intercambia en tiempo constante todos los elementos de this con los de c.

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

iterator Aleph::multiset< T, Compare, Tree >::upper_bound ( const T & value ) const

inline

Retorna un iterador posicionado sobre la última instancia de value dentro de multi-conjunto.

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.

Hace referencia a Aleph::multiset< T, Compare, Tree >::end() y Aleph::multiset< T, Compare, Tree >::size().

Gráfico de llamadas para esta función:

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

Multiset.H

Clases

Tipos públicos

Métodos públicos

Descripción detallada

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

Documentación del constructor y destructor

Documentación de las funciones miembro

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