Как использовать hash_map с нечувствительной к регистру строкой юникода для ключа?

Question

Я очень плохо знаком с STL и довольно плохо знаком с C ++ в целом.Я пытаюсь получить эквивалент .NET Dictionary<string, value>(StringComparer.OrdinalIgnoreCase), но в C ++.Это примерно то, что я пытаюсь:

stdext::hash_map<LPCWSTR, SomeStruct> someMap;
someMap.insert(stdext::pair<LPCWSTR, SomeStruct>(L"a string", struct));
someMap.find(L"a string")
someMap.find(L"A STRING")

Проблема в том, что ни одна операция поиска обычно не работает (она возвращает someMap.end()).Кажется, иногда это работает, но в большинстве случаев это не так.Я предполагаю, что хеш-функция, используемая hash_map, хэширует адрес памяти строки вместо содержимого самой строки, и почти наверняка не учитывает регистр.

Как получить словарную структуру, которая использует ключи без учета регистра и может хранить мою собственную структуру?

Спасибо.

Answer 1

Документация hash_map, на которую вы ссылаетесь, указывает, что вы можете указать свой собственный класс черт в качестве третьего параметра шаблона. Это должно соответствовать тому же интерфейсу, что и hash_compare .

Сканируя документы, я думаю, что то, что вам нужно сделать, это то, что в основном заменяет использование StringComparer.OrdinalIgnoreCase, которое вы использовали в своем словаре:

struct my_hash_compare {
    const size_t bucket_size = 4;
    const size_t min_buckets = 8;
    size_t operator()(const LPCWSTR &Key) const {
        // implement a case-insensitive hash function here,
        // or find something in the Windows libraries.
    }
    bool operator()(const LPCWSTR &Key1, const LPCWSTR &Key2) const {
        // implement a case-insensitive comparison function here
        return _wcsicmp(Key1, Key2) < 0;
        // or something like that. There's warnings about
        // locale plastered all over this function's docs.
    }
};

Я обеспокоен тем, что в документах говорится, что функция сравнения должна быть полным порядком, а не строгим слабым порядком, как обычно для отсортированных контейнеров в стандартных библиотеках C ++. Если MS действительно означает общий порядок, то hash_map может полагаться на то, что он соответствует operator==. То есть они могут потребовать, чтобы, если my_hash_compare()(a,b) было ложным, а my_hash_compare()(b,a) ложным, то a == b. Очевидно, это не относится к тому, что я написал, и в этом случае вам не повезло.

В качестве альтернативы, которая в любом случае, вероятно, более эффективна, вы можете нажать все ключи в общем случае, прежде чем использовать их на карте. Сравнение без учета регистра более затратно, чем обычное сравнение строк. Есть какой-то юникод, связанный с тем, что я никогда не смогу вспомнить. Возможно, вам нужно преобразовать -> нижний регистр -> верхний регистр, а не просто -> верхний регистр или что-то в этом роде, чтобы избежать некоторых неприятных случаев на определенных языках или с символами заглавных букв. Кто-нибудь?

Также, как говорили другие люди, вы, возможно, не хотите, чтобы LPCWSTR использовался в качестве ключа. Это будет хранить указатели на карте, что означает, что любой, кто вставляет строку, должен убедиться, что данные, на которые он указывает, остаются действительными, пока они находятся в hash_map. В долгосрочной перспективе часто лучше, чтобы hash_map сохранял копию строки ключа, переданной в insert, и в этом случае вы должны использовать wstring в качестве ключа.

Answer 2

Здесь была дана отличная информация. Я собрал по кусочкам из ответов и соединил это:

#include "stdafx.h"
#include "atlbase.h"
#include <map>
#include <wchar.h>

typedef std::pair<std::wstring, int> MyPair;

struct key_comparer
{
    bool operator()(std::wstring a, std::wstring b) const
    {
        return _wcsicmp(a.c_str(), b.c_str()) < 0;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    std::map<std::wstring, int, key_comparer> mymap;
    mymap.insert(MyPair(L"GHI",3));
    mymap.insert(MyPair(L"DEF",2));
    mymap.insert(MyPair(L"ABC",1));

    std::map<std::wstring, int, key_comparer>::iterator iter;
    iter = mymap.find(L"def");
    if (iter == mymap.end()) {
        printf("No match.\n");
    } else {
        printf("match: %i\n", iter->second);
    }
    return 0;
}

Answer 3

Если вы используете std::map вместо нестандартного hash_map, вы можете установить функцию сравнения, которая будет использоваться при выполнении двоичного поиска:

// Function object for case insensitive comparison
struct case_insensitive_compare
{
    case_insensitive_compare() {}

    // Function objects overloader operator()
    // When used as a comparer, it should function as operator<(a,b)
    bool operator()(const std::string& a, const std::string& b) const
    {
        return to_lower(a) < to_lower(b);
    }

    std::string to_lower(const std::string& a) const
    {
        std::string s(a);
        std::for_each(s.begin(), s.end(), char_to_lower);
        return s;
    }

    void char_to_lower(char& c) const
    {
        if (c >= 'A' && c <= 'Z')
            c += ('a' - 'A');
    }
};

// ...

std::map<std::string, std::string, case_insensitive_compare> someMap;
someMap["foo"] = "Hello, world!";
std::cout << someMap["FOO"] << endl; // Hello, world!

Answer 4

LPCWSTR - указатель на массив символов Юникод с нулевым символом в конце и, вероятно, не тот, который вам нужен в этом случае Вместо этого используйте wstring специализацию basic_string.

Для учета нечувствительности к регистру перед вставкой и поиском необходимо преобразовать ключи в верхний или нижний регистр. По крайней мере, я не думаю, что вы можете сделать это любым другим способом.