On Mon, 6 Apr 2026, 21:09 Jonathan Wakely, <cxx_at_[hidden]> wrote:

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


Specifically, you said "The resulting code is somewhat peculiar and the
results are not favorable for C++" but it seems that the results are not
for "C++" but instead for comparing two different data structures, where
anybody could have predicted that a RB tree would perform worse than an
array. And the complexity of the code is because of the decision to work
with nodes that you create+manage by hand, which was never how std::map is
meant to be used.



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