De GabaWiki

Contingut 1 Conceptos básicos de vectores 2 Iteradores, recorridos y ordenación 3 Vectores de vectores: matrices 4 Cuándo es preferible usar arrays a vectores

[edita] Conceptos básicos de vectores

Un vector (o tabla, o array) es la estructura de datos más básica: un contenedor que almacena n elementos del mismo tipo en n posiciones consecutivas de memoria. Si el vector se llama v, los elementos se denominan v[0], v[1], ..., v[n-1].

Todos los elementos de un vector son del mismo tipo, y éste se debe especificar en el momento de crearlo: un vector<T> es un vector cuyos elementos son de tipo T. El tamaño del vector (es decir, el número de elementos de tipo T que contiene) también se especifica en el momento de su creación; de otro modo, el vector empieza vacío. Veamos un ejemplo.

 
  vector<int> v(3);       //vector de 3 coordenadas enteras
  vector<string> vst(10); //vector de 10 palabras
  vector<bool> w;         //vector de booleanos, vacio
 

A diferencia de los arrays tradicionales del C, los vectores puede cambiar de tamaño durante la ejecución del programa. Más adelante veremos las instrucciones push_back y resize que nos permiten hacerlo.

Al crear un vector<T> se nos permite pasar un segundo parámetro, de tipo T, que indica el valor por defecte con el cual se inicializan los elementos del vector. Si no se especifica ningún valor, como en los ejemplos anteriores, se escoge el valor por defecto del tipo T, que es 0 para int, char, double, etc., false para bool, o "" (cadena vacía) para string.

