 |
| CURSO ON-LINE DE PREPARACIÓN |
| Sesión 1.4. La librería STL de C++ |
|
| CURSO ON-LINE DE PREPARACIÓN |
| Sesión 1.4. La librería STL de C++ |
¿Por qué utilizar C++ para programar las soluciones en un concurso de programación?
C++ incluye a C ⇒ Usar C en lugar de C++ no tiene ninguna ventaja.
Tipado algo más estricto ⇒ es más fácil detectar errores.
Para los que conozcan C, ¿por qué no aprovechar las características mejores de C++ en los programas cuando sean útiles?
STL (Standard Template Library): Librería de algoritmos y tipos de datos estándar listos para usar y muy adecuados para el tipo de problemas que se tienen que resolver.
Se pueden aprovechar patrones muy sencillos.
Para cada tipo de dato o algoritmo es necesario incluir las cabeceras (headers) específicas.
Usar el namespace std:
using namespace std;
La STL incluye el tipo string:
Manejo de memoria automático.
Facilidad de programación.
Todos los operadores habituales disponibles: + (concatenación), == (comparación), = (asignación), incluido el [] (Indexación)
Conversión directa a char* si se necesita.
Ejemplo:
#include <string>
using namespace std;
string str = "Hola";
string str("Hola");
string b = string("hola")+"2";
// b es "hola2"
b == "hola2" // true
Ejemplo más largo: ej1-string.C.
Variables cin y cout, definidas en <iostream> dentro del namespace std.
Operadores << y >>.
Modificador endl.
Ejemplos:
Escritura de datos:
#include <iostream>
using namespace std;
int i = 0;
cout << i << endl;
string str("hola");
cout << str << endl;
Lectura de datos:
#include <iostream>
using namespace std;
int i;
cin >> i;
string str;
cin >> str;
// Lee, por ejemplo:
2
cadena
Obsérvese que en el ejemplo anterior se ignoran los espacios y saltos de línea de la entrada.
Ejemplo de lectura de una línea:
#include <iostream>
using namespace std;
string str;
getline(cin, str);
// Lee, por ejemplo:
hola, soy yo
getline descarta el caracter de salto de línea (‘\n’) final (si existe).
Esta es, probablemente, la parte más útil de C++ para resolver los problemas de los concursos.
Incluidos en la STL:
Vectores (vector). Ejemplo: ej2-vector.C.
Listas (list). Ejemplo: ej3-list.C.
Pilas (stack).
Colas FIFO (queue)
Colas con dos extremos (deque). Ejemplo: ej4-deque.C.
Conjuntos (set).
Mapas (map). Ejemplo: ej5-map.C.
Los strings también se comportan como contenedores de caracteres.
Los ficheros a incluir son iguales a los nombres (no se debe añadir ‘.h’).
Todos estos tipos comparten gran parte de su interfaz. Operaciones comunes:
size.
push_front.
push_back.
empty.
insert.
erase.
Iteradores.
Todos los contenedores soportan el uso de iteradores para recorrerlos de manera uniforme.
Los iteradores de la STL se comportan de forma similar a los punteros de C, pero trabajan a un nivel un poco más alto de abstracción.
begin() y end() son los métodos que devuelven iteradores que apuntan al primer elemento del contenedor o al final del contenedor (en cierto modo, a la posición que ocuparía el elemento siguiente al último).
rbegin() y rend() permiten realizar el recorrido en orden inverso.
Ejemplos:
Uso de una lista:
#include <list>
#include <iostream>
using namespace std;
list<int> li;
li.push_front(1);
li.push_front(2);
list<int>::iterator it = li.begin();
while (it != li.end())
cout << *it++ << endl;
// Imprime:
2
1
Recorrido de un string como contenedor:
#include <string>
using namespace std;
string str = "hola";
cout << str.size() << endl;//4
string::iterator it = str.begin();
cout << *it++ << endl // 'h'
La STL proporciona algoritmos genéricos usando las templates de C++.
Plantillas que capturan patrones comunes (en la cabecera algorithm):
for_each
find_if
count_if
y otras (véase la documentación)
C++ utiliza objetos función para implementar higher order programming. Es decir, para poder pasar funciones con estado (aka closures) a los algoritmos arriba mencionados.
Un objeto función es cualquier tipo con operator() definido.
La sintaxis es algo más farragosa que en otros lenguajes, lo cual se ha solucionado en la versión más reciente del estándar de C++ (C++11, pero desgraciadamente aún no se puede utilizar esa versión en los concursos).
Ejemplo:
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v = // Suponemos inicializado
struct MovingAverage {
int n_;
double& avg_;
MovingAverage(double& avg) : n_(0), avg_(avg) {}
void operator()(const int& i) {
avg_ = n_ / (n_+1) * avg_ + i / (n_+1);
++n_;
}
};
double avg = 0;
MovingAverage m(avg);
for_each(v.begin(), v.end(), m);
cout << avg << endl; // Muestra la media acumulada hasta cada elemento
// Cuenta el número de elementos de v menores que 1
cout << count_if(v.begin(), v.end(),
bind2nd(less<int>(), 1));
El objeto less<int> compara con el operador <.
El objeto bind2nd fija el segundo operando de less a 1.
Otro ejemplo más largo: ej6-algorithm.C
La entrada de los problemas suele ser conjuntos de palabras o números.
¿Cuantas palabras/números debo leer?:
Para facilitar la lectura de la entrada, a veces, se indica en primer lugar la cantidad de datos a leer.
En otros casos no, se utiliza algún marcador para indicar el final de la entrada: palabra clave, línea en blanco, final del fichero…
La mayoría de las veces bastará con leer la entrada de cin mediante el operador >>.
Ejemplos:
Si nos dan el número de palabras:
Para leer:
4
casa
perro
coche
arbol
Se podría utilizar el siguiente programa:
vector<string> dic;
int nwords;
cin >> nwords;
for (int w = 0; w < nwords; w++) {
string word;
cin >> word;
dic.push_back(word); // Guarda la palabra
}
dic.sort(); // Ordenamos la lista
Si nos dicen que la entrada acaba con la palabrclave «END»:
Para leer:
casa
perro
coche
arbol
END
Se podría utilizar el siguiente programa:
vector<string> dic;
string word;
cin >> word;
while (word != "END") {
dic.push_back(word); // Guardas la palabra
cin >> word;
}
dic.sort();
Esta es la mejor forma para leer la entrada cuando no se differencian espacios de retornos de carro.
Si tenemos que tener en cuenta los espacios, los ítems se separan con retornos de carro y el final del diccionario es un línea en blanco (usando getline):
Para leer:
casa grande
perro pequeño
coche mediano
arbol azul
Se podría utilizar el siguiente programa:
getline(cin,word);
while (word.length() > 0) {
dic.push_back(word);
getline(cin,word);
}
O también el siguiente:
for (getline(cin,word); cin.good(); getline(cin,word))
lines.push_back(word);
Para leer palabra por palabra una vez leida la línea:
Para leer palabra por palabra la misma entrada del ejemplo anterior, se podría utilizar el siguiente programa.#include <sstream>
vector<string> words;
string line, str;
if (getline(cin,line)) {
stringstream ss(line);
while (ss >> str)
words.push_back(str);
}
Para leer números con getline:
Para leer:
4 8 15 16 23 42
Se podría utilizar el siguiente programa:
string word;
vector<int> numbers;
int num;
getline(cin,word);
stringstream ss(word);
while (ss >> num)
numbers.push_back(num);
El enunciado de este problema está disponible en el juez online de la Universidad de Valladolid.
Tabla Morse.
Cadena de símbolos Morse sin separaciones.
Conjunto de palabras.
Número de frases distintas.
No complejo, aunque cuidado con el tamaño:
1 000 caracteres morse, 10 000 palabras en el diccionario.
Tabla Morse:
map<char, string> Morse;
Morse['A'] = ".-";
Morse['B'] = "-...";
Morse['C'] = "-.-.";
Morse['D'] = "-..";
Morse['E'] = ".";
Morse['F'] = "..-.";
…
También valdría usar un array de cadenas de caractacteres.
Lectura de la entrada:
string cadena;
cin >> cadena;
int npalabras;
cin >> npalabras; // No se usará
vector<string> diccionario;
copy(istream_iterator<string>(cin),
istream_iterator<string>(),
back_inserter(diccionario));
Conversión a Morse:
string toMorse(string& in)
{
string output = "";
for (string::iterator it = in.begin ();
it != in.end ();
it++) {
output += Morse[*it];
}
return output;
}
vector<string>::iterator it;
for (it = diccionario.begin();
it != diccionario.end();
it++) {
*it = toMorse(*it);
}
o bién (más sofisticado…):
transform(diccionario.begin(), diccionario.end(),
diccionario.begin(), toMorse);
¿Podemos usar backtracking?
Puede ser muy largo en el caso peor.
Quizá no… no está muy claro. Se puede probar.
Para cada posición, construir una lista de palabras que «casan», y hacer el backtracking con eso
Caso peor:
.............................(1000)
10000
E
EE
EEE
EEEE
EEEEE
EEEEEE
EEEEEEE
EEEEEEEE
EEEEEEEEE
Dos alternativas:
Aprovechar la información obtenida hasta el momento para limitar el backtracking (podar).
Convertir proceso en memoria, usando tablas para evitar recalcular varias veces lo mismo (programación dinámica).
Consideremos el caso peor, el final de la cadena:
Imaginemos que la primera solución encontrada es E, E, E, …(todo ‘E’).
Con los dos últimos puntos, hay dos soluciones: (‘E’, ‘E’) y (‘EE’).
Eso significa que cualquier combinación que llegue a la misma posición sabe que hay dos soluciones a partir de ese punto.
⇒ ¿Por qué no guardar un vector que cuente el número de soluciones a las que se llega desde un punto dado? Ejemplo:
cadena: . . . . . . . . . . .
vector: ? ? ? ? ? 2 1
Si la cadena va de 0—(n-1), se sabe que en la posición (n-2) se llega a dos soluciones a partir de ahí (‘E’, ‘E’) y (‘EE’)
Al probar en (n-2) la cadena ‘EE’, se llega al final, con lo que se suma uno a vector[n-2].
Al probar la cadena ‘E’, se suma las soluciones disponibles en (n-1), por lo que finalmente es 2.
Al final, en vector[0] está el número de soluciones totales
Ejemplo:
Paso1 -----------------------
cadena: . . . . . . . . . . .*
vector: 0 0 0 0 0 0 0 0 0 0 1
Paso2 -----------------------
cadena: . . . . . . . . . .*.
vector: 0 0 0 0 0 0 0 0 0 1 1
E
Paso3 -----------------------
cadena: . . . . . . . . . .*.
vector: 0 0 0 0 0 0 0 0 0 2 1
E E
Implementación de la solución:
El vector con las soluciones parciales se llamará nsoluciones:
vector<int> nsoluciones(cadena.size(), 0);
Rellenado el vector:
void buscasoluciones() {
for (int pos = cadena.size(); pos >= 0; --pos) {
// Comprobar para todas las palabras del diccionario
vector<string>::const_iterator it = diccionario.begin();
for (;it != diccionario.end(); it++) {
int len = (*it).size();
if (cadena.substr (pos, len) == *it) {
// Se ha encontrado una cadena que casa
int newpos = pos + len;
if (newpos == cadena.size())
nsoluciones[pos]++;
else
nsoluciones[pos] += nsoluciones[newpos];
}
}
}
}
Llamada desde main:
buscasoluciones();
cout << nsoluciones[0] << endl;
Algunas técnicas vistas son algo sofisticadas.
Pero otras se pueden usar sin problemas con sólo un poco de práctica.
C++ permite el uso de estructuras dinámicas.
Sin necesidad de usar punteros.
Sin necesidad de manejar la memoria explícitamente.
Requiere de práctica.
En la red, sobre todo:
http://www.sgi.com/tech/stl (Referencia escueta pero con ejemplos esclarecedores)