======= Vectores ======= ===== Motivación ===== Supongamos que queremos crear programas capaces de realizar las siguientes tareas: - Dada una secuencia de números, determinar si tiene repetidos. - Dada una secuencia de números, decidir si es "capicúa". - 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. ===== El tipo vector ===== 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 '' 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'', y en el segundo un **vector de int**, que se escribe ''vector''. Por ejemplo, es válido en un programa ((En [[cpp-avanzado:c++11|C++11]])) declarar vectores de la forma mostrada: vector v1 = {"goma", "espuma", "goma", "eva"}; vector v2 = {"a", "b", "c"}; vector 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'' y ''vector'' 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\_v(1000)'' crea un vector de tamaño 1000, y ''vector 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 v(1000,5)'' declara una nueva variable v de tipo vector, que tendrá 1000 elementos, y todos ellos serán un 5. Similarmente, ''vector v(5, 2);'' es lo mismo que ''vector 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'', ''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. ==== Soluciones a los problemas planteados anteriormente ==== 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í. - #include #include using namespace std; int main() { int N; cin >> N; vector 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; } - #include #include using namespace std; int main() { int N; cin >> N; vector 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; } - #include #include using namespace std; int main() { int N; cin >> N; vector 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; } ==== Ejercicios ==== - [[http://juez.oia.unsam.edu.ar/#/task/cuenta_numeros/statement|Dada una secuencia de números, determinar cuántas veces aparece cada uno de los números del 1 al 10 en la secuencia]]. - [[http://juez.oia.unsam.edu.ar/#/task/mas_aparece/statement|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]]. - [[http://juez.oia.unsam.edu.ar/#/task/cuenta_pares/statement|Dada una secuencia de números distintos, determinar cuántos pares de números hay cuya suma sea un múltiplo de 10]]. - [[http://juez.oia.unsam.edu.ar/#/task/cuenta_primos/statement|Dada una secuencia de números distintos, determinar cuántos pares de números hay cuya suma sea un número primo]]. - [[http://juez.oia.unsam.edu.ar/#/task/cuenta_triangulos/statement|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). ===== Modificando el tamaño de un vector ===== 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'', ''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)''. ==== Ejercicio ==== - 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. [[http://juez.oia.unsam.edu.ar/#/task/busca_repetidos/statement|El programa debe determinar si la secuencia dada tiene repetidos o no]]. ===== Sobre el uso de ''.size()'' en comparaciones ===== Si compilamos con [[curso-cpp:ambiente:oiax#configuracion_de_compilacion_con_geany|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 ===== Otra forma de recorrer un vector ((En [[cpp-avanzado:c++11|C++11]])) 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 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). ===== Matrices ===== 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'' como los que ya hemos usado: vector fila1 = {1,2,5,8}; Y lo mismo ocurre con las demás filas: cada una es una lista de 4 elementos: vector fila2 = {9,3,1,5}; vector 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>'': 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''). El código para guardar la matriz completa queda entonces: vector fila1 = {1,2,5,8}; vector fila2 = {9,3,1,5}; vector fila3 = {30,5,3,4}; vector> matriz = {fila1, fila2, fila3}; O incluso, podríamos haber escrito todas las listas directamente sin usar variables intermedias: vector> 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> 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'' 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> 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> matriz(N, vector(M)); ''vector(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(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'', ''vector'', pero también ''vector>'', y ''vector>>'' (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. ==== Ejercicios ==== 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. - Dada una matriz de números, [[http://juez.oia.unsam.edu.ar/#/task/suma_filas/statement|imprimir las sumas de sus filas y sus columnas]] (N + M valores en total). - Dada una matriz de números, [[http://juez.oia.unsam.edu.ar/#/task/matriz_traspuesta/statement|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. - Dado un rectángulo de números enteros (podrían ser negativos), ¿[[http://juez.oia.unsam.edu.ar/#/task/max_sum_rect/statement|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. - Dado un rectángulo de **letras** y una lista de palabras, ¿[[http://juez.oia.unsam.edu.ar/#/task/sopa_de_letras/statement|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.