C++ Trucos

Enviado por jvilella el Lun, 23/09/2019 - 04:32

Requisitos:

A continuación se describen algunos pequeños detalles adicionales del lenguaje C++ que de cara a concursar pueden ser útiles porque ahorran tiempo de escritura o de ejecución. Son trucos que dificultan la mantenibilidad del código (porque lo hacen más difícil de entender) pero que son muy habituales, cosa que vol quiere decir que para a un programador experimentado no suponen ninguna dificultad a la hora de entender un código.

Temas

  1. Creación rápida de variables
  2. Modificaciones sobre una variable
  3. Simplificar estructuras lógicas
  4. Resultados como booleanos
  5. Un ejemplo con todo (o casi)
  6. Abreviar tipos complejos
  7. Incluir todas las cabeceras estándar
  8. Modificar tipos de variables y valores (cast)
  9. Entrada y salida rápida

 

CREACIÓN RÁPIDA DE VARIABLES

Podemos crear varias variables del mismo tipo de una tirada:

int a, b, c, d;

E incluso darle un valor inicial (a todas o a algunas):

int a = 3, b = 4, c, d = 2, e, f;

De la misma manera para cualquier otro tipo de variable:

vector<int> lista1(50), lista2(50);

También puedes asignar un valor a varias variables (ya declarades) a la vez:

int a, b, c, d;
a = b = c = d = 0;

Y en el caso de vectores (o arrays) puedes inicializar todos los valores de la siguiente manera:

vector<int> numeros = { 2, 6, 4, 8, 3, 8, 3 };

Esto creará un vector de tamaño 7. Fíjate que si inicializo los valores no necesito indicar qué tamaño tiene el vector, sino que lo deduce de la cantidad de valores que le paso. Pero también puedo usar esto más adelante para asignarle valores (comenzando desde la posición 0) aunque no sean todos los valores del vector (es decir, aunque queden posiciones del vector sin inicializar):

vector<int> fibonacci(100);
fibonacci = { 1, 1, 2, 3, 5, 8, 13, 21 };

 

MODIFICACIONES SOBRE UNA VARIABLE

"variable++;" es lo mismo que "variable = variable + 1;"
"variable--;" es lo mismo que "variable = variable - 1;"

"variable += valor;" es lo mismo que "variable = variable + valor;"
"variable -= valor;" es lo mismo que "variable = variable - valor;"
"variable *= valor;" es lo mismo que "variable = variable * valor;"
"variable /= valor;" es lo mismo que "variable = variable / valor;"
"variable %= valor;" es lo mismo que "variable = variable % valor;"

Verás por internet que alguna gente hace "++variable" en lugar de "variable++". NO ES LO MISMO. "variable++" usa el valor de la variable y después la incrementa, mientras que "++variable" la incrementa y después usa su valor. Por ejemplo:

int a = 0;
cout << a++ << endl; // Mostrara 0, y despues a pasara a ser 1
int b = 0;
cout << ++b << endl; // b pasara a ser 1 y despues mostrara por pantalla 1

 

SIMPLIFICAR ESTRUCTURAS LOGICAS

Cuando usamos if's y while's, si el contenido es únicamente una instrucción podemos ahorrarnos las llaves:

int num;
cin >> num;
while (num-- > 0)
    if (num % 2 != 0)
        cout << num << endl;

Incluso es habitual escribir la condición y su contenido en una única línea:

int num;
cin >> num;
while (num-- > 0) if (num % 2 != 0) cout << num << endl;

Atención, decimos"si el contenido es únicamente una instrucción" (hasta el primer punto-y-coma) no "una línea". ¡No es lo mismo! Este código será un bucle infinito:

int num = 10;
while (num > 0)
    cout << num; num--;     // La instruccion "cout << num;" esta dentro del while, pero la instruccion "num--;" esta fuera del while

De la misma manera podemos usarlo con un for:

int sumatorio = 0;
for (int num=10; num > 0; num--)
    sumatorio += num;
cout << sumatorio;

De hecho, tanto durante la inicialización del for (antes del primer punto-y-coma) com en el incremento del for (después del segundo punto-y-coma) podemos poner, separados por comas, más de una instrucción a ejecutar. El siguiente código es equivalente al anterior... ¡y no requiere que el for haga nada!

int num, sumatorio;
for (num=10, sumatorio=0; num > 0; num--, sumatorio+=num);
cout << sumatorio;

Otra simplificación que se puede hacer es hacer un if "inline", es decir, donde deberías poner un valor, poner un if. La estructura es muy extraña: "condición ? qué_hacer_cuando_true : qué_hacer_cuando_false;". Por ejemplo, en lugar de escribir:

int edad;
cin >> edad;
string tratamiento;
if (edad >= 18) tratamiento = "usted";
else tratamiento = "tu";

Puedes escribir:

