473,320 Members | 1,958 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

No std::hash_map

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?
Feb 14 '08 #1
3 3050
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
Feb 14 '08 #2
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.
Feb 17 '08 #3
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
Feb 17 '08 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Mark | last post by:
Hi, I'm trying to use hash_map (gcc 3.2.2) with a std::string as the key. It will compile if I use <map> but I get a bunch of template compile errors when I change it to hash_map. Any...
5
by: peter_k | last post by:
Hi I've defined hash_map in my code using this: ------------------------------------------- #include <string> #include <hash_map.h> & namespace __gnu_cxx {
1
by: David Chazin | last post by:
I have simple hash_map<int, int>. When I insert 1000 entries my memory grows by about 2 MB (or almost 2k per entry). Anybody have any ideas on whats going on here? This is a real problem because I...
0
by: Jon Cosby | last post by:
Why does this work std::hash_map <int, int> hm1; typedef pair <int, int> pr1; hm1.insert(pr1(1, 20)); cout << "First value is " << hm1 << endl; but not this using namespace std;
10
by: g | last post by:
hello! I wanna replace an std::map<std::string,Services*> with hash_map.How I will do this? any link with examples? transactions.insert(std::pair<std::string,Services*>("Aservice",new...
1
by: Amit Bhatia | last post by:
Hi, I have defined something like the following in tree.h file: //everything else including using namespace __gnu_cxx; typedef hash_map<pair<int,int>, Qd_Node, Qd_Node_HasherLoc_Tree;...
1
by: joseysaac | last post by:
i have this code in a archive called ffont.h #ifndef FFONT_H_FILE #define FFONT_H_FILE #include "FBase.h" #include "FShape.h" #include <vector> #include <hash_map>
2
by: Harinezumi | last post by:
Hi, I want to use SGI's hash_map in my code, but when compiling (with gcc 3.3.3) I get the following error: hash_map_test.h:3: error: syntax error before `;' token I reduced the code to...
4
by: James Kanze | last post by:
On Jul 16, 10:53 pm, Mirco Wahab <wa...@chemie.uni-halle.dewrote: It depends. You might like to have a look at my "Hashing.hh" header (in the code at kanze.james.neuf.fr/code-en.html---the...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.