Linked list on the stack

Question

Is there a C++ library that implements a linked list with all the memory on the stack?

Yes I know there will be an upper limit but looking for functionality to search it, add and delete items.

I am being lazy am hoping that somebody has done this. I would also like to know the number of failed attempts so next time around I could increase the amount off space required — Ed Heal, Aug 09 '14 at 22:24
@EdHeal Try this: http://stackoverflow.com/questions/8049657/stack-buffer-based-stl-allocator and this http://home.roadrunner.com/~hinnant/stack_alloc.html — PaulMcKenzie, Aug 09 '14 at 22:54
If it's on the stack, then I assume the number of elements is small. If the elements can be copied (or better, moved), you may find that a stack-based array is a simple and fast solution. Even though inserting or removing elements not at the end will cause other elements to be copied or moved, this cost can be smaller than you think for small numbers of elements. — Neil Kirk, Aug 09 '14 at 22:57
Why do you want to do that? Seems like an XY question, so I would like to understand what the Y is... — Mats Petersson, Aug 09 '14 at 23:47
@MatsPetersson If it's an XY question then surely it's X we're after... — , Aug 10 '14 at 00:26
The X is that it will be in an application that needs to know the upper bound so dynamic (heap) is not an option — Ed Heal, Aug 10 '14 at 00:29
You can put an upper limit on heap space if you need to, or simply do not add more than _x_ elements.....?? — Lightness Races in Orbit, Aug 10 '14 at 01:22
@LightnessRacesinOrbit - I was also thinking of using it in a memory allocator to record things. So do not wish to use dynamic memory allocation as I will end in an infinite loop — Ed Heal, Aug 10 '14 at 08:33
@LightnessRacesinOrbit - For example to record when memory is dynamically allocated and therefore do not wish to use dynamic memory allocation during that process - as that will lead to going back around the circle. — Ed Heal, Aug 10 '14 at 12:06
@LightnessRacesinOrbit - Got a hook into the memory allocator and planning to utilise it to find our the usage of memory by a third party. Therefore do not wish to pollute the results with further dynamic memory allocations — Ed Heal, Aug 10 '14 at 12:15
@EdHeal: "A" "What" "A" "Why A?" "Entirely unrelated B" just never mind — Lightness Races in Orbit, Aug 10 '14 at 12:34
You can use `alloca` to allocate memory on the stack instead of the heap. — nwp, Aug 10 '14 at 13:41

score 0 · Accepted Answer · answered Aug 10 '14 at 13:34

Ok, so typically, when you hook/replace the memory alloocator, the method is to add X bytes (it's best if it's a multiple of the normal alignment, so 16 or 32 bytes in the common case) to the actual allocation, and in that store whatever information is required. Typically, you store a pointer to the "previous" allocation in this extra memory, so you can later on walk that list and examine for example what the caller is and produce some sort of histogram or "top 10 biggest users", or whatever it may be.

You can't really use stack for what you want, since you are (I presume) returning from the call to the allocation function before you are done with the information you need, so storing the data on the stack seems unreasonable.

Linked list on the stack

1 Answers1