int edad;
cin >> edad;
string tratamiento = (edad >= 18) ? "usted" : "tu"; // Fijate que la asignacion ( = ) tiene menos prioridad que la operacion "inline if" ( ?: ) Puedes repasar las precedencias entre operadores en el articulo https://aprende.olimpiada-informatica.org/cpp-precedencia-operadores

 

RESULTADOS COMO BOOLEANOS

¿Sabías que un bool en realidad internamente es un int? ¿Y que 0 es false y 1 es true? Comprobémoslo, el siguiente código funciona idéntico al anterior:

int num;
cin >> num;
while (num-- > 0) if (num % 2) cout << num << endl;

De la misma manera, si queremos obtener los valores pares podemos hacer:

int num;
cin >> num;
while (num-- > 0) if (!(num % 2)) cout << num << endl;

El motivo por el cual hemos de hacer "(!(num % 2))" y no simplemente "(!num % 2)" es que la operación "!" tiene más prioridad que la operación "%", por tanto "(!num % 2)" equivale a "((!num) % 2)".

Otro ejemplo, el último for de la sección “SIMPLIFICAR ESTRUCTURAS LOGICAS“ podría dejarse así:

int num, sumatorio;
for (num=10, sumatorio=0; num; num--, sumatorio+=num);
cout << sumatorio;

Porque cuando llegue a 0 será false.

 

UN EJEMPLO CON TODO (o casi)

El siguiente código calcula cuantos pasos tardamos en completar la "Conjetura de Collatz" (una hipótesis matemática nunca demostrada, desde hace casi 100 años, que dice que si cojemos cualquier número y si es par lo dividimos entre 2 y si es impar lo multiplicamos por 3 y le sumamos 1, y repetimos este proceso indefinidamente con los resultados, antes o después llegamos al valor 1), y también hace el sumatorio de todos los números que van saliendo en la serie:

int main() {
    int num;
    cin >> num;
    int pasos = 0;
    int sumatorio = 0;
    while (num > 1) {
        if (num % 2 == 0) {
            num = num / 2;
        } else {
            num = 3 * num + 1;
        }
        cout << num << " ";
        sumatorio = sumatorio + num;
        pasos = pasos + 1;
    }
    cout << "Pasos: " << pasos << ". Sumatorio: " << sumatorio << endl;
}

Es exactamente equivalente a este código:

int main() {
    int num, pasos, sumatorio;
    for (pasos=sumatorio=0, cin >> num; num > 1; pasos++, sumatorio += num, cout << num << " ") num = (num % 2) ? 3 * num + 1 : num / 2;
    cout << "Pasos: " << pasos << ". Sumatorio: " << sumatorio << endl;
}

 

ABREVIAR TIPOS COMPLEJOS

En ocasiones tenemos que escribir con mucha frecuencia tipos de datos complejos, como "vector<int>" y queremos reducir el tiempo invertido en escribirlo. Podemos darles un "alias", o dicho de otra manera, podemos crear nuestros propios tipos de datos con "typedef". Por ejemplo, si escribimos "typedef vector<int> vi;" podremos declarar vectores de int con el tipo "vi": vi puntuaciones;

Podemos incluso crear nuevo tipos de datos a partir de los tipos que hemos creado, por ejemplo ahora podríamos simplificar "vector<vector<int> >" como "vvi" con la instrucción "typedef vector<vi> vvi;".

Esto se utiliza con mucha frecuencia en la programación, casi siempre con los mismos nombres de "alias". A continuación los más habitaules:

typedef vector<ll> vi​;
typedef vector<vector<int> > vvi; // o typedef vector<vi> vvi;

typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;

typedef set<int> si;
typedef pair<int,​int> pi;
typedef pair<int, int> ii;

typedef vector<pair<int, int> > vpi; // o typedef vector<pi> vpi;
typedef vector<pair<int, int> > vii; // o typedef vector<ii> vii;

typedef long long ll​;
typedef long double ld;

typedef unsigned int ui;
typedef unsigned long long ull;

 

INCLUIR TODAS LAS CABECERAS ESTANDAR

Aunque no es elegante, para programar más rápido se puede incluir todas las (include) estándar de C++ con una única instrucción de manera que no hace falta escribir una cabecera para incluir iostream, vector, algorithm, etc. Esto sólo se puede hacer con compiladores de la GNU GCC. En programación no competitiva no se debe hacer porque hace que el programa sea menos portable, incrementa el tamaño del programa ejecutable y puede aumentar el tiempo de compilación, pero en programación competitiva los programas son pequeños y se premia la velocidad por lo que es útil no tener que pensar qué cabeceras incluir ni tener problemas de compilación por olvidar alguna. La instrucción que incluye todas las cabeceras estándar de C++ es la siguiente:

#include <bits/stdc++.h>

 

MODIFICAR TIPOS DE VARIABLES Y VALORES (CAST)

