Arreglos

Ya se conoce una de las estructuras más simples: ¡el arreglo! En C++11, además de los arreglos normales, existe una clase array en la STL. Por ejemplo, un array de 25 ints se puede inicializar con esta línea:

array<int, 25> arr;

La clase array soporta operaciones de la STL (como .empty() o .size()) y también el operador de acceso con corchetes:

arr[5]  // accede al elemento en el índice 5

En C++, los arreglos inicializados de forma local con la sintaxis por defecto (es decir, int arr[25];) o con la clase array quedan inicializados con números aleatorios porque C++ no tiene gestión de memoria incorporada. Para inicializar un arreglo en cero hay varias opciones:

• Usar un bucle for (o bucles for anidados).
• Declarar el arreglo de forma global.
• Declarar el arreglo con una lista de inicialización vacía (es decir, int arr[25]{};) como se menciona aquí .
• Usar una función de la biblioteca como std::fill_n(arr, 25, 0) o std::fill(arr, arr+25, 0).

Arreglos dinámicos

Los arreglos dinámicos (vector en C++) soportan todas las funciones de un arreglo normal y pueden cambiar de tamaño para acomodar más elementos. En un arreglo dinámico también se pueden agregar y borrar elementos al final en $\mathcal{O}(1)$.

Por ejemplo, el siguiente código crea un arreglo dinámico y le agrega los números del $1$ al $10$:

vector<int> v;
for (int i = 1; i <= 10; i++) { v.push_back(i); }

g++ permite crear un arreglo de longitud variable:

int n;
cin >> n;
int v[n];

Sin embargo, los arreglos de longitud variable no forman parte del estándar de C++. Recomendamos usar un vector para esto:

// una forma
vector<int> v(n);
 
// otra forma
vector<int> v;
v.resize(n);

En problemas de concurso basados en arreglos, usaremos la mayor parte del tiempo arreglos estáticos de una, dos y tres dimensiones. Sin embargo, también podemos tener arreglos dinámicos de arreglos dinámicos (p. ej. vector<vector<int>>), arreglos estáticos de arreglos dinámicos (p. ej. array<vector<int>,5>), arreglos dinámicos de arreglos estáticos (p. ej. vector<array<int,5>>), y así.

Iterar

Una forma de recorrer todos los elementos de un arreglo estático o dinámico es usar un bucle for normal.

vector<int> v{1, 7, 4, 5, 2};
for (int i = 0; i < int(size(v)); i++) { cout << v[i] << " "; }
cout << endl;

También se pueden usar iteradores. Un iterador permite recorrer un contenedor apuntando a un objeto dentro de él. Sin embargo, no son lo mismo que los punteros.

Por ejemplo, v.begin() o begin(v) devuelve un iterador que apunta al primer elemento del vector v. Además de la forma estándar de recorrer un vector (tratándolo como un arreglo), también se pueden usar iteradores:

for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
	cout << *it << " ";  // imprime los valores del vector usando el iterador
}

Otra forma de escribirlo. auto (desde C++11) infiere automáticamente el tipo de un objeto:

vector<int> v{1, 7, 4, 5, 2};
for (auto it = begin(v); it != end(v); it = next(it)) {
	cout << *it << " ";  // imprime los valores del vector usando el iterador
}

También se puede usar un bucle for-each.

for (int element : v) {
	cout << element << " ";  // imprime los valores del vector
}

Insertar y borrar

Hay que tener en cuenta que insertar y borrar en el medio de un vector son $\mathcal{O}(n)$.

vector<int> v;
v.push_back(2);          // [2]
v.push_back(3);          // [2, 3]
v.push_back(7);          // [2, 3, 7]
v.push_back(5);          // [2, 3, 7, 5]
v[1] = 4;                // pone el elemento del índice 1 en 4 -> [2, 4, 7, 5]
v.erase(v.begin() + 1);  // saca el elemento del índice 1 -> [2, 7, 5]
// este método de borrado es O(n); conviene evitarlo
v.push_back(8);        // [2, 7, 5, 8]
v.erase(v.end() - 1);  // [2, 7, 5]
// sacamos el elemento del final de la lista; esto es O(1).
v.push_back(4);                     // [2, 7, 5, 4]
v.push_back(4);                     // [2, 7, 5, 4, 4]
v.push_back(9);                     // [2, 7, 5, 4, 4, 9]
cout << v[2];                       // 5
v.erase(v.begin(), v.begin() + 3);  // [4, 4, 9]
// esto borra los primeros tres elementos; O(n)

Strings

Los problemas introductorios a veces piden hacer cosas con strings, como

• Leer strings de la entrada estándar
• Saber usar getline y cin juntos (más raro; ver el recurso de LCPP de arriba)
• Saber ordenar strings, concatenarlos, recorrer los caracteres de un string
• Obtener el $i$-ésimo carácter de un string
• Saber obtener subcadenas con string::substr

Arreglos

Las estructuras de datos por defecto de Collections en Java están diseñadas para guardar cualquier tipo de objeto. Sin embargo, por lo general queremos que nuestras estructuras solo guarden un tipo de dato, como enteros o strings. Lo hacemos poniendo el tipo deseado entre los corchetes <> al declarar la estructura, así:

