Supongamos que queremos crear programas capaces de realizar las siguientes tareas:

1. Dada una secuencia de números, determinar si tiene repetidos.
2. Dada una secuencia de números, decidir si es “capicúa”.
3. Dada una secuencia de números, imprimirla al revés.

Recomendamos fuertemente al lector que piense primero cómo haría para resolver estas consignas con las herramientas que ya hemos enseñado. Probablemente le resulte muy difícil, y es bueno notar esa dificultad.

A continuación veremos una nueva herramienta muy poderosa que podemos agregar a nuestros programas. Sin ella, resulta imposible (o al menos mucho más difícil) resolver cualquiera de los problemas planteados en esta lección.

Así como int es un tipo de datos que usamos para guardar y manipular números enteros, string es un tipo de datos que usamos para guardar textos, char el que usamos para guardar letras individuales y bool el que usamos para guardar valores true o false, aprenderemos ahora un nuevo tipo que sirve para guardar listas de valores: es el tipo vector.

Para poderlo utilizar, hay que poner #include <vector> al comienzo del programa, exactamente igual que ocurría con el tipo string. Una particularidad del tipo vector es que es lo que se denomina un tipo paramétrico: Esto lo que significa es que no hay un único tipo de vector, sino que depende del tipo de elementos que tenga la lista.

Así, podemos imaginar por ejemplo las lista {“goma”, “espuma”, “goma”, “eva”}, que es una lista de textos, o sea una lista de string, de longitud 4. O podemos imaginar también la lista {2,3,5,7,11}, que es una lista de enteros, o sea una lista de int de longitud 5. En el primer caso, tendremos entonces un vector de string, que se escribe vector<string>, y en el segundo un vector de int, que se escribe vector<int>.

Por ejemplo, es válido en un programa ¹⁾ declarar vectores de la forma mostrada:

vector<string> v1 = {"goma", "espuma", "goma", "eva"};
vector<string> v2 = {"a", "b", "c"};
vector<int> v3 = {2,3,5,7,11};

Como con los otros tipos, es posible utilizar el operador de asignación para copiar toda una lista de una variable a otra: v1 = v2; sería una instrucción válida en el caso anterior, que copia todo el contenido de v2 y lo guarda en v1 (se perdería por lo tanto completamente la lista que había en v1, es decir, {“goma”, “espuma”, “goma”, “eva”}). En cambio, sería inválido hacer v2 = v3;, y tal instrucción generaría un error al compilar: vector<int> y vector<string> son ambos vectors, pero de distinto tipo. Una lista de enteros y una lista de textos no son intercambiables.

Ya hemos mencionado que lo que distingue a un tipo de los demás son las operaciones que pueden realizarse con los valores de ese tipo. A continuación, mostramos las principales operaciones que pueden realizarse con los vectors (que, recordemos, se usan para guardar listas, secuencias o vectores de valores):

• Si v es un vector, v.size() indica su tamaño (cantidad de elementos de la lista). Esto se parece a lo que ya vimos para string.
• Podemos indicar un valor de tipo vector directamente dando su lista de elementos entre llaves: {1,2,3} o {5}, o incluso es posible usar {} para indicar un vector vacío.
• Podemos crear un vector de una cierta longitud directamente al declararlo, indicando la longitud entre paréntesis: vector<int> v(1000) crea un vector de tamaño 1000, y vector<int> v(N) crea un vector de tamaño N, donde N es por ejemplo una variable de tipo int. Si queremos indicar un valor inicial específico para todas las posiciones del vector, utilizamos para eso un segundo número: vector<int> v(1000,5) declara una nueva variable v de tipo vector, que tendrá 1000 elementos, y todos ellos serán un 5. Similarmente, vector<int> v(5, 2); es lo mismo que vector<int> v = {2,2,2,2,2};
• De manera similar a lo que pasaba con los strings, podemos referirnos a un elemento puntual de un vector utilizando corchetes y la posición que nos interesa, comenzando desde cero. Por ejemplo, si v es un vector<int>, v[0] es el primer elemento de la lista, v[9] sería el décimo, y v[v.size()-1] sería el último.
• Los corchetes pueden usarse tanto para leer como para escribir los valores del vector: cout << v[1] mostraría por pantalla el segundo elemento del vector, mientras que v[2] = 10 cambia el tercer elemento del vector, de manera que ahora tenga un 10. Otro uso muy común es leer de la entrada: cin >> v[i] lee de la entrada y lo guarda en la posición i del vector v, donde i generalmente será una variable contadora que indica la posición donde vamos a guardar.