En ocasiones necesitamos modificar el tipo de una variable. Por ejemplo supongamos que queremos mostrar el código ASCII asociado con la letra 'A'.  Si hacemos "char letra = 'A'; cout << letra;" nos mostrará la letra 'A'. Lo que debemos hacer es indicar que que queremos obtener su valor numérico: "cout << (int) letra;". A esta conversión explícita se le llama cast.

char letra;
int valor_letra;
cin >> letra
valor_letra = (int) letra;
cout << letra;

También en ocasiones tenemos que hacer cálculos con valores literales pero especificando el tipo de este valor. Por ejemplo, 3 * 1000000000 debería ser 30000000000, sin embargo en C++ da -1294967296 porque los valores numéricos por defecto son de tipo int, que abarca valores entre -2147483647 y 2147483647 por lo que no alcanza para mostrar el resultado de la operación. Para poder calcular con valores más grandes se usa el tipo long. Entonces, ¿cómo indicamos que un valor literal es de tipo long en lugar de int? Una manera, como hemos visto, es con un cast:

cout << 3 * (long) 1000000000;

Sin embargo cuando usamos literales podemos reducir el tiempo invertido en el cast añadiendo al literal los siguientes sufijos:

  • "l" o "L" para long
  • "ll" o "LL" para long long
  • "u" o "U" para unsigned
  • "ul" o "UL" para unsigned long
  • "ull" o "ULL" para unsigned long long
  • "." para double (por ejemplo, "2." o "2.0")
  • "f" o "F" para float (por defecto los literales decimales, como 3.14, son de tipo double. El valor literal debe tener coma, por ejemplo "1.0f")

Por lo tanto podríamos simplificar el código anterior como:

cout << 3 * 1000000000L;

 

ENTRADA Y SALIDA RÁPIDA

Mostrar un texto en pantalla o leer del teclado son acciones muy rápidas pero que cuando se ejecutan centenares o miles de veces suman un tiempo de ejecución que puede resultar demasiado grande, tanto como para que nuestro programa sea eliminado por el juez por tardar demasiado en completar su ejecución (un error de tipo "TLE" o "Time Limit Exceeded"). ¿Podemos optimizar la escritura en pantalla y la lectura del teclado? ¡Sí!

Es necesario explicar primero cómo funciona internamente la escritura en pantalla. Cuando un programa solicita escribir en pantalla  el ordenador no va enviando a la pantalla letra a letra a medida que las va recibiendo, sino que espera a tener una cierta cantidad de text para enviarlo todo a la vez, porque enviar un texto a la pantalla requiere más tiempo de ejecución que memorizar un texto. El texto que no ha enviado todavía a pantalla se almacena en una pequeña memoria que se llama "buffer". Cuando el buffer está lleno envía el contenido a la pantalla. Pero en ocasiones envía el contenido a la pantalla antes de llenar el buffer.

Una optimización muy sencilla es no usar endl. El motivo es que endl siempre envía a la pantalla el texto almacenado en el buffer. En su lugar podemos usar simplemente "\n" dentro de un string. Por ejemplo, en lugar de

for (int i = 0; i < 100000; i++) cout << i << endl;

podríamos ejecutar

for (int i = 0; i < 100000; i++) cout << i << "\n";

y veremos que se ejecuta mucho más rápido.

También cin envía todo lo que haya en el buffer a la pantalla antes de leer del teclado (para asegurar que pantalla y teclado van sincronizados), sin embargo cuando el juez ejecuta nuestro programa realmente no necesita leer lo que muestra la pantalla porque ya sabe lo que tiene que escribir en el teclado en cada momento, así que puede esperar a leer la pantalla cuando haya acabado de ejecutarse tot el programa. Para indicar a cin que no envíe nunca el buffer a la pantalla tenemos que escribir la siguiente instrucción al principio del main():

cin.tie(0);

Por último, en C++ las librerías proporcionan varias formas de tratar la entrada y salida estándar: la que usamos normalmente en estos manuales, con cin y cout, y la que viene de C (printf, scanf). Estas dos formas están "sincronizadas" para que podamos usar las dos, pero si sólo usamos una de ellas es mejor "dessincronizarlas" para que vayan más rápido, especialmente en el caso de que usemos cin y cout. Para esto podemos poner este código:

ios_base::sync_with_stdio(false);

 

Printer Friendly, PDF & Email

Comentarios

Artículo muy útil. Sin embargo me gustaría señalar dos errores:
1. En ABREVIAR TIPOS COMPLEJOS, al final del segundo párrafo, debería decir "typedef vector<vi> vvi;", no "typedef vector<vi>;".
2. En la última sección, en el penúltimo párrafo, dice "ban" en lugar de "van.
Muchas gracias

Añadir nuevo comentario

Texto sin formato

  • No se permiten etiquetas HTML.
  • Saltos automáticos de líneas y de párrafos.
  • Las direcciones de correos electrónicos y páginas web se convierten en enlaces automáticamente.