#include <Multiset.H>

Classes
class	iterator

Public Types
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.

Public Member Functions
	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.

Detailed Description

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.

Parameters

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

See also: Treap_Rk Rand_Tree set map multimap

Constructor & Destructor Documentation

◆ multiset()

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.

Parameters

[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.

Exceptions

domain_error	si los iteradores beg y end no estÃ¡n asociados al mismo contenedor.
bad_alloc	si no hay suficiente memoria.

Note: El elemento posicionado por el iterador end no se incluye.

Here is the call graph for this function:

◆ ~multiset()

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.

Here is the call graph for this function:

Member Function Documentation

◆ begin()

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.

◆ count()

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.

Parameters

[in] value valor de clave a buscar.

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

◆ end()

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.

Here is the caller graph for this function:

◆ erase() [1/3]

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.

Parameters

[in] value valor del elemento a borrar.

Returns: cantidad de instancias de value que fueron borradas.

Here is the call graph for this function:

◆ erase() [2/3]

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.

Parameters

[in] pos iterador cuyo valor actual serÃ¡ borrado.

Exceptions

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.

Here is the call graph for this function:

◆ erase() [3/3]

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.

Parameters

[in]	beg	iterador posicionado sobre el elemento inicio del rango.
[in]	end	iterador posicionado sobre el Ãºltimo mÃ¡s un elemento del rango.

Exceptions

domain_error si los iteradores beg y end no estÃ¡n asociados a this.

Note: El elemento posicionado por el iterador end no se incluye.

◆ find()

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.

Parameters

[in] value valor a buscar dentro del multi-conjunto.

Returns: 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.

Here is the call graph for this function:

◆ insert() [1/3]

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.

Parameters

[in] value valor a insertar en el multi-conjunto.

Returns: un iterador posicionado sobre el elemento reciÃ©n insertado

Exceptions

bad_alloc si no hay suficiente memoria.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [2/3]

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

Parameters

[in]	pos	iterador a partir del cual se desea realizar la inserciÃ³n.
[in]	value	valor a insertar en el multi-conjunto.

Returns: un iterador posicionado sobre el elemento reciÃ©n insertado.

Exceptions

bad_alloc	si no hay suficiente memoria.
overflow_error	si el iter

Here is the call graph for this function:

◆ insert() [3/3]

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.

Parameters

[in]	beg	iterador posicionado sobre el elemento inicio del rango.
[in]	end	iterador posicionado sobre el Ãºltimo mÃ¡s un elemento final del rango.

Exceptions

domain_error	si los iteradores beg y end no estÃ¡n asociados al mismo contenedor.
bad_alloc	si no hay suficiente memoria.

Note: El elemento posicionado por el iterador end no se incluye.

Here is the call graph for this function:

◆ lower_bound()

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.

Parameters

[in] value valor a buscar dentro del multi-conjunto.

Returns: 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.

Here is the call graph for this function:

◆ operator!=()

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.

◆ operator<()

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.

◆ operator<=()

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.

◆ operator==()

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.

Here is the call graph for this function:

◆ operator>()

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.

◆ operator>=()

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.

◆ swap()

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.

◆ upper_bound()

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.

Parameters

[in] value valor a buscar dentro del multi-conjunto.

Returns: 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.

Here is the call graph for this function:

The documentation for this class was generated from the following file:

Multiset.H

Classes

Public Types

Public Member Functions

Detailed Description

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

Constructor & Destructor Documentation

◆ multiset()

◆ ~multiset()

Member Function Documentation

◆ begin()

◆ count()

◆ end()

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ lower_bound()

◆ operator!=()

◆ operator<()

◆ operator<=()

◆ operator==()

◆ operator>()

◆ operator>=()

◆ swap()

◆ upper_bound()

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