Para trabajar con un vector<T>, al igual que con todas las estructuras de datos que veremos de la STL, se suelen usar los métodos que la estructura ofrece. Es fácil encontrar en la web páginas que describen qué métodos usar, y qué hacen estos métodos (podéis consultar, por ejemplo, la [http://www.sgi.com/tech/stl/Vector.html documentación oficial del vector<T> de la STL], aunque fácilmente encontraréis muchísimos tutoriales, tanto en español como en inglés, que expliquen lo mismo). Por ejemplo, cuando escribimos v[3], en realidad estamos llamando al método T &vector<T>::operator[](int i) del vector<T> v: un método que recibe un entero i y que devuelve (una referencia a) el valor que v contiene en la i-ésima posición.

Otros métodos que tiene el vector v son v.size() (devuelve el tamaño del vector), v.push_back(e) (añade un elemento e a v, incrementando en 1 su tamaño), v.resize(n) (modifica el tamaño de v para que pase a valer n, borrando o añadiendo elementos al final, según convenga).

Los vectores, al igual que todas los contenedores de la STL, tienen la muy útil propiedad de actuar como variables normales y corrientes: podemos asignarlos, compararlos, copiarlos, pasarlos como parámetro o hacer que una función los devuelva, etc. Por ejemplo, podemos escribir código como éste:

 
  vector<int> v(10, 3);
  vector<int> w = v;   //w es una copia de v
  ++v[0];              //v y w son ahora distintos
  w.resize(0);         //ahora w esta vacio
  v = w;               //ahora v tambien esta vacio
  bool iguales = v==w; //iguales vale true
 

En concreto, si tenemos dos vectores del mismo tipo T, podemos asignar uno al otro con el igual =, y compararlos con el doble igual == o el símbolo de distinto !=. También podemos compararlos con el <, >, >=, <=. Los vectores se comparan según el orden lexicográfico, que es el orden con el que se ordenan las palabras del diccionario: se usa el primer elemento del vector para decidir qué vector va antes; en caso de empate, se mira el segundo elemento, y así sucesivamente.

 
  vector<char> v(2), w;
  v[0] = v[1] = 'a';
  w = v;
  w[1] = 'z';  //v == {'a','a'}, w == {'a','z'}
  cout << "v<w?" << (v<w) << endl;  //true
 

Los programadores de C, acostumbrados a trabajar con arrays, suelen olvidarse de la facilidad con la que los vectores pueden ser pasados como parámetros o ser devueltos por funciones, de una forma cómoda y,

• generalmente*, eficiente. Por ejemplo:

 
vector<int> lee_vector() {
  int n;
  cin >> n;
  vector<int> v(n);
  for(int i=0;i<n;++i) cin >> v[i];
  return v;
}
 
void escribe_vector(const vector<int> &v) {
  for(int i=0;i<v.size()-1;++i) {
    cout << v[i] << " ";
  }
  if (v.size()>0) cout << v[v.size()-1];
  cout << endl;
}
 
void pon_a_cero(vector<int> &v) {
  for(int i=0;i<v.size();++i) v[i]=0;
}
 

Otra de las ventajas de los vectores sobre los arrays clásicos es que resultan muy prácticos para almacenar una lista de elementos el tamaño de la cual pueda ir aumentanto. Para ello, se usa el método push_back del vector.

 
int main() {
  string palabra;
  vector<string> vs;
  while (cin >> palabra) {
    vs.push_back(palabra);
  }
  cout << "Palabras leidas: " << vs.size() << endl;
 

Ésta es una de las pocas excepciones a la regla de no cambiar a menudo el tamaño de un vector: el código anterior es razonablemente eficiente.

[edita] Iteradores, recorridos y ordenación

[edita] Vectores de vectores: matrices

El tipo T del vector<T> puede ser prácticamente cualquier tipo de datos. En particular, podemos tener vectores de vectores, es decir, vectores donde el tipo T es otro vector. Por ejemplo, el tipo vector<vector<double> > representa matrices de reales.

Una matriz (es decir, una tabla bi-dimensional) no es más, pues, que un vector de ``filas, donde una fila es un vector de elementos. A diferencia de los arrays bidimensionales, no existe la obligación de que todas las filas tengan el mismo número de elementos: cada vector fila es independiente de los demás, y la única restricción es que todos ellos deben contener elementos del mismo tipo. Por último, remarcar que los nombres de los tipos involucrados suelen ser tan largos que es una práctica habitual redefinirlos. Veamos un ejemplo.

 
typedef vector<int> VI;
typedef vector<VI> VVI;
 
int main() {
  VVI M(5);          //matriz de 5 filas vacías (5x0)
  for(int i=0;i<M.size();++i) {
    M[i].resize(3);  //ahora obtenemos matriz (5x3)
  }
  VVI M2(5,VI(3));   //otro modo de tener una matriz 5x3
 
  //rellenamos las matrices
  for(int i=0;i<M.size();++i) {
    for(int j=0;j<M[i].size();++j) {
      M[i][j]=M2[i][j]=i+j;
    }
  }
}
 

Como puede verse, para crear una matriz de tamaño n por m debemos escribir VVI M(n,VI(m)), donde VVI es el tipo matriz y VI es el tipo fila. La única cosa es necesario recordar es que una matriz no es más que un vector de vectores, y que no tiene ningún método adicional a los que ya tuvieran los vectores. Crear una matriz de n filas por m columnas no es más, pues, que crear un vector de n filas, donde cada uno de los elementos de este vector es una fila de m columnas. El código VI(m) sirve, precisamente, para crear una fila anónima de m columnas.

{{codeavanzado: El uso de matrices vector<vector<T> > es un poco menos eficiente que el uso de arrays, puesto que cada una de las filas de la matriz se guardan por separado, y se realizan varios accesos de memoria para acceder a una posición (i,j) de la matriz: primero un acceso al tipo matriz (en el stack) para saber dónde guarda sus vectores-fila; un segundo acceso (en el heap) para saber dónde guarda el vector-fila i-ésimo sus datos; y un tercer acceso (también en el heap) para acceder al elemento j-ésimo de la fila. A cambio, las matrices son más versátiles que los arrays.}}

Es muy fácil equivocarse cuando se hacen recorridos sobre matrices, y confundir, por ejemplo, el índice que recorre las filas con el que recorre las columnas. Es conveniente usar algún tipo de convenio para equivocarse lo menos posible. Por ejemplo, usar los nombres de variables i y j para referirse siempre a las filas y las columnas de una matriz. De este modo, sabemos que código como este m[i][j] tiene buen aspecto, mientras que código como este m[j][i] es probablemente erróneo. Como ejemplo, mostramos como multiplicar dos matrices.

 
typedef vector<int> Fila; 
typedef vector<Fila> Matriz;
 
//asumimos que las matrices son rectangulares, y que
//el numero de columnas de la primera es igual al
//numero de filas de la segunda
Matriz producto(const Matriz &ma, const Matriz &mb) {
  int nfa = ma.size(), nca = ma[0].size(), ncb = mb[0].size();
  Matriz m(nfa, Fila(ncb));
  for (int i=0;i<nfa;++i) {     //fila de m
    for (int j=0;j<ncb;++j) {   //columna de m
      for (int k=0;k<nca;++k) { //columna en ma, fila en mb
        m[i][j] += ma[i][k]*mb[k][j];
      }
    }
  }
  return m;
}
 

La misma idea de las matrices bidimensionales puede usarse para tener matrices tridimensionales o de más dimensiones. Sin embargo, la notación excesivamente engorrosa (es necesario usar varios typedefs, y es molesto inicializar una matriz de un tamaño concreto) y los niveles adicionales de indirección (vectores de vectores de vectores etc.) hacen que ésta no sea la mejor opción.

[edita] Cuándo es preferible usar arrays a vectores

Existen unas pocas situaciones en las que es preferible usar arrays tradicionales en vez del tipo vector<T>. Ya que hemos comentado ampliamente las ventajas de estos últimos, sería justo repasar dónde son preferibles los primeros.

• Eficiencia (1).

En general, acceder a un elemento de un vector es igual de eficiente que acceder a un elemento de un array a través de un puntero (por ejemplo, cuando se declara un array con malloc o new): el compilador optimiza la llamada a la función operator[] para que esto sea así. Hay algunos casos, sin embargo, donde el compilador puede hacer optimizaciones adicionales con los arrays (por ejemplo, si están en el heap). Los arrays también serán más veloces si se usan para matrices de varias dimensiones, o si se compila sin optimizaciones.

• Eficiencia (2).

El código que inicializa o cambía el tamaño de un vector se asegura de limpiar o inicializar todos los elementos del mismo. En algunas ocasiones concretas, esta operación puede ser demasiado lenta; usar memoria dinámica o arrays estáticos puede resultar más eficiente.

• Comodidad.

Se puede poblar los elementos de un array en la misma línea dónde se declara, cosa que no es posible en C++ en la actualidad (lo será con el nuevo estándard C++0x que se está preparamdo). El ejemplo más típico es el siguiente:

 
void vecinos(int x, int y) {
  int dx[] = {0, 1, 0, -1};
  int dy[] = {1, 0, -1, 0};
  string nombres[] = {"sur", "este", "norte", "oeste"};
  for (int i=0; i<4; ++i) {
    cout << nombres[i] << ": (" << x+dx[i] << "," << y+dy[i] << ")" << endl; 
  }
}