Hola, bienvenidos a mi nuevo post. Hoy hablaremos sobre STL, tambien conocido como Libreria estandar de plantillas y la abreviatura es por sus siglas en ingles Standard Templates Library. Como vimos al final del post anterior el STL es un conjunto de contenedores de plantillas donde nos dan la posibilidad de ser reutilizables en nuestros codigos, ahora vamos a hablar sobre algunos de los contenidos en esta libreria.

Contenedores

Un contenedor es un objeto donde se guarda otros objetos, existen dos tipos de contenedores: de secuencia y asociativa. Los de tipo secuencia estan diseñados para proporcionar un acceso secuencial y a aleatorio a sus miembros, en cambio la asociativa esta optimizado para obtener acceso a sus elementos mediante valores claves, y por ultimo todas las clases contenedoras de STL estan definidas en el espacio de nombres std. Hablemos sobre contenedores de secuencia, la biblioteca estandar de C++ provee tres contenedores de secuencia:

  • vector, es un contenedor optimizado para proporcionar un acceso rapido a sus elementos mediante un indice
  • list, esta diseñado para optimizar la insercion y eliminacion frecuente de elementos
  • deque, es un contenedor vector con dos extremos, hereda la eficiencia de la clase vector en las operaciones secuenciales de lectura y escritura.

Ahora comenzaremos a hablar sobre el contenedor vector, como dijimos anteriormente es un version mejorada de un array, esto es porque tiene la capacidad de incrementarse automaticamente cuando sea necesario. Para verlo un poco mejor, hagamos el siguiente ejemplo:

stl00.cpp

#include
#include
#include

using namespace std;

class Estudiante
{
public:
Estudiante();
Estudiante(const string & nombre, const int edad);
Estudiante(const Estudiante & rhs);
~Estudiante();
void AsignarNombre(const string & nombre);
string ObtenerNombre() const;
void AsignarEdad(const int edad);
int ObtenerEdad() const;
Estudiante & operator = (const Estudiante & rhs);
private:
string suNombre;
int suEdad;
};

Estudiante::Estudiante():
suNombre(“Nuevo Estudiante”),
suEdad(16)
{}

Estudiante::Estudiante(const string & nombre, const int edad):
suNombre(nombre),
suEdad(edad)
{}

Estudiante::Estudiante(const Estudiante & rhs):
suNombre(rhs.ObtenerNombre()),
suEdad(rhs.ObtenerEdad())
{}

Estudiante::~Estudiante() {}

void Estudiante::AsignarNombre(const string & nombre)
{
suNombre = nombre;
}

string Estudiante::ObtenerNombre() const
{
return suNombre;
}

void Estudiante::AsignarEdad(const int edad)
{
suEdad = edad;
}

int Estudiante::ObtenerEdad() const
{
return suEdad;
}

Estudiante & Estudiante::operator= (const Estudiante & rhs)
{
suNombre = rhs.ObtenerNombre();
suEdad = rhs.ObtenerEdad();
return *this;
}

ostream & operator << (ostream & os, const Estudiante & rhs)
{
os << rhs.ObtenerNombre() << ” tiene “;
os << rhs.ObtenerEdad() << ” años de edad.”;
return os;
}

template < class T >
void MostrarVector(const vector< T > & v);

typedef vector< Estudiante > ClaseEscuela;

int main()
{
Estudiante Harry;
Estudiante Sally(“Sally”, 15);
Estudiante Bill(“Bill”, 17);
Estudiante Peter(“Peter”, 16);

ClaseEscuela ClaseVacia;
cout << “ClaseVacia:\n”;
MostrarVector(ClaseVacia);

ClaseEscuela ClaseCreciendo(3);
cout << “ClaseCreciendo(3):\n”;
MostrarVector(ClaseCreciendo);

ClaseCreciendo[ 0 ] = Harry;
ClaseCreciendo[ 1 ] = Sally;
ClaseCreciendo[ 2 ] = Bill;
cout << “ClaseCreciendo(3) despues de asignar estudiantes:: \n”;
MostrarVector(ClaseCreciendo);

ClaseCreciendo.push_back(Peter);
cout << “ClaseCreciendo() despues de agregar al 4to estudiante:\n”;
MostrarVector(ClaseCreciendo);

ClaseCreciendo[ 0 ].AsignarNombre(“Harry”);
ClaseCreciendo[ 0 ].AsignarEdad(18);
cout << “ClaseCreciendo() despues de Asignar:\n”;
MostrarVector(ClaseCreciendo);

return 0;
}

