(Opcional) C++ — escribir código genérico

Plantillas

Una plantilla (template) consiste en código que se asume presente en cada archivo. ¡No hay que tener miedo de escribir una propia, o de no usar ninguna! Abajo damos un ejemplo de cómo podría verse una plantilla.

Las plantillas en C++ pueden aprovechar funcionalidades más potentes (p. ej. macros) que los otros lenguajes de contest, y se pueden personalizar más para cada competidor.

// CodeSnip{CPP Short Template}
 
int main() { setIO(); }

Este módulo cubre muchas de las funcionalidades usadas en el código de arriba.

¿Qué es el código genérico?

El código genérico es un concepto importante en informática. Por supuesto, como con todos los conceptos, se puede esquivar el código genérico y seguir escribiendo en un estilo hiper-específico. Por eso, hay que empezar cuestionando el propósito.

El código genérico es adaptable, es decir, se puede poner en uso de inmediato de muchas formas sin cambios mayores. Se puede reutilizar, extender e incluso versionar de forma potente para ahorrar tiempo. El tiempo es esencial en informática, y me refiero tanto a la complejidad temporal algorítmica como al tiempo de codificación.

Incluso si se está escribiendo una estructura de datos o un algoritmo muy específico, para realmente entenderlo, una buena pregunta es “¿Puedo generalizar lo que aprendí a una clase más amplia de problemas?” Hay que responderla intentando generalizar. Dicho esto, antes de seguir, dejo la siguiente advertencia:

C++ moderno, un lenguaje pionero en la escena actual de la informática, tiene varias funcionalidades incorporadas para soportar y agilizar el código genérico. Aquí cubriremos las básicas e importantes que definitivamente se van a querer agregar al arsenal.

Clases

Las clases son, de lejos, la utilidad más importante en código extensible. Si se quiere escribir una estructura de datos con varias funciones miembro para procesar datos almacenados, las clases sirven. Por supuesto, las clases pueden tener secciones públicas y privadas. Por ejemplo, considérese una clase Human, que mantiene varias funciones miembro relevantes.

#include <bits/stdc++.h>
using namespace std;
 
class Human {
  private:  // internal properties
	int body_temp;
	int temper;
	string name;
 
  public:  // external reactions
	string get_name() { return name; }
 
	string get_feeling() {
		if (body_temp >= 97 && body_temp <= 99) { return "good"; }
		return "bad";
	}
 
	string get_emotion() {
		if (temper <= 10) {
			return "sad";
		} else if (temper <= 30) {
			return "happy";
		}
		return "angry";
	}
};

¿Pero cómo se usa (y reutiliza) realmente esta estructura de datos de clase que creamos? Creando instancias de esta clase, conocidas concretamente como objetos.

Abajo hay una instancia de ejemplo de la clase Human llamada sal.

Human sal;

Por supuesto, vamos a querer inicializar cualquier objeto de esta clase human con sus atributos fundamentales (body_temperature y temper de arriba), pero el problema es que no podemos acceder a ellos directamente: son privados y quedan sin inicializar.

Para aliviar esto en parte, se pueden inicializar variables en la declaración de la clase misma:

#include <bits/stdc++.h>
using namespace std;
 
class Human {
  private:  // internal properties
	int body_temp = 98;
	int temper = 25;
	string name = "Sal";
 
  public:  // external reactions
	string get_name() { return name; }
 
	string get_feeling() {
		if (body_temp >= 97 && body_temp <= 99) { return "good"; }
		return "bad";
	}
 
	string get_emotion() {
		if (temper <= 10) {
			return "sad";
		} else if (temper <= 30) {
			return "happy";
		}
		return "angry";
	}
};

Esto nos da algo con qué trabajar, y ahora podemos crear sal en main() además de llamar a sus funciones miembro (instanciadas directamente desde la clase base Human).

int main() {
	Human sal;
	cout << sal.get_name() << " feels " << sal.get_feeling() << " and is "
	     << sal.get_emotion() << endl;
}

