Introducción a C++

Tal y como indica el nombre, C++ es una extensión de C, y por tanto permite todas las mismas estructuras (variables, punteros, arrays, bucles, etc.) Sin embargo, las librerías de C++ contienen muchos más algoritmos y estructuras útiles.

La librería "iostream"

La librería más básica es la de entrada y salida, que siempre aparece en los concursos de programación:

#include <iostream>

En particular, esta librería contiene dos variables, cin y cout, que permiten leer y escribir datos (por ejemplo en la pantalla o en un archivo). Son mucho más fáciles de usar que scanf y printf, ya que no es necesario especificar de qué tipo de datos se trata.

Cada uno de los componentes de C++ se indica por medio de std ("standard"). Por ejemplo, std::cin indica la variable cin, y std::cout indica la variable cout. Para evitar de escribir "std::" enfrente de cada componente, se puede incluir la siguiente línea al principio del programa:

using namespace std;

Para ilustrar cómo escribir un programa básico vamos a resolver el primer ejercicio en la página de la OIE, que se llama "Duplica". El problema consiste en leer una serie de números, duplicar cada uno, y escribir el resultado por pantalla. En los concursos de programación, los casos de prueba que el programa debe resolver siempre hallan en archivos. Por lo tanto, el programa tiene que leer los datos del archivo por medio de "cin". Un ejemplo de un archivo para Duplica es:

duplica.in

De acuerdo con la descripción del problema, n=4 es el número de casos de prueba. Cada caso empieza con un número k, indicando cuántos números hay que duplicar en este caso. Vamos a necesitar tres variables de tipo número entero: n, k y x (el número a duplicar). Ahora estamos listos para escribir el programa:


#include <iostream>

using namespace std;

int main() {
   int n, k, x;
   cin >> n;
   for (int i = 0; i < n; ++i) {
      cin >> k;
      for (int j = 0; j < k; ++j) {
         cin >> x;
         cout << " " << 2*x;
      }
      cout << endl;
   }
}

Vamos a analizar lo que hace el programa. Primero declara las variables necesarias y lee el valor de n por medio de cin y el operador >>. Después pasa por todos los n casos de prueba por medio de un bucle que se repite n veces. Para cada caso de prueba, lee el valor de k por medio de cin. Ahora pasa por todos los k números a duplicar por medio de otro bucle que se repite k veces. El valor x de cada número se lee por medio de cin. Mediante cout y el operador << se imprime por pantalla un espacio (" ") para separar un resultado de otro, seguido por dos veces el valor del número (2*x). Al final del bucle interior se imprime por pantalla "endl" (salto de línea) para separar un caso de prueba del siguiente.

Suponiendo que el programa se halla en el archivo "duplica.cpp" y los casos de prueba en "duplica.in", los siguientes comandos compilan, mostrando los warnings y errores si los hay, y ejecutan el código:

Al enviar esta solución (el archivo "duplica.cpp") al juez de la OIE recibimos la siguiente error:

OIE error

La razón es que al principio de cada línea sobra un espacio (si se pone un espacio después de cada resultado sobrará un espacio al final de la línea, algo que es mucho más difícil ver). Una manera de resolver este problema es incluir un "if" dentro del bucle interior:


      for (int j = 0; j < k; ++j) {
         cin >> x;
         if (j > 0) cout << " ";// no incluir espacio enfrente del primer resultado
         cout << 2*x;
      }

Ahora sí el juez acepta la solución.

OIE ok

Tipos de variables

Se puede leer y escribir varios datos de diferentes tipos a la vez:


char c;
int x;
cin >> c >> x;
cout << "El carácter es " << c << " y el número es " << x << endl;

En el siguiente archivo encontraréis un ejemplo sobre los diferentes tipos de variables y como leerlas o imprimirlas con el código. Y en este otro ejemplo podéis ver los límites de cada tipo de variable, los bits que utilizan, la precisión, etc...

cin vs getline

"cin" automáticamente ignora los espacios, las tabulaciones y los saltos de línea. A veces es necesario leer toda una línea a la vez, lo que se puede hacer mediante el siguiente código:


string s;
getline(cin, s)

La diferencia entre "cin >> s" y "getline(cin, s)" es que el primero sólo lee la cadena hasta el primer espacio o tabulación, mientras el segundo lee toda la línea (espacios incluidos).

Finalmente hay una particularidad de "cin" que se puede explotar: la primera vez que la lectura de un dato falla (por ejemplo porque el tipo del dato es incorrecto) el estado de "cin" cambia (ya no se puede leer más datos). El estado de "cin" se puede comprobar simplemente por el valor de la misma variable: el valor de "cin" es "true" si todavía se puede leer datos y "false" en caso contrario. Todo esto es útil si el problema no especifica cuántos casos de prueba hay. Por ejemplo, el siguiente código lee líneas enteras hasta que no haya ninguna línea más:


string s;
for (getline(cin, s); cin; getline(cin, s)) {
   // procesar la línea s
}

El bucle falla precisamente cuando no hay ninguna línea más por leer (el valor de "cin" es "false").

Las librerías STL

Otra clase de librerías de C++ es la que se llama STL (Standard Template Library). Incluye varias estructuras útiles como vectores, listas, diccionarios y colas de prioridad. Cada estructura tiene su propia librería. Las tres estructuras que vamos a mirar esta semana son las siguientes:


#include <vector> // vectores
#include <list>   // listas
#include <map>    // diccionarios

Una ventaja con estas estructuras es que el programador ya no necesita reservar y liberar memoria manualmente, como podéis comprobar en el siguiente enlace. En la UPC han desarrollado un tutorial de la STL muy bueno que podéis mirar. La documentación indica qué métodos existen para cada una de las estructuras.

Tutorial de la STL

Documentación de la STL

La librería "algorithm"

Finalmente hay una serie de algoritmos que se pueden aprovechar escribiendo código en C++. Estos hallan en la librería "algorithm":


#include <algorithm>

Notablemente hay un algoritmo llamado "sort" para ordenar arrays, vectores o listas. Los algoritmos de esta librería están optimizados y por lo tanto uno nunca debería escribir su propio código si ese algoritmo lo proporciona C++. En este fichero os proporcionamos 4 ejemplos de algoritmos de esta librería.

Documentación de los algoritmos

Problemas para resolver esta semana:

Sencillos:

UVa logo 1124 - Celebrity jeopardy
UVa logo 11172 - Relational Operators
UVa logo 11727 - Cost Cutting
UVa logo 10812 - Beat the Spread!
UVa logo 401 - Palindromes
UVa logo 579 - ClockHands
UVa logo 10189 - Minesweeper
OIE logo Calendario
OIE logo Aaaaah!

Avanzados:

UVa logo 454 - Anagrams
UVa logo 1061 - ABO Alleles
UVa logo 11450 - Wedding Shopping
UVa logo 12269 - Lawn mower
OIE logo cifras y LETRAS
OIE logo Palíndromo más pequeño