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.

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
which, on a non-trivial program, will likely require further allocations
and deallocations. 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.