C++ / estructura de datos secuenciales

Bienvenidos sean a este post, hoy veremos otra estructura de datos.

Esta es otra de las estructuras de datos mas utilizadas. Tambien se la denomina como array de crecimiento unidireccional dinamico, y mas usualmente denominado como vector. Este miembro de los contenedores STL, del cual hablamos en este post, tiene la particularidad de que almacena elementos del mismo tipo ubicados secuencialmente en memoria. Tomemos como ejemplo un vector de enteros de 4 bytes. Donde podemos considerar a cada elemento como un espacio de 4 bytes y se iran agregando de forma secuencial pero vector tiene la particularidad de que podemos acceder a ellos en tiempo real.

Una cuestion que debemos tener en cuenta es como diferenciar a los contenedores con sus operaciones para poder aplicarlo a los problemas especificos. Para esto usualmente, definimos la complejidad de tiempo de ejecucion de sus operaciones en relacion al numero de elementos en el contenedor. Por esta razon, el vector tiene la particularidad de al momento de acceder a un elemento es definido como una operacion constante de tiempo. Dando como resultado que siempre es la misma cantidad de instrucciones para obtener un elemento del vector sin importar el tamaño del mismo. Por lo tanto, acceder al primer elemento o al numero 100 tardara la misma cantidad de trabajo. A esto se lo denomina como operacion de tiempo constante, tambien conocido como O(1) operation.

Como dijimos, acceder a los elementos de un vector es relativamente rapido pero agregar uno nuevo es algo complicado. Cuando ingresamos un nuevo elemento al final del vector, debemos tener en cuenta el tamaño del vector. Este crecera dinamicamente en tamaño cuando no haya mas espacio ubicable para el vector. Veamos como es la definicion de la funcion push_back de vector:

template <typename T>
class Vector
{
public:
  Vector() : buffer_{nullptr}, capacity_{2}, size_{0}
  {
    buffer_ = new T[capacity_]; // iniciando un array vacio
  }
  ~Vector() { delete [] buffer_; }
  // codigo omitido para facilitarlo...

public:
  void push_back(const T& item)
  {
    if (size_ == capacity_) {
      capacity_ *= 2; // incrementa la capacidad del vector al doble 
      T* temp_buffer = new T[capacity_];
      // copiar elementos del buffer viejo al nuevo
      for (int ix = 0; ix < size_; ++ix) {
        temp_buffer[ix] = buffer_[ix];
      }
      delete [] buffer_; // libera al array viejo
      buffer_ = temp_buffer; // apunta el buffer_ al nuevo array
    }
    buffer_[size_++] = item;
  }
  // codigo omitido para facilitarlo...
};

Observen como se inicia, tiene una capacidad inicial y un tamaño de 0, asi como tambien un buffer inicial establecido por la capacidad. Pero lo que mas nos interesa es la funcion, donde si el tamaño y la capacidad son iguales procedemos a agrandar el tamaño mediante el valor actual multiplicado por dos. Lo siguiente es crear un buffer nuevo con la nueva capacidad. Mediante un bucle pasaremos los elementos del viejo al nuevo, cuando haya finalizado lo eliminamos y al buffer viejo le copiamos el nuevo. Por ejemplo, si tenemos un vector con los siguientes valores almacenados:

14, 42

Si nosotros agregamos un nuevo valor mediante push_back 25, nos quedara de la siguiente manera:

14, 42, 25

Y si ejecutamos a push_back 92, nos quedara de la siguiente manera:

14, 42, 25, 92

Y a medida que agreguemos mas valores mediante push_back se agregaran al final del vector y cambiara el tamaño para poder aceptar los nuevos valores. Tal como lo describimos anteriormente en la funcion y para nosotros es completamente invisible.

Si volvemos al bloque de push_back, cuando incrementarmos el tamaño por dos. Esto hara que el vector se duplique cada vez que se complete. Esto hara que cada vez que agreguemos un nuevo elemento en un slot libre pero de tanto en tanto incrementara al vector para poder recibir los nuevos valores. Pero que sucede cuando ingresamos un elemento por el frente y no por el final? Aqui utilizamos a la funcion push_front y en la teoria desplaza todos los elementos hacia la derecha para dejar libre el primer slot y asi poder agregar el nuestro. Veamos como es su bloque de codigo:

void push_front(const T& item)
{
  if (size_ == capacity_) {
    // codigo omitido por brevedad
  }
  // cambiando todos los elementos para la derecha
  for (int ix = size_ - 1; ix > 0; --ix) {
    buffer_[ix] = buffer[ix - 1];
  }
  // agregando elemento al frente
  buffer_[0] = item;
  size_++;
}

Cuando el tamaño y la capacidad son iguales ahi se procede a hacer el cambio del tamaño del vector como vimos en push_back. Pero la diferencia radica en el bucle donde nos encargaremos de desplazar todos los elementtos a la siguiente posicion desde donde se ubican. Y una vez finalizado, agregaremos el elemento recibido en la primera posicion. Tomemos el caso donde tenemos un vector con estos dos valores:

14, 42

Y si le agregamos el un valor mediante push_front 25, el vector quedara de la siguiente manera:

25, 14, 42

Y si le agregamos otro valor mediantte push_front 92, nos quedaran los valores de la siguiente manera:

92, 25, 14, 42

Ocurre lo comentado en el codigo de push_front, se nos desplazaran todos los valores hacia la derecha y en la primer posicion quedara siempre el ultimo valor ingresado. Esto nos demuestra que vector no puede ser una gran solucion si solo debemos ingresar al frente, pero tenemos otra opcion para esto pero eso sera tema para otro post.

En resumen, hoy hemos visto a estructuras de datos secuenciales, que son, para que nos sirven, como se utilizan, y algunas caracteristicas propias de estos. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.