使用char*作为键的C++ unordered_map

Question

尝试使用容器时,我感到筋疲力尽unordered_map与char*作为键(在Windows中,我使用VS 2010).我知道我必须定义自己的比较函数char*,它继承自binary_function.以下是示例程序.

#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两次并查找它.第二次插入失败,abcunordered_map中只有一个.但是,输出大小为3.似乎比较功能在这里不能正常工作.

而且,我得到了关于该find功能的另一个奇怪的结果,通过多次运行程序,发现结果甚至改变了!有时abc找到字符串,而其他时间abc找不到!

有人可以帮我吗？非常感激您的帮忙!

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

编辑:在char*我自己定义哈希函数后,程序正常工作.完整的程序代码如下所示.谢谢你们.

#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容器的键类型可能是危险的,一种安全的方式(似乎是唯一的方法)是:在main函数中,new或者malloc在堆上的块(例如c字符串数组)并用c字符串填充它.将这些c字符串插入unordered_map.分配的内存块在main函数结束时释放(by delete或free).

Answer 1

你的比较器很好（尽管传递 nullptr 是未定义的，可能应该处理）

哈希，::std::tr1::hash<char*>对指针进行哈希处理，因此每个“abc”（通常）位于不同的存储桶中

您需要编写自己的哈希函数，以保证 hash("abc") 始终给出相同的答案

现在 - 性能会很糟糕，但是有一个返回 0 的哈希 - 你应该看到第二个“abc”与第一个匹配

根据评论 - 使用std::string简化了内存管理并提供了支持哈希和比较器的库，所以就std::unordered_map<std::string, X>可以工作。这也意味着删除后unordered map所有字符串都将被释放。您甚至可以std::strings安全地实例化堆栈上的 char 数组。

如果您仍然想使用，char *那么您仍然需要自己的比较器和哈希，但是您可以使用它来std::shared_ptr为您管理内存（不要使用堆栈实例 - 执行 a new char[]），然后您将有一个std::unordered_map<shared_ptr<char *>, X>，但以后不会因内存泄漏而出现并发症。

如果您仍然想使用char *，那么您就走在正确的轨道上，但重要的是您使用 purify 或 valgrind 等内存泄漏工具来确保您真正控制了所有内存管理。（这对于任何项目来说通常都是一个好主意）

最后，应该避免全局变量。