Jump to content
  • Advertisement
Sign in to follow this  
okonomiyaki

hash_map header

This topic is 4497 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I know hash_map isn't in the C++ standard yet, but I'm using it because it seems to be installed on all the systems I need to support. The problem is, it's either in "hash_map" or "ext/hash_map". Can someone explain when it is in either of these locations? I need to know how to setup my macros to detect where to include it. I noticed that Ogre simply does this
#ifdef EXT_HASH
#   include <ext/hash_map>
#   include <ext/hash_set>
#else
#   include <hash_set>
#   include <hash_map>
#endif
But I can't find anything on the EXT_HASH define, in Ogre or elsewhere. Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
i would suspect that currently this is very compiler-specific. as long as hash map isn't in the standard (no, i don't mean tr1 or tr2) you can't assume to find it in the compiler's default include path.
a solution for this might be to reference hash_map in the boost library. the boosters have included a mechanism for boost to fall back to the compiler vendor's or the library vendor's tr1 compliant implementation of hash_map if it exists. otherwise the boost implementation is used.
let the boosters track all the vendor specific stuff and do the #ifdef work :-)

if you don't want to use boost you have to use compiler vendor specific #defines so the compiler always finds the tr1 hash_map.

cheers,
simon.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
i would suspect that currently this is very compiler-specific. as long as hash map isn't in the standard (no, i don't mean tr1 or tr2) you can't assume to find it in the compiler's default include path.
a solution for this might be to reference hash_map in the boost library. the boosters have included a mechanism for boost to fall back to the compiler vendor's or the library vendor's tr1 compliant implementation of hash_map if it exists. otherwise the boost implementation is used.
let the boosters track all the vendor specific stuff and do the #ifdef work :-)

if you don't want to use boost you have to use compiler vendor specific #defines so the compiler always finds the tr1 hash_map.

cheers,
simon.

Share this post


Link to post
Share on other sites
Quote:
Original post by okonomiyaki
The problem is, it's either in "hash_map" or "ext/hash_map". Can someone explain when it is in either of these locations?


There are loads of special cases you'll need to handle:

VC++ < v7.1 in header "hash_map" in namespace std.
VC++ >= v7.1 in header "hash_map" in namespace stdext (std version deprecated in VC++).

GCC < 4.* series in header "ext/hash_map" in namespace __gnu_cxx.

GCC >= 4.* series in header "tr1/unordered_map" it's called unordered_map and it's in namespace std::tr1 yes nested namespace because unordered_map is in the C++ library technical report 1 (TR1).

Notes.

