Пара unordered_map STL для поиска обоих

Question

Я хочу создать хэш-карту, чтобы я мог как-то искать обе части ключа. Скажем, у меня есть пара, и я хочу, чтобы это было ключом. Я не хотел бы искать точное {string, id}, но иногда для поиска int и иногда для строки, возможно ли это сделать?

Answer 1

Да, вы можете, std::map дает вам такие варианты.

Допустим, у вас есть std::map<std::string, int> example = {{"name1", 1},{"name2", id}}; // etc...

Используйте find для поиска ключа (то есть строки):

if (example.find("name2")!= example.end()) {
   // Success
}

Используйте для итерации карты и найдите ваше значение:

for(const auto& itr : example){
   if(itr.second == int_value) return true;
}

Или используйте этот класс, который я создал для вас:

template<class T, class K, class value_compare = std::equal_to<K>, class key_compare = std::less<T> >
class MyMap : public std::map<T, K>
{
    value_compare vc;
    key_compare kc;

    using my_iterator = typename std::map<T, K, key_compare>::iterator;

public:

    my_iterator find_value(const K val) {
        my_iterator itr = std::map<T, K>::begin();
        my_iterator map_end = std::map<T, K>::end();

        for (; itr != map_end; ++itr)
        {
            if (vc(itr->second, val)) return itr;
        }

        return itr;
    }

};

использовал его так же, как std::map, но теперь вы можете вызвать find_value и получить первый итератор, который указывает на пару карт. (если вам нужен список или другое возвращаемое значение, измените его)

Пример:

MyMap< std::string, int>  ss_map;

ss_map["aab"] = 1;
ss_map["aba"] = 2;
ss_map["aaa"] = 3;
ss_map["abb"] = 4;
ss_map["baa"] = 5;

auto itr = ss_map.find("abb"); // return iterator<pair<"abb",4>>

auto itr2 = ss_map.find_value(2); // return iterator<pair<"aba",2>>

Answer 2

Да, это возможно! Однако это не так полезно и имеет плохой дизайн.

Решение состоит в том, чтобы использовать пользовательский тип сравнения, который будет настраивать операцию сравнения. Если вам нужно одно поведение от компаратора, тогда вам нужен только свободный тип сравнения контекста, который делает все, что вы хотите.

Но если вы хотите изменить поведение извне карты по мере необходимости, вы будете использовать компаратор с контекст, который переживает карту

struct CompareContext
{
   bool id = false;
};

struct Comparer
{
   const CompareContext& ctx;

   using arg_t = std::pair<std::string, int>;

   Comparer(const CompareContext& ctx) : ctx{ ctx } {}

   bool operator()(const arg_t& first, const arg_t& second) const
   {
       if (ctx.id)
       {
           std::less<int> l;
           return l(first.second, second.second);
       }
       else
       {
           std::less<std::string> l;
           return l(first.first, second.first);
       }
   }

};


int main()
{
    CompareContext ctx;
    Comparer comp{ ctx };
    using key_t = Comparer::arg_t;
    using val_t = int;
    using map_t = std::map<key_t, val_t, Comparer>;

    map_t mp{ comp };

}

Еще один пример поиска с использованием строки или целочисленного значения ключа std::pair<std::string, int>

#include <map>
#include <iostream>

int main()
{
   using key_t = std::pair<std::string, int>;
   auto cmp = [](const key_t & first, const key_t& second)
   {
      std::less<int> li;
      if (li(first.second, second.second))
         return true;
      std::less<std::string> ls;
      return ls(first.first, second.first); 
   };

   using map_t = std::map<key_t, int, decltype(cmp)>;

   key_t key1{ "string1", 1 };
   key_t key2{ "string2", 2 };

   map_t mp{ cmp };
   mp.emplace(key1, 1);
   mp.emplace(key2, 2);

   key_t search_1{ "string1", 5 }; // match using string
   key_t search_2{ "string5", 2 }; // match using int
   key_t search_3{ "string3", 3 }; // doesn't exist

   auto it = mp.find(search_1); // search and if not exist returns an iterator to end
   if (it != mp.end())
      std::cout << "Found " << it->second << std::endl;

   auto val = mp[search_2];
   std::cout << "Found " << val << std::endl;

   val = mp[search_3]; // since not found a node will be created with key search_3
   std::cout << "Created a node with int = " << val << std::endl;

}

Обратите внимание, что std::map не выполняет поиск с использованием равенства lhs == rhs но сравнивается с меньшим и большим чем, поскольку он сортируется, и этот подход будет быстрее

С другой стороны std::unordered_map использует хеш (обычно std::hash) для проверки на равенство, поскольку это не так заказал.