One last thing that I forgot:
1.the priority que isn't a good way to fix it but I think flat maps may be

On Mon, 6 Apr 2026, 5:07 am Muneem, <itfllow123_at_[hidden]> wrote:

> 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
>>
>