Jump to content
  • Advertisement

Archived

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

IFooBar

bug in std::hash_map?

This topic is 5485 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
Advertisement
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
I had tried using SGI''s STL at one point with VC6, and it died.
Anybody know how well it works with VS7.1?

Share this post


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

Share this post


Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!