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.