   Hash tables, where are they?
  I am currently implementing a buffer manager in c/c++ and I need a hash table too quickly look if the node I''m requesting is in memory.The problem is that STL hasn''t any standard hash table.Any ideas where I can get a ''good'' (that, is approved by the community) hash table implementation, either as a source or in a library.I have looked for hours for a good hash table, but no luck yet.   Friðrik Ásmundsson 
  er... stl has:   1.  set   2. map   3. multiset   4. multimap   5. hash_set   6. hash_map   7. hash_multiset   8. hash_multimap   9. hash -me ;  What compiler are you using? Chances are it already has a hash table implementation bundled with it. For example: MSVC .NET 2003 has a hash map as stdext::hash_map in the <hash_map> header. If your compiler doesn''t ship with one, you can probably use STLPort''s hash table containers. ;  Look at std::map. It is a red-black tree that should be suitable. Some implementations provide a hash_map class as well, but try the map out first. ;quote:Original post by SiCrane  What compiler are you using? Chances are it already has a hash table implementation bundled with it. For example: MSVC .NET 2003 has a hash map as stdext::hash_map in the <hash_map> header. If your compiler doesn''t ship with one, you can probably use STLPort''s hash table containers.   I''m using  KDevelop, that uses the g++ compiler, so theres probably nothing bundled with that package (not 100% sure though, have to look it up).;quote:Original post by FrikkaSoft  quote:Original post by SiCrane   What compiler are you using? Chances are it already has a hash table implementation bundled with it. For example: MSVC .NET 2003 has a hash map as stdext::hash_map in the <hash_map> header. If your compiler doesn''t ship with one, you can probably use STLPort''s hash table containers.   I''m using  KDevelop, that uses the g++ compiler, so theres probably nothing bundled with that package (not 100% sure though, have to look it up). Sure there is. Check in your (probably) /usr/include/c++ directory (probably a version subdirectory as well). If you have g++, you''ve got map, multimap, hash_map, etc...  If you don''t, then you should probably upgrade. If KDevelop can''t find the headers, you may have to fix your paths, but they should be there.   GolemBlender--The Gimp--Python--Lua--SDLNethack--Crawl--ADOM--Angband--Dungeondweller;  STLPort has:hash_sethash_map;  Thanks for all the helpful replies!As I see it now, hash_set does not allow modification of elements (which I need) while the hash_map doesn''t allow modification of keys, but the value part can be modified (OK this should do it for me). Also they share the same requirement that no two elements may have the same key. Now, In my buffer manager I could have many threads accessing this container, and if I am correct the hashtable has a semaphore that protects it (so only one can write it an entry the same time). This is what I need, and I don''t think this synchronization is included in the hash_map/hash_set.I downloaded the STLPort, SiCrane suggested, and it looks promising. There I found a hashtable class (stlport\stl\_hashtable.h) that I might use, but I tried looking up (test\regression\*) code examples in the regression test, but there it is never used or tested. Any examples/explenations on how to use the STLPort''s hashtable class would be greatly appreciatedAnd thanks again!   Friðrik Ásmundsson ;quote:Original post by FrikkaSoft  Thanks for all the helpful replies!As I see it now, hash_set does not allow modification of elements (which I need) while the hash_map doesn''t allow modification of keys, but the value part can be modified (OK this should do it for me).You''re unlikely to find many hashtable implementations that allow changing the key, since that''s really just equivalent to deleting the original element and adding the new one.quote:Also they share the same requirement that no two elements may have the same key.Check out hash_multiset and hash_multimap. These are declared, in the g++ headers, in hash_set and hash_map, respectively.   "Sneftel is correct, if rather vulgar." --Flarelocke 