Sign in to follow this  
DavW

hash_map

Recommended Posts

Is this part of the STL? It's in some guides but not in others and I don't seem to have an implementation of it (in GNU C++). It sounds useful for the script parser I'm writing as I don't need the sorting capabilities of a map and performance is necessary.

Share this post


Link to post
Share on other sites
hash_map is not a part of the standard library currently.

edit: though I believe STLPort has a hash_map version, if your copy of gcc doesn't ship with one.

Share this post


Link to post
Share on other sites
As mentioned hash_map is a standard library extension not part of the standard and is currently being reviewed to be incorporated into the standard under a new name unordered_map in the TR1 technical library review 1.

GCC does have hash_map but its in a different header in a different namespace than expectated.

GCC >= 4.0 its unordered_map in namespace std::tr1 in the header tr1/unordered_map i believe.
GCC < 4.0 && GCC >= 4.0 its hash_map in namespace __gnu_cxx in header ext/hash_map.

Note if you intend on using GCC hash_map's key type to be std::basic_string you either need to do a specialization for std::hash or provide a custom hasher type not sure if this is the case for GCC's imp of std::tr1::unordered_map.

[Edited by - snk_kid on July 8, 2005 1:44:53 PM]

Share this post


Link to post
Share on other sites
Quote:

Note if you intend on using GCC hash_map's key type to be std::basic_string you either need to do a specialization for std::hash or provide a custom hasher type...


An example of the specialization, since it's tricky, and pretty vital to using it effectively:

This should probably be in it's own header, so that inclusion guards, and portability stuff can be wrapped around it.


namespace __gnu_cxx{

template <>
struct hash<string>{
size_t operator()(const string &s) const {
hash<const char *> h;
return(h(s.c_str()));
}
};
}

Share this post


Link to post
Share on other sites
I've heard that there is a boost library implementing the TR1 functionality (including unordered_map) coming in the near future, but that could just be a rumour.

Also, std::map offers a very similar interface to unordered_map (just the hash function differs), so it's easy to just use std::map then switch if your profiling reveals that to be a bottleneck (which it could well do with medium-large amounts of data).

So you could use a typedef like:

typedef std::map<T1,T2> associative_container_T1_T2;

later to be replaced by

typedef std::unordered_map<T1,T2,hash_function_object> associative_container_T1_T2;

Share this post


Link to post
Share on other sites
Quote:
Original post by Telastyn
*** Source Snippet Removed ***


How about generalizing & internalization it [grin]:


#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> > {};
};

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this