通过搜索键结构的成员值查找 unordered_map 个元素

Question

我的应用程序有一个类似 std::unordered_map<my_struct *, std::string> 的地图，其中包含成千上万个元素。 my_struct 有一些字符串、向量和其他类型的成员。

在某些步骤中，我需要构建一个新的 my_struct，然后查找以 my_struct 作为键的地图元素，其成员值与我最近构建的对象中的值相同。

我唯一能让它工作的方法是使用一个额外的数字 "ID" 成员，并将 std::hash 替换为自定义谓词，即 returns 它来自其 operator() 方法。然而，这不是解决方案。在查找地图的某些元素时，我无法知道该 ID。

这是我写的测试代码(test_key = my_struct):

#include <unordered_map>
#include <string>
#include <iostream>

struct test_key
{
        std::size_t id; //can't exist in my application
        std::string test_str1;
        std::string test_str2;
        unsigned int test_uint;

        test_key(std::size_t id_, std::string test_str1_, std::string test_str2_, unsigned int test_uint_)
                : id(id_), test_str1(test_str1_), test_str2(test_str2_), test_uint(test_uint_)
        {}
};

struct test_key_hasher
{
        std::size_t operator() (test_key* const& tst_k) const
        {
                return tst_k->id;
        }
};


int main()
{
        std::unordered_map<test_key *, std::string, test_key_hasher> values;
        test_key *tst_k1, *tst_k2, *tst_k3, *tst_k4, *tst_lk;

        tst_k1 = new test_key(1, "something 11", "something 12", 1112);
        tst_k2 = new test_key(2, "something 21", "something 22", 2122);
        tst_k3 = new test_key(3, "something 31", "something 32", 3132);
        tst_k4 = new test_key(4, "something 41", "something 42", 4142);

        values.emplace(tst_k1, "first thing");
        values.emplace(tst_k2, "second thing");
        values.emplace(tst_k3, "third thing");
        values.emplace(tst_k4, "fourth thing");

        tst_lk = new test_key(3, "something 31", "something 32", 3132); //there is no way I could know ID 3 here

        std::cout << values[tst_lk] << std::endl; //Expected output: third thing

        delete tst_k1;
        delete tst_k2;
        delete tst_k3;
        delete tst_k4;
        delete tst_lk;
}

我什至认为在 unordered_map 构造函数上为我自己的谓词替换 key_equal 可以解决它，但这也行不通（我得到 none 地图的值作为输出).我写的key_equal替换谓词是：

struct test_key_comp
{
        bool operator() (test_key* const& tst_k1, test_key* const& tst_k2) const
        {
                //debug
                std::cout << tst_k1->test_str1 << " == " << tst_k2->test_str1 << " ?" << std::endl;

                return tst_k1->test_str1 == tst_k2->test_str1
                        && tst_k1->test_str2 == tst_k2->test_str2
                        && tst_k1->test_uint == tst_k2->test_uint;
        }
};

然后我的地图看起来像 std::unordered_map<test_key *, std::string, std::hash<test_key *>, test_key_comp>。

上面的代码在使用 test_key_comp 代替默认值 key_equal 时给出了以下输出：

something 21 == something 11 ?
something 31 == something 11 ?

看起来它停在第一个元素上...

第一个输出行很奇怪，即使我不尝试查找或访问任何元素它也会出现（在 main() 上评论 std::cout 行）。

我也尝试过使用 find() 方法，但结果与 operator[] 和 at() 相同。

问题：关于为什么它不起作用以及我应该如何对其进行编码以快速有效地完成我想完成的事情有什么建议吗？

我想避免遍历所有元素，因为会有很多元素（成千上万...）并且这看起来不是最有效和最快的方法。

额外问题：也许我应该使用从 test_key 的成员值构建的字符串作为地图的键？我知道这会更容易编码，但它会更高效、更快吗？ test_key/my_struct 的实际实现有 std::map<std::string, std::string>s、std::vector<std::string>s 和许多其他类型的成员（已经有很多工作来比较其中两个结构）和将它全部放在一个字符串中很难构建和解析...我知道我必须对其进行基准测试，但我想得到一些提示。

Answer 1

您想通过散列以外的其他方式在散列映射中高效地查找某些内容吗？他们不是这样工作的。

您需要选择另一种数据结构 -- 一种可以按您要搜索的内容排序的数据结构。它可以是一个独立的数据结构，也可以是一个并行的数据结构——可能与您的 unordered_map 相关，但您必须拥有按您要搜索的内容组织的内容，否则您将进行详尽的搜索搜索。

通过搜索键结构的成员值查找 unordered_map 个元素

Find unordered_map elements by searching for key struct's members values

c++

lookup

unordered-map