🔒 Locked

bug in std::hash_map?

Started by IFooBar Jul 6, 2003 at 5:37 AM 13 replies 1.5k views

Original Post

Jul 6, 2003 at 5:37 AM

I was messing around with the std::hash_map and I tried making my own hash function for a key of type const char*. I looked into the hash_map source files and in the file called xhash a few lines down the hash_compare class has a function that hashes the key into a size_t type, so it does "return ((size_t)_Key)". hash_compare takes a template parameter of type _Pt. and _Pt is a function object that should provide two overloaded operator () for key comparisons and key hashing. the variable "comm" is of type _Pt in class hash_compare. in the _Traits parameter of std::hash_map I was passing in the following

struct obj
{
    size_t operator () ( const char* str )
    {
        size_t ret = 0;
        while( *str )
        {
            ret ^= *str | ret;
        }
        return ret;
    }

    bool operator () ( const char* left, const char* right )
    {
        return strcmp( left, right ) > 0;
    }
};
       
hash_map<const char*, ValueType, hash_compare<const char*, obj> >

it says that the second parameter in the hash_compare function should be an object with to function objects. one to compare values and the other to hash a value. It says this in msdn. so in the file xhash I has to change "return ((size_t)_Key);" to "return comm(_Key);" Everything works fine apparently, but i dunno is this a bug in xhash or in msdn?

:::: [ Triple Buffer V2.0 ] ::::

Zipster

Jul 6, 2003 at 5:58 AM

It''s an error in the implementation. By the way, what implementation is this exactly? I''m not surprised if it''s Microsoft''s, because they love these small quirks. Like forcing us to use less as a list sorting predicate. What the heck is that?

IFooBar

Jul 8, 2003 at 2:57 AM

hmm...it is indeed microsofts

the stl that ships with MSVC 7

thanks for the reply

:::: [ Triple Buffer V2.0 ] ::::

udragon

Jul 8, 2003 at 4:58 AM

You can download SGI''s STL version at :

http://www.sgi.com/tech/stl/

It produces a lot less warnings, is thread save and it''s internally more clean.
(It doesn''t produce UMR''s like Microsofts implementation does )

Happy coding !

U''dragon

NOTE :

Make sure if you use it in a MS-Visual Studio project to add the SGI/Stl include-path as the top-most include dir in the directory options (tools->options->directories)

Fruny

Jul 8, 2003 at 5:28 AM

a) you have an infinite loop in your unary operator.
b) you should not try to replace the hash_compare class, but pass it a custom comparison predicate.


#include <iostream>
#include <hash_map>
#include <functional>

struct pchar_less
   : std::binary_function<char*, char*, bool>
{
   inline bool operator()( const first_argument_type& first, 
                           const second_argument_type second ) const
   {
      return strcmp(first,second) < 0;  // first < second

   }
};

typedef stdext::hash_compare<char*,pchar_less> pchar_hash_compare;
typedef stdext::hash_map<char*, int, pchar_hash_compare> pchar_int_hash;

pchar_int_hash MyHash;

int main()
{
   MyHash["abcd"] = 10;
   MyHash["abce"] = 20;

   std::cout << MyHash["abcd"] << std::endl;

   return 0;
}

Before VS.NET 2003, hash_map was in std, even though it is not (yet) standard. Change the code accordingly.

Additionally, I strongly suggest you use std::string instead of char* as the map''s key. It will safe you much grief.

C-Junkie

Jul 8, 2003 at 10:54 AM

i strong suggest you don''t use microsoft''s hash_map implementation.

I would be STRONGLY surprised if that''s the one that ends up becoming part of the standard.

my hash_map''s are usually just

struct hash { ... } // specialization for hashing strings

struct equal_to { ... } // specialization for comparing strings

hash_map maps;

which is obviously a different implementation. and the one i''ve found most prevalent...

daerid

Jul 8, 2003 at 12:11 PM

I had tried using SGI''s STL at one point with VC6, and it died.
Anybody know how well it works with VS7.1?

Zipster

Jul 8, 2003 at 4:27 PM

It worked great for me in VC6 at work. Must be your mojo

udragon

Jul 10, 2003 at 1:51 AM

I've been using it with VC++ 6 for 3 years now.

What's the exact problem you got ?

U'dragon

[edited by - udragon on July 10, 2003 2:52:08 AM]

IFooBar

Jul 10, 2003 at 7:16 AM

quote:
Original post by Fruny
a) you have an infinite loop in your unary operator.

Yes I do. forgot "str++". It was correct in the original though.

quote:
Original post by Fruny
b) you should not try to replace the hash_compare class, but pass it a custom comparison predicate.

If I do that then the hash key dosnt get hashed properly. It just gets cast to a size_t. So I would have make the function
"operator size_t ( const char* p );" Either that or me no get what you're saying.

quote:

Before VS.NET 2003, hash_map was in std, even though it is not (yet) standard. Change the code accordingly.

ok. thanks

quote:

Additionally, I strongly suggest you use std::string instead of char* as the map's key. It will safe you much grief

Actually thats what I did at first. But the framerate seems to increase dramatically if I use char pointers instead. In the main game loop all I was doing was

Texture* p1 = TextureMgr["Font.tga"];
Texture* p2 = TextureMgr["Ariel"];

Blit( x, y, p1 );
Blit( x, y, p2 );

When I uses std::string as the key I would get an ok frame rate, then when i used const char* instead, the frame rate shot up 10 times higher.

thanks for replies

[edit] quote insanity [/edit]

:::: [ Triple Buffer V2.0 ] ::::

[edited by - ifoobar on July 10, 2003 8:18:46 AM]

Fruny

Jul 10, 2003 at 7:44 AM

quote:

If I do that then the hash key dosnt get hashed properly. It just gets cast to a size_t. So I would have make the function
"operator size_t ( const char* p );" Either that or me no get what you''re saying.

Have you tried the code I gave you ?

I created a predicate intended to compare char*-based strings, and then use with in the hash_compare template to produce a Traits parameter of the form hash_map needs, including typedefs and stuff your class doesn''t provide.

quote:

When I uses std::string as the key I would get an ok frame rate, then when i used const char* instead, the frame rate shot up 10 times higher.

Better a slower solution that works than a fast one which doesn''t

Having your graphic system rely on strings (whatever their kind) is not a good idea anyway, you''d go faster with integer IDs.

Anyway, size_t is an integral type, usually unsigned long int, and is the type of array offsets (32 bits on a ''32-bit platform'', 64 bits on a ''64-bit platform'' & so on). It is a perfectly valid type for a hashed key.

IFooBar

Jul 11, 2003 at 11:05 AM

quote:
Having your graphic system rely on strings (whatever their kind) is not a good idea anyway, you''d go faster with integer IDs.

heeeey! thanks for that. peh...something so simple and never even crossed my mind.

quote:

Anyway, size_t is an integral type, usually unsigned long int, and is the type of array offsets (32 bits on a ''32-bit platform'', 64 bits on a ''64-bit platform'' & so on). It is a perfectly valid type for a hashed key.

yes size_t is an integral type. And yes it is a valid type for a hashkey. However I think you missed my problem. The problem was that all the hash_compare class was doing was casting the KeyType to a size_t type without doing any hashing on it. SO I had to change the source code in xhash for it to actually call the unary operator on the key.

:::: [ Triple Buffer V2.0 ] ::::

Fruny

Jul 11, 2003 at 11:35 AM

Ah, well. If you''re using VC6, did you install all the service packs ? Did you patch the lib (see link in sig).

IFooBar

Jul 15, 2003 at 2:44 AM

Im using msvc7 the 2002 one.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.