具有char *键的C ++ unordered_map产生意外行为 [英] C++ unordered_map with char* key produces unexpected behavior
问题描述
我试图使用unordered_map将char *键散列为整数值。在编写自定义函子以哈希并比较char *之后,无序映射似乎可以工作。但是,我最终注意到,哈希有时会返回错误的结果。我创建了一个测试项目来重现该错误。下面的代码创建一个带有char *键和自定义函子的unordered_map。然后,它将运行1000次循环并记录发生的任何哈希错误。我想知道函子是否有问题,或者问题出在unordered_map之内。任何帮助,将不胜感激。谢谢!
I attempted to use an unordered_map to hash a char* key to an integer value. After writing custom functors to hash and compare char*, the unordered map appeared to work. However, I eventually noticed that the hash would occasionally return incorrect results. I created a test project to reproduce the error. The code below creates an unordered_map with a char* key and custom functors. It then runs 1000x cycles and records any hash errors that occurred. I am wondering if there is something wrong with my functors, or if the problem lies within unordered_map. Any help would be appreciated. Thanks!
#include <cstdlib>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <tr1/unordered_map>
using namespace std;
//These varaibles are just used for printing the status.
static const char* c1;
static const char* c2;
static int cmpRet;
static int cmpVal;
static const char* hashChar;
static size_t hashVal;
// Character compare functor.
struct CmpChar {
bool operator()(const char* s1, const char* s2) const {
c1 = s1;
c2 = s2;
cmpVal = strcmp(s1, s2);
cmpRet = (cmpVal == 0);
return cmpRet;
}
};
// Hash functor.
struct HashChar {
size_t operator()(const char* str) const {
hashChar = str;
size_t hash = 0;
int c;
while (c = *str++)
hash = c + (hash << 6) + (hash << 16) - hash;
hashVal = hash;
return hash;
}
};
void printStatus() {
printf("'%s' was hashed to: '%lu'\n", hashChar, hashVal);
printf("strcmp('%s','%s')='%d' and KeyEqual='%d'\n", c1, c2, cmpVal, cmpRet);
}
int main(int argc, char** argv) {
// Create the unordered map.
tr1::unordered_map<const char*, int, HashChar, CmpChar > hash_map;
hash_map["apple"] = 1;
hash_map["banana"] = 2;
hash_map["orange"] = 3;
// Grab the inital hash value of 'apple' to see what it hashes to.
char buffer[256];
bzero(buffer, sizeof (buffer));
strcpy(buffer, "apple");
if (hash_map[buffer] == 1) {
printf("First hash: '%s'=1\n", buffer);
}
printStatus();
// Create a random character
srand((unsigned int) time(NULL));
char randomChar = (rand() % 26 + 'a');
// Use the hash 1000x times to see if it works properly.
for (int i = 0; i < 1000; i++) {
// Fill the buffer with 'apple'
bzero(buffer, sizeof (buffer));
strcpy(buffer, "apple");
// Try to get the value for 'apple' and report an error if it equals zero.
if (hash_map[buffer] == 0) {
printf("\n****Error: '%s'=0 ****\n", buffer);
printStatus();
}
// Fill the buffer with a random string.
bzero(buffer, sizeof (buffer));
buffer[0] = randomChar;
buffer[1] = '\0';
// Hash the random string.
// ** Taking this line out removes the error. However, based on the functors
// it should be acceptable to reuse a buffer with different content.
hash_map[buffer];
// Update the random character.
randomChar = (rand() % 26 + 'a');
}
printf("done!\n");
return EXIT_SUCCESS;
}
推荐答案
在容器中使用char *,因为char *不会像您希望的那样被复制。
You must be really careful when using char* in containers, as the char* won't be copied as you may hope.
通过使用unordered_map的operator []作为密钥,地图不是您想要的字符串。
By using the operator[] of unordered_map what is used as the key in the map is not the string you want.
operator []应该将密钥插入地图,并通过调用默认构造函数将其复制(请参见参考),在这种情况下,它将很简单复制缓冲区[0]。
operator[] is supposed to insert the key into the map, copying it invoking the default constructor (see the reference), in this case, it will simply copy buffer[0].
因此,此后,您的方法CmpChar将具有奇怪的行为,因为它将在键中读取的下一个字节可以是任意值。
So afterwards, your method CmpChar will have a strange behaviour, as the next bytes it'll read in the keys can be anything.
如果使用字符串objetcs,则不会出现此类问题。
You would not have such problems if using string objetcs.
这篇关于具有char *键的C ++ unordered_map产生意外行为的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!