Date: Tue, 23 Jul 2019 00:42:18 +0300

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.

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.

Received on 2019-07-22 16:44:27