C++ unordered_map 以 char* 为键

C++ unordered_map with char* as key

提问by Bloodmoon

I feel exhausted when trying to use the container unordered_mapwith 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.

尝试使用容器时，我感到筋疲力尽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;
} 

I insert the same C string abctwice and look it up. The second insertion should fail and there will be only one abcin the unordered_map. However, the output size is 3. It seems that the compare function does not work properly here.

我将相同的 C 字符串插入abc两次并查找。第二次插入应该失败，并且abcunordered_map 中只有一个。但是输出大小是3，这里好像比较功能不能正常工作。

Moreover, I get another strange result about the findfunction, by running the program for many times, the finding result even changes! Sometimes the string abcis found, while the other times abcis not found!

而且，我得到了另一个关于find函数的奇怪结果，通过多次运行程序，查找结果甚至发生了变化！有时abc找到字符串，而其他时候abc找不到！

Could anyone help me on this? Your help is very much appreciated!

有人可以帮我吗？非常感激你的帮助！

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

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

Edit: After defining a hash function for char*by my own, the program works properly. The full program code is listed below. Thank you all.

编辑：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;
}

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, newor malloca 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 deleteor free).

注意：使用char* 作为 unordered_map 或其他 STL 容器的键类型可能是危险的，一种安全的方法（似乎是唯一的方法）是：在主函数中，new或malloc在堆上的块（例如 c 字符串数组）并用c字符串填充它。将这些 c 字符串插入 unordered_map。分配的内存块在 main 函数结束时被释放（bydelete或free）。

采纳答案by Glenn Teitelbaum

You comparator is fine (although passing a nullptr is undefined and probably should be handled)

你的比较器很好（虽然传递一个 nullptr 是未定义的，可能应该被处理）

The hash, ::std::tr1::hash<char*>is hashing off pointers so each "abc" goes (usually) in a different bucket

散列，::std::tr1::hash<char*>正在散列指针，因此每个“abc”（通常）进入不同的存储桶

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

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

For now - performance will be terrible, but have a hash that returns 0 - and you should see the second "abc" match the first

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

As per comments - using std::stringsimplifies 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 mapall strings will be deallocated for you. You can even instantiate the std::stringsfrom char arrays on the stack safely.

根据评论 - usingstd::string简化了内存管理并提供了一个支持哈希和比较器的库，所以就std::unordered_map<std::string, X>可以了。这也意味着在删除unordered map所有字符串时将为您解除分配。您甚至可以std::strings安全地实例化堆栈上的 from char 数组。

If you still want to use char *then you will still need your own comparator and hash, but you can use std::shared_ptrto 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 *那么您仍然需要自己的比较器和散列，但是您可以使用它std::shared_ptr来为您管理内存（不要使用堆栈实例 - 做 a new char[]）您将有一个std::unordered_map<shared_ptr<char *>, X>但没有内存泄漏的并发症.

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)

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

Finally, global variables should be avoided.

最后，应避免使用全局变量。

回答by Jeff

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

像上面一样使用字符指针作为键几乎肯定不是您想要做的。

STL containers deal with stored values, in the case of std::unordered_map<char *, unsigned int, ...>, you are dealing with pointers to c strings, which may not even be around on subsequent insertion/removal checks.

STL 容器处理存储的值，在这种情况下std::unordered_map<char *, unsigned int, ...>，您正在处理指向 c 字符串的指针，在随后的插入/删除检查中甚至可能不会出现。

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

请注意，您my_unordered_map是一个全局变量，但您正在尝试插入本地字符数组 a、b 和 c。你有什么期望你的比较函数my_equal_to()来strcmp()当插入的C字符串的范围掉下来？（你突然有指向随机垃圾的键，可以与新插入的未来值进行比较。）

It is important that STL map keys be copyable values that cannot have their meanings changed by external program behavior. You should almost certainly use std::stringor similar for your key values, even if their construction seems wasteful to you at first glance.

重要的是 STL 映射键是可复制的值，它们的含义不能被外部程序行为改变。您几乎肯定应该std::string为您的关键值使用或类似，即使它们的构造乍一看对您来说似乎是浪费。

The following will work exactly as you intend things to work above, and is vastly 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;
}

回答by Lucas S

When you define something such as "abc"it get assigned a const char*. Every time that you write "abc"within your program there is going to be a new memory alocated. So:

当您定义诸如“abc”之类的内容时，它会被分配一个 const char*。每次在程序中写入“abc”时，都会分配一个新的内存。所以：

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

Will always return false because new memory is alocated each time "abc"is wrriten (sorry if I sound a bit repetitive).

将始终返回 false，因为每次写入“abc”时都会分配新的内存（对不起，如果我听起来有点重复）。