CP-UPV Bootcamp - Capítulo 4

Capítulo 4: Arrays unidimensionales y bidimensionales

PROBLEMAS DEL CAPÍTULO
Para acceder a los problemas de este capítulo, accede con tu usuario y contraseña a cpupv.contest.codeforces.com. Si no tienes usuario y contraseña, inscríbete aquí.

Introducción a los arrays

En este cuarto capítulo del Bootcamp explicaremos el concepto y utilidad de los arrays, unidimensionales y bidimensionales, y vectores. El 95% de los problemas en programación competitiva involucran arrays, lo que hace este capítulo extremadamente importante.

Contenidos

Arrays unidimensionales

Un array es un conjunto de elementos del mismo tipo almacenados en ubicaciones de memoria contiguas. Podemos imaginarnos una string s = "prueba"; como un array de 6 carácteres, los 6 se guardan en orden en la memoria, uno detrás de otro. Las posiciones de un array se empiezan a contar desde 0, decimos que la PRIMERA posición es la posición 0. Entonces si la primera posición del array de carácteres s se encuentra en la posición 100000 de la RAM, la posición 1 se encontrará en la posición 100001 y así sucesivamente. Los arrays siempre tienen el mismo tamaño desde que se declaran, quiere decir que si un array empieza con 10 elementos, no se puede hacer más grande o más pequeño, siempre tendrá 10 posiciones.

Trabajando con éstos

Para declarar arrays se hace de las siguientes formas:

Es muy importante saber que en C++ cuando se declara un array de elementos primitivos como int, double... todos los elementos son inicialmente números aleatorios (lo que había en la memoria antes del array)

// Sin inicializar (En cada posición habrá un número random)
int miArray[10];
// miArray[0] = ???
// miArray[5] = ???

int n; cin >> n;
int arr[n]; // Tamaño n, dado por el usuario, no mayor a 10^6

// Inicializar todos los elementos a 0
memset(miArray, 0, sizeof(miArray));

// Igual que memset() pero menos eficiente
for (int i = 0; i < 10; ++i) {
    miArray[i] = 0;
}

// Inicializar con valores predeterminados (poco común)
int miArray[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

Para el ejemplo de encima, hemos creado un array de longitud 10, con índices del 0 al 9 (se empieza a contar por el 0); por tanto tenemos diez posiciones en memoria reservadas para guardar ints.

¿Cómo accedemos para modificar y/u obtener los valores de los elementos de nuestro array? Al final un array de 10 posiciones son como 10 variables, pues nos referiremos a una de las variables por el nombre del array y su posición:

// Asignar 10 a la TERCERA posición del array
miArray[2] = 10;

// Asignar el valor de la variable `a` + 4 a la PRIMERA posición del array
int a = 22;
miArray[0] = a + 4;

// Copiar la SEXTA posición del array a la variable a
a = miArray[5];

// Cualquier operación es posible con los elementos de un array
miArray[0] += miArray[1] - 2;
miArray[0]--;
if (miArray[0] > 5) { ... }

¿Qué ocurre si consultamos elementos fuera del array? Es decir, si para el ejemplo de un array de longitud diez, ¿consultamos el elemento en la ONCEAVA posición o más? El compilador de C++ nos avisará en algunos casos que estamos intentando acceder a una posición en el array que no existe. Si el tamaño del array es desconocido durante la compilación entonces podría ocurrir un 'Segmentation fault' por acceder a una posición no permitida en la memoria y el programa crasheará, o podría devolver un valor aleatorio.

Ejemplo

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[10]; // creo un array de 10 elementos
    memset(arr, 0, sizeof(arr)); // Inicializo todo a '0'

    cout << arr[0] << endl; // 0

    arr[1]=42;
    cout << arr[1] << endl; // 42

    cout << arr[1000000] << endl; // Segmentation fault o número random

    return 0;
}

Vectores

Un vector es una secuencia dinámica que puede cambiar de tamaño automáticamente cuando se añaden o eliminan elementos. Los vectores son parte de la biblioteca estándar de C++ (<vector>) y proporcionan muchas funcionalidades útiles que no están disponibles en los arrays tradicionales.

Trabajando con éstos

Para crear un vector se hace de la siguiente manera:

// Vector que guarda `int` con tamaño inicial 0
vector<int> a;
// Valores random!

// Vector que guarda `int` con tamaño inicial n
int n = 10;
vector<int> b(n);
// Valores random!

// Vector que guarda `int` con tamaño inicial 10 y todos los elementos inicializados a 0
vector<int> miVector(10, 0);

// Vector con 10 elementos `int` predeterminados
vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

