#include <Multimap.H>

Clases
class	iterator

Tipos públicos
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

Métodos públicos
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	find (const Key &key) const

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

const_iterator	lower_bound (const Key &key) const

iterator	upper_bound (const Key &key)

const_iterator	upper_bound (const Key &key) const

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

std::pair< const iterator, const 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 Exception_Prototypes(std

Descripción detallada

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

Parámetros

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.

Ver también: BinNodeXt Treap_Rk Rand_Tree set map multiset

Autor: Leandro Rabindranath León

Documentación de las funciones miembro

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

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 )

inline

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

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::end() y KEY.

Referenciado por Aleph::multimap< Key, T, Compare, KTree, TTree >::equal_range().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

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<const iterator,const iterator> Aleph::multimap< Key, T, Compare, KTree, TTree >::equal_range ( const Key & key ) const

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::equal_range().

Gráfico de llamadas para esta función:

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.

Hace referencia a KEY.

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

Parámetros

[in]	first	position del primer elemento a eliminar.
[in]	last	posición al elemento sucesor del último elemento a eliminar.

Devuelve: iterador al el elemento sucesor del último eliminado (debe corresponderse con last).

Tareas pendientes:: Aprovechar salto interclaves dados por los contadores de repitencias.

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::erase().

Gráfico de llamadas para esta función:

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 )

inline

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

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::end().

Referenciado por Aleph::multimap< Key, T, Compare, KTree, TTree >::find() y Aleph::multimap< Key, T, Compare, KTree, TTree >::operator[]().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

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_iterator Aleph::multimap< Key, T, Compare, KTree, TTree >::find ( const Key & key ) const

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::find().

Gráfico de llamadas para esta función:

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.

Hace referencia a Node_Pool< Node >::allocate(), Node_Pool< Node >::deallocate() y KEY.

Referenciado por Aleph::multimap< Key, T, Compare, KTree, TTree >::insert(), Aleph::multimap< Key, T, Compare, KTree, TTree >::multimap() y Aleph::multimap< Key, T, Compare, KTree, TTree >::operator[]().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

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

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::insert().

Gráfico de llamadas para esta función:

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.

Parámetros

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

Devuelve: un iterador apuntando a una copia del par recién insertado.

Excepciones

bad_alloc si no hay suficiente memoria.

Hace referencia a Node_Pool< Node >::allocate(), Node_Pool< Node >::deallocate(), Aleph::multimap< Key, T, Compare, KTree, TTree >::insert() y KEY.

Gráfico de llamadas para esta función:

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_iterator Aleph::multimap< Key, T, Compare, KTree, TTree >::lower_bound ( const Key & key ) const

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::lower_bound().

Gráfico de llamadas para esta función:

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

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.

Ver también: lexicographical_compare

Hace referencia a KEY.

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.

Ver también: lexicographical_compare

Hace referencia a KEY.

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.

Hace referencia a Aleph::copyRec() y Aleph::destroyRec().

Gráfico de llamadas para esta función:

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.

Ver también: lexicographical_compare

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.

Ver también: lexicographical_compare

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().

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::insert().

Gráfico de llamadas para esta función:

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.

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::end() y Aleph::multimap< Key, T, Compare, KTree, TTree >::find().

Gráfico de llamadas para esta función:

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

Referenciado por Aleph::multimap< Key, T, Compare, KTree, TTree >::operator==().

Gráfico de llamadas a esta función:

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 )

inline

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

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::begin(), Aleph::multimap< Key, T, Compare, KTree, TTree >::end() y KEY.

Referenciado por Aleph::multimap< Key, T, Compare, KTree, TTree >::upper_bound().

Gráfico de llamadas para esta función:

Gráfico de llamadas a esta función:

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_iterator Aleph::multimap< Key, T, Compare, KTree, TTree >::upper_bound ( const Key & key ) const

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

Hace referencia a Aleph::multimap< Key, T, Compare, KTree, TTree >::upper_bound().

Gráfico de llamadas para esta función:

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

Multimap.H

Clases

Tipos públicos

Métodos públicos

Descripción detallada

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 >

Documentación de las funciones miembro

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 >