No std::hash_map

[saneman]

I have read that hash_map is not part of the C++ standard and therefore
std::hash_map does not exist (even though it can be found in sgi).

But is hash_map not just a std::map thats more efficient and implemented
with tables instead of an underlying balanced search tree and a
hashfunction?

[Victor Bazarov]

Re: No std::hash_map

saneman wrote:

I have read that hash_map is not part of the C++ standard

....yet...

and
therefore std::hash_map does not exist (even though it can be found
in sgi).
But is hash_map not just a std::map thats more efficient and
implemented with tables instead of an underlying balanced search tree
and a hashfunction?

Not sure what you mean. 'std::map' does not use hashfunction.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Juha Nieminen]

Re: No std::hash_map

Jerry Coffin wrote:

I don't know of an existing implementation, but the idea is pretty
simple. You create the hash map as a table of balanced trees (e.g. AVL
or R-B trees). In the worst case, if all your hashes collide, you're
working with a single balanced tree, which is exactly what you have with
std::set, std::map, std::multiset and std::multimap, so you get
precisely the same characteristics as they provide.

How is this different from simply using one single balanced tree?

Since you are having the overhead of a balanced tree anyways, adding
some properties of hashmaps to the mix probably won't cause a
significant increase in any performance.

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

Re: No std::hash_map

On 2008-02-17 09:03, Juha Nieminen wrote:

Jerry Coffin wrote:

>I don't know of an existing implementation, but the idea is pretty
>simple. You create the hash map as a table of balanced trees (e.g. AVL
>or R-B trees). In the worst case, if all your hashes collide, you're
>working with a single balanced tree, which is exactly what you have with
>std::set, std::map, std::multiset and std::multimap, so you get
>precisely the same characteristics as they provide.

>
How is this different from simply using one single balanced tree?
>
Since you are having the overhead of a balanced tree anyways, adding
some properties of hashmaps to the mix probably won't cause a
significant increase in any performance.

If you have luck with your hash-algorithm and the values inserted you
will only have one element per tree/bucket giving you O(1) insertion,
removal, and retrieval. In a normal hash-map (where the buckets are
linked lists) you have O(M) for these operations, where M is the number
of elements in the buckets (again, if you are lucky M==1) but in the
worst case you have O(N) when all elements are in the same bucket. If
the buckets are trees you get O(log N).

--
Erik Wikström