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 дважды и посмотрите. Вторая вставка должна потерпеть неудачу и будет только одна abc в unordered_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 может быть опасным, безопасный способ (кажется, единственный) заключается в следующем: в основной функции new или же malloc блок (например, массив строк c) в куче и заполнить его строками c. Вставьте эти строки c в unordered_map. Выделенный блок памяти освобождается в конце основной функции ( delete или же free ).

Answer 1

С компаратором все в порядке (хотя передача nullptr не определена и, вероятно, должна быть обработана)

Хеш, ::std::tr1::hash<char*> хэширует указатели, поэтому каждый "abc" идет (обычно) в отдельном ведре

Вам нужно написать свою собственную хеш-функцию, которая гарантирует, что хеш ("abc") всегда дает один и тот же ответ

На данный момент - производительность будет ужасной, но есть хеш, который возвращает 0 - и вы должны увидеть, что второй "abc" соответствует первому

Согласно комментариям - используя std::string упрощает управление памятью и предоставляет библиотеку, поддерживающую хэш и компаратор, так что просто std::unordered_map<std::string, X> буду работать. Это также означает, что после удаления unordered map все строки будут освобождены для вас. Вы даже можете создать экземпляр std::strings из массивов символов в стеке безопасно.

Если вы все еще хотите использовать char * тогда вам все еще понадобится ваш собственный компаратор и хеш, но вы можете использовать std::shared_ptr управлять памятью для вас (не используйте экземпляры стека - сделайте new char[]) тогда у вас будет std::unordered_map<shared_ptr<char *>, X> но не будет никаких осложнений позже от утечек памяти.

Если вы все еще хотите использовать char * вы на правильном пути, но важно, чтобы вы использовали инструмент утечки памяти, такой как Очистить или Valgrind, чтобы убедиться, что вы действительно под контролем все управление памятью. (Это вообще хорошая идея для любого проекта)

Наконец, глобальных переменных следует избегать.

Answer 2

(Ответ для современного С++, для людей, которые все еще натыкаются на этот вопрос)

В наши дни, если вы используете C++17 или выше, вы можете использовать std::string_view в качестве ключа в unordered_map.

std::string_view хранит только ссылку на необработанные данные char* вместо их копирования, что позволяет избежать копирования, когда вы уверены, что необработанные данные char* переживут unordered_map.

Однако, в отличие от char*, std::string_view реализует различные методы и операторы, такие как std::hash, что делает его полезным во многих других местах.

      std::unordered_map<std::string_view, unsigned int> my_map;
my_map["some literal"] = 123;
printf("%d\n", my_map["some literal"]);

В приведенном выше коде я помещаю в карту только строковые литералы, что безопасно. Будьте осторожны, помещая другие вещи на карту с ключами string_view — вы несете ответственность за то, чтобы они не были уничтожены до того, как карта!

Answer 3

Использование указателя символа в качестве клавиши, как вы выше, почти наверняка не то, что вы хотите сделать.

Контейнеры STL имеют дело с сохраненными значениями, в случае std::unordered_map<char *, unsigned int, ...>, вы имеете дело с указателями на строки c, которых может даже не быть при последующих проверках вставки / удаления.

Обратите внимание, что ваш my_unordered_map является глобальной переменной, но вы пытаетесь вставить локальные массивы символов a, b и c. Что вы ожидаете, что ваша функция сравнения my_equal_to() в strcmp() когда вставленные строки c выпадают из области видимости? (У вас внезапно появляются ключи, указывающие на случайный мусор, который можно сравнить с вновь вставленными будущими значениями.)

Важно, чтобы ключи карты STL были копируемыми значениями, значения которых не могут быть изменены внешним поведением программы. Вы должны почти наверняка использовать std::string или аналогичные для ваших ключевых ценностей, даже если их конструкция кажется вам расточительной на первый взгляд.

Следующее будет работать именно так, как вы намереваетесь, и намного безопаснее:

#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 4

Когда вы определяете что-то вроде "abc", ему присваивается const char*. Каждый раз, когда вы пишете "abc" в вашей программе, будет выделяться новая память. Так:

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

Всегда будет возвращать false, потому что новая память выделяется каждый раз, когда пишется "abc" (извините, если я звучу немного повторяющимся).