CODEWITHSUNDEEP
c++dictionaryhashmap
C. Cristi
C. Cristi

Reputation: 579

Pair unordered_map STL search for both

I want to create a hashmap that I can search for both part of the key somehow. Say I have a pair and I want this to be the key. I wouldn't like to search for the exact {string, id} but sometime to search for the int and sometime for the string, is it possible to do this?

Upvotes: 0

Views: 78

Answers (2)

Maor Dahan
Maor Dahan

Reputation: 392

Yes you can, the std::map give you those kind of options.

Lets say you have std::map<std::string, int> example = {{"name1", 1},{"name2", id}}; // etc...

Use find to search the key (i.e string):

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

Use for to iterate the map and find your value:

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

Or use this class I made for you:

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;
    }

};

used it the same as std::map except now you can invoke find_value and get the first iterator which point to the map pair. (if you want list or some other return value change it)

Example:

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>>

Upvotes: 0

dev65
dev65

Reputation: 1605

Yes it's possible ! However it's not that useful and has a bad design .

The solution is to use a custom compare type which will customize the comparing operation . If you want one behavior from the comparer then you only need a free context compare type which does whatever you want .

But if you want to alter the behavior from outside the map as needed you will use a comparer with a context which outlives the map

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 };

}

Another example to search using the string or int of key 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;

}

Note that std::map doesn't search using equality lhs == rhs but compares with less than and greater than since it is sorted and this approach will be faster

On the other hand std::unordered_map uses a hasher (usually std::hash) to test for equality since it isn't ordered .

Upvotes: 1

Related Questions