C ++ unordered_map，使用char *作为键 [英] C++ unordered_map with char* as key
问题描述
尝试使用 unordered_map 时以 char * 为键（在Windows，I我使用VS 2010）。我知道我必须为 char * 定义自己的比较函数，它继承自 binary_function 。以下是示例程序。
I feel exhausted when trying to use the container unordered_map with char* as the key (on Windows, I am using VS 2010). I know that I have to define my own compare function for char*, which inherits from binary_function. The following is a sample 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;
}
我插入相同的C字符串 abc 两次并查找。第二次插入应该失败，并且在unordered_map中只有一个 abc 。
I insert the same C string abc twice and look it up. The second insertion should fail and there will be only one abc in the unordered_map. However, the output size is 3. It seems that the compare function does not work properly here.
此外，我得到另一个关于的奇怪结果，找到函数，通过运行程序多次，查找结果甚至更改！有时找到字符串 abc ，而找不到其他时间 abc ！
Moreover, I get another strange result about the find function, by running the program for many times, the finding result even changes! Sometimes the string abc is found, while the other times abc is not found!
任何人都可以帮助我吗？您的帮助非常感谢！
Could anyone help me on this? Your help is very much appreciated!
++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++ ++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
编辑：在我自己定义 char * 的哈希函数后，程序正常工作。完整的程序代码如下所示。非常感谢大家。
After defining a hash function for char* by my own, the program works properly. The full program code is listed below. Thank you all.
#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;
}
注意：使用 char *作为unordered_map或其他STL容器的密钥类型可能是危险的，一个安全的方式（似乎是唯一的方法）是：在主函数 new 或 malloc 在堆上的一个块（例如c字符串数组），并用c字符串填充它。将这些c字符串插入unordered_map。分配的内存块在主函数结尾（ delete 或 free ）释放。
Note: Using char* as the key type for an unordered_map or other STL containers may be dangerous, a safe way (seems to be the only way) is: in the main function, new or malloc a block (e.g. an array of c strings) on heap and fill it with c strings. Insert these c strings into unordered_map. The allocated block of memory is freed at the end of of main function (by delete or free).
推荐答案
您的比较器很好（虽然传递一个nullptr是未定义的，可能应该处理）
You comparator is fine (although passing a nullptr is undefined and probably should be handled)
散列， :: std :: tr1 :: hash< char *> 是散列指针，所以每个abc ）in a different bucket
The hash, ::std::tr1::hash<char*> is hashing off pointers so each "abc" goes (usually) in a different bucket
您需要编写自己的散列函数，以确保散列（abc）总是给出相同的答案
You need to write your own hash function that guarantees that hash("abc") always gives the same answer
现在 - 性能将会糟糕，但是有一个返回0的哈希值 - 你应该看到第二个abc匹配第一个
For now - performance will be terrible, but have a hash that returns 0 - and you should see the second "abc" match the first
根据注释 - 使用 std :: string 简化内存管理并提供一个库支持的哈希和比较器，所以只需 std :: unordered_map< std ::字符串，X> 将工作。这也意味着删除无序映射后，所有字符串将被释放。你甚至可以从堆栈中的字符数组安全地实例化 std :: strings 。
As per comments - using std::string simplifies memory management and provides a library supported hash and comparator, so just std::unordered_map<std::string, X> will work. This also means that upon deletion of the unordered map all strings will be deallocated for you. You can even instantiate the std::strings from char arrays on the stack safely.
如果你还想使用 char * 然后你仍然需要你自己的比较器和哈希，但你可以使用 std :: shared_ptr 来管理为你的内存（不使用堆栈实例 - 做一个 new char [] ）
然后你会有一个 std :: unordered_map ; shared_ptr< char *> ;, X> ，但后来没有内存泄漏的并发症。
If you still want to use char * then you will still need your own comparator and hash, but you can use std::shared_ptr to manage the memory for you (do not use stack instances - do a new char[])
you will then have a std::unordered_map<shared_ptr<char *>, X> but have no complications later from memory leaks.
如果你还想使用 char * 你是在正确的轨道，但重要的是你使用内存泄漏工具，如purify或valgrind，以确保你真正有所有的内存管理控制。 （这对任何项目都是一个好主意）
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 truly have all the memory management under control. (This is generally a good idea for any project)
最后，应该避免全局变量。
Finally, global variables should be avoided.
这篇关于C ++ unordered_map，使用char *作为键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
