std::set<T,…>
La clase set permite describir un conjunto ordenado y sin repetición de elementos. Previamente es necesario parar este orden como parámetro template (un funtor). Por defecto, el funtor std::less (basado en el operador <) es utilizado, lo que equivale a tener un conjunto de elementos clasificados del más pequeño al más grande. Concretamente, basta con implementar el operador < de una clase o una estructura de tipo T para poder definir un std::set<T>. Además, el tipo T debe disponer de un constructor vacío T().
Dificultad:
- O(log(n)) para la búsqueda e inserción. Efectivamente, la estructura std::set saca partido del orden sobre T para construir una estructura de árbol roja y negra, lo que permite la búsqueda logarítmica de un elemento
#include <set>
#include <iostream>
int main(){
std::set<int> s; // equivale a std::set<int,std::less<int> >
s.insert(2); // s contiene 2
s.insert(5); // s contiene 2 5
s.insert(2); // el repetido no es insertado
s.insert(1); // s contiene 1 2 5
std::set<int>::const_iterator
sit (s.begin()),
send(s.end());
for(;sit!=send;++sit) std::cout << *sit << ' ';
std::cout << std::endl;
return 0;
}
Atención: el eliminar o agregar un elemento en un std::set vuelve invalido a sus iteradores.
No se debe modificar un std::set en un bucle for basado en sus iteradores.
std::map<K,T,…>
Un map permite asociar una contraseña a un dato.
El map toma al menos dos parámetros templates:
- el tipo de la clave K
- el tipo del dato T
Al igual que std::set, el tipo K debe ser ordenado (este orden puede ser pasado como 3er parámetro template, std::less<K> par défaut) y , el tipo T solo impone tener un constructor vacio.
Dificultad:
- O(log(n)) para la búsqueda e inserción. En efecto, la estructura std::map saca partido del orden sobre T para construir una estructura de árbol rojo y negro, lo que permite una búsqueda logarítmica de un elemento.
Atención: el eliminar o agregar un elemento en un std::map vuelve invalido a sus iteradores. No se debe modificar un std::map en una bucle for basada en sus iteradores.
Atención: el hecho de acceder a una clave vía el operador [] inserta esta clave (con el dato T()) en el map. Por ello, el operador [] no es adaptado para verificar si una clave está presente en el map, es necesario utilizar el método find. Además no asegura la constancia del map (a causa de las potenciales inserciones) y por lo tanto no puede ser utilizado en un const std::map.
Ejemplo:
#include <map>
#include <string>
#include <iostream>
int main(){
std::map<std::string,unsigned> map_mis_idx;
map_mes_idx["enero"] = 1;
map_mes_idx["febrero"] = 2;
//...
std::map<std::string,unsigned>::const_iterator
mit (map_mis_idx.begin()),
mend(map_mis_idx.end());
for(;mit!=mend;++mit) std::cout << mit->first << '\t' << mit->second << std::endl;
return 0;
}
Los iteradores
En la sección precedente vimos que los iteradores permiten recorrer fácilmente una estructura de la STL. Un iterador recuerda un poco la noción de puntero, pero no es una dirección. A continuación veremos cuatro iteradores clásicos de la STL.
Estos son definido para todas las clases de la STL dichas anteriormente (entre ellas por supuesto std::pair)
iterator y const_iterator
Un iterador (y un const_iterator) permite recorrer un contenedor de inicio a fin. Un const_iterator contrariamente a un iterator, da acceso únicamente para la lectura del elemento deseado. Así, un recorrido con const_iterator no produce cambios en el contenedor. Es por ello que un contenedor “const” puede ser recorrido por const_iterators pero no por iterators.
En general, cuando se debe elegir entre iterators y const_iterators, siempre hay que preferir los const_iterators ya que estos vuelven la sección de código a la cual sirven más genérica (aplicable a los contenedores const o no const)
- begin(): devuelve un iterador que apunta al primer elemento
- end(): devuelve un iterador que apunta justo después del ultimo elemento
++: Permite incrementar el iterador haciéndolo pasar al elemento siguiente.
Ejemplo:
<< #include <list>
#include <iostream>
const std::list<int> crear_lista(){
std::list<int> l;
l.push_back(3);
l.push_back(4);
return l;
}
int main(){
const std::list<int> mi_lista(crear_lista());
// no compila ya que es const
// std::list<int>::iterator
// lit1 (l.begin()),
// lend(l.end());
//for(;lit1!=lend1;++lit1) std::cout << *lit1 << ' ';
//std::cout << std::endl;
std::list<int>::const_iterator
lit2 (l.begin()),
lend2(l.end());
for(;lit2!=lend2;++lit2) std::cout << *lit2 << ' ';
std::cout << std::endl;
return 0;
}
reverse_iterator y const_reverse_iterator
El principio de reverse_iterator y const_reverse_iterator es similar a los iterators y const_iterator pero el recorrido se hace en el sentido opuesto.
Utilizamos:
- rbegin() : devuelve un iterador que apunta hacia el último elemento
- rend() : devuelve un iterador que apunta justo antes del primer elemento
- — : permite disminuir el reverse_iterator haciéndolo pasar al elemento precedente.
#include <set>
#include <iostream>
int main(){
std::set<unsigned> s;
s.insert(1); // s = {1}
s.insert(4); // s = {1, 4}
s.insert(3); // s = {1, 3, 4}
std::set<unsigned>::const_reverse_iterator
sit (s.rbegin()),
send(s.rend());
for(;sit!=send;++sit) std::cout << *sit << std::endl;
return 0;
}
… muestra:
4 3 1
Los algoritmos
Si dominas el concepto de iterador, puedes ver este documento:
http://www.sgi.com/tech/stl/table_of_contents.html
Debemos recordar algunos métodos prácticos que hemos visto como find (para los std::set y std::map) para buscar un elemento, std:fill para (re)inicializar un std::vector, algoritmos de selección, de búsqueda de min o max.
Te esperamos en la segunda parte del artículo en donde hablaremos mas acerca de estos temas, los cuales hoy en día son de vital importancia en el mundo de la tecnología.
