#1
  1. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,594
    Rep Power
    4207

    Tip about STL hash_map and string


    This is not really a question, but a tip for others who may possibly search the forum for this particular issue:

    The problem:
    This code works:
    Code:
    #include <iostream>
    #include <hash_map>
    using namespace std;
    
    hash_map <const char *, int> months;
    int main(void) {
       months["january"] = 31;
       months["february"] = 28;
       return 0;
    }
    However, this code doesn't compile:
    Code:
    #include <iostream>
    #include <string>
    #include <hash_map>
    using namespace std;
    
    hash_map <string, int> months;
    int main(void) {
       months["january"] = 31;
       months["february"] = 28;
       return 0;
    }
    Note that the only difference between the two codes is that one uses const char * and the other uses string for the hash key type. So why does the second instance not compile?

    Background: What is a hash_map?
    The STL library provides a template type called map which allows a C++ programmer to create an associative array (i.e). array[key] = value;
    However, a map template automatically orders its elements as they're inserted, therefore lookups are a little slower. A hash_map is a template type that allows a programmer to quickly look up a value. The hash_map template uses a hashing algorithm to store values that are inserted into it, hence the elements are NOT sorted. This is OK, if you just want to do quick in-memory lookups, but don't care about the data being sorted. The map type is part of the STL, but hash_map was introduced by SGI and is present in only some implementations of the STL (M$ VC++ 6.0 and .NET do not have it in their default installation). However, two of the well known implementations from SGI (http://www.sgi.com/tech/stl/index.html) and stlport (http://www.stlport.org/) do and can be used as drop in replacements, if your compiler does not support hash maps. See http://www.sgi.com/tech/stl/table_of_contents.html for documentation and sample code using hash_map :).

    The reason it doesn't compile:
    Since hash_map is not part of the standard STL, there are certain other parts of the STL that it doesn't work with (notably the string template, which is pretty much standard across all STL implementations). You need to supply some extra code yourself, for the hash function to work correctly with other parts of the STL, which are standard across all implementations.

    The solution:
    Add the following chunk of code between the BEGIN FIX and END FIX comments:
    Code:
    #include <iostream>
    #include <string>
    #include <hash_map>
    using namespace std;
    
    /** BEGIN FIX **/
    namespace std                                                                                 
    {                                                                                             
      template<> struct hash< std::string >                                                       
      {                                                                                           
        size_t operator()( const std::string& x ) const                                           
        {                                                                                         
          return hash< const char* >()( x.c_str() );                                              
        }                                                                                         
      };                                                                                          
    }          
    /** END FIX **/
    
    hash_map <string, int> months;
    int main(void) {
       months["january"] = 31;
       months["february"] = 28;
       return 0;
    }
    I tested this code on the following OS/compiler environments:
    Red Hat Linux 7.1: gcc version 2.96 20000731 (Red Hat Linux 7.1 2.96-81)
    FreeBSD 4.7-RELEASE-p7:gcc version 2.95.4 20020320 [FreeBSD]
    OpenBSD 3.3-CURRENT:gcc version 2.95.3 20010125 (prerelease, propolice)

    [edit] Note that I was using the STL implementations that came by default with the distros and they all supported hash_map :)[/edit]

    Hope this helps! :)

    Comments on this post

    • sizablegrin agrees
    Last edited by Scorpions4ever; March 12th, 2003 at 06:11 PM.
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2005
    Posts
    227
    Rep Power
    0
    According to this post, all I need to include in order to use Hash Tables is:

    #include <iostream>
    #include <hash_map>

    using namespace std;
    but this seems not to be the case. When I do, I get a compile error

    hash.cpp(70) : error C2065: 'hash_map' : undeclared identifier
    When I right click on my code where I define my hash_map and look at the definition, I see different definitions that use three parameters instead of two.
  4. #3
  5. ASP.Net MVP
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Aug 2003
    Location
    WI
    Posts
    4,378
    Rep Power
    1510
    I know this is old now, but I just ended up here via a google search, and so others might as well.

    The key to fixing complete's problem is that Visual Studio 2003 and 2005 put hash_map in the stdext namespace rather than just std.

    Take that to heart and everything is suddenly fine again.

    Comments on this post

    • sizablegrin agrees : Same for VC++ 2008
    Primary Forum: .Net Development
    Holy cow, I'm now an ASP.Net MVP!

    [Moving to ASP.Net] | [.Net Dos and Don't for VB6 Programmers]

    http://twitter.com/jcoehoorn
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2010
    Posts
    3
    Rep Power
    0

    Linux Mint 9 (Ubuntu 10.04)


    I had to do something different for my linux. I don't know if it's because I have a newer gcc, but this is the code that works for me.

    Code:
    #include <iostream>
    #include <string>
    #include <hash_map>
    using namespace std;
    
    /** BEGIN FIX **/
    _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
    
      template<> struct hash< ::std::string >
      {
        size_t operator()( const ::std::string& x ) const
        {
          return hash< const char* >()( x.c_str() );
        }
      };
    
    _GLIBCXX_END_NAMESPACE
    /** END FIX **/
    
    int main(void) {
       __gnu_cxx::hash_map <string, int> months;
       months["january"] = 31;
       months["february"] = 28;
       return 0;
    }
    I'm using Linux Mint 9 (Ubuntu 10.04) , with gcc 4.4.3

    I noticed that in Linux Mint 8 (Ubuntu 9.10), with gcc 4.4.1 , I had to do #include <ext/hash_map> but in Linux 9, both #include <hash_map> and #include <ext/hash_map> works , but I also switched my build system, so I don't know if that changes anything.
  8. #5
  9. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,594
    Rep Power
    4207
    Heh, the original method I'd posted was valid in 2003. Nice to see that people are still following up on this and found the original post useful :). The best way to handle this with recent gcc compilers is as follows:
    Code:
    #include <string>
    #include <unordered_map>
    
    std::unordered_map <std::string, int> months;
    int main(void) {
       months["january"] = 31;
       months["february"] = 28;
       return 0;
    }
    Compile with the following options:
    Code:
    g++ -Wall -std=c++0x -o hash_fun hash_fun.cpp
    The -std=c++0x tells it to use the upcoming C++ standards (unordered_map is part of the new standard). New gcc compilers will tell you that hash_map is deprecated and to use unordered_map instead. Better still, the new unordered_map template handles string keys correctly without the additional workaround that I detailed in the first post of my thread.

    Tested on both:
    gcc version 4.4.1 (Ubuntu 4.4.1-4ubuntu9) <-- Ubuntu 9.10
    gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) <-- Ubuntu 10.04

    Will test my OpenBSD sparc64 boxes with gcc 4.1 in a little bit.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2010
    Posts
    3
    Rep Power
    0
    Originally Posted by Scorpions4ever
    The -std=c++0x tells it to use the upcoming C++ standards (unordered_map is part of the new standard). New gcc compilers will tell you that hash_map is deprecated and to use unordered_map instead. Better still, the new unordered_map template handles string keys correctly without the additional workaround that I detailed in the first post of my thread.
    Wow, that looks a lot cleaner than the workaround I had to do. I was wondering if it's safe, though. I mean, it seems unlikely, but might they change the standard? Do you happen to know how to find out what's the lowest gcc version that supports this new standard? It doesn't seem to be usable on my lab's Scientific Linux (gcc-4.2.2), even though it works fine on my Linux Mint 9 (Ubuntu 10.04 gcc-4.4.3). I guess for now, I'll have to use the old workaround :-/. I wish my people would update their compilers, or come out with standards sooner, but I guess it's a complex process with the standards.
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2010
    Posts
    3
    Rep Power
    0

    New Revision


    Well, I was too lazy to download and compile the newer gcc on my school's lab, so I came up with this solution,
    Code:
    #include <cstddef>
    
    using std::size_t;
    
    namespace __gnu_cxx
    {
       template<> struct hash<uint64_t>
       {
          size_t operator()(uint64_t __x) const
          { return __x; }
       };
    }
    This worked on Linux Mint 9's gcc 4.4.3 and Scientific Linux (like Fedora) gcc 4.1.2 . Someone online said to not put stuff into namespace with double underscore in front of it and use some template hash thing. If someone can show me this "better" way of doing it, that'd be great.

IMN logo majestic logo threadwatch logo seochat tools logo