Найти unordered_map элементы, выполнив поиск значений элементов ключевой структуры

Question

У моего приложения есть карта, подобная std::unordered_map<my_struct *, std::string> с десятками тысяч элементов. my_struct имеет несколько строк, векторов и других элементов.

На каком-то этапе мне нужно построить новый my_struct, а затем искать элемент карты, у которого есть ключ my_struct, имеющий те же значения элементов, что и в моем объекте, построенном в последнее время.

Только способ, которым я мог заставить его работать, был с дополнительным числовым элементом «ID» и заменой std::hash на пользовательский предикат, который просто возвращает его из своего метода operator(). Однако это не решение. Я не мог знать этот идентификатор, когда искал какой-то элемент карты.

Это тестовый код, который я написал (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; 
} 

Я даже подумал, что замена key_equal на unordered_map конструктор для моего собственного предиката может решить, но это также не работает (я не получайте ни одного из значений карты в качестве вывода). 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 ? 

выглядит, как он останавливается на первом элементе ...

Первая линия выхода очень странно, кажется, даже если я не пытаюсь найти или получить доступ к любому элементу (комментарий 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, но вы должны иметь что-то, что организовано тем, что вы хотите найти, или вы собираетесь выполнять исчерпывающий поиск.