Para resolverlo por completo, podríamos vernos forzados a hacer públicas estas variables, pero en su lugar podemos ser más astutos y escribir una función constructora para esta clase, esencialmente una función que se llama automáticamente cada vez que se crea una instancia de la clase. Los constructores son útiles cuando se quiere impedir la modificación de variables que se crean pero poder inicializarlas para usarlas, lo que las hace de forma natural la opción más viable para empresas de software propietario.

Podemos crear un constructor para la clase human y exigir la inicialización de las variables body_temperature y temper, lo que nos da algo de control sobre las propiedades intrínsecas de Sal al inicializarlas. El código completo queda:

#include <bits/stdc++.h>
using namespace std;
 
class Human {
  private:  // internal properties
	int body_temp;
	int temper;
	string name;
 
  public:  // external reactions
	Human(string name_, int body_temp_, int temper_) {
		name = name_;
		body_temp = body_temp_;
		temper = temper_;
	}
 
	string get_name() { return name; }
 
	string get_feeling() {
		if (body_temp >= 97 && body_temp <= 99) { return "good"; }
		return "bad";
	}
 
	string get_emotion() {
		if (temper <= 10) {
			return "sad";
		} else if (temper <= 30) {
			return "happy";
		}
		return "angry";
	}
};
 
int main() {
	Human sal("Sal", 98, 25);
	cout << sal.get_name() << " feels " << sal.get_feeling() << " and is "
	     << sal.get_emotion() << endl;
}

Esto es de inmediato muy extensible si queremos crear varias instancias de human, cada una con sus propias propiedades iniciales. De hecho, podemos ser aún más generales creando una función externa condition que indique fácilmente sentimientos y emociones sin tener que reescribirse.

// Prints out the condition of a human to cout
void condition(Human h) {
	cout << h.get_name() << " feels " << h.get_feeling() << " and is "
	     << h.get_emotion() << endl;
}
 
int main() {
	Human sal("Sal", 98, 25);
	Human bob("Bob", 100, 9);
	Human joe("Joe", 85, 35);
	// Print out the conditions of all three people
	condition(sal);
	condition(bob);
	condition(joe);
}

Como nota muy específica pero útil sobre constructores, cuando simplemente queremos inicializar propiedades, podemos adoptar una declaración alternativa que se ejecuta significativamente más rápido que la primera; usar el nombre del argumento como la variable misma también es permisible y es comportamiento definido garantizado:

Human(string name, int body_temp, int temper)
    : name(name), body_temp(body_temp), temper(temper) {}

Structs

Los structs son útiles cuando nos importa menos mantener propiedades privadas y más tener una estructura de datos general reutilizable. Eso significa que todo es público en un struct por defecto, y un struct human, junto con el constructor reformateado de arriba, se vería así:

struct Human {
	int body_temp;
	int temper;
	string name;
 
	Human(string name_, int body_temp_, int temper_) {
		name = name_;
		body_temp = body_temp_;
		temper = temper_;
	}
 
	string get_name() { return name; }
 
	string get_feeling() {
		if (body_temp >= 97 && body_temp <= 99) { return "good"; }
		return "bad";
	}
 
	string get_emotion() {
		if (temper <= 10) {
			return "sad";
		} else if (temper <= 30) {
			return "happy";
		}
		return "angry";
	}
};

De inmediato, nuestro struct es más fácil de manejar dada su naturaleza abierta. Está más integrado con el código de alrededor, y podemos hacer manipulaciones como la siguiente:

int main() {
	// Initialize Sal
	Human sal("Sal", 98, 25);
	condition(sal);       // Get Sal's initial condition
	sal.name = "Sally";   // Sal's friends sometimes call him Sally
	sal.body_temp = 102;  // Sal gets sick
	sal.temper = 40;      // He develops a bad temper due to his sickness
	condition(sal);       // Now we get Sal's new condition
}

