#include <Multimap.H>

Classes
class	iterator

Public Types
typedef std::pair< Key, T >	Pair

typedef Pair	value_type
	Tipo de valor de clave manejado (que es un par)

typedef multimap::value_type &	reference
	Referencia al par.

typedef const multimap::value_type &	const_reference

typedef size_t	size_type

typedef Key	key_type

typedef T	mapped_type

typedef const iterator	const_iterator
	iterador constante

Public Member Functions
void	clear ()
	VacÃa el multimapeo. Todos los elementos son borrados.

const size_t &	size () const

size_type	max_size () const

bool	empty () const

iterator	insert (const value_type &value)

template<class InputIterator >
void	insert (InputIterator first, const InputIterator &last)

template<class InputIterator >
	multimap (InputIterator first, const InputIterator &last)
	Construye un multimapeo con los pares del rango [first,last).

	multimap (const multimap &m)
	Constructor copia.

multimap &	operator= (const multimap &m)

iterator	insert (const_iterator &hint, const value_type &value)

iterator	erase (const_iterator &position)
	Elimina del multimapeo el elemento situado en position.

size_type	erase (const key_type &key)

iterator	erase (iterator first, const_iterator &last)

iterator	begin () const
	retorna un iterador al primer elemento del multimapeo.

iterator	end () const
	retorna un iterador al Ãºltimo elemento del multimapeo.

size_type	count (const Key &key) const
	retorna la cantidad pares con clave igual a key

iterator	find (const Key &key) const

iterator	lower_bound (const Key &key) const
	Retorna un iterador posicionado en el lugar donde serÃa insertado key.

iterator	upper_bound (const Key &key) const

std::pair< iterator, iterator >	equal_range (const Key &key) const

void	swap (multimap &other)
	Intercambia los valores de this con los de other.

bool	operator< (const multimap &rhs) const

bool	operator<= (const multimap &rhs) const

bool	operator== (const multimap &rhs) const
	Retorna true si this es exactamente igual a rhs.

bool	operator!= (const multimap &rhs) const
	Retorna true si this es distinto de rhs.

bool	operator> (const multimap &rhs) const

bool	operator>= (const multimap &rhs) const

const T &	operator[] (const Key &key)

const T &	operator[] (const Key &key) const

Detailed Description

template<typename Key, typename T, class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>
class Aleph::multimap< Key, T, Compare, KTree, TTree >

ImplementaciÃ³n Aleph del tipo estÃ¡ndar multimap<Key,T> basada en Ã¡rboles binarios de bÃºsqueda con rangos.

Esta es una implantaciÃ³n parcial, aunque bastante avanzada y de posible mejor rendimiento, de la clase estÃ¡ndar C++ multimap<Key,T>.

La implementaciÃ³n estÃ¡ basada en Ã¡rboles binarios de bÃºsqueda con rango. Por omisiÃ³n, se emplean treaps con tango, pero podrÃan emplearse otros tipos de Ã¡rboles binarios de bÃºsqueda siempre y cuando respeten la interfaz.

Una diferencia de esta implementaciÃ³n con el estÃ¡ndar es que el tipo de Ã¡rbol es un parÃ¡metro. En Aleph los Ã¡rboles binarios de bÃºsqueda con rango (BinNodeXt), treaps (Treap_Rk) y los Ã¡rboles aleatorizados (Rand_tree) pueden emplearse para implementar esta clase.

Otra diferencia con el estÃ¡ndar, quizÃ¡ la mÃ¡s importante, es que los pares del mapeo que repitan la clave primaria estÃ¡n ordenados entre sÃ. Esto exige la presencia del operador < para el tipo T. Del mismo modo, viola la normativa del estÃ¡ndar de que los pares de clave primaria repetida estÃ©n ordenados segÃºn su orden de inserciÃ³n.

La implementaciÃ³n emplea un Ã¡rbol binario de bÃºsqueda con rangos para indizar las claves primarias de tipo Key. Cada nodo de este Ã¡rbol contiene otro Ã¡rbol binario de bÃºsqueda con rangos que contiene las claves asociadas. Cada nodo, en ambos tipos de Ã¡rboles, maneja un contador de repeticiones. AsÃ, por ejemplo, para los pares (1,0),(1,0),(1,0),(1,0),(1,5),(1,5),(1,5) se usa un solo nodo KTree con clave 1 y dos nodos TTree con claves 0 y 1 respectivamente. Este estilo de implantaciÃ³n ahorra mucho espacio si en efecto, tendrÃa sentido esperar, el multimapeo contiene muchas duplicidades.

