Std :: map <key_type, value_type> :: find (different_key_type)

Question

I have a map:

std::map<TyString, int> myMap; 

However, in some cases I want to make a std::map::find record by comparing TyString == TyStringRef , i.e.

 myMap.find(TyStringRef("MyString")); 

The reason is because TyString wraps const char * , which it allocates and frees itself. However, just to search for a record, I do not like to select a new line, instead I want to use only a link ( TyStringRef only wraps const char * without allocating or freeing memory).

Of course, I can just convert TyStringRef to TyString , but then I have the memory overhead described above.

Is there any reasonable way to solve this problem?

Thanks!

Answer 1

Note that std::map::find uses operator< by default or a custom comparison functor. Therefore, if you do not overload operator< for TyString and TyStringRef , you cannot find the key in logarithmic time. With operator== overloaded, you can still search in linear time , but without using std::map::find .

To do this, you should use the general algorithm from #include <algorithm> , which is independent of the container classes. It can take any type of T and compares it with operator== based on the result of the operator*() iterators you pass.

 std::find(sequence.begin(), sequence.end(), myKey); 

However, there is one problem: since you have a std::map that uses pairs for iterators, a key-value pair is compared. So you should use std::find_if , which takes a predicate instead of the value to search for. This predicate should return true for the item you are looking for. You want to have an element (pair) for which first == myKey , so you get this code:

 std::find_if(myMap.begin(), myMap.end(), [](const std::pair<TyString,int> & pair) { return pair.first == TyStringRef("MyString"); }; 

This works conceptually, but it will not use the binary tree in std::map . So this will be linear time compared to the logarithmic time std::map::find .

There is an alternative that looks a little strange at the beginning, but has the advantage that it will be a logarithmic time search. This requires overloading the operator<(TyString,TyStringRef) . . You can use std::lower_bound to find the first element that is not less than (greater than or equal to) some element relative to a given comparison function.

 std::lower_bound(myMap.begin(), myMap.end(), TyStringRef("MyString"), [](const std::pair<TyString,int> & entry, const & TyStringRef stringRef) { return entry.first < stringRef; } ); 

After the "lower bound" has been found, you still need to check if the keys are compared. If they do not, the item is not found. Since it is possible that all elements are less compared with the element you are looking for, so the returned iterator may be a final iterator that should not be dereferenced. Thus, the complete code becomes such that it is similar to std::map::find and returns the final iterator if the key was not found:

 template<class Map, class KeyCompareType, class Iterator = typename Map::const_iterator> Iterator findInMap(const Map &map, const KeyCompareType &key) { typedef typename Map::value_type value_type; auto predicate = [](const value_type & entry, const KeyCompareType & key) { return entry.first < key; }; Iterator it = std::lower_bound(map.begin(), map.end(), key, predicate); if (it != map.end()) { if (!(it->first == key)) it = map.end(); } return it; } 

Living example

Answer 2

You can use STLport, which already does this on its own. Maybe other implementations of the standard library do the same? Alternatively, you can use std :: find (), but it will cost you a logarithmic search.