ArrayList<String> list = new ArrayList<String>();

Esto crea una estructura ArrayList que solo guarda objetos de tipo String.

En los ejemplos de abajo usamos principalmente el tipo Integer, pero se pueden tener Collections de cualquier tipo de objeto, incluyendo Strings, otras Collections u objetos definidos por el usuario.

Los tipos de Collections siempre tienen un método add para agregar un elemento a la colección, y un método remove que saca y devuelve cierto elemento de la colección. También soportan el método size(), que devuelve la cantidad de elementos de la estructura, y el método isEmpty(), que devuelve true si la estructura está vacía y false si no.

Arreglos dinámicos

Los arreglos dinámicos (ArrayList en Java) soportan todas las funciones de un arreglo normal y pueden reasignar almacenamiento de forma repetida para acomodar más elementos a medida que se agregan.

En un arreglo dinámico también se pueden agregar y borrar elementos al final en $\mathcal{O}(1)$. Por ejemplo, el siguiente código crea un arreglo dinámico y le agrega los números del $1$ al $10$:

ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 1; i <= 10; i++) { list.add(i); }

En problemas de concurso basados en arreglos, usaremos la mayor parte del tiempo arreglos estáticos de una, dos y tres dimensiones. Sin embargo, también podemos tener arreglos estáticos de arreglos dinámicos, arreglos dinámicos de arreglos estáticos, y así. Por lo general, la elección entre un arreglo estático y uno dinámico es solo preferencia personal.

Iterar

Para recorrer un arreglo estático o dinámico se puede usar el bucle for normal o el bucle for-each.

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(7);
list.add(4);
list.add(5);
list.add(2);
int[] arr = {1, 7, 4, 5, 2};
 
// bucle for normal
for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); }
 
// bucle for-each
for (int element : arr) { System.out.println(element); }

Agregar y sacar

Se puede agregar y sacar en cualquier índice de un arreglo dinámico en $\mathcal{O}(n)$.

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(2);     // [2]
list.add(3);     // [2, 3]
list.add(7);     // [2, 3, 7]
list.add(5);     // [2, 3, 7, 5]
list.set(1, 4);  // pone el elemento del índice 1 en 4 -> [2, 4, 7, 5]
list.remove(1);  // saca el elemento del índice 1 -> [2, 7, 5]
// este método de borrado es O(n); conviene evitarlo
list.add(8);                   // [2, 7, 5, 8]
list.remove(list.size() - 1);  // [2, 7, 5]
// sacamos el elemento del final de la lista; esto es O(1)
System.out.println(list.get(2));  // 5

Listas

La forma por defecto de guardar datos en Python es una lista, que puede cambiar de tamaño automáticamente para acomodar más elementos. Se pueden agregar y borrar elementos al final en $\mathcal{O}(1)$. Una lista se puede inicializar así:

arr = []

Las listas de Python son genéricas. Eso significa que pueden guardar cualquier tipo de dato, incluyendo objetos. Por ejemplo, el siguiente código crea un arreglo dinámico y le agrega los números del $1$ al $10$:

for i in range(1, 11):  # Observar que range(i, j) incluye i, pero no incluye j
	arr.append(i)

En Python se le puede dar un tamaño inicial a un arreglo dinámico. El código de abajo crea un arreglo dinámico con $30$ ceros.

arr = [0] * 30

Iterar

Se puede usar un bucle for normal para recorrer todos los elementos de una lista.

arr = [1, 7, 4, 5, 2]
 
for i in range(len(arr)):
	print(arr[i], end=" ")
print()
 
for element in arr:
	print(element, end=" ")
print()

También se pueden usar iteradores. Un iterador permite recorrer un contenedor apuntando a un objeto dentro de él. iter(arr) devuelve un iterador que apunta al primer elemento de la lista arr.

arr = [4, 2, 0, 0, 5]
it = iter(arr)
 
print(next(it))  # 4
print(next(it))  # 2
print(next(it))  # 0

Insertar y borrar

arr = []
arr.append(2)  # [2]
arr.append(3)  # [2, 3]
arr.append(7)  # [2, 3, 7]
arr.append(5)  # [2, 3, 7, 5]
arr[1] = 4
# pone el elemento del índice 1 en 4 -> [2, 4, 7, 5]
arr.pop(1)  # saca el elemento del índice 1 -> [2, 7, 5]
# este método de borrado es O(n); conviene evitarlo
arr.append(8)  # [2, 7, 5, 8]
arr.pop()  # [2, 7, 5]
# sacamos el elemento del final de la lista; esto es O(1).
arr.append(4)  # [2, 7, 5, 4]
arr.append(4)  # [2, 7, 5, 4, 4]
arr.append(9)  # [2, 7, 5, 4, 4, 9]
print(arr[2])  # 5
arr = arr[3:]  # [4, 4, 9]
# esto borra los primeros tres elementos; O(n)

Comprensiones de listas

Las comprensiones de listas (list comprehensions) son muy útiles para simplificar un bucle for de Python que modifica/crea una lista en una sola expresión. La sintaxis general es: [ expression for item in list if conditional ]