Por último, podemos descartar el constructor por completo y optar por una lista de inicialización basada en el orden de declaración de las variables intrínsecas. En el caso de Human, las variables en orden son body_temp, temper y name, así que podemos quitar el constructor y optar por una lista de inicialización como:

human Sal{98, 25, "Sal"};

Ni hace falta decir que todo esto permite una inicialización y manipulación muy limpias de clases y structs, integrales al código genérico.

Templates

El ejemplo de la clase Human, aunque bien definido, estuvo pensado sobre todo para servir como ejemplo de la versatilidad de clases y structs. Ahora pasamos a algo más simple. Imaginemos un punto tridimensional en el espacio como el siguiente struct y dos de esos puntos 3D: p1 y p2.

struct Point3D {
	int x;
	int y;
	int z;
} p1{1, 2, 3}, p2{3, 4, 5};  // We can make some instances right before the ;

¿Pero qué pasa si queremos un punto p3 con coordenadas de tipo double? Entonces nos veríamos forzados a crear un segundo struct de punto pt1:

struct Point3D {
	int x;
	int y;
	int z;
} p1{1, 2, 3}, p2{3, 4, 5};
 
struct Point3DDouble {
	double x;
	double y;
	double z;
} p3{1.1, 2.2, 3.3};

Esto puede no parecer tan malo de inmediato, pero imaginen tener que crear structs así una y otra vez solo para acomodar varios cambios de tipo. Necesitamos algo mejor.

Y he aquí que llega el template al rescate. Podemos usar el formato template<...> para especificar las condiciones concretas de templating y luego simplemente definir el struct de forma normal. En particular, si usamos una clase T, logramos:

template <class T> struct Point3D {
	T x;
	T y;
	T z;
};
 
Point3D<int> p1{1, 2, 3};
Point3D<int> p2{3, 4, 5};
Point3D<double> p3{1.1, 2.2, 3.3};
Point3D<long long> p4{9223372036854775807, 9223372036854775807, 9223372036854775807};

Sería estrecho de miras pensar que los templates se limitan de algún modo a clases y structs. Se pueden usar con funciones y mucho más. Por ejemplo, mírese esta función ckmin:

/**
 * If b is less than a, this changes the value of a to that of b
 * and returns true. If not, the function simply returns false.
 */
