Use std::list in Arduino programming

Question

When trying to compile

#include <list>
std::list<byte> l = { 7, 5, 16, 8 };

in the Arduino IDE (with ATtinyCore for ATtiny4313), I get this message:

error: list: No such file or directory
#include <list>

How to use the standard C++ std::list with Arduino/ATtiny?

Answer 1

I back up Michel Keijzers' suggestion to use a plain array, especially given the tiny amount of RAM in your MCU (only 256 bytes).

Concerning the removal of items from the list, and given that your list will be 16 bytes at most, you don't need to get fancy: just move back the items that are past the one you removed. It will not take long.

Here is a barebones implementation of a list that can hold at most 16 bytes and supports removal:

class List {
public:
    byte length;
    byte data[16];
    void append(byte item) {
        if (length < 16) data[length++] = item;
    }
    void remove(byte index) {
        if (index >= length) return;
        memmove(&data[index], &data[index+1], length - index - 1);
        length--;
    }
};

Note that this only takes 17 bytes of RAM (16 items max plus a length count). There is not vtable, as it has no virtual methods. You can get fancier if you want, make this a template parametrized by the data type and the maximum length, add accessors and such... but if you are just writing a simple sketch (as opposed to a general purpose library), I would recommend keeping it as simple as possible.

Example usage, based on your pseudo-code:

List l { .length = 3, .data = { 12, 82, 29 } };
l.remove(1);

This will indeed result in the list [12, 29].

Answer 2

I don't think that this library is supported by attiny (or even Arduino in general).

However, beyond that, it is not advised to use it, since it is uncertain how much memory and flash overhead it consumes.

Especially the memory is an issue for two reasons:

• Internally, you don't know the exact data structures used for the list. In most efficient way, it will only use 4 bytes (4 times 1 byte for the array), however, since it is a class under the hood a vtable is added, and who knows what more memory (maximum capacity, current capacity of the list etc).
• Also when adding/removing an item from the list, either the entire list is copied, or some tricks with pointers are used. In the first case you get memory gaps, in the second case maybe (and additional memory for the pointers is used).

My advice is to use just a simple array, and define a maximum of the array at compile time (if possible). Not as flexible, but robust, less memory usage and more reliable with a low SRAM device like the Attiny (and Arduino in general).

Removing elements

Based on your first comment:

Removing items is indeed an issue, however, note that if you use the standard library it might copy the entire array (excluding) the new item, so temporarily you will have double the array AND a memory gap.

There are some ways to implement it yourself:

• If you only want to remove items (and never add), add a new array with booleans that denote which are present and which are deleted (e.g. deleted[4] = 1 means that item 4 is deleted. This only cost 1 bit per element.
• Use two arrays with items, and copy them back and forth each time. This will cause not really a memory gap, but you need the storage needed for two arrays. And keep a variable which of the two arrays is the 'current'.