Dynamic array without knowing the number of elements

Projects Programming
1

Hi!

I am creating a library, and I have a problem that seems quite simple, but I can't find a solution.
Basically, I would like to do this:

// from the user sketch

myLibrary.addSmiley(":)");
myLibrary.addSmiley(":D");
myLibrary.addSmiley(":P");

// from the library

for (var i = 0; i < smileys.length(); i++) {
  Serial.println(smileys[i]);
}

You get it, I want the addSmiley function to push the given smiley to an array, and then iterates through this array. It would be quite easy if I knew how many elements would be in the array, and if these elements were ints, because they have a fixed size. But I don't know how to do without knowing the number of elements that will get into the array. Plus, a smiley might be ":)" or be ":-)", therefore elements are not guaranteed to be the same size.

Do you have any idea of how I can achieve this? Using malloc probably, but the fact is I can't find anywhere an implementation of what I am trying to do.

Thanks!

2

marvinroger:
Do you have any idea of how I can achieve this? Using malloc probably, but the fact is I can't find anywhere an implementation of what I am trying to do.

Thanks!

I'm guessing that each element of the array won't exceed say three or even four bytes. So construct the array to accommodate the largest:

char myArray[10][[3]={
  {NULL, ':', ')'},
  {':', '-', ')'},
  ...
};
5

Another option is a linked list. Adding a new node to the list is relatively simple. It involves calling malloc() with the size of the node, and then storing the pointer to the new node in the last node created.

The advantage is that you use the minimum amount of storage for the known data. The disadvantage comes from needing to understand pointers and how to create and add to a linked list, plus the overhead of the pointer to the next node, for each node.

6

Thanks for your answers.

BulldogLowell:
I'm guessing that each element of the array won't exceed say three or even four bytes. So construct the array to accommodate the largest:

char myArray[10][[3]={

{NULL, ':', ')'},
  {':', '-', ')'},
  ...
};

Delta_G:
I would construct them as strings to make printing a little more friendly and put the null on the end.

char myArray[10][5] = {

{ ':' , ')' , 0} ,
{ ':' , '-' , ')' , 0},
...

Well, I lied! The library won't store smileys specifically, the strings given might be longer than that. I wanted to simplify my question, sorry about that. So I can't use this method, as I don't want to waste too much space allocating this array.

Delta_G:
The thing about not knowing the number ahead of time is that there is a very limited amount of RAM to work with. Using malloc every time they add a new one isn't really practical in this environment. You could have the user call a method (or possibly put it in the class constructor) in the beginning that states how many they will create and malloc the array ONCE and only once at the beginning of the program. That's probably the safest option.

I know malloc is bad in an embedded environment, but the user might call addSmiley later in the program, based on events for example. So the size of the array won't be fixed anyway.
Memory fragmentation should not be a problem, because the sketch runs on an ESP8266 which has sufficient RAM for what I want to do, and addSmiley will probably not be called more than a dozen of times.

PaulS:
Another option is a linked list. Adding a new node to the list is relatively simple. It involves calling malloc() with the size of the node, and then storing the pointer to the new node in the last node created.

The advantage is that you use the minimum amount of storage for the known data. The disadvantage comes from needing to understand pointers and how to create and add to a linked list, plus the overhead of the pointer to the next node, for each node.

I like this one! So something like:

struct Smiley {
  String text;
  Smiley *next;
};

int size = 0;
Smiley *top;
top = nullptr;

void add(String text){
  Smiley *smiley = new Smiley();
  smiley->text = text;
  smiley->next = top;
  top = smiley;
  size++;
}

But then, how to iterate in a for loop without popping elements?

7

marvinroger:
But then, how to iterate in a for loop without popping elements?

By creating an iterator function to "walk" the list.

8

So something like:

No, nothing like that. Do NOT use String ANYWHERE in your code.

void add(String text){
  Smiley *smiley = new Smiley();
  smiley->text = text;
  smiley->next = top;
  top = smiley;
  size++;
}

If you set to top to the recently created Smiley EVERY TIME, you are going to have problems. You need to set top to the recently created Smiley ONLY is top is a NULL pointer.

9

You say you have plenty of memory, and you say you won't be adding more than a dozen "things". So what is the problem with statically creating room for up to a dozen "things", and setting some reasonable maximum length for each?

If you truly don't know up front how many things you'll have, or their maximum lengths, then you have no choice but to use dynamic allocation, with either "new" or malloc. A linked list them becomes a reasonable way to manage the data.

Contrary to what is repeatedly stated as indisputable fact here, there is NOTHING wrong with using malloc - a great many real embedded application use malloc all the time. It works perfectly, and will not create any problems if used properly. I use it very often in my applications, and have never had a single problem.

Regards,
Ray L.