通過搜索關鍵結構的成員值來查找unordered_map元素

Question

我的應用程序有一個類似std::unordered_map<my_struct *, std::string>的地圖，有幾十個元素。 my_struct有一些字符串，向量和其他類型的成員。

在某個步驟中，我需要構建一個新的my_struct，然後查找具有與我最近的構建對象相同成員值的關鍵my_struct的地圖元素。

唯一能讓它工作的方式是使用額外的數字「ID」成員，並用自定義謂詞替換std::hash，該自定義謂詞僅從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我自己的謂語可以解決這個問題，但也不能正常工作（我沒有得到地圖的值作爲輸出）。該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>。

上面的代碼讓我來代替使用默認key_equal的test_key_comp時輸出如下：

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

看起來它停止的第一元素...

首頁輸出線是非常奇怪的，它出現即使我不試圖找到或訪問任何元素（註釋std::cout行main()）。

我也嘗試使用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，但是你必須擁有一些你想要搜索的東西，或者你將要做一個詳盡的搜索。