Thread: more serious hash table

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    242

    more serious hash table

    first question: does boost or other already have a hash table implementation?

    if not, then second question: it should presumably be a class template HashTable<T>, then the constructor will have to feed it a hash function, including mapping T objects into unsigned int, right?

  2. #2
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    does boost or other already have a hash table implementation?
    STL, it's magik. And it comes standard with every[?] implementation of C++.
    http://www.sgi.com/tech/stl/hash_map.html
    EDIT:
    also there's http://www.sgi.com/tech/stl/hash_set.html if you don't need a map.
    Last edited by bernt; 09-22-2010 at 05:34 PM.
    Consider this post signed

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by bernt View Post
    STL, it's magik. And it comes standard with every[?] implementation of C++.
    hash_map<Key, Data, HashFcn, EqualKey, Alloc>
    Not standard..
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    Not standard..
    It's a shame hashing didn't get in.
    Consider this post signed

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    242
    so... where does that leave us? i have no desire to re-invent the wheel but would like to have a nice hash_map and hash_set

    those linked to look very nicely done

  6. #6
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    If you're using Visual Studio or g++, hash_set and hash_map are included. If you're using something else that doesn't have hash_set for reasons unknown, you could try downloading the headers you need from here.
    The implementation is entirely in headers because of templating, so it compiles in with your program and there's no linking involved. Simple enough.
    Consider this post signed

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    242
    cool, thanks! as long as there's a good and at least fairly widely accepted implementation out there, the best way to learn is probably just to study that.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    If you are using a sufficiently recent compiler, its standard library may come with the TR1 extensions, and thus you would have access to std::tr1::unordered_map and std::tr1::unordered_set.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    242
    visual studio 2010?
    any way to look at source code?

  10. #10
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    any way to look at source code?
    Open the header file? It's under <Visual studio install dir>\VC\include.

    Or I guess right-click the #include directive and select "open document".
    Consider this post signed

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help understanding Hash Table
    By boblettoj99 in forum C Programming
    Replies: 3
    Last Post: 12-29-2009, 01:23 PM
  2. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 09:23 PM
  3. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 05:06 PM
  4. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  5. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 09:00 PM