¿Cómo accedemos para modificar y/u obtener los valores de los elementos de nuestro vector? De la misma forma que con los arrays, siempre asegurándonos que esa posición verdaderamente existe y no se sale fuera de límites.

// Vector con 10 elementos `int` predeterminados
vector<int> miVector = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// Asignar 10 a la TERCERA posición del vector
miVector[2] = 10;

// Asignar el valor de la variable `a` + 4 a la PRIMERA posición del vector
int a = 22;
miVector[0] = a + 4;

// Copiar la SEXTA posición del vector a la variable a
a = miVector[5];

// Pero además podemos eliminar el último elemento del vector
miVector.pop_back();
// Ahora el tamaño del vector 

// Añadir el valor `5` al final del vector
miVector.push_back(5);

También en los vectores cuando los creamos los elementos no se inicializan automáticamente a un valor por defecto a menos que se especifique. Podemos inicializar un vector con un tamaño y un valor por defecto usando la sintaxis vector<int> miVector(10, 0), lo que creará un vector de tamaño 10 con todos sus elementos inicializados a cero. También podemos usar memset().

¿Qué ocurre si consultamos elementos fuera del vector? Es decir, si para el ejemplo de un vector de longitud diez, ¿consultamos el elemento en posición 10 o más? C++ no realiza comprobación de límites en los vectores cuando se accede mediante el operador [], lo que puede provocar resultados incoherentes y sin sentido, al estar accediendo a posiciones de memoria no válidas. Sin embargo, podemos usar el método miVector.at() que sí realiza comprobación de límites y lanzará una excepción si intentamos acceder a una posición fuera del rango válido. Por ejemplo, miVector.at(10) lanzará una excepción si el vector tiene menos de 11 elementos.

Ejemplo

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> vec; // creo un vector de enteros

    // Añadir elementos al final del vector
    vec.push_back(10);
    vec.push_back(20);
    cout << vec[0] << endl; // 10
    cout << vec[1] << endl; // 20

    // Acceder y modificar elementos
    vec[0] = 42;
    cout << vec[0] << endl; // 42

    // Obtener el tamaño del vector
    cout << "Tamaño del vector: " << vec.size() << endl; // 2

    // Eliminar el último elemento
    vec.pop_back();
    cout << "Tamaño del vector después de pop_back: " << vec.size() << endl; // 1

    // Acceder a un elemento fuera del rango usando at() (lanzará una excepción)
    try {
        cout << vec.at(10) << endl;
    } catch (out_of_range e) {
        cout << "Excepción: " << e.what() << endl; // Excepción: vector::_M_range_check: __n (which is 10) >= this->size() (which is 1)
    }

    // Comprobar si el vector está vacío
    cout << "¿El vector está vacío? " << (vec.empty() ? "Sí" : "No") << endl; // No

    // Limpiar todos los elementos del vector
    vec.clear();
    cout << "Tamaño del vector después de clear: " << vec.size() << endl; // 0

    return 0;
}

Arrays bidimensionales

Un array bidimensional es una estructura de datos que permite almacenar elementos en forma de matriz, es decir, en filas y columnas. Cada elemento del array bidimensional se puede acceder mediante dos índices: uno para la fila y otro para la columna. Se pueden interpretar como un "array de arrays". (De hecho se pueden hacer arrays de múltiples dimensiones)

Trabajando con éstos

Para crear un array bidimensional se hace así

// Array 2D de 3 filas y 4 columnas
int miArray[3][4];
// Valores random!

¿Cómo accedemos para modificar y/u obtener los valores de los elementos de nuestro array bidimensional?

// Guardará en la variable `a`, el elemento en la fila cero y columna uno del array que hemos creado.
int a = miArray[0][1];

// Modificará el valor del elemento en la fila cero  y columna uno del array que hemos creado, y fijará su valor a 1.
miArray[0][1] = 1;

// Guardará en el array `arr2` la fila 0 del array 2D.
int arr2[] = miArray[0];

Nota: las propiedades de acceso y problemas sobre los arrays y sus tipos se heredan cuando trabajamos con arrays bidimensionales (No podemos acceder a valores de posiciones que no existen).

Ejemplo

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[3][4]; // creo un array de 3 filas y 4 columnas

    // Inicializar el array con valores específicos
    int arr2[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

    //              Columnas
    //             0   1   2   3
    //              
    //         0:  1   2   3   4
    //   Filas 1:  5   6   7   8
    //         2:  9   10  11  12

    // Acceder y modificar elementos
    arr[0][0] = 42;
    cout << arr[0][0] << endl; // 42

    // Acceder a un elemento inicializado
    cout << arr2[1][2] << endl; // 7

    // Acceder a un elemento fuera del rango (puede dar resultados incoherentes)
    cout << arr[3][4] << endl; // Resultado no definido

    return 0;
}