template < class T >
void MostrarVector(const vector< T > & v)
{
cout << “max_size() = ” << v.max_size();
cout << “\tsize() = ” << v.size();
cout << “\tcapacity() = ” << v.capacity();
cout << “\t” << (v.empty() ? “vacio” : “no vacio”);
cout << endl;
for (int i = 0; i < v.size(); i++)
cout << v[ i ] << endl;
cout << endl;
}

Vamos a analizar este caso, primero vamos a incluir tres archivos de encabezado, la de siempre (iostream), la de string para poder utilizar el tipo string y por ultimo vector el cual nos permitira acceder a las funciones miembro de la misma pero esto lo veremos mas adelante, nuestro siguiente paso sera crear una clase llamada Estudiante, esta se encargara basicamente de almacenar la informacion de nombre y edad del estudiante, en este caso se utiliza string en lugar de char * para una mayor comodidad. En la clase declaramos el prototipo de las funciones miembro de la misma, luego iremos definiendo uno por uno, observen un detalle en el constructor predeterminado, donde definen a suNombre con “Nuevo Estudiante” y le asignan un valor de 16 a suEdad. Despues solamente redefiniremos al operador = y <<, antes de main() vamos a crear un template llamada T para mostrar los valores de vector, luego crearemos un typedef para tener un objeto del tipo vector llamado ClaseEscuela. Luego pasemos al main(), en el vamos a crear a cuatro estudiantes, donde salvo Harry en el resto pasaremos los datos de los mismos y retengan este detalle, ahora les voy a mostrar la salida para comentar cada uno de los bloques siguientes dentro de main():

$ ./program/stl00
ClaseVacia:
max_size() = 153391689  size() = 0      capacity() = 0  vacio

ClaseCreciendo(3):
max_size() = 153391689  size() = 3      capacity() = 3  no vacio
Nuevo Estudiante tiene 16 años de edad.
Nuevo Estudiante tiene 16 años de edad.
Nuevo Estudiante tiene 16 años de edad.

ClaseCreciendo(3) despues de asignar estudiantes::
max_size() = 153391689  size() = 3      capacity() = 3  no vacio
Nuevo Estudiante tiene 16 años de edad.
Sally tiene 15 años de edad.
Bill tiene 17 años de edad.

ClaseCreciendo() despues de agregar al 4to estudiante:
max_size() = 153391689  size() = 4      capacity() = 6  no vacio
Nuevo Estudiante tiene 16 años de edad.
Sally tiene 15 años de edad.
Bill tiene 17 años de edad.
Peter tiene 16 años de edad.

ClaseCreciendo() despues de Asignar:
max_size() = 153391689  size() = 4      capacity() = 6  no vacio
Harry tiene 18 años de edad.
Sally tiene 15 años de edad.
Bill tiene 17 años de edad.
Peter tiene 16 años de edad.

Antes de seguir comentando a main() vamos a hablar sobre MostrarVector(), observen como utilizamos el template, para decirle al compilador sobre la definicion de nuestro prototipo de MostrarVector(), en esta funcion se encargara de mostrarnos las funciones miembro provenientes de vector, estas son:

  • max_size(), encargada de mostrar el tamaño maximo disponible para el vector
  • size(), encargada de mostrar el tamaño actual del vector
  • capacity(), encargada de mostrar la capacidad del vector
  • empty(), esta se encarga de definir si el vector tiene contenido o no por medio de chequeo simple ya que devuelve un booleano

Y por ultimo, utilizamos un bucle for para mostrar los valores contenidos en el vector v, hasta aca la explicacion de MostrarVector() sigamos con el main(). Despues de declaradas nuestros objetos (estudiantes), vamos a analizar los bloques, en el primer nos encargaremos de crear una instancia llamada ClaseVacia donde no crearemos nada ni le asignaremos ningun valor entonces al mostrarlo no nos indicara nada, salvo el tamaño maximo disponible para este vector, y al final que esta vacio. En el siguiente bloque crearemos una instancia llamada ClaseCreciendo donde le asignaremos tres posiciones, si ven la salida ahora dira que no esta vacio, muestra el nuevo valor de size() y de capacity(), y por ultmo como utiliza el constructor predeterminado los alumnos no tendran ningun datos sino el nombre como “Nuevo Estudiante” y la edad de 16, en el proximo bloque asignaremos a tres estudiantes (Harry, Sally y Bill), observen como Harry al no tener ningun dato no modifica los datos establecidos, en cambio en las otras dos posiciones si se modifican como se ve en la salida. Para el proximo bloque, agregaremos una nueva posicion en el vector esto por medio de push_back(), funcion miembro tambien de vector, en este caso agregaremos al estudiante Peter y por ultimo observen como size() paso a cuatro y capacity() paso al valor seis (esto lo hizo el compilador automaticamente), y finalmente en el ultimo bloque vemos como modificamos los datos de Harry por medio de las funciones miembro de la clase Estudiante, esto nos producira la salida mostrada. Hasta aqui el contenedor vector, ahora pasemos a hablar sobre list, esta tambien hereda las funciones miembro de la clase vector, para entender mejor su funcionamiento veamos el siguiente ejemplo:

