That change would probably be a breaking change to std::map, but you could
make a new container "ordered_hash_map" that had those properties.

On Mon, Jul 22, 2019 at 5:42 PM VALERIU SMERICA via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> 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.
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> http://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>

-- 
Be seeing you,
Tony