Hello. I was thinking of std::map and its friends. Why is there the need to
tie the search strategy to the decision of having the container sorted?
A hash table could be used for search and a red black tree holding the
addresses of the elements from inside the hash table for when we want to
iterate in a sorted way or just want lower_bound/upper_bound. If each
element in the hash table holds a reference to its corresponding node in
the tree, for a delete we could hint the to-be-deleted node through the
reference held by the to-be-deleted element in the hash table. A red-black
tree does O(1) rotations for delete, so the hint reduces what it would be
O(log n) to O(1).
So, search and delete would be O(1) average (compute hash value) and insert
O(log n) average (compute hash value + traversing the tree to add the
address of the newly added element). Wouldn't that work better than what we
have now? Since std::unordered_map's purpose is to be used rather than
std::map for when we don't need an order, this combination of hash table
and binary search tree should be as a consequence a superior option to what
we already have. There is also the fact that since allocations in the tree
are made for addresses rather than the real elements (which could have big
sizes) when insertions are made, those should be faster, so the O(log n)
average should be very close to the O(log n) from now, since you lose some
to compute the hash value, but from the small memory allocations you also
win some. The best thing is that search would gain a significant
performance boost.
Is this strategy a viable one for C++ 23 maybe? Thanks.