stl01.cpp

#include <iostream>
#include <list>

using namespace std;

typedef list< int > ListaEnteros;

int main()
{
ListaEnteros listaInt;

for(int i = 1; i <= 10; ++i)
listaInt.push_back(i * 2);
for(ListaEnteros::const_iterator ci = listaInt.begin(); ci != listaInt.end(); ++ci)
cout << *ci << ” “;
cout << endl;
return 0;
}

En este codigo incluiremos el archivo de encabezado list, esto nos proporcionara acceso a las funciones miembro de list, como en el caso anterior declaramos un typedef de list para poder utilizarlo, en el main() crearemos una instancia llamada listaInt del typedef, luego utilizaremos un bucle for, llenar a la instancia de tipo list por medio de push_back(), hace exactamente lo mismo que en vector, en el siguiente bucle for, utilizaremos la funcion iterator(), esta funcion es una especie de apuntador y puede desreferenciarse para poder recuperar al nodo que apunta. en el programa const_iterator() y la diferencia entre este y el iterator() es: el primero nos permite un acceso de solo lectura sobre el vector y con el otro podremos tambien modificar el contenido del mismo, por eso en este caso creamos uno de tipo const llamado ci para asignarle el primer valor del objeto listaInt, el condicional es que sea distinto del ultimo valor almacenado en listaInt, y lo incrementamos, la linea se encargara de mostrar todos los valores almacenados en ci dando una salida como esta:

$ ./program/stl01
2 4 6 8 10 12 14 16 18 20

Como se puede ver se “enlisto” todo el contenido en cada una de las posiciones del vector almacenado, para esto se utiliza el contenedor list. Finalmente nos queda el contenedor deque, como digimos es una version mas eficiente de vector, sus operaciones se implementan de manera similar a list en donde las asignaciones de memoria solo se aplican a los nuevos elementos eliminando la necesidad de reasignar todo el contenedor a una nueva ubicacion de memoria, como sucede con el contenedor vector. Los contenedores deque estan idealmente adaptados para aplicaciones en donde las inserciones y eliminaciones ocurren en uno o en ambos extremos, y para la cual es importante el acceso secuencial de los elementos. Ahora pasemos a contenedores asociativas, las contenedores de este tipo son las siguientes:

  • map, es similar a vector pero concede un mejor acceso aleatorio a traves de un valor clave
  • multimap, es similar a map pero sin restriccion de claves unicas
  • set, trabaja de forma similar a map pero en lugar de utilizar dos valores claves, ya lo veremos en el siguiente ejemplo, utiliza uno solo
  • multiset, es similar a set pero permite claves duplicadas

Ahora hablaremos sobre set, para eso veamos el siguiente ejemplo:

stl02.cpp

#include <iostream>
#include <string>
#include <map>

using namespace std;

class Estudiante
{
public:
Estudiante();
Estudiante(const string & nombre, const int edad);
Estudiante(const Estudiante & rhs);
~Estudiante();
void AsignarNombre(const string & nombre);
string ObtenerNombre() const;
void AsignarEdad(const int edad);
int ObtenerEdad() const;
Estudiante & operator = (const Estudiante & rhs);
private:
string suNombre;
int suEdad;
};

Estudiante::Estudiante():
suNombre(“Nuevo Estudiante”),
suEdad(16)
{}

Estudiante::Estudiante(const string & nombre, const int edad):
suNombre(nombre),
suEdad(edad)
{}

Estudiante::Estudiante(const Estudiante & rhs):
suNombre(rhs.ObtenerNombre()),
suEdad(rhs.ObtenerEdad())
{}

Estudiante::~Estudiante() {}

