Implementar un array de tamaño dinámico en Arduino

Una petición habitual que vemos en foros y páginas de Arduino es cómo conseguir una colección en C++ que cambie su tamaño dinámicamente, permitiendo añadir y eliminar elementos, en una implementación suficientemente ligera para funcionar correctamente en un microprocesador como Arduino.

Bueno, afortunadamente no somos los primeros ni los últimos dentro del mundo de la programación con esta necesidad de crear colecciones dinámicas. De hecho, esta problemática lleva con nosotros desde que el mundo es mundo (o bueno, al menos desde los principios de la informática).

Como resultado, se han encontrado múltiples soluciones que los distintos lenguajes han implementado en distintas colecciones (árboles, array de tamaño dinámico, linked list), cada una con sus propias ventajas y desventajas.

En esta entrada vamos a implementar un array de tamaño dinámico, y en la siguiente abordaremos la problemática desde el punto con una linked list.

¿Qué es un array de tamaño dinámico?

En primer lugar… ¡imposible!. Me diréis, un array no puede variar su tamaño una vez creado. Al instanciar un array se reserva espacio en la memoria para almacenar sus elementos, y una vez creado es imposible cambiar su tamaño (entre otras cosas porque puede no tener sitio para crecer donde está guardado)

Y tenéis toda la razón, un array no puede cambiar su tamaño una vez creado. Pero nada nos impide crear un nuevo array con el tamaño deseado (más grande o más pequeño), copiar el contenido del array original, y finalmente eliminarlo. Así es precisamente como trabaja un array de tamaño dinámico.

En primer lugar creamos un array con una determinada capacidad. Cuando guardemos elementos, contabilizamos la cantidad de elementos que tenemos en el array.

Mientras el número de elementos sea inferior a la capacidad del array, el array de tamaño dinámico se comporta igual que un array normal.

Si seguimos añadiendo elementos en algún momento agotaremos la capacidad del array.

En ese momento generamos un nuevo array, copiamos los elementos, y borramos el antiguo array.

La norma que se suele tomar es que el nuevo array tenga el doble de capacidad que el array original (2*N). No obstante, cualquier otra norma es posible (por ejemplo 1.2*N, N+10…).

Si queremos reducir el array para disminuir la cantidad de memoria ocupada por el mismo, generamos un nuevo array que tenga como capacidad el número de elementos almacenados, e igualmente copiamos y borramos el original. Si lo preferimos podemos dejar un cierto margen aunque, en general, no es lo habitual.

En cuanto a la eficiencia, el array de tamaño dinámico se comporta igual que un array normal (porque de hecho lo es). En particular, las lecturas por índice son O(1), y las escrituras por índice son O(1). Las inserciones de elementos es de O(n). Añadir un elemento (al final de la colección) es O(1), salvo, si existe capacidad restante.

Si es necesario expandir (cambiar el tamaño del array) las operaciones se ralentizan, porque es necesario generar el nuevo array, y copiar todos los elementos, lo cual es un proceso relativamente lento.

Implementar un array dinámico en Arduino

A continuación tenemos una implementación muy básica de un array de tamaño dinámico para ilustrar su funcionamiento.

Únicamente disponemos de dos métodos, AddItem() y RemoveTail() que, respectivamente, añaden o eliminan el último elementos del array dinámico.

Por otro lado, tenemos el método resize(), que realiza el cambio de tamaño del array, y el método Trim() que reduce el tamaño del array al número de elementos para reducir la memoria consumida.

int* list;
size_t count;
size_t capacity;

// Crear una nueva lista
void CreateList(size_t _capacity)
{
  list = new int[_capacity];
  capacity = _capacity;
  count = 0;
}

// Añadir elemento al final de la lista
void AddItem(int item)
{
  ++count;
    
  if (count > capacity)
  {
    size_t newSize = capacity * 2;
    resize(newSize);
  } 

  list[count - 1] = item;
}

// Eliminar ultimo elemento de la lista
void RemoveTail()
{
  --count;
}

// Reducir capacidad de la lista al numero de elementos
void Trim()
{
  resize(count);
}

// Reescalar lista
void resize(size_t newCapacity)
{
  int* newList = new int[newCapacity];
  memmove(newList, list, count  * sizeof(int));
  delete[] list;
  capacity = newCapacity;
  list = newList;
}

// Muestra la lista por Serial para debug
void printList()
{
  Serial.print("Capacity:");
  Serial.print(capacity);

  Serial.print("  Count:");
  Serial.print(count);

  Serial.print("  Items:");
  for (size_t index = 0; index < count; index++)
  {
    Serial.print(list[index]);
    Serial.print(' ');
  }
  Serial.println();
}

void setup()
{
  Serial.begin(9600);

  Serial.println("Lista con 2 elementos");
  CreateList(2);

  Serial.println();
  Serial.println("Introducir 1 y 2 elementos");
  AddItem(1);
  AddItem(2);
  printList();

  Serial.println();
  Serial.println("Resize e introducir 3 y 4 elementos");
  AddItem(3);
  AddItem(4);
  printList();

  Serial.println();
  Serial.println("Resize e introducir 5 y 6 elementos");
  AddItem(5);
  AddItem(6);
  printList();

  Serial.println();
  Serial.println("Eliminar dos ultimos");
  RemoveTail();
  RemoveTail();
  printList();

  Serial.println();
  Serial.println("Ajustar tamaño");
  Trim();
  printList();
}

void loop()
{
}

Si ejecutamos el código, veremos la siguiente salida.

Array dinámico en una librería

Por supuesto esto no podía quedar aquí. Aquí tenéis el enlace a la librería List, una implementación completa de una lista dinámica, con añadir, insertar, eliminar elementos, invertir el orden, convertir desde/hacia un array, etc…

A la vez que sigue siendo lo suficientemente sencilla para funcionar en un procesador como Arduino. ¡A disfrutar!

Descarga el código

Todo el código de esta entrada está disponible para su descarga en Github.