Vectors in Arduino
C++VectorArduinoC++ Problem Overview
I am making a vector of "waypoints" on the Arduino. Each waypoint is an object. The Arduino will obviously need to store multiple waypoints for waypoint navigation. But instead of storing these waypoints in a standard preprogrammed array, the user will need to be able to add, remove waypoints and move them around. Unfortunately the Arduino does not offer a vector type as a built-in library.
I am currently contemplating two options:
-
In Container for objects like C++ 'vector'?, someone posted a general purpose library. It does not contain any index deletion, or movement operations. But it does contain some memory management strategies.
-
I have used malloc, dealloc, calloc in the past. But I do not like that option at all, especially with classes. But is this a better option in my senario?
Which one is a better path to go down?
C++ Solutions
Solution 1 - C++
Standard C++ for Arduino might be an option. It lets you use the STL vector in Arduino.
Solution 2 - C++
You can write this LinkedList template class and simply call it wherever you want :
#ifndef LinkedList_hpp
#define LinkedList_hpp
template <class T>
class ListNode {
public:
T element;
ListNode* next;
ListNode* prev;
ListNode(T element, ListNode* prev, ListNode* next) : element(element)
{
this->next = next;
this->prev = prev;
};
};
template <class T>
class LinkedList {
private:
int length;
ListNode<T>* head;
ListNode<T>* tail;
ListNode<T>* curr;
public:
LinkedList();
LinkedList(const LinkedList<T>&);
~LinkedList();
T& getCurrent();
T& First() const;
T& Last() const;
int getLength();
void Append(T);
void DeleteLast();
void DeleteFirst();
void DeleteCurrent();
bool next();
bool moveToStart();
bool prev();
void Delete(T&);
bool Search(T);
void Clear();
void PutFirstToLast();
void Update(T elem);
LinkedList& operator = (const LinkedList<T>&);
};
template <class T>
LinkedList<T>::LinkedList() {
length = 0;
head = nullptr;
tail = nullptr;
curr = nullptr;
}
template <class T>
LinkedList<T>::LinkedList(const LinkedList<T> & list) {
length = 0;
head = nullptr;
tail = nullptr;
curr = nullptr;
ListNode<T> * temp = list.head;
while(temp != nullptr)
{
Append(temp->element);
temp = temp->next;
}
}
template <class T>
LinkedList<T> & LinkedList<T>::operator=(const LinkedList<T> & list)
{
Clear();
ListNode<T> * temp = list.head;
while(temp != nullptr)
{
Append(temp->element);
temp = temp->next;
}
return *this;
}
template <class T>
LinkedList<T>::~LinkedList() {
Clear();
}
template<class T>
T& LinkedList<T>::getCurrent()
{
return curr->element;
}
template<class T>
T& LinkedList<T>::First() const
{
return head->element;
}
template<class T>
T& LinkedList<T>::Last() const
{
return tail->element;
}
template<class T>
int LinkedList<T>::getLength()
{
return length;
}
template <class T>
void LinkedList<T>::Append(T element)
{
ListNode<T> * node = new ListNode<T>(element, tail, nullptr);
if(length == 0)
curr = tail = head = node;
else {
tail->next = node;
tail = node;
}
length++;
}
template <class T>
void LinkedList<T>::DeleteLast()
{
if(length == 0)
return;
curr = tail;
DeleteCurrent();
}
template <class T>
void LinkedList<T>::DeleteFirst()
{
if(length == 0)
return;
curr = head;
DeleteCurrent();
}
template <class T>
bool LinkedList<T>::next()
{
if(length == 0)
return false;
if(curr->next == nullptr)
return false;
curr = curr->next;
return true;
}
template <class T>
bool LinkedList<T>::moveToStart()
{
curr = head;
return length != 0;
}
template<class T>
bool LinkedList<T>::prev()
{
if(length == 0)
return false;
if(curr->prev != nullptr)
return false;
curr = curr->prev;
return true;
}
template <class T>
void LinkedList<T>::Delete(T & elem)
{
if(Search(elem))
DeleteCurrent();
}
template <class T>
void LinkedList<T>::DeleteCurrent()
{
if(length == 0)
return;
length--;
ListNode<T> * temp = curr;
if(temp->prev != nullptr)
temp->prev->next = temp->next;
if(temp->next != nullptr)
temp->next->prev = temp->prev;
if(length == 0)
head = curr = tail = nullptr;
else if(curr == head)
curr = head = head->next;
else if(curr == tail)
curr = tail = tail->prev;
else
curr = curr->prev;
delete temp;
}
template <class T>
bool LinkedList<T>::Search(T elem)
{
if(length == 0)
return false;
if(moveToStart())
do {
if(curr->element == elem)
return true;
} while (next());
return false;
}
template <class T>
void LinkedList<T>::PutFirstToLast()
{
if(length < 2)
return;
ListNode<T>* temp = head->next;
head->next->prev = nullptr;
head->next = nullptr;
head->prev = tail;
tail->next = head;
tail = head;
head = temp;
}
template <class T>
void LinkedList<T>::Update(T elem)
{
if(Search(elem))
curr->element = elem;
}
template <class T>
void LinkedList<T>::Clear()
{
if(length == 0)
return;
ListNode<T> * temp = head;
while(temp != nullptr)
{
head = head->next;
delete temp;
temp = head;
}
head = curr = tail = nullptr;
length = 0;
}
#endif
Use this class as follow:
LinkedList<int> list;
list.Append(1);
list.Append(2);
list.Append(3);
list.Append(4);
int my_integer;
if(list.moveToStart())
do{
my_integer = list.getCurrent();
}while(list.next());
Solution 3 - C++
Sounds like you would want to implement a simple linked list. A linked list allows you to move objects (waypoints, in your case) around without the overhead associated with C++ vectors.
Here's an implementation on GitHub
Solution 4 - C++
The arduino has limited memory so you need to know how many waypoints you will allow. In which case a simple array to hold memory pointers (addresses) of allocated waypoints will provide the sequence/order you need. Keeping one array slot free as a working area will allow waypoints to be moved around (re-ordered).
Solution 5 - C++
You could also have a fixed array of waypoint structures and include a variable in the structure if the waypoint is in use or not. When adding a waypoint, all you have to loop through the array until you find a structure that is not in use.
Solution 6 - C++
In case you want to create an int vector, the arduino has the following memory specifications. In Arduino Uno (and other ATmega-based boards) an int stores a 16-bit (2 bytes) value. This guarantees a range from -32.768 to 32.767 (a minimum value of -2 ^ 15 and a maximum value of (2 ^ 15) - 1). In Arduino Due and other boards based on SAMD computers (such as MKR1000 and Zero), an int stores a 32-bit value (4 bytes). This guarantees a range of -2,147,483,648 to 2,147,483,647 (a minimum value of -2 ^ 31 and a maximum value of (2 ^ 31) - 1). See more information here
Solution 7 - C++
I wouldn't use std::vector<> nor any other types which do dynamic memory allocation behind-the-scenes at run-time on Arduino, period, on any safety-critical device. It opens up the Arduino to the potential for severe, unsafe crashes due to stack overflow.
Instead, what you need for run-time safety is a fixed-size memory pool which is statically allocated, or dynamically-allocated one single time at program initialization, but never increased at run-time. Your "vector" should be a custom vector class, array, linked list, or library which uses this fixed-size memory pool at run-time.
> the user will need to be able to add, remove waypoints and move them around
The easiest way to do this in my opinion would be to use a statically-allocated array of structs as a memory pool. Each struct in the static array would be a linked list node.
You have a fixed max number of these nodes in the array, to prevent stack overflow. Adding, "deleting", and re-arranging the order of the waypoints is now all possible. Adding and "deleting" would be simply removing the node from the linked list, and re-arranging would be done by changing the nodes that are pointed to, and in what order.
This can now be done in a perfectly-safe manner for a safety-critical, memory-constrained, microcontroller such as the Arduino. Again, a static array of structs is your "memory pool", and you'll use a manually-implemented linked list of nodes, all of which lie in that static array of structs.