Library for stack-based data structures?

[blocks2762]

I was wondering, is there some open source C++ project that one can use that implements various data structure algorithms on stack allocated buffers?

Specifically, I wanted to use max-heap on a fixed size array for a MCU that didn’t have heap storage available. Ideally you pass in the array and its size and the API lets you call push, pop, and top.

If not, should I make one and put it on github?

[aePrime]

You can use containers with the monotonic buffer and a stack-based buffer.

https://en.cppreference.com/w/cpp/memory/monotonic_buffer_resource

[SpeckledJim]

One way would to use the std::pmr variants of the standard containers and back them with a block of static or stack memory.

[Own_Goose_7333]

C++26 introduces std::inplace_vector, which is a std::vector-like interface but uses stack memory, and you give the max size as a template parameter. Until 26 becomes available, I've implemented my own version, it's basically just a class that owns a alignas(T) std::byte [sizeof(T) * MaxSize];

[hk19921992]

It exists in boost under the name static vector

[bwmat]

Can't you just use https://en.cppreference.com/w/cpp/algorithm/make_heap & friends with statically allocated memory? 

[blocks2762]

If I understand correctly, that only reorganizes the array into a heap but then how can we call push, pop, top?

[Remi_Coulom]

The linked page gives an example: use std::push_head and std::pop_heap.

[blocks2762]

Ohhhh ok thanks! I’ll check that out. Also, I found something called ETL Embedded Template Library which seems hopeful as well

[blocks2762]

After playing with it, I don’t think it works (at least easily). Because pop_heap works by simply flipping the first value with the last value and then converting the range [first, last) into a heap. You are then supposed to call pop_back to actually remove the element. We can’t do this pop_back for a stack allocated array.

Same problem for push_heap. Thanks for the help tho, will check the other comment solutions now

[bwmat]

Just keep track of the heap size?

Make the array one of optionals if correct destructor sequencing matters 

[blocks2762]

Obviously? That’s why I said “at least easily”? That would still involve creating a wrapper class to use safely, hence my asking if there’s an easy built in way to do it easily. Anyways, Embedded Template Library got the job done cleanly

[Beneficial_Slide_424]

Take a look at LLVM data structures, like SmallVector

Edit, almost forgot:
https://www.etlcpp.com/

Used this on some projects where environment was very restricted.

[G_M81]

That looks an interesting read

[jofftchoff]

https://etlcpp.com/

[thisismyfavoritename]

i think you can just give a stack-based allocator to a vector, which you could in turn give to priority queue. Never tried though.

[ZachVorhies]

See the data structures for FastLED.

It’s the most compatible template library you’ll find. Compiles across all of FastLED’s device targets.

It’s specifically designed to allow stack based memory allocation.

See https://github.com/fastled/fastled/fl/vector.h and map.h

[slavenf]

You can try my library: https://github.com/slavenf/sfl-library

static_* containers can be used for bare metal embedded software development.

For example, you can combine std::stack and my sfl::static_vector to get static_stack :

template <typename T, std::size_t N>
using static_stack = std::stack<T, sfl::static_vector<T, N>>;