如何使用带有不区分大小写的unicode字符串作为键的hash_map？

Question

我对 STL 很陌生，对 C++ 也很陌生。我试图获得相当于 .NET Dictionary(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) 为 false，且 my_hash_compare()(b,a) 为 false，则 a == b。显然我所写的内容并非如此，在这种情况下你就不走运了。

作为替代方案（在任何情况下都可能更有效），您可以将所有键推送到常见情况，然后再在地图中使用它们。不区分大小写的比较比常规字符串比较的成本更高。不过，有一些与此相关的 Unicode 陷阱我永远记不清了。也许你必须转换->小写->大写，而不只是 ->大写或类似的东西，以避免某些语言或标题字符中出现一些令人讨厌的情况。有人吗？

另外，正如其他人所说，您可能并不真正希望 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 是一个指向以 null 结尾的 unicode 字符数组的指针，在这种情况下可能不是您想要的。请改用 basic_string 的 wstring 特化。

对于不区分大小写的情况，您需要在插入和搜索之前将键转换为全部大写或全部小写。至少我认为你无法以其他方式做到这一点。