GCC < 4.* series hash (not hash_map, it's default hasher type) is not specialized for std::basic_string (you can hunt my posts for the code to handle this).

VC++'s hash_map interface is slightly different and unique from SGI's one (and thus GCC's hash_map). You could handle this by making a wrapper who's interface conforms with C++ TR1 unordered_map interface.

To handle the different namespaces you can use the preprocessor & namespace aliases.


Quote:
Original post by okonomiyaki
I noticed that Ogre simply does this


#ifdef EXT_HASH
# include <ext/hash_map>
# include <ext/hash_set>
#else
# include <hash_set>
# include <hash_map>
#endif


But I can't find anything on the EXT_HASH define, in Ogre or elsewhere. Thanks.


This isn't anything standard, it's probably just there for you to add to your list defines in your project, outside of code i.e -DEXT_HASH.

Share this post


Link to post
Share on other sites
Thanks man, got it completely implemented, though I haven't tested it on gcc yet. Do you have any information on how the interfaces are different? That really does suck. I'm not doing anything more advanced then just storing and retrieving data, do you think I'm going to run into problems? I think I'm gonna run with it and implement something and wait until testing to tweak the interface.

Share this post


Link to post
Share on other sites
The most signficant difference between VC++'s hash_map/set and other compilers that follow SGI's interface is that VC++'s version takes a different number of template parameters, it takes 4 while SGI's takes 5. VC++'s hash_map/set takes a hash traits type instead of a seperate hash and comparator type you can read it all about it on MSDN. If i remember correctly some methods dont exist and/or are named differently in VC++'s version from SGI's version.

MSDN VC++'s hash_map

SGI's hash_map

Share this post


Link to post
Share on other sites
Also note that < VC7.1 hash_maps don't actually hash at all (well, all it does is cast to a size_t), and don't have a std::basic_string specialisation.

Share this post


Link to post
Share on other sites
Save you time from searching here is the code to make GCC < 4.* series work with std::basic_string as keys out the box:


#include <string>
#include <locale>
#include <ext/hash_map>

namespace __gnu_cxx {

template< typename CharT, typename Traits, typename Alloc >
struct hash< const std::basic_string<CharT, Traits, Alloc> > {
size_t operator()(const std::basic_string<CharT, Traits, Alloc>& s) const {

const std::collate<CharT>& c = std::use_facet<std::collate<CharT> >(std::locale());
return c.hash(s.c_str(), s.c_str() + s.length());

}
};

template< typename CharT, typename Traits, typename Alloc >
struct hash< std::basic_string<CharT, Traits, Alloc> >
: hash< const std::basic_string<CharT, Traits, Alloc> > {};
};
s

Share this post


Link to post
Share on other sites
Thanks a lot snk_kid, you've been a great help. I was looking at those hash_map reference pages as you posted them, and yeah, they are quite different. crap. I found your other posts that had your basic_string implementation too, but thanks for the quick reference here! That is surely a much better way of implementing then I would have done.

Python - interesting. good thing my project shouldn't usually compiled on versions < 7.1.

The different number of template arguments is bad, but what makes it worse is that the VC implementation of a hash object uses a "less" comparison while others use an "equal_to" comparison. It seems to keep some kind of order to the hash:

From msdn:
Quote:

"The hash_map orders the sequence it controls by calling a stored hash Traits object of class value_compare. This stored object may be accessed by calling the member function key_comp. Such a function object must behave the same as an object of class hash_compare<Key, less<Key> >. Specifically, for all values _Key of type Key, the call Traits(_Key ) yields a distribution of values of type size_t.

In general, the elements need be merely less than comparable to establish this order: so that, given any two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements."


If you are using a hash, you shouldn't care about the order. Why is it trying to order things?

I guess I could use an "equal_to" comparison to keep things consistent, but it will order things differently in the VC implementation, but I could care less about ordering.

I really don't want to use something else like google's sparse hash because it introduces a different interface and would require refactoring when hash_map does become standard. Plus it's just code from a totally different source.

Share this post


Link to post
Share on other sites
Quote:
Original post by okonomiyaki
If you are using a hash, you shouldn't care about the order. Why is it trying to order things?

I guess I could use an "equal_to" comparison to keep things consistent, but it will order things differently in the VC implementation, but I could care less about ordering.


I wouldn't worry about it, if you continue reading from that part it says:

Quote:

... On a more technical note, the comparison function is a binary predicate that induces a strict weak ordering in the standard mathematical sense. A binary predicate f(x,y) is a function object that has two argument objects x and y and a return value of true or false. An ordering imposed on a hash_map is a strict weak ordering if the binary predicate is irreflexive, antisymmetric, and transitive and if equivalence is transitive, where two objects x and y are defined to be equivalent when both f(x,y) and f(y,x) are false. If the stronger condition of equality between keys replaces that of equivalence, then the ordering becomes total (in the sense that all the elements are ordered with respect to each other) and the keys matched will be indiscernible from each other.

The actual order of elements in the controlled sequence depends on the hash function, the ordering function, and the current size of the hash table stored in the container object. You cannot determine the current size of the hash table, so you cannot in general predict the order of elements in the controlled sequence.



If you want to have a consistent, (semi-)stable interface i'd follow unordered_(multi)map/set from TR1 spec, it's here. Just copy the interface :P

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!