On Mon, 6 Apr 2026, 18:28 Adrian Johnston, <ajohnston4536_at_[hidden]> wrote:

>
> Hello Jonathan,
>
> > it seems like you described a flat map for C, but you aren't using
>
> > one for C++. Why not?
>
> The goal was to assess/evaluate the design for the standard interface for
> red black trees. The C version was intended as a baseline, not an apples to
> apples comparison.
>

So you're comparing a RB tree to an array. Is that meaningful?



> When I used to write real time code full time we would just use an array
> and linear probing for something small like this. If your array is
> unordered then you can just swap the end element down when erasing an
> element.
>
> From my own code:
>
> template<hxarray_concept_ T_, size_t capacity_>
>
> void hxarray<T_, capacity_>::erase_unordered(const T_* pos_) {
>
> hxassertmsg(pos_ >= this->data() && pos_ < m_end_, "invalid_iterator");
>
> if(pos_ != --m_end_) {
>
> *const_cast<T_*>(pos_) = hxmove(*m_end_);
>
> }
>
> m_end_->~T_();
>
> }
>
> This is something I think the std::vector could definitely use.
>
> > 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?
>
> This requires me to call constructors and destructors on the map nodes
>

Why? I don't understand this claim at all.

which, on a non-trivial program, will likely require further allocations
> and deallocations.
>

Eh?


This could become a headache compared to maintaining a free list of
> non-trivial nodes.
>
> In my ideal world a node type would be nothing but a contract to avoid
> multiple inheritance.
>
>