template <class T> bool ckmin(T &a, const T &b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

Un caso de uso interesante es el del tamaño de varios contenedores. La función miembro size de un contenedor suele devolver un tipo incompatible con int, pero podemos escribir fácilmente una función con template para arreglarlo, manejando todos los tipos de contenedores de una vez:

template <class T> int sz(const T &container) { return (int)container.size(); }

Se puede llamar escribiendo sz<vector<int>>(v) donde v es un vector<int>, pero desde C++11, las funciones (pero no las clases o structs hasta C++14 y C++17) pueden inferir argumentos de template, lo que significa que simplemente podemos usar sz(v).

¿Y si quisiéramos poner varios argumentos en un template para manejar varias clases? Considérese el siguiente struct comparador secundario de pares como ejemplo:

struct CPS {
	template <class T, class U>
	bool operator()(const pair<T, U> &a, const pair<T, U> &b) {
		return make_pair(a.second, a.first) < make_pair(b.second, b.first);
	}
};

Y en este diseño, como los argumentos de template aplican solo a una función, se pueden inferir fácilmente. Por ejemplo, declarar un conjunto de pair<double, int> en C++11 es tan fácil como set<pair<double, int>, CPS>.

¿Qué constituye los otros tipos de cosas que podemos poner en templates? Como regla general, hasta C++17, los tipos válidos en argumentos de template son solo clases y tipos fundamentales, de los cuales solo las clases se pueden inferir de forma directa en muchos casos por las funciones.

De hecho, incluso podemos tener templates que toman un número variable de argumentos, conocidos como templates variádicos, o templates dentro de templates, conocidos como templates anidados, ambos más allá del alcance de esta exposición básica pero se pueden encontrar aquí  y aquí .

Como dato curioso, así como los templates nos dan tanto control sobre la generalidad del lenguaje, gran parte del estándar de C++ en sí está escrito de forma genérica con templates por debajo.

Alias de tipos con using

typedef ahora está bastante desactualizado (aunque algunos todavía lo usan) porque es más o menos solo una versión molesta de using con semántica frustrante, así que no lo cubriremos aquí.

using es una palabra clave fascinante, usada con frecuencia para simplificar el prefijo de namespaces cuando aplica. Por ejemplo, sentencias como

using namespace std;

realmente nos permiten usar un namespace entero. Por supuesto, como using namespace std suele limitarse a la comunidad de programación competitiva y se mira con recelo en otros contextos, podemos usar using para invocar simplificaciones mejores.

Supongamos que mucho de mi código usa std::cout, que me resulta frustrante de escribir. Puedo escribir

using std::cout;

y luego quedarme con cout. ¿Pero qué pasa si usaba strings y no quería escribir ni std::string ni string? Podría usar using dos veces para arreglarlo:

using std::string;   // Unnecessary if already using namespace std
using str = string;  // Use str as an alias for string

O podría comprimir esto en una sola sentencia:

using str = std::string;  // str is an alias for std::string directly

Podemos hacer aún más alias, incluso alias dentro de alias (véase ll), para entornos donde la velocidad es clave, como la programación competitiva:

using namespace std;
using ll = long long;
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;

Por último, podemos llevar using al siguiente nivel e invocar templates. Por ejemplo, si queremos poder escribir arr<int, 6> en lugar de std::array<int, 6>, escribimos:

template <class T, int SZ> using arr = std::array<T, SZ>;

Como otro ejemplo, si queremos usar ai para significar arreglo de enteros, podemos hacer que construcciones como ai<6> funcionen también:

template <int SZ> using ai = std::array<int, SZ>;

En general, es importante que las declaraciones using tengan garantías fuertes de alcance, es decir, que no funcionen fuera de su alcance definido. Para usar declaraciones en todo el programa, hay que invocarlas en alcance global. Pero, si queremos ser astutos y crear un struct reutilizable y solo especificar argumentos de template internamente, siempre tenemos la opción de:

struct Point {
	using T = int;
	/*
	 * Within this scope, T is an alias for int.
	 * Just change this declaration to change T's meaning within this struct
	 */
	T x;
	T y;
	T z;
};

En caso de que queramos acceder al significado del alias del tipo T fuera de Point, esto también se vuelve muy fácil:

struct Point {
	using T = int;
	T x;
	T y;
	T z;
};
 
int main() {
	// U becomes a copy of T from Point's scope and is now in the scope of main
	using U = Point::T;
}

Macros

Cerramos esta sección con #define, que se usa para definir macros.

#define es esencialmente un buscar-y-reemplazar crudo que ocurre antes del tiempo de compilación (en la etapa del preprocesador). En ese sentido es fácil de usar: #define NAME VALUE idealmente encontraría todas las instancias de NAME en el código y las reemplazaría por VALUE.

Este ejemplo define MOD como 1e9 + 7 por buscar y reemplazar.

#define MOD 1e9 + 7
 
int main() {
	cout << int(MOD) << "\n";      // outputs 1000000007
	cout << int(MOD * 2) << "\n";  // outputs 1000000014
	cout << int(2 * MOD) << "\n";  // outputs 2000000007
}

Pero eso obviamente no es una buena idea. Una alternativa mejor es la siguiente:

const int MOD = 1e9 + 7;
 
int main() { cout << MOD << "\n"; }

Además, using es preferible a #define. Por ejemplo, el siguiente código con #define no va a compilar (pero sí con using).

#define ll long long
// using ll = long long;
 
int main() { cout << ll(1e18); }

La conclusión es evitar #define cuando sea posible. Por supuesto, algunos programadores competitivos usan macros de forma extensa. Abajo se presentan algunos ejemplos.

Pares

using pi = pair<int, int>;
#define mp make_pair
#define f first
#define s second

Puede ser molesto seguir escribiendo first y second, especialmente si se tienen pares anidados. Estas macros lo arreglan.

Vectores

using vi = vector<int>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)