Este estilo de implantaciÃ³n tiende a ser mÃ¡s veloz que otros esquemas tradicionales. Especialmente, el avance de los iteradores.

NÃ³tese tambiÃ©n que en el caso de no contener muchas duplicidades esta implementaciÃ³n consume prÃ¡cticamente el mismo espacio que una basada en Ã¡rboles mÃ¡s listas enlazadas de repitencias (que es el usado por la mayorÃa de las instrumentaciones del estÃ¡ndar).

Parameters

Key	el tipo de clave primaria
T	el tipo de dato que asociarÃ¡ a una clave primaria.
Compare	el criterio de comparaciÃ³n entre los elementos de tipo T. Por omisiÃ³n se implanta Key::operator<(const T&).
KTree	la clase de Ã¡rbol binario de bÃºsqueda con rangos conque se indizan las claves primarias de tipo Key.
TTree	la clase de Ã¡rbol binario de bÃºsqueda con rangos conque se indizan las claves asociadas.

See also: BinNodeXt Treap_Rk Rand_Tree set map multiset

Author: Leandro Rabindranath LeÃ³n

Member Function Documentation

◆ empty()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

bool Aleph::multimap< Key, T, Compare, KTree, TTree >::empty ( ) const

inline

Retorna true si el multimapeo estÃ¡ vacÃo (no contiene ningÃºn elemento).

◆ equal_range()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

std::pair<iterator,iterator> Aleph::multimap< Key, T, Compare, KTree, TTree >::equal_range ( const Key & key ) const

inline

Retorna un par de iteradores que definen el rango completo de claves con valor key que estÃ¡n contenidas en el multimapeo.

Here is the call graph for this function:

◆ erase() [1/2]

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

size_type Aleph::multimap< Key, T, Compare, KTree, TTree >::erase ( const key_type & key )

inline

Elimina todos los pares con clave key. Retorna la cantidad de pares eliminados.

Here is the call graph for this function:

◆ erase() [2/2]

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

iterator Aleph::multimap< Key, T, Compare, KTree, TTree >::erase	(	iterator	first,
		const_iterator &	last
	)

inline

Elimina todos los pares comprendidos en el rango [first,last).

Parameters

[in]	first	position del primer elemento a eliminar.
[in]	last	posiciÃ³n al elemento sucesor del Ãºltimo elemento a eliminar.

Returns: iterador al el elemento sucesor del Ãºltimo eliminado (debe corresponderse con last).

Todo:: Aprovechar salto interclaves dados por los contadores de repitencias.

Here is the call graph for this function:

◆ find()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

iterator Aleph::multimap< Key, T, Compare, KTree, TTree >::find ( const Key & key ) const

inline

Retorna un iterador posicionado sobre el primer par con clave key; end() de lo contrario.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [1/3]

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

iterator Aleph::multimap< Key, T, Compare, KTree, TTree >::insert ( const value_type & value )

inline

Inserta en el multimapeo los elementos contenidos en el rango [first,last).

Esta inserciÃ³n toma $\lg n$ ; donde n es la cantidad de claves distintas de tipo Key que contiene el multimapeo.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert() [2/3]

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

template<class InputIterator >

void Aleph::multimap< Key, T, Compare, KTree, TTree >::insert	(	InputIterator	first,
		const InputIterator &	last
	)

inline

Inserta en el multimapeo los elementos contenidos en el rango [first,last).

Here is the call graph for this function:

◆ insert() [3/3]

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

iterator Aleph::multimap< Key, T, Compare, KTree, TTree >::insert	(	const_iterator &	hint,
		const value_type &	value
	)

inline

InserciÃ³n "ayudada" de posiciÃ³n.

Esta versiÃ³n de insert() aprovecha la posiciÃ³n del iterador hint para efectuar una inserciÃ³n mÃ¡s rÃ¡pida que la tradicional.

Si hint->first == value.first segÃºn el criterio de comparaciÃ³n, entonces esta inserciÃ³n consume $\lg m$ ; donde m es la cantidad de repeticiones distintas de la clave secundaria asociada a hint->first o value.first. De lo contrario se efectÃºa la inserciÃ³n tradicional.

Parameters

