unordered_map 的正确值

Question

我有一组字符串，我必须将它们放入哈希 table 中并检索它的字谜。我选择 unordered_map 因为它是 C++ 中的内置哈希 table。字符串如下，

cat, act, art, tar, rat... etc..

现在我使用按字母顺序排序的单词作为键，使用无序单词的向量作为值。此实现在插入时需要花费大量时间。这是满足要求的最佳实现方式，还是我可以使用更省时的方式？

    std::tr1::unordered_map<std::string, std::vector<std::string>> map;
    if(map.find(sortedWord) == map.end()){
        std::vector<std::string> temp;
        temp.push_back(word);
        map.insert(make_pair(sortedWord, temp));
    }else{
        map.find(sortedWord)->second.push_back(word);
    }

Answer 1

你让事情变得比必要的复杂得多，而且在这个过程中你也通过以下方式减慢了速度：

两次搜索密钥，并且
当你有一个新密钥时复制一个矢量（包含单词）。其实大概是复制了两次。

以下代码适用于 C++11，我很确定它适用于 tr1:

/* Name of map changed because I don't like to use "map"
 * or "string" as variable names */
wordMap[sortedWord].push_back(word);

如果 sortedWord 不存在于映射中，则 wordMap[sortedWord] 将使用默认构造的 std::vector<std::string>> 插入它。所以无论 sortedWord 是否存在，新词都可以附加到下标返回的值上。

Answer 2

只是为了提供另一种解决方案，您可以使用具有自定义哈希算法和相等比较的 C++11 std::unordered_multiset。

自定义哈希算法可以简单地将每个字符的哈希值与交换运算结合起来，比如按位异或，这样所有的字谜都具有相同的哈希值。

自定义相等比较可以用std::is_permutation等同所有的字谜

struct AnagramHash
{
    typedef std::string argument_type;
    typedef std::hash<char>::result_type result_type;

    result_type operator()(const argument_type& s) const
    {
        std::hash<char> char_hash;
        result_type result = 0;

        for (const auto& x : s)
        {
            result ^= char_hash(x);
        }

        return result;
    }
};

‖

struct AnagramEqual
{
    typedef bool result_type;
    typedef std::string first_argument_type;
    typedef std::string second_argument_type;

    result_type operator()(const first_argument_type& lhs, const second_argument_type& rhs) const
    {
        if (lhs.size() == rhs.size())
            return std::is_permutation(std::begin(lhs), std::end(lhs), std::begin(rhs));
        else
            return false;
    }
};

‖

int main()
{
    std::unordered_multiset<std::string, AnagramHash, AnagramEqual> anagrams;

    anagrams.insert("arc");
    anagrams.insert("rac");
    anagrams.insert("car");

    anagrams.insert("H2O");
    anagrams.insert("2OH");

    auto range = anagrams.equal_range("car");
    for (auto it = range.first ; it != range.second ; ++it)
    {
        cout << *it << endl;
    }

    cout << endl;

    range = anagrams.equal_range("HO2");
    for (auto it = range.first ; it != range.second ; ++it)
    {
        cout << *it << endl;
    }
}

unordered_map 的正确值

Proper value for unordered_map

c++

algorithm

containers

data-structures