> Why are you using lower_bound then insert, why not just insert the node
handle directly?


At this point you are optimizing a very synthetic benchmark. As much as I
appreciate all the effort and feedback, the use of integers in my sample
code is entirely representative of much more complex objects and more
complex use cases.


Programmers don't always know if a node will be constructed or not, and may
want to do different things depending on whether it has been. The example I
posted doesn't actually do that, but this pathway was the one I was trying
to exercise.


> Why are you using vector::reserve(n) followed by vector::resize(n), why
not just resize?


Habit. I am used to reserving arrays before I use them. Sorry.


> You can replace your entire StackArena and Map and pool of Map::node_type
with this:

>

> alignas(std::max_align_t) char buf_[kArenaCapacity];

> std::pmr::monotonic_buffer_resource bufres_{buf_, sizeof(buf_),

>
std::pmr::null_memory_resource()};

> std::pmr::unsynchronized_pool_resource res_{&bufres_};

> std::flat_map<int, int, std::less<int>, std::pmr::vector<int>,
std::pmr::vector<int>> map_{&res_};


I appreciate the usage advice. That certainly looks a lot saner than what I
came up with.


In practice I suspect I would still be using a custom allocator because I
would want telemetry and would be trying to merge allocations into larger
blocks to avoid hitting individual allocator limits. Hitting individual
allocator limits for fine allocators tends to make your program crash
constantly.


In all honesty what I am getting from this conversation is that I should
delete the red-black tree code from the research project I was working on
because it sucks for real-time use.


And humorously, as it happens, Ubuntu 24.04.4 LTS doesn't even have
std::flat_map yet.


> This will use a stack buffer (not malloc) and maintain a free list of
deallocated

> nodes in an object pool.


Again, this is a synthetic example. A lot of embedded projects run with an
8-32 KB stack, so dumping all of your allocations on the stack will not
work.