Yes, without reading the code yet, it seems like you described a flat map
for C, but you aren't using one for C++. Why not?

Your use of node handles is unconventional and not at all how they're
supposed to be used (they were never designed as a way to pre-allocate
storage). Why not use an allocator that has a fixed capacity with enough
space for the nodes you plan to allocate, then just let the nodes get
allocated as needed?



On Mon, 6 Apr 2026, 01:11 Muneem via Std-Proposals, <
std-proposals_at_[hidden]> wrote:

> 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
>>>
>> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>