Tema 7
Colas de prioridad
7.1. Plantillas de clases y funciones en C++
7.2. El TAD Cola de Prioridad
7.3. El montículo binario (heap)
IS13. Estructuras de datos y de la información — 2003/2004
1
Plantillas de clases y funciones en C++
Hasta ahora hemos dotado de cierto grado de genericidad a una clase mediante una
definición de tipo:
typedef int TBL;
que obliga a modificar la definición de la clase y recompilarla para adaptar la clase al
tipo específico que necesitamos.
C++ proporciona un mecanismo explícito para definir clases y funciones genéricas.
Una plantilla de clase o de función es un modelo para crear clases o funciones en
el que se parametrizan uno o más tipos o valores.
template <class TBABB>
class ArbolBB;
template <class T>
int SeparaIntervalo
(T* vec, int n, T inf, T sup);
template <class TBL>
class Lista {
public:
...
private:
...
};
IS13. Estructuras de datos y de la información — 2003/2004
2
Plantillas de clases y funciones en C++
Declaración y definición de plantillas de clase
Una declaración o definición de plantilla empieza con template.
A continuación se da una lista de parámetros de plantilla, separados por comas
y delimitados por < y >. No puede estar vacía.
Un parámetro de plantilla puede ser de tipo o de expresión constante.
Parámetro de tipo. Se compone de class o typename y un identificador.
class y typename son equivalentes en esta lista de parámetros.
Cualquier tipo predefinido de C++ (int, float, char*, etc.) o definido por
el usuario podrá ser un argumento válido como parámetro de tipo.
Un parámetro de tipo es un especificador de tipo en toda la definición de la
plantilla. Puede usarse en los mismos contextos que un tipo en una clase.
Parámetro de expresión constante. Es una declaración normal de un parámetro.
El nombre del parámetro representa un valor constante.
IS13. Estructuras de datos y de la información — 2003/2004
3
Plantillas de clases y funciones en C++
Transformación de la clase Vector (de enteros) en una plantilla de clase.
class Vector {
public:
typedef int TBV;
explicit Vector(int cap_inicial=0)
{ capacidad=cap_inicial; elementos=new TBV[cap_inicial]; }
...
};
template <class TBV>
class Vector {
public:
explicit Vector(int cap_inicial=0)
{ capacidad=cap_inicial; elementos=new TBV[cap_inicial]; }
...
};
// El resto de la definición de la plantilla es igual que la de la clase Vector
IS13. Estructuras de datos y de la información — 2003/2004
4
Plantillas de clases y funciones en C++
Tras la lista de parámetros de plantilla, se da la declaración o definición de la plantilla
de clase, exactamente igual que una declaración o definición normal de clase.
Dentro de la definición de la plantilla de clase, su nombre puede utilizarse como
especificador de tipo, igual que se hacia hasta ahora con el nombre de una clase.
Cada ocurrencia de
Vector
dentro de su definición es un abreviatura de
Vector<TBV>.
Esta abreviatura sólo puede utilizarse aquí y dentro de la definición de sus miembros.
Cuando se utiliza fuera de su definición, se debe especificar la lista de parámetros
completa: Vector<TBV>.
IS13. Estructuras de datos y de la información — 2003/2004
5
Plantillas de clases y funciones en C++
Instanciación de plantillas de clase
Una definición de plantilla de clase sirve como modelo para la generación automática
de instancias de tipo específico de la clase.
Cuando después se escribe:
Vector<double> vd;
se crea automáticamente una clase Vector cuyos componentes son de tipo double.
El resultado es equivalente a reescribir el texto de la definición de la plantilla de
clase sustituyendo TBV por double y quitando template <class TBV>.
La creación de una clase concreta a partir de una plantilla genérica de clase se llama
instanciación de la plantilla.
Vector<int> vi;
Vector<char*> vpc; ⇐ vector de punteros a caracteres
Vector<bool> *pvb; ⇐ puntero a vector de booleanos
⇐ vector de enteros
IS13. Estructuras de datos y de la información — 2003/2004
6
Plantillas de clases y funciones en C++
Cada instanciación de una plantilla de clase es una clase independiente
Los objetos de la clase Vector<int> no tienen permiso de acceso a los miembros
no públicos de Vector<char*>.
La lista de argumentos de plantilla se separa por comas y se delimita por < y >,
asociándose los tipos y valores específicos dados en la instanciación a los parámetros
de plantilla por su posición.
Vector<int> es un nombre de clase, e <int> es su lista de argumentos.
Una instancia de una plantilla de clase puede utilizarse en un programa donde pueda
utilizarse cualquier clase, y sus objetos se declaran y usan como los de cualquier clase.
void Ordena(Vector<long> & vl) { ... }
Vector<float> *pvf = new Vector<float>[100];
IS13. Estructuras de datos y de la información — 2003/2004
7
Plantillas de clases y funciones en C++
Métodos de las plantillas de clase
Se pueden definir dentro de la definición de la plantilla de clase (inline), o fuera.
Si un método se define fuera, debe hacerse con una sintaxis especial:
template <class TBV>
inline
Vector<TBV>::Vector(int cap_inicial) {
capacidad = cap_inicial;
elementos = new TBV[cap_inicial];
}
Se debe escribir template con la misma lista de parámetros que la plantilla de
clase, para que el método sea una plantilla de función con los mismos parámetros.
Se debe cualificar el nombre del método (constructor, en este caso) con el nombre de
la plantilla de clase acompañada de la lista de parámetros de plantilla.
En el cuerpo del método, los parámetros de plantilla se pueden usar sin cualificar.
IS13. Estructuras de datos y de la información — 2003/2004
8
Plantillas de clases y funciones en C++
template <class TBV>
void Vector<TBV>::Inicia(int pri, int fin, TBV val) {
...
}
template <class TBV>
Vector<TBV> & Vector<TBV>::operator=(const Vector & der) {
...
}
template <class TBV>
void Vector<TBV>::ModificaCapacidad(int nueva_cap) {
...
}
template <class TBV>
void Vector<TBV>::Mostrar(ostream & fsal) const {
...
}
// El código de cada uno de estos métodos de la plantilla es el mismo
// que había en su correspondiente método de la clase Vector
IS13. Estructuras de datos y de la información — 2003/2004
9
Plantillas de clases y funciones en C++
Plantillas de función
Se declaran y definen igual que las plantillas de clase:
template más la lista de parámetros.
Después se declara o define la plantilla como una función normal, incluyendo el uso
de los parámetros de plantilla.
La instanciación de plantillas de función es distinta de las de clase.
En principio, no es necesario dar la lista de argumentos de plantilla, porque puede
deducirse de los tipos de los argumentos de función.
Cuando sea necesario puede darse una lista explícita de argumentos de plantilla.
IS13. Estructuras de datos y de la información — 2003/2004
10
Plantillas de clases y funciones en C++
template <class T>
int SeparaIntervalo(T* vec, int n, const T & inf, const T & sup) {
int ult = -1;
for (int i=0 ; i < n ; i++)
T tmp;
if (inf <= vec[i] && vec[i] <= sup)
{ ult++;
return(ult);
tmp = vec[ult];
vec[ult] = vec[i];
vec[i] = tmp; }
}
...
char vc[500];
double * vd = new double[3000];
...
int u1 = SeparaIntervalo(vc,500,’g’,’m’);
int u2 = SeparaIntervalo(vd,3000,34.0945,7772.8097021);
int u3 = SeparaIntervalo<double>(vd,3000,34.0945,7772.8097021);
IS13. Estructuras de datos y de la información — 2003/2004
11
Plantillas de clases y funciones en C++
Las plantillas se pueden sobrecargar, conjuntamente con las funciones normales.
El compilador elegirá la más apropiada para una llamada entre las funciones y las
instancias factibles de las plantillas, según los argumentos y sus tipos.
template <class T>
int SeparaIntervalo(Vector<T> & vec, const T & inf, const T & sup) {
int ult = -1;
for (int i=0 ; i < vec.Capacidad() ; i++)
T tmp;
if (inf <= vec[i] && vec[i] <= sup)
{ ult++;
return(ult);
tmp = vec[ult];
vec[ult] = vec[i];
vec[i] = tmp; }
}
...
long * vl1 = new long[1000];
Vector<long> vl2(2500);
...
int u4 = SeparaIntervalo(vl1,1000,999999,4999999);
int u5 = SeparaIntervalo(vl2,999999,4999999);
IS13. Estructuras de datos y de la información — 2003/2004
12
Plantillas de clases y funciones en C++
Amistad en las plantillas de clase
Conoceremos sólo la declaración de amistad de una plantilla de función en una de
clase en la que ambas utilizan la misma lista de parámetros de plantilla.
template <class TBV> class Vector {
friend ostream & operator<< <TBV>(ostream &, const Vector<TBV> &);
...
};
template <class Tipo>
ostream & operator<<(ostream & fsal, const Vector<Tipo> & v) {
fsal << "[";
if (v.capacidad > 0) {
for (int i=0 ; i < v.capacidad-1 ; i++)
fsal << v.elementos[i] << ", ";
fsal << v.elementos[v.capacidad-1];
}
fsal << "]";
}
Una instancia de tipo específico de la plantilla de clase sólo
da acceso a instancias del mismo tipo de la plantilla de función.
IS13. Estructuras de datos y de la información — 2003/2004
13
Plantillas de clases y funciones en C++
Cuando se instancie Vector con un determinado tipo, como por ejemplo:
struct Punto3D { double x, y, z; };
Vector<short> vec1;
Vector<Punto3D> vec2;
es responsabilidad del programador asegurarse de que ese tipo esté provisto del
operador de salida <<, ya que es necesario en:
fsal << v.elementos[i] << ", ";
Así, no se obtendrá error de compilación al escribir:
cout << vec1; ⇐ Correcto
cout << vec2; ⇐ Error: Punto3D no tiene definido <<
Si el tipo no dispone del operador de salida <<, puede instanciarse Vector, y no
habrá ninguna pega mientras no se utilice el operador de salida de Vector.
IS13. Estructuras de datos y de la información — 2003/2004
14
Plantillas de clases y funciones en C++
Tipos anidados en plantillas de clases
Se puede anidar la definición de una p
Crear cuenta
Comentarios de: Tema 7 Colas de prioridad (0)
No hay comentarios