Convertimos un size a un entero con signo para evitar el desbordamiento sin signo, como muestra este ejemplo:

vi x;
cout << x.size() - 1 << "\n";  // otutputs 18446744073709551615 (incorrect)
cout << sz(x) - 1 << "\n";     // outputs -1 (correct)

all(v) hace un poco más corto ordenar parte o todo un vector.

vi v{2, 4, 1, 5, 3};
sort(1 + all(v));  // v is now {2, 1, 3, 4, 5}
// This expands to sort(1 + begin(v), end(v));
sort(all(v));  // {1, 2, 3, 4, 5}

Lógica de preprocesamiento

¿Alguna vez se quiso escribir un programa que compile de formas distintas según algunas condiciones iniciales? Podemos usar directivas del preprocesador como #if y #else, o #ifdef y #ifndef para permitir eso.

Por ejemplo, puede que quiera que mi struct Point sea bidimensional en algunos casos y tridimensional en otros. Puedo hacerlo así:

const bool d2 = false;  // true for 2D, false for 3D
 
template <class T> struct Point {
#if (d2)
	T x;
	T y;
#else
	T x;
	T y;
	T z;
#endif
};

Si no nos oponemos a usar #define, podríamos usar #ifdef y #ifndef para ver si una macro está definida vía #define.

// #define 2D  // Uncomment to make Point 2D
 
template <class T> struct Point {
#ifdef 2D
	T x;
	T y;
#else
	T x;
	T y;
	T z;
#endif
}

Hay muchas aplicaciones astutas de esto, incluido el versionado. De forma importante, si queremos que el código corra distinto para distintas versiones de C++, podemos escribir:

#if (__cplusplus < 201703L)
/**
 * "Clamps" v between the values of lo and hi if it's
 * out of the bounds defined by those two values.
 */
template <class T> constexpr const T &clamp(const T &v, const T &lo, const T &hi) {
	assert(lo <= hi);
	if (v < lo) {
		return lo;
	} else if (hi < v) {
		return hi;
	}
	return v;
}
#endif

Namespaces

Por último, podemos escribir nuestros propios namespaces para separar varias funciones. Dentro de un namespace podemos tener funciones, variables, clases e incluso más namespaces. Luego podemos invocar declaraciones using para usar el namespace entero.

namespace test {
const string greeting = "hi";
namespace test1 {
const int time = 2;
}
using namespace test1;
 
template <class T> struct TestDS {
	T s;
 
	void add(T x) { s += x; }
 
	T get() { return s; }
};
}  // namespace test

Estos son bastante autoexplicativos, pero una funcionalidad más rara de C++11 es el inline namespace. Los namespaces inline no son técnicamente namespaces reales, pero nos permiten trocear el código y evitar tener que usar namespaces solo para ganar acceso.

inline namespace test {
const string greeting = "hi";
}

¿Entonces para qué tener namespaces inline? Podemos usar sus funcionalidades de forma interesante. Por ejemplo, supongamos que teníamos una funcionalidad en una versión vieja v1 de un programa pero ahora la quitamos en la versión nueva v2.

namespace v1 {
const string buggy_feature = "bugs";
const string greeting = "hi";
}  // namespace v1
 
inline namespace v2 {
// removed the buggy_feature from this new version
const string buggy_feature = "what buggy feature?";
const string greeting = "hi";
}  // namespace v2
 
int main() {
	cout << buggy_feature << "\n";      // outputs "what buggy feature?"
	cout << v1::buggy_feature << "\n";  // outputs "bugs"
}

Ahora, no usar un namespace va a usar automáticamente v2. Pero si queremos acceso a v1 de buggy_feature, simplemente podemos escribir v1::buggy_feature. Ahí lo tienen: control de versiones simple y efectivo.