C ++ unordered_map with char * as key

Question

I feel exhausted when I try to use the unordered_map container with char* as the key (on Windows I use VS 2010). I know that I need to define my own comparison function for char* , which inherits from binary_function . The following is an example program.

 #include<unordered_map> #include <iostream> #include <string> using namespace std; template <class _Tp> struct my_equal_to : public binary_function<_Tp, _Tp, bool> { bool operator()(const _Tp& __x, const _Tp& __y) const { return strcmp( __x, __y ) == 0; } }; typedef unordered_map<char*, unsigned int, ::std::tr1::hash<char*>, my_equal_to<char*> > my_unordered_map; //typedef unordered_map<string, unsigned int > my_unordered_map; my_unordered_map location_map; int main(){ char a[10] = "ab"; location_map.insert(my_unordered_map::value_type(a, 10)); char b[10] = "abc"; location_map.insert(my_unordered_map::value_type(b, 20)); char c[10] = "abc"; location_map.insert(my_unordered_map::value_type(c, 20)); printf("map size: %d\n", location_map.size()); my_unordered_map::iterator it; if ((it = location_map.find("abc")) != location_map.end()) { printf("found!\n"); } return 0; } 

I insert the same line of C abc twice and look through it. The second insertion should fail, and there will be only one abc in unordered_map. However, the output size is 3. It seems that the comparison function does not work here.

In addition, I get another strange result about the find function, running the program many times, the search result even changes! Sometimes the string abc found, but other times abc not found!

Can someone help me with this? Your help is much appreciated!

++++++++++++++++++++++++++++++++++++++++++++++++++ +++ ++++++++++++++++++++++++++++++++++

Edit: after defining the hash function for char* its own, the program works correctly. The full program code is given below. Thanks to everyone.

 #include<unordered_map> #include <iostream> using namespace std; template <class _Tp> struct my_equal_to : public binary_function<_Tp, _Tp, bool> { bool operator()(const _Tp& __x, const _Tp& __y) const { return strcmp( __x, __y ) == 0; } }; struct Hash_Func{ //BKDR hash algorithm int operator()(char * str)const { int seed = 131;//31 131 1313 13131131313 etc// int hash = 0; while(*str) { hash = (hash * seed) + (*str); str ++; } return hash & (0x7FFFFFFF); } }; typedef unordered_map<char*, unsigned int, Hash_Func, my_equal_to<char*> > my_unordered_map; int main(){ my_unordered_map location_map; char a[10] = "ab"; location_map.insert(my_unordered_map::value_type(a, 10)); char b[10] = "abc"; location_map.insert(my_unordered_map::value_type(b, 20)); char c[10] = "abc"; location_map.insert(my_unordered_map::value_type(c, 20)); printf("map size: %d\n", location_map.size()); my_unordered_map::iterator it; if ((it = location_map.find("abc")) != location_map.end()) { printf("found!\n"); } return 0; } 

Note. Using char *, since the key type for unordered_map or other STL containers can be dangerous, the safe way (seems to be the only way): in the main function new or malloc block (for example, an array of strings c) in the heap and fill it with strings c. Insert these lines c in unordered_map. The allocated memory block is freed at the end of the main function (via delete or free ).

Answer 1

The comparator is fine (although the nullptr transmission is undefined and probably should be handled)

Hash, ::std::tr1::hash<char*> means hashing pointers, so each "abc" goes (usually) to another bucket

You need to write your own hash function, which ensures that the hash ("abc") always gives the same answer

At the moment - performance will be terrible, but has a hash that returns 0 - and you should see that the second "abc" matches the first

According to the comments, using std::string simplifies memory management and provides a hash and comparator supported by the library, so only std::unordered_map<std::string, X> will work. It also means that after deleting the unordered map all lines will be freed for you. You can even create arrays of std::strings from char on the stack.

If you still want to use char * , you still need your own comparator and hash, but you can use std::shared_ptr to manage the memory for you (don't use stack instances - execute new char[] ). then you will have std::unordered_map<shared_ptr<char *>, X> , but later there will be no complications after memory leaks.

If you still want to use char * , you are on the right track, but it is important that you use a memory leak tool like purify or valgrind to make sure that you really control all memory management. (This is generally a good idea for any project)

Finally, global variables should be avoided.

Answer 2

Using a char pointer as a key, as you above, is almost certainly not what you want to do.

STL containers are processed with stored values; in the case of std::unordered_map<char *, unsigned int, ...> you are dealing with pointers to c lines that may not even appear during subsequent insert / delete checks.

Note that your my_unordered_map is a global variable, but you are trying to insert local char a, b, and c arrays. What do you expect from the comparison function my_equal_to() to strcmp() when the inserted c lines fall out of scope? (You suddenly have keys that indicate random garbage that can be compared to newly inserted future values.)

It is important that the keys of the STL card are copied values ​​that cannot change their values ​​according to external programmatic behavior. You almost certainly use std::string or similar for your key values, even if their design seems wasteful at first sight.

The following will work just as you intend to work on it, and much safer:

 #include <unordered_map> #include <iostream> #include <string> using namespace std; // STL containers use copy semantics, so don't use pointers for keys!! typedef unordered_map<std::string, unsigned int> my_unordered_map; my_unordered_map location_map; int main() { char a[10] = "ab"; location_map.insert(my_unordered_map::value_type(a, 10)); char b[10] = "abc"; location_map.insert(my_unordered_map::value_type(b, 20)); char c[10] = "abc"; location_map.insert(my_unordered_map::value_type(c, 20)); cout << "map size: " << location_map.size() << endl; my_unordered_map::iterator it; if ((it = location_map.find("abc")) != location_map.end()) { cout << "found \"" << it->first << "\": " << it->second << endl; } return 0; } 

Answer 3

When you define something like "abc", it is assigned const char *. Each time you write "abc" in your program, a new memory will be allocated. So:

 const char* x = "abc"; const char* y = "abc"; return x==y; 

It will always return false, because new memory is allocated every time "abc" is a script (sorry if I repeat a little).