Diferencias entre ellos

A simple vista, comprendiendo las propiedades y características de estas estructuras de datos antes mencionadas, podemos destacar ciertas ventajas y desventajas:

Nota: es importante saber usar todos los tipos de estructura e implementar soluciones según las necesidades; es posible que para ciertos problemas un vector o un array se moldee mejor a éste.

Iterando sobre ellos

En el capítulo anterior se repasó en profundidad la forma de realizar bucles e instrucciones repetidas dada una condición, para evitar escribir muchas líneas de código. Aplicándolo al contenido de hoy, esto nos será muy útil y además aprenderemos un poquito más.

for "tradicional"

No debería ser una sorpresa ver una sentencia del tipo:

for(int i = 0; i < n; ++i) {
    metodoGuay();
}

Teniendo en cuenta las propiedades de consulta de arrays, vectores..., es evidente que en el bloque for poseemos un contador i, con el cual jugaremos un poco para hacer correctamente las consultas. Pensemos que queremos, por ejemplo, recorrer TODO un array, entonces deberíamos usar índices de la forma 0, 1, 2, 3, ... , size - 3, size - 2, size - 1. Nos detenemos en size - 1porque en programación contamos desde el cero, siempre hay que tenerlo en cuenta.

Luego, ya con la secuencia del contador planeada, introducimos la condición en el for, si comienza desde 0 y va hasta size, entonces incrementaré el contador por cada caso en el que se verifique el contador sea más pequeño que el tamaño del array, eso es:

int arr[5] = {1,2,3,4,5};
int size = sizeof(arr)/sizeof(int);

/*
OJO: sizeof() devuelve tamaño en BYTES, no numero de elementos. Para encontrar el número de elementos hay que dividir el tamaño en bytes del array entre el tamaño de uno de sus elementos.

En este caso, sizeof(arr) = 20B y sizeof(int) = 4B
*/

for(int i = 0; i < size; ++i) {
    int temp = arr[i];

    cout << temp << endl;
}

En este caso, dado un array de cinco elementos, obteniendo su tamaño mediante el metodo `sizeof()` y dividiendo entre el tamaño de cada elemento, iteraremos sobre éste y sacaremos una línea por cada elemento en consola. La salida sería:

1
2
3
4
5

De la misma forma, en vez de obtener los elementos, se pueden modificar por cada iteración, añadir condiciones para derivar la solución, etc... Cuestiones y problemas que tienes planteadas en los ejercicios del bootcamp

foreach

Cuando buscamos un recorrido sin preocuparnos mucho por el contador característico del for "tradicional", podemos optar por los foreach. Los foreach son una implementación más cómoda de un recorrido, con una sentencia clara y limpia. Cabe aclarar que los foreach no son universales, es decir, un foreach es funcional porque alguien lo ha definido antes, es decir, por cada tipo de variable se define un iterador que te permite iterar sobre ese tipo, si fuera una estructura de datos; por ende no siempre se podrá usar un foreach, pero para los casos de programación competitiva no debería haber muchas pegas.

Por tanto, un recorrido de un array, vector, etc... se puede simplificar en este bloque:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5] = {1,2,3,4,5};

    for(int n : arr) {
        cout << n << endl;
    }
}

Como se puede apreciar, no necesitamos un contador ni obtener un tamaño para determinar el número de iteraciones; esto puede ser un problema o no, pues de esta forma perdemos el "control" de las operaciones. Por ejemplo, para detener la ejecución de un for "tradicional", podemos utilizar un flag booleano que se haga false, operar con un AND, y de esa forma hacer que se detenga el for.

Si carecemos de este tipo de cabeceras, debemos utilizar otro tipo de sentencias que nos permitan controlar las operaciones:

Estas sentencias se pueden usar en todos los bloques que impliquen iteraciones es decir, while, for, foreach, etc...

Estrategias, tipos de problema y consejos

Ya conociendo la forma de iterar sobre las estructuras, habiendo asimilado la lógica y criterios detrás del concepto de iterar, podemos agrupar los problemas de vectores, arrays y arrays 2D en tres tipos:

Adicionalmente, añadimos un pequeño sumario aquí para aplicar durante este capítulo, métodos que puedan llegar a serles útiles:

Conclusión

En este capítulo hemos cubierto la mayoría de conceptos y términos necesarios para trabajar con estructuras de datos tipo array, array 2D y vectores. Además hemos visto y comprendido los métodos más útiles para amenizar la implementación de soluciones con estas estructuras de datos, además de formalizar el criterio a seguir para clasificar problemas y saber por dónde atacarlos con más velocidad, que al fin y al cabo, es lo que más importa: ser veloz y tener la cabeza ordenada.