La gran conveniencia que aporta el vector que no teníamos antes es la posibilidad de crear un número arbitrario de variables. Creando un vector de tamaño 1000 tenemos a nuestra disposición 1000 variables (v[0], v[1], v[2], ... , v[998], v[999]), sin tener que escribir 1000 líneas de código diferentes.

Otra ventaja importante de usar vector es a la hora de procesar una secuencia que viene en la entrada del programa: si no usamos vector, no podremos almacenar toda la secuencia a la vez, y entonces en una sola pasada a medida que vamos leyendo cada valor, tendremos que realizar todas las operaciones que nos interesen. Al tener vector, podemos primero leer toda la secuencia y guardarla en el vector, y luego recorrerla todas las veces que nos sea cómodo, realizando los cómputos que queramos.

En estos tres ejemplos, así como en los cinco ejercicios que siguen, siempre que el programa reciba secuencias, supondremos que primero se lee un entero N, con la cantidad de elementos, y luego se leen los elementos de la secuencia en sí.

1. #include <iostream>
   #include <vector>
    
   using namespace std;
    
   int main()
   {
       int N;
       cin >> N;
       vector<int> v(N);
       for (int i = 0; i < N; i++)
           cin >> v[i];
       bool huboRepeticion = false;
       for (int i = 0; i < N; i++)
           for (int j = 0; j < i; j++)
               if (v[j] == v[i])
                   huboRepeticion = true;
    
       if (huboRepeticion)
           cout << "La secuencia tiene repetidos" << endl;
       else
           cout << "Todos los elementos de la secuencia son distintos" << endl;
       return 0;
   }

2. #include <iostream>
   #include <vector>
    
   using namespace std;
    
   int main()
   {
       int N;
       cin >> N;
       vector<int> v(N);
       for (int i = 0; i < N; i++)
           cin >> v[i];
       bool esCapicua = true;
       for (int i = 0; i < N; i++)
           if (v[i] != v[N-1-i])
               esCapicua = false;
    
       if (esCapicua)
           cout << "La secuencia es capicua" << endl;
       else
           cout << "La secuencia NO es capicua" << endl;
       return 0;
   }

3. #include <iostream>
   #include <vector>
    
   using namespace std;
    
   int main()
   {
       int N;
       cin >> N;
       vector<int> v(N);
       for (int i = 0; i < N; i++)
           cin >> v[i];
       for (int i = N-1; i >=0; i--)
       {
           if (i != N-1) // No ponemos el espacio al principio de la linea
               cout << " ";
           cout << v[i];
       }
       cout << endl;
       return 0;
   }

1. Dada una secuencia de números, determinar cuántas veces aparece cada uno de los números del 1 al 10 en la secuencia.
2. Dada una secuencia de números, determinar cuál es el número que más veces aparece en la secuencia, así como cuántas veces aparece.
3. Dada una secuencia de números distintos, determinar cuántos pares de números hay cuya suma sea un múltiplo de 10.
4. Dada una secuencia de números distintos, determinar cuántos pares de números hay cuya suma sea un número primo.
5. Dada una secuencia de números distintos, determinar cuántas ternas (combinaciones de tres) de estos números forman un triángulo (considerando que los números son las longitudes de los lados). Por ejemplo, 2 4 5 son longitudes que forman un triángulo, pero 1 2 5 no (si lo intentamos, primero dibujamos el lado de 5, y luego los lados de 1 y 2 entre los dos son demasiado cortos y “no alcanzan” a cerrar un triángulo junto con el lado de 5).

Cuando sabemos la cantidad de elementos que tiene o va a tener nuestra lista, en general lo mejor es crear directamente un vector de ese tamaño. Sin embargo, a veces queremos cambiar el tamaño de una lista: los motivos más comunes son para poder agregar o sacar elementos a una lista existente.

Para esto tenemos en C++ tres operaciones útiles de vector:

• Si v es un vector, con v.resize(nuevoTam) podemos cambiar su tamaño al nuevo valor, que está indicado por nuevoTam. Si este valor es más chico que el tamaño actual de v, los elementos sobrantes del final se pierden.
• Con v.push_back(e), agregamos el elemento e al final de toda la lista. Por ejemplo si v es un vector<int>, v.push_back(15) le agrega un 15 al final. El tamaño de un vector aumenta en 1 cuando se hace push_back.
• Con v.pop_back() podemos borrar el último elemento de la lista. El tamaño se reduce en 1 al hacer pop_back. Es por lo tanto una forma más práctica de hacer v.resize(v.size()-1).