Hay un ejemplo en el bloque de código de abajo.

# Si un número es impar, agregar el número por 2 al arreglo
old_list = [2, 5, 3, 1, 6]
new_list = []
for i in old_list:
	if i % 2 == 1:
		new_list.append(i * 2)
print(new_list)  # [10, 6, 2]
# Una línea simplificada con comprensión de listas
# Recordar la forma [ expression for item in list if conditional ]
# expression: i * 2
# list: old_list
# conditional: i % 2 == 1 (solo incluir el ítem i si cumple la condición)
new_list = [i * 2 for i in old_list if i % 2 == 1]
print(new_list)  # [10, 6, 2]

Un uso muy aplicable de las comprensiones de listas en programación competitiva es crear una lista de enteros a partir de una entrada separada por espacios:

# Entrada de ejemplo: 5 3 2 6 8 1
# El condicional de la comprensión de listas es opcional, y vale True si no se indica
arr = [int(x) for x in input().split()]
print(arr)  # [5, 3, 2, 6, 8, 1]

Para más información sobre comprensiones de listas, incluyendo cómo anidarlas para crear listas multidimensionales, ver los recursos de abajo.

Tanto vector<vector<int>> como vector<array<int,2>> alcanzarían en este caso, pero un par también puede guardar dos elementos de tipos distintos.

Pares en C++ 

• pair<type1, type2> p: Crea un par p con dos elementos, el primero de type1 y el segundo de type2.
• make_pair(a, b): Devuelve un par con valores a, b.
• {a, b}: Con C++11 o superior, se puede usar esto para crear un par, que es más fácil de escribir que make_pair(a, b).
• pair.first: El primer valor del par.
• pair.second: El segundo valor del par.

Demo

#include <iostream>
#include <vector>
 
using namespace std;
 
/**
 * Salida:
 * Testing 123
 * It is possible to edit pairs after declaring them 123
 * Testing curly braces
 */
int main() {
	pair<string, int> pair1 = make_pair("Testing", 123);
	cout << pair1.first << " " << pair1.second << endl;
 
	pair1.first = "It is possible to edit pairs after declaring them";
	cout << pair1.first << " " << pair1.second << endl;
 
	pair<string, string> pair2{"Testing", "curly braces"};
	cout << pair2.first << " " << pair2.second << endl;
}

Tuplas en C++ 

Podemos guardar más de dos valores con algo como pair<int, pair<int, int>>, pero se vuelve engorroso cuando hacen falta muchos elementos. En ese caso, usar tuplas puede ser más cómodo.

• tuple<type1, type2, ..., typeN> t: Crea una tupla con N elementos, el i-ésimo de typei.

• make_tuple(a, b, c, ..., d): Devuelve una tupla con los valores escritos entre los paréntesis.

• get<i>(t): Devuelve el i-ésimo elemento de la tupla t. También se puede usar para cambiar el elemento de una tupla.

  Esta operación solo funciona para un i constante. En concreto, no está permitido hacer algo como lo siguiente porque i no es constante:

  tuple<int, int, int> t{3, 4, 5};
  int i = 1;
  cout << get<i>(t) << endl;  // no está permitido!

• tie(a, b, c, ..., d) = t: Asigna a, b, c, ..., d a los elementos de la tupla $t$ de forma correspondiente.

Demo

#include <iostream>
#include <tuple>
 
using namespace std;
 
/**
 * Salida:
 * 3 4 5
 * 7 4 5
 * Hello world 100
 */
int main() {
	int a = 3, b = 4, c = 5;
	tuple<int, int, int> t = tie(a, b, c);
	cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
	get<0>(t) = 7;
	cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl;
 
	tuple<string, string, int> tp2 = make_tuple("Hello", "world", 100);
	string s1, s2;
	int x;
	tie(s1, s2, x) = tp2;
	cout << s1 << " " << s2 << " " << x << endl;
}

Aunque en Java no hay pares ni tuplas, podemos hacer los nuestros con clases y tipos genéricos.

import java.io.*;
 
/**
 * Salida:
 * 5 hello
 * 1234 hello
 */
public class PairDemo {
	public static void main(String[] args) throws IOException {
		Pair<Integer, String> p = new Pair<>(5, "hello");
		System.out.println(p.first + " " + p.second);
		p.first = 1234;
		System.out.println(p.first + " " + p.second);
	}
}
 
class Pair<K, V> {
	public K first;
	public V second;
 
	public Pair(K first, V second) {
		this.first = first;
		this.second = second;
	}
}

Aunque Python no tiene una clase específica solo para pares, las tuplas  de 2 elementos dan casi exactamente la misma funcionalidad. El único problema es que no se pueden modificar los elementos porque las tuplas son inmutables.

Por otro lado, Python tiene soporte de comparación incorporado para tuplas. Al comparar, mira los primeros elementos de cada par, después los segundos, y así sucesivamente.

"""
Salida:
(5, 'asdf')
5
True
"""
 
p1 = (5, "asdf")
print(p1)
print(p1[0])  # accede al primer elemento de la tupla
 
p2 = (6, "asdf")
print(p1 < p2)