Página principal   Lista alfabética   Lista de componentes   Lista de archivos   Miembros de las clases   Páginas relacionadas  

Referencia de la Clase Diccionario

T.D.A. Diccionario. Más...

#include <diccionario.h>

Lista de todos los miembros.

Tipos públicos

typedef const_iterador iterador
 Tipo iterador también de sólo lectura. Más...


Métodos públicos

const_iterador begin () const
const_iterador end () const
 Diccionario ()
 Diccionario (const Diccionario< Tk, Ti > &orig)
 ~Diccionario ()
Diccionario<Tk,Ti>& operator= (const Diccionario< Tk, Ti > &original)
void insertar (const Tk &llave, const Ti &valor)
 Insertar una nueva pareja. Más...

iterador borrar (iterador it)
 Borrar una pareja del diccionario. Más...

iterador buscar (const Tk &llave)
 Buscar una pareja en el diccionario. Más...

int num_elementos () const
 Número de elementos del diccionario. Más...


Métodos privados

bool posicion_indice (int &pos, const Tk &llave) const
 Localizador de una posición en parejas. Más...

void expandir ()
 Aumenta la memoria reservada para parejas. Más...

void contraer ()
 Disminuye la memoria reservada para parejas. Más...


Atributos privados

Par<Tk,Ti>* parejas
int nelementos
int reservados

Descripción detallada

template<class Tk, class Ti> class Diccionario

T.D.A. Diccionario.

Una instancia d del tipo de datos abstracto Diccionario sobre los tipos Tk,Ti es una colección de parejas (l,v) donde

El número de parejas de d se denomina el tamaño del diccionario. Un diccionario de tamaño cero se denomina diccionario vacío.

Un diccionario de tamaño n se puede representar como

{(l1,v1),(l2,v2),...,(ln,vn)}

donde li<lj si i<j

La eficiencia en espacio es O(n), donde n es el número de parejas en el diccionario

Un ejemplo de su uso: 

#include <iostream>
#include <cassert>
#include <string>
#include <conjunto.h>
using namespace std;

void mostrar_conjunto(const Conjunto<int>& c, string encabezado)
{
  cout << encabezado << endl;
  cout << "  El conjunto tiene " << c.num_elementos() << " elementos" << endl;
  for (Conjunto<int>::iterador p=c.begin();p!=c.end();++p)
    cout <<  "  "<< *p;
  cout << endl;
}

int main()
{
  Conjunto<int> c1,c2;

  for (int i=0;i<10;i++)
    c1.insertar(i);
  for (int i= 5;i<15;i++)
    c2.insertar(i);

  mostrar_conjunto(c1,"Primer Conjunto");
  mostrar_conjunto(c2,"Segundo Conjunto");

  Conjunto<int> res;
  for (Conjunto<int>::iterador p=c1.begin();p!=c1.end();++p)
    res.insertar(*p);
  for (Conjunto<int>::iterador p=c2.begin();p!=c2.end();++p)
    res.insertar(*p);
    
  mostrar_conjunto(res,"Unión de conjuntos");

  return 0;
}

Autor:
Antonio Garrido
Fecha:
Marzo-2002

Definición en la línea 45 del archivo diccionario.h.

Documentación de los 'Tipos Definidos' miembros de la clase

template<class Tk, class Ti>
typedef const_iterador Diccionario<Tk, Ti>::iterador
 

Tipo iterador también de sólo lectura.

El tipo iterador se hace equivalente a const_iterador. El tipo Diccionario sólo admite iteración de lectura. Por tanto, se ha optado por permitir que el usuario pueda usar los dos tipos con la misma semántica.

Definición en la línea 142 del archivo diccionario.h.

Referenciado por buscar().

Documentación de las funciones miembro

template<class Tk, class Ti>
iterador Diccionario<Tk, Ti>::borrar ( iterador it )
 

Borrar una pareja del diccionario.

Parámetros:
it   iterador que indica la pareja a borrar. it!=end()
Devuelve:
El iterador a la siguiente pareja (end() si era la última)
Postcondición:
Los iteradores quedan invalidados. El único iterador que es válido tras la llamada es el devuelto por la función.

Definición en la línea 133 del archivo diccionario.cpp.

template<class Tk, class Ti>
iterador Diccionario<Tk, Ti>::buscar ( const Tk & llave )
 

Buscar una pareja en el diccionario.

Parámetros:
llave   Llave de la pareja a localizar en el diccionario
Devuelve:
El iterador a la pareja que contiene la llave. end() si la pareja no se encuentra.

Definición en la línea 147 del archivo diccionario.cpp.

template<class Tk, class Ti>
void Diccionario<Tk, Ti>::contraer ( ) [private]
 

Disminuye la memoria reservada para parejas.

Precondición:
nelementos<=reservados/2
Postcondición:
reservados vale la mitad y la matriz parejas apunta a una zona de memoria con la mitad de capacidad.

Definición en la línea 48 del archivo diccionario.cpp.

Referenciado por borrar().

template<class Tk, class Ti>
void Diccionario<Tk, Ti>::expandir ( ) [private]
 

Aumenta la memoria reservada para parejas.

Postcondición:
Si el número de elementos es cero, hace parejas una matriz de un sólo elemento. Si no, la hace de tamaño 2*nelementos

Definición en la línea 35 del archivo diccionario.cpp.

Referenciado por insertar().

template<class Tk, class Ti>
void Diccionario<Tk, Ti>::insertar ( const Tk & llave,
const Ti & valor )
 

Insertar una nueva pareja.

Parámetros:
llave   Llave de la nueva pareja a insertar
valor   Valor de la pareja asociado a llave
Postcondición:
. Si la llave ya existe, se reemplaza el valor asociado por el de valor. Los iteradores quedan invalidados

Definición en la línea 114 del archivo diccionario.cpp.

template<class Tk, class Ti>
int Diccionario<Tk, Ti>::num_elementos ( ) const [inline]
 

Número de elementos del diccionario.

Devuelve:
El tamaño del diccionario

Definición en la línea 176 del archivo diccionario.h.

template<class Tk, class Ti>
bool Diccionario<Tk, Ti>::posicion_indice ( int & pos,
const Tk & llave ) const [private]
 

Localizador de una posición en parejas.

Parámetros:
llave   valor de la llave a localizar en la matriz parejas
Valores devueltos:
pos   La posición donde se encuentra la llave llave (si está) o la posición donde debería insertarse si no está
Devuelve:
Si la llave llave está en el vector
Nota:
La eficiencia es logarítmica (usa búsqueda binaria)

Definición en la línea 12 del archivo diccionario.cpp.

Referenciado por buscar(), y insertar().

Documentación de los datos miembro

template<class Tk, class Ti>
int Diccionario<Tk, Ti>::nelementos [private]
 

Número de elementos usados en la matriz parejas

Definición en la línea 70 del archivo diccionario.h.

template<class Tk, class Ti>
Par< Tk, Ti > * Diccionario<Tk, Ti>::parejas<Tk,Ti> [private]
 

Vector para almacenar las parejas

Definición en la línea 69 del archivo diccionario.h.

template<class Tk, class Ti>
int Diccionario<Tk, Ti>::reservados [private]
 

Número de posiciones reservadas en parejas

Definición en la línea 71 del archivo diccionario.h.

La documentación para esta clase fué generada a partir de los siguientes archivos:
Programación en C++. Desarrollado por Antonio Garrido, © 2001