1. Se debe leer una secuencia de números positivos que viene de la entrada, pero no sabemos su longitud: la secuencia termina cuando viene un cero, que indica que ya no hay que leer más. El programa debe determinar si la secuencia dada tiene repetidos o no.

Si compilamos con todos los warnings activados, podremos observar que el compilador genera una advertencia cuando utilizamos .size() en una comparación con enteros. Por ejemplo en un simple recorrido:

for (int i = 0; i < v.size(); i++)
    cout << v[i] << endl;

El compilador generará un warning de que estamos comparando .size() contra enteros (en este caso, contra i en la parte i < v.size()). Esto es porque .size() en realidad no genera un int, sino que genera un unsigned int, que es siempre no negativo y tiene ciertas diferencias que pueden generar errores fácilmente, por lo que recomendamos usar siempre int y olvidarse de unsigned int.

Si bien en este ejemplo es relativamente inofensivo, ignorar estas advertencias del compilador puede llevar a graves errores en otros casos (por ejemplo, si quisiéramos ignorar el último elemento, y cambiáramos la comparación i < v.size() por i < v.size() - 1, nuestro programa podría colgarse o fallar de manera imprevista). La solución práctica a esto es siempre que usemos .size() en una comparación, rodear a v.size() de int(...), para indicarle al compilador que queremos que v.size() sea un int “normal”. El ejemplo quedaría:

for (int i = 0; i < int(v.size()); i++)
    cout << v[i] << endl;

Esta regla práctica logra dos cosas: elimina la advertencia del compilador, y evita los posibles errores, fallos o problemas que podríamos tener al mezclar int con unsigned int.

Otra forma de recorrer un vector ²⁾ es utilizando lo que se suele denominar foreach. Es una forma más conveniente de escribir la iteración que ya vimos.

En lugar de hacer por ejemplo:

for (int i=0; i<int(v.size()); i++)
    cout << v[i] << endl;

Podríamos equivalente utilizar el siguiente código:

for (int x : v)
    cout << x << endl;

Al escribir for (int x : v), directamente x va tomando todos los valores v[i] del ejemplo anterior, es decir, “la iteración se hace sola”, lo cual es mucho más cómodo cuando simplemente queremos procesar una vez cada elemento en orden. Cuando queremos trabajar con varios elementos a la vez, generalmente será más cómodo usar la “iteración clásica” que vimos antes (pues queremos tener a mano la variable i que indica la posición actual).

Llamamos matriz a un rectángulo de valores (generalmente números). En programación, las matrices son muy muy comunes. Por ejemplo, una matriz podría ser:

 1 2 5 8
 9 3 1 5
30 5 3 4

Generalmente las matrices se usan para representar datos interesantes de la realidad: por ejemplo, los números podrían indicar la altura de un terreno en cada posición, teniendo así una especie de mapa físico del mismo.

Hemos visto que podemos usar vector para representar listas de valores, en particular, listas de números. Una manera posible de trabajar con matrices en computación es considerarlas como listas de filas: En efecto, si miramos la primera fila del ejemplo anterior, no es más que una lista de 4 números: {1,2,5,8}. Por lo tanto, esa primera fila podríamos guardarla en un vector<int> como los que ya hemos usado:

vector<int> fila1 = {1,2,5,8};

Y lo mismo ocurre con las demás filas: cada una es una lista de 4 elementos:

vector<int> fila2 = {9,3,1,5};
vector<int> fila3 = {30,5,3,4};

¿Cómo podríamos representar la matriz entera? Para describirla, basta dar la lista de sus 3 filas... Por lo tanto, la matriz será un vector (lista), y cada uno de los valores de dicha lista será a su vez, otra lista (de números: una fila). Nuestra matriz será entonces un vector<vector<int>>: Una lista (por eso el primer vector), tal que cada elemento de la lista es a su vez una lista (por eso cada elemento es vector<int>).

El código para guardar la matriz completa queda entonces:

vector<int> fila1 = {1,2,5,8};
vector<int> fila2 = {9,3,1,5};
vector<int> fila3 = {30,5,3,4};
vector<vector<int>> matriz = {fila1, fila2, fila3};