void Estudiante::AsignarNombre(const string & nombre)
{
suNombre = nombre;
}

string Estudiante::ObtenerNombre() const
{
return suNombre;
}

void Estudiante::AsignarEdad(const int edad)
{
suEdad = edad;
}

int Estudiante::ObtenerEdad() const
{
return suEdad;
}

Estudiante & Estudiante::operator= (const Estudiante & rhs)
{
suNombre = rhs.ObtenerNombre();
suEdad = rhs.ObtenerEdad();
return *this;
}

 

ostream & operator << (ostream & os, const Estudiante & rhs)
{
os << rhs.ObtenerNombre() << ” tiene “;
os << rhs.ObtenerEdad() << ” años de edad.”;
return os;
}

template < class T, class A >
void MostrarMap(const map< T, A > & v);

typedef map< string, Estudiante > ClaseEscuela;

int main()
{
Estudiante Harry(“Harry”, 18);
Estudiante Sally(“Sally”, 15);
Estudiante Bill(“Bill”, 17);
Estudiante Peter(“Peter”, 16);

ClaseEscuela ClaseMatematicas;
ClaseMatematicas[ Harry.ObtenerNombre() ] = Harry;
ClaseMatematicas[ Sally.ObtenerNombre() ] = Sally;
ClaseMatematicas[ Bill.ObtenerNombre() ] = Bill;
ClaseMatematicas[ Peter.ObtenerNombre() ] = Peter;

cout << “ClaseMatematicas:\n”;
MostrarMap(ClaseMatematicas);

cout << “Sabemos que “;
cout << ClaseMatematicas[ “Bill” ].ObtenerNombre();
cout << ” tiene “;
cout << ClaseMatematicas[ “Bill” ].ObtenerEdad();
cout << ” años de edad\n”;

return 0;
}

template < class T, class A >
void MostrarMap(const map< T, A > & v)
{
for(typename map< T, A >::const_iterator ci = v.begin(); ci != v.end(); ++ci )
cout << ci->first << “:” << ci->second << “\n”;
cout << endl;
}

Este ejemplo es similar al visto en vector pero con unas sutiles diferencias, primero utilizamos otro archivo de encabezado, map, despues el resto del programa es similar, salvo cuando definimos a la funcion de MostrarMap():

template < class T, class A >
void MostrarMap(const map< T, A > & v);

typedef map< string, Estudiante > ClaseEscuela;

Observen como agregamos una nueva clase cuando llamamos al template, estas representan la clave y el valor, como en este caso la clave va a ser el nombre del alumno lo definimos como string y el valor va a ser del tipo Estudiante. En main() crearemos cuatro estudiantes, con todos sus datos, luego una instancia llamada ClaseMatematicas, donde los agregaremos, observen como la clave la identificamos con el nombre del estudiante, y le asignamos el valor almacenado en el objeto (estudiante) correspondiente. Despues ejecutaremos MostrarMap() donde nos traera todos los datos de los alumnos para luego traer solo un dato especifico e indicamos como valor clave al nombre del estudiante (Bill en este ejemplo), veamos la salida:

$ ./program/stl02
ClaseMatematicas:
Bill:Bill tiene 17 años de edad.
Harry:Harry tiene 18 años de edad.
Peter:Peter tiene 16 años de edad.
Sally:Sally tiene 15 años de edad.

Sabemos que Bill tiene 17 años de edad

Lo unico nuevo con respecto al ejemplo anterior fue la necesidad de anteponer typename a map en el bucle for, y utilizamos los elementos first y second para poder obtener acceso al valor de clave y al valor almacenado respectivamente, con esto terminamos contenedores pasemos al siguiente tema.

Pilas

La pila es una de las estructura de datos mas utilizadas en programacion, pese a esto no se implementa como una clase contenedora independiente y es utilizado como una envoltura de un contenedor. Para esto existe la clase de plantilla stack, el archivo de encabezado es stack y es miembro del espacio de nombre std. Una pila es un bloque asignado en forma continua con la posibilidad de crecer o encoger en su parte posterior. Solo se puede acceder a los elementos de una pila, y su elimimacion es desde la parte posterior, para implementar una pila solamente se necesita un contenedor de secuencia con soporte de los metodos back(), push_back() y pop_back(). Esta clase esta preparada para utilizar cualquier tipo de objeto pero con solo una condicion, todos los elementos deben ser del mismo tipo.
La pila es una estructura LIFO (Last In First Out), ultimo en entrar y primero en salir, por convencion la parte superior de la pila es llamada tope de la pila, las operaciones utilizadas son push (empujar) y pop (sacar).

