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.