Archived

This topic is now archived and is closed to further replies.

bug in std::hash_map?

This topic is 5264 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 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 ] ::::

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
std::hash_map isn''t part of the C++ standard. No wonder Microsoft didn''t bother to polish it''s implementation..

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites
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.


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Share this post


Link to post
Share on other sites
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 ] ::::

Share this post


Link to post
Share on other sites
Ah, well. If you''re using VC6, did you install all the service packs ? Did you patch the lib (see link in sig).


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Share this post


Link to post
Share on other sites