Sign in to follow this  
ArnoAtWork

hashmap

Recommended Posts

ArnoAtWork    138
Does anybody has problem with hashmap of STLport with VC7.1? I don't known why, but if I do a loop using iterator from beginning to the end of the map, it never stops... Moreover, the find function always returns the end of the map even if the string is used. Thanks very much.

Share this post


Link to post
Share on other sites
dalleboy    324
VC.NET and STLPort uses different implementations of hashmap, they use different Predicates. STLPort wants a predicate that returns equal(a, b) while VC.NET wants a pred that returns less(a, b)...

Share this post


Link to post
Share on other sites
dalleboy    324
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};

typedef std::hash_map<char*, int, std::hash<const char*>, eqstr> StringToIntHashMap;

A note on this code: Don't use char*, use std::string instead...

Share this post


Link to post
Share on other sites
ArnoAtWork    138
I don't know if it's the reason of the pb.

Why does an iterator set to the beginning of the map never reach the end(or do not valid the test [iterator == map.end()]) after a loop of ++ite? That never happens.

The only pb that i though was that the conversion string->integer was wrong. However, it seems correct....

Share this post


Link to post
Share on other sites
ArnoAtWork    138
Huumm, I am confused.

In STL implementation, I have seen that a fonction already exists to convert string to integer. When you do for example: map[txt]=(int)
you can see that the txt is converted to integer, so after that, it's just a simple map implementation to search, access,....

So, how does the operator == can be right?


Share this post


Link to post
Share on other sites
VolkerG    151
Quote:
Original post by ArnoAtWork
Huumm, I am confused.

In STL implementation, I have seen that a fonction already exists to convert string to integer. When you do for example: map[txt]=(int)
you can see that the txt is converted to integer, so after that, it's just a simple map implementation to search, access,....

So, how does the operator == can be right?

Now I'm confused. But I'll try to explain what happens.
- First, the hash for the key (in your case the string) is calculated.
- Then, for every element that has the same hash, the key (not only its hash value) of the element is compared with the key you supplied. Only for an exact match, find returns the iterator for the element.

How the map is implemented in detail is up the the STL implementor.

At what point are you confused?

Share this post


Link to post
Share on other sites
ArnoAtWork    138
For me a hash map converts the string to integer to store at the end a kind of map<int, something>.
So, I do not really understand why I have to give a char*==char* test because at the end, only integer representation of the text is used...

Share this post


Link to post
Share on other sites
VolkerG    151
But mapping from string to int may not be unique (the values that can be represented by an int is limeted, but not the number of different strings). Two different strings may produce the same hash, so you always have to compare the strings to make sure the key is really equal.

Share this post


Link to post
Share on other sites
VolkerG    151
Perhaps someone has a good link to the theory of hash maps for you, that could be of help. Can't find one in my bookmarks at the moment.
Perhaps this one.

Share this post


Link to post
Share on other sites
ArnoAtWork    138
I have tested, it is working. However data access still seems to fail...

Even, if text is converted to integer and even if I can find element with the find function, iteration fails.

This code leads to an infinite loop:



for(hash_map<X>::iterator it=hash.begin(); it!=hash.end(); ++it){
}



even if I have 1 or more elements in it.

Share this post


Link to post
Share on other sites
Zahlman    1682
Try checking the values of *it on successive iterations and see if any weird patterns crop up. (You might also want to output *hash.begin() and *hash.end() for reference.)

Share this post


Link to post
Share on other sites
ArnoAtWork    138
It seems that values of *it are also different from beginning to the end. However, the only problem seems to be the test it == hash.end() which always returns false...

Share this post


Link to post
Share on other sites
dalleboy    324
Try to start small: Test with std::hash_map<int>, does that work? Then try with std::hash_map<std::string>, does that work? Then try with std::hash_map<char*, int, std::hash<const char*>, eqstr>, does that work?

Share this post


Link to post
Share on other sites
ArnoAtWork    138
Baaaahhh, I've seen my mistake!

I used a char* for the hash key, but as soon as the program exited the function, the const char* was destroyed and of course, the key became unvalid....

I replaced the char* by std::string and adds the hash functions for them, and it is working perfectly.

But, the reason why invalid char* means a infinite loop with iterators ....

Thanks for all.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this