O incluso, podríamos haber escrito todas las listas directamente sin usar variables intermedias:

vector<vector<int>> matriz = {{1,2,5,8}, {9,3,1,5}, {30,5,3,4}};

Es común en estos casos usar enters y espacios para mayor claridad:

vector<vector<int>> matriz = { {1,2,5,8}, 
                               {9,3,1,5}, 
                               {30,5,3,4}
                             };

¿Cómo podríamos acceder, por ejemplo, al 8 que está guardado en la matriz? Recordando que nuestra matriz es una lista de filas, primero tenemos que ver en qué fila está: El 8 está en la primera fila, que contando desde 0 es la fila 0. Por lo tanto, matriz[0] (que es el primer elemento de la lista de filas) será la primera fila de la matriz: Un vector<int> que será {1,2,5,8}. De esta lista, el 8 es el elemento 3 (contando desde 0). Por lo tanto, matriz[0][3] == 8.

Podemos cambiar el 8 por un 100 haciendo matriz[0][3] = 100. Similarmente, matriz[1][0] == 9 y matriz[1][1] == 3.

Hemos visto una manera de crear una matriz pequeña manualmente. ¿Cómo podríamos crear una matriz de N filas y M columnas? La siguiente sería una manera basada en las ideas que ya vimos:

vector<vector<int>> matriz(N);
for (int i = 0; i < N; i++)
    matriz[i].resize(M);

Primero creamos matriz, un vector de N elementos, pues la matriz tendrá N filas. Luego recorremos las N filas (por eso hacemos un for, con i variando de 0 hasta N-1), y a cada una de ellas le cambiamos el tamaño a M, con el método resize que ya vimos antes.

Una forma más práctica de lograr esto (aunque más avanzada de entender) es directamente usar la siguiente línea:

vector<vector<int>> matriz(N, vector<int>(M));

vector<int>(M) es una expresión que denota directamente un vector de tamaño M. Eso es lo que queremos que sean cada uno de los N elementos de la matriz (que es una lista de filas). Cuando queríamos crear un vector de N elementos, que todos tengan un cierto valor inicial, indicábamos dos valores entre paréntesis: primero la cantidad, y en segundo lugar el valor. En este caso, queremos que nuestra matriz tenga N filas, y que cada una de ellas sea una lista de tamaño M. Por eso indicamos vector<int>(M) como segundo valor entre paréntesis luego de la coma: es el valor que queremos que tome cada elemento de la lista de filas.

Con esta técnica de usar un vector de vectors para guardar matrices, ya podemos trabajar con rectángulos de valores (sean letras, números, palabras, etc). Además, al aprender vector y este tipo de técnicas, por primera vez tenemos a nuestra disposición infinitos tipos de datos: Antes de conocer vector, solamente conocíamos 4 tipos: int, string, char y bool. Ahora que conocemos vector, no tenemos 5 tipos sino infinitos: Pues tenemos vector<int>, vector<string>, pero también vector<vector<int>>, y vector<vector<vector<int>>> (que sería una lista de matrices de enteros, o lo que es lo mismo, una lista de listas de listas de enteros...) y así podríamos seguir infinitamente. Hemos mostrado el ejemplo de las matrices (o las listas de listas) que son por mucho el caso más común.

En estos ejercicios, suponer que primero se da una línea con un N y un M, que indican la cantidad de filas y columnas respectivamente de la matriz, y luego N líneas con M valores cada una, indicando el contenido de cada fila.

1. Dada una matriz de números, imprimir las sumas de sus filas y sus columnas (N + M valores en total).
2. Dada una matriz de números, imprimir la matriz traspuesta, es decir, aquella que tiene en la fila i, columna j, lo que la original tenía en la fila j, columna i.
3. Dado un rectángulo de números enteros (podrían ser negativos), ¿Cuál es la máxima suma posible de un subrectángulo de mayor suma? Un subrectángulo se forma tomando los elementos de un conjunto de filas y columnas todas contiguas, sin dejar “agujeros”. Notar que el subrectángulo no puede ser vacío.
4. Dado un rectángulo de letras y una lista de palabras, ¿Cuáles de las palabras aparecen en esta sopa de letras? Las palabras pueden aparecer en horizontal (tanto hacia la derecha como hacia la izquierda) o en vertical (tanto hacia arriba como hacia abajo). No se cuentan las posibles apariciones en diagonal.