Lab Vectors - Vectores

En C++, los arreglos proveen una forma rudimentaria de trabajar con conjuntos de elementos del mismo tipo. Sin embargo, tienen limitaciones tales como las siguientes:

El Standard Template Library (STL) es una librería del lenguaje de programación C++ que provee, entre muchas otras cosas, una clase llamada vector que combina lo mejor de lo de los arreglos estáticos y dinámicos mientras elimina sus limitaciones. Algunas cosas chéveres que podemos hacer a un vector:

Para poder utilizar objetos de tipo vector en tu programa debes asegurarte que incluyes su header file así:

#include <vector>

El vector del STL es lo que se conoce como un contenedor, i.e. un ente que sirve para almacenar una colección de otros objetos del mismo tipo. Los vectores (y muchas de las estructuras de datos del STL) están implementados como clases plantilla. En esencia, una clase plantilla es una clase que durante la declaración de sus objetos permite que se especifique qué tipo de datos desean almacenar esos objetos. Por ejemplo, a continuación la declaración de un vector de enteros.

vector <int> A;

El int que aparece entre < > especifica que A será un vector que almacenará una colección de datos de tipo entero. Podemos crear vectores de objetos de cualquier tipo, por ejemplo la siguiente es la declaración de un vector de objetos string.

vector <string> S;

Como toda clase útil, los vectores tienen métodos que podemos invocar sobre sus objetos para realizar operaciones sobre los datos que contienen. Uno de los métodos más comúnmente usados sobre los vectores es push_back(), que añade un elemento al final del vector. Por ejemplo, el vector V del siguiente código contendrá los elementos 15 y 33 al final del código:

vector <int> V;  // declara un vector de enteros, inicialmente vacío
V.push_back(15);
V.push_back(33);

Los elementos de los vectores se pueden acceder usando el operador de suscrito ([ ]) como los arreglos. Por ejemplo, luego del código anterior, el elemento V[0] contiene el valor 15 mientras que V[1] contiene 33.

Se puede cambiar el tamaño a un vector usando el método resize(unsigned int). Por ejemplo, en el siguiente código creamos un vector (vacío), luego le agrandamos a tamaño 4 y asignamos 55 a su elemento con índice 2. El resto de los elementos tienen valor desconocido.

vector <int> W;  // declara un vector de enteros, inicialmente vacío
W.resize(4);
W[2] = 55;

El operador de asignación (=) está sobrecargado para realizar una copia profunda de un vector a otro. En otras palabras, cuando haces una operación como W = V, el vector W le serán copiados los elementos del vector V (en el mismo orden). Esto contrasta con la operación A = B donde A y B son arreglos, en donde meramente se logra que A y B apunten al comienzo del arreglo B.

vector <int> W, V;
V.push_back(18);
W = V;  // luego de esta instrucción W contiene su propia copia la colección {18}
W.push_back(42);  // ahora W contiene {18, 42}

El método size() devuelve el tamaño de un vector, i.e. la cantidad de elementos que contiene. Por ejemplo,

vector <int> W;
W.push_back(44); 
W.push_back(55);
W.push_back(18);
cout << W. size() << endl;  // imprimiría el número 3

Cuando quieras asignar una serie de valores a un vector puedes hacerlo usando el formato:

V.assign( {10, 20, 33} );

Pasando como parámetro El siguiente código muestra un ejemplo de una función (sum) recibiendo un parámetro objeto vector.

// Dado v, un vector de enteros, devolver la sumatoria de sus elementos.
int sum( const vector<int> &v ) {
   int res = 0;

   for (unsigned int i = 0; i < v.size(); i++) {
       res = res + v[i];
   }

   return res;
}

int main() {
   std::vector<int> v ;

   v.assign( {1, 8, 10});

   cout << sum( v ) << '\n';  //imprimir la sumatoria
}

Nota lo siguiente:

La función recibe el parámetro vector por referencia y constante. Es recomendable pasar objetos (no solo vectores) por referencia pues pasarlos por valor implicaría crear una copia del objeto exclusivamente para ser utilizada por la función.

No hubo necesidad de pasar el tamaño del vector a la función, ya que podemos invocar v.size() y averigualo dentro de la función.

