Hi!
1.Sorry if I didn't understand your text(you said it's not a proposal), but
can't allocators help with that?
2.Also, if the goal is to allocate once (in the start of the program) then
dosent using pmr monolithic resource with pmr allocator help with that?
3. Dosent a class of functions like heap_sort exist in c++?
4. Aren't maps for constant latency, like if you want maximum bandwidth use
a vector or deque.
5. C++ standard template library is meant to be general (provide general
solutions) and as far as I know, it does provide all the solutions use
existing cache friendly arrays that can be treated like a map using heap.
6. Priority ques also exist and can be based of any container you want to
use. So if your goal was the most constant latency then use std list, if
bandwidth then use vector.


Hope my feedback was satisfactory.


On Mon, 6 Apr 2026, 4:25 am Adrian Johnston via Std-Proposals, <
std-proposals_at_[hidden]> wrote:

> Hello,
>
> I am interested in designing container classes that look like the STL but
> are adapted for use in embedded systems, specifically in real-time contexts
> where dynamic memory allocation is not allowed for safety and performance
> reasons. The Joint Strike Fighter Air Vehicle C++ Coding Standards would be
> an example of such requirements.
>
> Ideally, programmers familiar with the C++ standard library would not need
> to learn entirely new interfaces. This led me to study the design of the
> existing library from that perspective. In order to better understand the
> design and quality of std::map::insert( const_iterator pos, node_type&&
> nh ), I set up a benchmark for that method. The resulting code is
> somewhat peculiar and the results are not favorable for C++.
>
> I would like to present my findings not as a proposal but as a request for
> comments, as I am not yet convinced that a red-black tree is even ideal for
> real-time use, even though it is popular in places like the Linux kernel.
>
> For this test I created a C++ version and a C version. The C++ version
> uses std::map<Key, T, Compare, Allocator>::lower_bound and iterator
> std::map<Key, T, Compare, Allocator>::insert( const_iterator pos,
> node_type&& nh ). The C version implements a map using a simple sorted
> array, binary search for lookup, and memmove to create an empty slot.
> Both tests use a small custom stack allocator that allocates memory by
> simply incrementing a pointer.
>
> Please keep in mind that these results were not designed to favor the
> algorithmic advantages of a tree data structure. They were instead intended
> to be a representative example of ordinary code. My initial goal was to
> provide an example of interface design, not to make a point about
> performance numbers, although I found the performance numbers to be
> somewhat concerning as well.
>
> With that said, let me present the performance numbers first as they are
> easier to summarize. Each test either adds or removes a node from the map
> 32 times. Each test is run 10 times as a warm up first, so there should be
> no cache effects. It is then run 100 times in a loop and the results timed.
>
> Each C++ run took 365.6 ns on average. Each C run took 194.4 ns on
> average, making the C++ version 1.88x slower. The C++ test allocated 1216
> bytes for node storage while the C test used 128 bytes for its arrays, a
> difference of 9.5x. Finally, the C++ executable used 4240 more bytes when
> stripped. Knuth has already addressed cache coherence concerns around
> linear probing versus trees, but I would also note that the locality of
> reference with node handles is worse in this case and was hopefully not
> measured.
>
> The interface requirements of std::map::insert( const_iterator pos,
> node_type&& nh ) are well known to this list, but I would like to show
> some of the code I ended up with. What made my usage example particularly
> convoluted was the addition of a C++ custom allocator framework. The JSF AV
> requirements prohibit globals, so the requirement that containers be
> constructed with an allocator handle instance does make sense. Again, this
> is primarily a request for comments.
>
> The first major issue was using a temporary std::map to allocate node
> handles during startup. If handles cannot be allocated at all later on at
> all, this seems like a very strange ceremony to go through to obtain them
> all up front. A template<class... Args> std::map::make_handle(Args&&...
> args) function returning a handle would seem far more sensible.
>
> If the programmer already knows they have a fixed array of map nodes to
> work with after startup, the overhead of stripping used nodes out of a map
> so they can be recycled without being destroyed also seems excessive.
> Ideally, both an array of available nodes and a map containing them that is
> not needed anymore should be resettable by simply updating a few pointers.
> Note how much simpler the C version is in this regard.
>
> I am going to attach the code as it runs on far too long for an email.
> However, let me quote some of the types involved. While using statements
> bring the complexity under control, I want to illustrate the cognitive load
> involved in reading compiler errors generated by this code. The array or
> node handles is quite a beast.
>
> using PairAlloc = StackAllocator<std::pair<const int, int>,
> kArenaCapacity>;
>
> using Map = std::map<int, int, std::less<int>, PairAlloc>;
>
> using NodeAlloc = StackAllocator<Map::node_type, kArenaCapacity>;
>
> using IntAlloc = StackAllocator<int, kArenaCapacity>;
>
> // Arena must be declared before any member that holds a StackAllocator,
>
> // so it is constructed first and destroyed last.
>
> StackArena<kArenaCapacity> arena_;
>
> // std::map<int, int, std::less<int>,
>
> // StackAllocator<std::pair<const int, int>, kArenaCapacity>>
>
> // map_{StackAllocator<std::pair<const int, int>,
> kArenaCapacity>(arena_)};
>
> Map map_{PairAlloc(arena_)};
>
> // std::vector
>
> // std::map<int, int, std::less<int>,
>
> // StackAllocator<std::pair<const int, int>,
> kArenaCapacity>>::node_type,
>
> // StackAllocator
>
> // std::map<int, int, std::less<int>,
>
> // StackAllocator<std::pair<const int, int>,
> kArenaCapacity>>::node_type,
>
> // kArenaCapacity>>
>
> // pool_{StackAllocator
>
> // std::map<int, int, std::less<int>,
>
> // StackAllocator<std::pair<const int, int>,
> kArenaCapacity>>::node_type,
>
> // kArenaCapacity>(arena_)};
>
> std::vector<Map::node_type, NodeAlloc> pool_{NodeAlloc(arena_)};
>
> // std::vector<int, StackAllocator<int, kArenaCapacity>>
>
> // free_indices_{StackAllocator<int, kArenaCapacity>(arena_)};
>
> std::vector<int, IntAlloc> free_indices_{IntAlloc(arena_)};
>
>
>
> Attached are the C++ and C files. I don't think either are great examples
> of programming. They are both designed to be idiomatic examples of a
> certain test in modern versions of each language.
>
> The git repo for these tests is here:
> https://github.com/whatchamacallem/map-nodes
>
> I would be interested in any design feedback for making this kind of
> interface simpler and more efficient. Things get a lot easier when you
> drop the requirement for node handles, and start working with pointers to
> nodes instead, but that works against the desire for safety as we move
> forward.
>
>
> Regards,
>
> Adrian Johnston
>
>
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>