Colas

Esta es tambien una estructura de datos, los elementos se agregan a la cola en un extremo y salen por el otro. La forma de trabajo es FIFO (First In First Out), primero en entrar y primero en salir, donde entran por atras y salen por adelante. La clase contenedora es llamada queue, al igual que la pila se utiliza como envoltura de un contenedor y utiliza los mismos metodos back(), push_back() y pop_back().

Clases de algoritmos

Un contenedor es utilizado para guardar una secuencia de elementos, los contenedores estandar definen operaciones para manipular contenedores y sus elementos. La biblioteca estandar proporciona aproximadamente 60 algoritmos las cuales realizan las operaciones mas basicas y utilizadas de los contenedores. Los algoritmos son declarados por medio del archivo de encabeza <algorithm> y tambien pertenece al espacio de nombres std, para entender el concepto de algoritmo se debe entender el concepto de objeto de funcion, lo cual nos permitira definir una sobrecarga al operador () permitiendonos llamarlo desde una funcion, veamoslo a traves del siguiente ejemplo:

stl03.cpp

#include <iostream>

using namespace std;

template< class T >
class Imprimir
{
public:
void operator()(const T & t)
{ cout << t << ” “; }
};

int main()
{
Imprimir< int > HacerImpresion;
for(int i=0; i < 5; i++)
HacerImpresion(i);
cout << endl;
return 0;
}

En este ejemplo, vean como se sobrecarga el operador () para mostrar un valor recibido, luego en el main() al crear a la instancia HacerImpresion en base a la planilla, es utilizada en el bucle for para mostrar una salida agregando al operador () en la instancia  HacerImpresion, dando una salida como esta:

$ ./program/stl03
0 1 2 3 4

Ya vimos la base de como funciona ahora hablemos sobre algoritmos de secuencia no mutantes, estos no cambian los elementos de una secuencia, estos son algunos operadores de ejemplo:

  • for_each()
  • find()
  • search()
  • count()

Ahora veremos un codigo  con el operador for_each() para ver el contenido de un vector:

stl04.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template < class T >
class Imprimir
{
public:
void operator()(const T & t)
{ cout << t << ” “; }
};

int main()
{
Imprimir< int > HacerImpresion;
vector< int > vInt(5);

for(int i = 0; i < 5; ++i)
vInt[ i ] = i * 3;
cout << “for_each()\n”;
for_each(vInt.begin(), vInt.end(), HacerImpresion);
cout << “\n”;
return 0;
}

Como pueden ver, tenemos nuestra plantilla volvemos a crear la instancia HacerImpresion pero ahora tambien creamos un vector y con el primer bucle for lo llenaremos, para luego recuperarlo a traves del operador for_each(), donde definimos el origen (vInt.begin()), el final (vInt.end()) y como lo mostraremos (HacerImpresion) pero como pueden ver solamente hace eso, veamos la salida:

$ ./program/stl04
for_each()
0 3 6 9 12

Ahora hablemos del ultimo tema, algoritmo de secuencias mutantes. A diferencia del caso anterior este si modificara el contenido, veamos el siguiente ejemplo:

stl05.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template < class T >
class Imprimir
{
public:
void operator()(const T & t)
{ cout << t << ” “; }
};

int main()
{
Imprimir< int > HacerImpresion;
vector< int > vInt(10);

fill(vInt.begin(), vInt.begin() + 5, 1);
fill(vInt.begin() + 5, vInt.end(), 2);
for_each(vInt.begin(), vInt.end(), HacerImpresion);
cout << “\n”;
return 0;
}

Como ven, en este caso la diferencia esta en la implementacion del operador fill() para poder llenar nuestro vector vInt, en la primera linea, llenaremos desde la primera posicion hasta la quinta con el numero uno, en la segunda linea llenaremos desde la sexta hasta la decima posicion con el numero dos y por ultimo con el for_each() mostrara todos los valores ingresados, les dejo la salida:

$ ./program/stl05
1 1 1 1 1 2 2 2 2 2

Hasta aqui hemos visto todo sobre STL, hemos visto contenedores, de que tipo son, hemos visto algunos ejemplos, como implementarlos, hemos hablado sobre la pila y la cola, y finalmente sobre algoritmos, espero les haya sido util nos vemos en el proximo post.

Anuncios