Could a re-sizable container be built on the on stack

Question

I've searched this up but was unable to find answers. We all know that a lot of the STL containers are re-sizable (except for things like std::array, etc.), but they all are allocated on the heap. So I was wondering if a re-sizable container could be built on the stack and if somebody could give me an example.

A thought about this:

I think that a linked list would could be built on the stack because (as far as I know) you only allocate the nodes on the heap because of the lifetime, but all in all, I'm not sure if that would work.

C allows variable length arrays. (Recommend only 1 language tag) — chux - Reinstate Monica, May 26 '20 at 20:37
[See this about a stack-based allocator](https://howardhinnant.github.io/stack_alloc.html) — PaulMcKenzie, May 26 '20 at 20:39
There's the not-standard and probably [not safe](https://stackoverflow.com/a/1018865/669576) [`alloca()`](https://www.man7.org/linux/man-pages/man3/alloca.3.html). — 001, May 26 '20 at 20:41
@chux-ReinstateMonica -- Yes, but: (1) they are very restrictive (they *have* to be known at consts) (1) you can't really append to it — xilpex, May 26 '20 at 20:46
I used to statically allocate linked lists all the time to keep fragmentation down on embedded systems. They did not go on the stack, though and the upper limit to the size was fixed by the number of nodes allocated. — user4581301, May 26 '20 at 20:46
I think it would be pretty simple. Just allocate a big chunk of stack memory, then overload `new` to hand it out for the elements of you container. Whether this is a good idea, I don't know. Fundamentally, it depends on *why* you want to do this. — Jasper Kent, May 26 '20 at 20:50
[small_strings.h](https://github.com/Ambeco/SmallContainers/blob/master/SmallContainers/small_string.h) and [stack_allocator](https://github.com/Ambeco/SmallContainers/blob/master/SmallContainers/stack_allocator.h) seem relevant — Mooing Duck, May 26 '20 at 20:57
@Xilpex " they are very restrictive (they have to be known at consts) " --> No. `int n = rand() % 10 + 1; double x[n];` is just fine. — chux - Reinstate Monica, May 26 '20 at 21:57

eerorika · Accepted Answer · 2020-05-26T21:43:35.380

It would also have to be very limited in size due to limited size of the stack.

What you could for example implement is a vector-like resizable container that has small constant storage, and thus small constant maximum size.

You could also create a linked list within a recursive function where head is on the current frame, and successor nodes are in the frames that called the function recursively. The size would be increased by calling the function, and decreased by returning.

Whether such containers would be useful is another matter.

If you don't mind could you explain the linked list idea more (maybe, just maybe give a small demo)?

Here is an extremely silly way to print a series of numbers using a linked list on the execution stack:

struct node {
    int data;
    node* next;
};

void foo(node* p) 
{ 
    if (p->data > 0) {
        node n {
            .data = p->data - 1,
            .next = p,
        };
        foo(&n);
    } else {
        for (; p ; p = p->next) {
            std::cout << p->data;
        }
    }
} 

int main () 
{
    node n {
        .data = 10,
        .next = nullptr,
    };
    foo(&n);
}

If you don't mind could you explain the linked list idea more (maybe, just maybe give a small demo)? — xilpex, May 26 '20 at 20:50
There's no reason for it to be non-copiable. It just has to have a fixed-size upper bound. I have a few in my personal library. Handy when you know the size is always less than 16 or something. — Mooing Duck, May 26 '20 at 20:54

Could a re-sizable container be built on the on stack

1 Answers1