[in]	hint	iterador de "ayuda"
[in]	value	par a insertar

Returns: un iterador apuntando a una copia del par reciÃ©n insertado.

Exceptions

bad_alloc si no hay suficiente memoria.

Here is the call graph for this function:

◆ max_size()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

size_type Aleph::multimap< Key, T, Compare, KTree, TTree >::max_size ( ) const

inline

Retorna un estimado sobre la mÃ¡xima cantidad de elementos que puede albergar el multimapeo

◆ operator<()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

bool Aleph::multimap< Key, T, Compare, KTree, TTree >::operator< ( const multimap< Key, T, Compare, KTree, TTree > & rhs ) const

inline

Retorna true si this es menor que rhs segÃºn la comparaciÃ³n lexicogrÃ¡fica.

See also: lexicographical_compare

Here is the call graph for this function:

◆ operator<=()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

bool Aleph::multimap< Key, T, Compare, KTree, TTree >::operator<= ( const multimap< Key, T, Compare, KTree, TTree > & rhs ) const

inline

Retorna true si this es menor o igual que rhs segÃºn la comparaciÃ³n lexicogrÃ¡fica.

See also: lexicographical_compare

Here is the call graph for this function:

◆ operator=()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

multimap& Aleph::multimap< Key, T, Compare, KTree, TTree >::operator= ( const multimap< Key, T, Compare, KTree, TTree > & m )

inline

AsignaciÃ³n. Todos los elementos del lado izquierdo son liberados.

Here is the call graph for this function:

◆ operator>()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

bool Aleph::multimap< Key, T, Compare, KTree, TTree >::operator> ( const multimap< Key, T, Compare, KTree, TTree > & rhs ) const

inline

Retorna true si this es menor que rhs segÃºn la comparaciÃ³n lexicogrÃ¡fica.

See also: lexicographical_compare

◆ operator>=()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

bool Aleph::multimap< Key, T, Compare, KTree, TTree >::operator>= ( const multimap< Key, T, Compare, KTree, TTree > & rhs ) const

inline

Retorna true si this es mayor o igual que rhs segÃºn la comparaciÃ³n lexicogrÃ¡fica.

See also: lexicographical_compare

◆ operator[]() [1/2]

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

const T& Aleph::multimap< Key, T, Compare, KTree, TTree >::operator[] ( const Key & key )

inline

Acceso como arreglo.

El operador [] puede emplearse para escribir y leer datos en el multimapeo.

Si m es un mapeo, entonces m[key] = item; insertarÃ¡ el par (key,item).

La expresiÃ³n cout << m[key] "lee" el item asociado a la clave key. Si la clave ya existe, entonces se retorna el primer item asociado. De lo contrario, se inserta un nuevo par cuyo valor de item estÃ¡ inicializado por el constructor T::T().

Here is the call graph for this function:

◆ operator[]() [2/2]

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

const T& Aleph::multimap< Key, T, Compare, KTree, TTree >::operator[] ( const Key & key ) const

inline

Acceso como arreglo constante. Si la clave no estÃ¡ insertada entonces se dispara excepciÃ³n.

Here is the call graph for this function:

◆ size()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

const size_t& Aleph::multimap< Key, T, Compare, KTree, TTree >::size ( ) const

inline

Retorna la cantidad de elementos que contiene el multimapeo (cantidad total de pares).

Here is the caller graph for this function:

◆ upper_bound()

template<typename Key , typename T , class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>

iterator Aleph::multimap< Key, T, Compare, KTree, TTree >::upper_bound ( const Key & key ) const

inline

Retorna un iterador posicionado en el lugar sucesor de key si key fuese insertado.

Here is the call graph for this function:

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

Multimap.H

Classes

Public Types

Public Member Functions

Detailed Description

template<typename Key, typename T, class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk> class Aleph::multimap< Key, T, Compare, KTree, TTree >

Member Function Documentation

◆ empty()

◆ equal_range()

◆ erase() [1/2]

◆ erase() [2/2]

◆ find()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ max_size()

◆ operator<()

◆ operator<=()

◆ operator=()

◆ operator>()

◆ operator>=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ size()

◆ upper_bound()

template<typename Key, typename T, class Compare = Aleph::less<Key>, template< class, class > class KTree = Treap_Rk, template< class, class > class TTree = Treap_Rk>
class Aleph::multimap< Key, T, Compare, KTree, TTree >