Ejercicio 1

El censo de palmas del balneario de Luquillo contó 100 palmas antes del huracán Irma y le asignó un número único entre 1 y 100 a cada una. Acabamos de recibir una lista con las palmas que cayeron durante el huracán. Implementa un programa que dada la lista de las palmas caídas (no necesariamente en orden ascendente) dé como resultado la lista de las que quedan en pie en orden ascendente. Trabaja este problema en http://vpl.ccom.uprrp.edu , ejercicio Vectors: Palmas sobrevivientes.

Especificaciones de input

El input consiste de una secuencia de números enteros positivos entre 1 y 100. Al final de la lista hay un -1.

Especificaciones de output

Debe ser una secuencia de números enteros en orden ascendente. Al final de la lista también hay un -1 y un new line ('\n').

Ejemplo de input:

10 9 15 26 90 91 92 93 94 95 96 98 99 100 -1

Ejemplo de output:

1 2 3 4 5 6 7 8 11 12 13 14 16 17 18 19 20 21 22 23 24 25 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 97 -1

Para este ejercicio debes realizar y documentar al menos los primeros 5 pasos de la metodología que discutimos en clase (los 7 pasos para resolver problemas de programación). No implementes sin antes hacer un diseño!!!!

Vectores de vectores

Los arreglos de 2 dimensiones pueden ser implementados usando vectores de vectores. Por ejemplo supón que deseas almacenar la siguiente tabla de datos en memoria. 

42 25 77 90 56
80 99 15 66 23
17 83 75 13 12

Una matriz de datos como esa puede ser representada como por un vector de tamaño 3 (el número de filas) que en cada elemento contiene un vector de 5 elementos (el número de columnas de la tabla). La Figura 1 ilustra cómo queda organizado.

https://i.imgur.com/XMnH8Q5.png

Figura 1. Ilustración de un vector de 3 vectores de 5 enteros.

A continuación cómo declarar e inicializar tal vector de vectores:

vector< vector<int> > V {
  {42, 25, 77, 90, 56},
  {80, 99, 15, 66, 23},
  {17, 83, 75, 13, 12} } ;

for (unsigned int i = 0; i < V.size(); i++) {
    for (unsigned int j = 0; j < V[i].size(); j++) {
        cout << V[i][j] << " ";
    }
    cout << '\n';
}

Observa:

Ejercicio 2

En el ejercicio Vectors: 2D Sum rows/cols en Vocareum se te provee el código que mostramos anteriormente. Debes implementar las siguientes dos funciones: void printRowSum(const vector <vector <int> > &V) que imprime la sumatoria de cada una de las filas del vector de vectores. void printColSum(const vector <vector <int> > &V) que imprime la sumatoria de cada una de las columnas del vector de vectores.

Ejercicio 3

During this course you will learn about graphs, a data structure that is commonly used when representing relations between entities. A graph consists of nodes (which represents entities such as people) and edges, i.e. connections between the nodes which represent a relation between them. For example, in a graph that represents friendships in a community each person can be represented by a node. If Lola and Nina are friends then the graph contains an edge between them. Here is a graph in which Nina and Lola, Lola and Daisy, Daisy and Nina, and Olga and Daisy are friends (poor Irma has no friends).

https://i.imgur.com/wp3Ccfa.png

One way to represent graphs is by using a 2D array of booleans. To represent a graph with N nodes, we use an N x N array where the entry (i,j) is true only if there exists an edge between i and j. For example, here is a representation of the friendship graph using a 2D array. Instead of using names, we have assigned a number to each person (Lola is 0, Nina 1, etc.)

   0  1  2  3  4  
0  F  T  T  F  F             
1  T  F  T  F  F              
2  T  T  F  T  F           
3  F  F  T  F  F          
4  F  F  F  F  F

In the exercise Vectors: 2D Friends in Vocareum implement a program where the user inputs N the number of nodes in the graph then is asked for each of the entries of the edge table (25 in the example). The program stores the values a entries in a vector of vector of booleans.

Example input:

3
0 1 1
1 0 0
1 0 0

Hints:

Implement the following functions: