A common request we see in Arduino forums and pages is how to get a collection in C++ that changes its size dynamically, allowing to add and remove elements, in a lightweight implementation that works correctly in a microprocessor like Arduino.
Well, fortunately, we are not the first or the last in the programming world with this need to create dynamic collections. In fact, this problem has been with us since the beginning of computing.
As a result, multiple solutions have been found that different languages have implemented in different collections (trees, dynamic array, linked list), each with its own advantages and disadvantages.
In this post, we are going to implement a dynamic array, and in the next one we will address the problem from the point of view of a linked list.
What is a dynamic array?
First of all… impossible!. You will say, an array cannot change its size once created. When instantiating an array, space is reserved in memory to store its elements, and once created, it is impossible to change its size (among other things because it may not have room to grow where it is stored).
And you are absolutely right, an array cannot change its size once created. But nothing prevents us from creating a new array with the desired size (larger or smaller), copying the contents of the original array, and finally deleting it. This is precisely how a dynamic array works.
First, we create an array with a certain capacity. When we store elements, we count the number of elements we have in the array.
As long as the number of elements is less than the capacity of the array, the dynamic array behaves like a normal array.
If we continue to add elements, at some point we will exhaust the capacity of the array.
At that point, we generate a new array, copy the elements, and delete the old array.
The rule that is usually taken is that the new array has twice the capacity of the original array (2*N). However, any other rule is possible (for example 1.2*N, N+10…).
If we want to reduce the array to decrease the amount of memory occupied by it, we generate a new array that has a capacity equal to the number of elements stored, and likewise, we copy and delete the original. If we prefer, we can leave a certain margin, although, in general, it is not usual.
As for efficiency, the dynamic array behaves like a normal array (because it actually is). In particular, index reads are O(1), and index writes are O(1). Element insertions are O(n). Adding an element (at the end of the collection) is O(1), unless there is remaining capacity.
If it is necessary to expand (change the size of the array), the operations slow down because it is necessary to generate the new array and copy all the elements, which is a relatively slow process.
Avoiding the expansion of the array is the reason why it is usual to double the capacity. However, in a microcontroller with little memory like Arduino, it may be excessive, and it may be preferable to sacrifice some speed by decreasing the growth factor.
Implementing a dynamic array in Arduino
Next, we have a very basic implementation of a dynamic array to illustrate its operation.
We only have two methods, AddItem() and RemoveTail(), which, respectively, add or remove the last elements of the dynamic array.
On the other hand, we have the resize() method, which changes the size of the array, and the Trim() method, which reduces the size of the array to the number of elements to reduce the consumed memory.
int* list;
size_t count;
size_t capacity;
// Create a new list
void CreateList(size_t _capacity)
{
list = new int[_capacity];
capacity = _capacity;
count = 0;
}
// Add element to the end of the list
void AddItem(int item)
{
++count;
if (count > capacity)
{
size_t newSize = capacity * 2;
resize(newSize);
}
list[count - 1] = item;
}
// Remove last element from the list
void RemoveTail()
{
--count;
}
// Reduce list capacity to the number of elements
void Trim()
{
resize(count);
}
// Resize list
void resize(size_t newCapacity)
{
int* newList = new int[newCapacity];
memmove(newList, list, count * sizeof(int));
delete[] list;
capacity = newCapacity;
list = newList;
}
// Show the list by Serial for debugging
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("List with 2 elements");
CreateList(2);
Serial.println();
Serial.println("Enter 1 and 2 elements");
AddItem(1);
AddItem(2);
printList();
Serial.println();
Serial.println("Resize and enter 3 and 4 elements");
AddItem(3);
AddItem(4);
printList();
Serial.println();
Serial.println("Resize and enter 5 and 6 elements");
AddItem(5);
AddItem(6);
printList();
Serial.println();
Serial.println("Remove last two");
RemoveTail();
RemoveTail();
printList();
Serial.println();
Serial.println("Adjust size");
Trim();
printList();
}
void loop()
{
}If we run the code, we will see the following output.
Dynamic array in a library
Of course, this couldn’t end here. Here is the link to the List library, a complete implementation of a dynamic list, with methods to add, insert, delete elements, reverse the order, convert to/from an array, etc…
While still being simple enough to work on a processor like Arduino. Enjoy!
Download the code
All the code from this post is available for download on Github. 