Vectors in Arduino

Question

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:

1. 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.

2. 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?

Answer 1

Standard C++ for Arduino might be an option. It lets you use the STL vector in Arduino.

Answer 2

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());

Answer 3

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

Answer 4

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).

Answer 5

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.

Answer 6

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

Answer 7

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.