How can I create my own comparator for a map?

Question

typedef map<string, string> myMap; 

When inserting a new pair in myMap it will use the string key for comparison using its own string comparator. Is it possible to override this comparator? For example, I would like to compare the string key by length, not alphabetically. Or is there another way to sort the map?

Answer 1

std::map takes up to four arguments of type template, the third is a comparator. For example:.

 struct cmpByStringLength { bool operator()(const std::string& a, const std::string& b) const { return a.length() < b.length(); } }; // ... std::map<std::string, std::string, cmpByStringLength> myMap; 

Alternatively, you can also pass the comparator to the map constructor .

Please note, however, that when comparing in length, you can only have one line of each length on the map as a key.

Answer 2

Yes, the third parameter of the template on map indicated by a comparator, which is a binary predicate. Example:

 struct ByLength : public std::binary_function<string, string, bool> { bool operator()(const string& lhs, const string& rhs) const { return lhs.length() < rhs.length(); } }; int main() { typedef map<string, string, ByLength> lenmap; lenmap mymap; mymap["one"] = "one"; mymap["a"] = "a"; mymap["fewbahr"] = "foobar"; for( lenmap::const_iterator it = mymap.begin(), end = mymap.end(); it != end; ++it ) cout << it->first << "\n"; } 

Answer 3

Starting with C ++ 11 , you can also use a lambda expression instead of defining a comparator structure:

 auto comp = [](const string& a, const string& b) { return a.length() < b.length(); }; map<string, string, decltype(comp)> my_map(comp); my_map["1"] = "a"; my_map["three"] = "b"; my_map["two"] = "c"; my_map["fouuur"] = "d"; for(auto const &kv : my_map) cout << kv.first << endl; 

Exit:

one
two
three
fouuur

I would like to repeat the final note of Georg's answer: when comparing in length, only one line of each length on the map can be used as a key.

Ideone Code

Answer 4

Indicate the type of pointer to the comparison function as the 3rd type on the map and indicate the function pointer to the map constructor:
map<keyType, valueType, typeOfPointerToFunction> mapName(pointerToComparisonFunction);

Take a look at the example below to provide a comparison function on map with a vector iterator as a key and int as a value.

 #include "headers.h" bool int_vector_iter_comp(const vector<int>::iterator iter1, const vector<int>::iterator iter2) { return *iter1 < *iter2; } int main() { // Without providing custom comparison function map<vector<int>::iterator, int> default_comparison; // Providing custom comparison function // Basic version map<vector<int>::iterator, int, bool (*)(const vector<int>::iterator iter1, const vector<int>::iterator iter2)> basic(int_vector_iter_comp); // use decltype map<vector<int>::iterator, int, decltype(int_vector_iter_comp)*> with_decltype(&int_vector_iter_comp); // Use type alias or using typedef bool my_predicate(const vector<int>::iterator iter1, const vector<int>::iterator iter2); map<vector<int>::iterator, int, my_predicate*> with_typedef(&int_vector_iter_comp); using my_predicate_pointer_type = bool (*)(const vector<int>::iterator iter1, const vector<int>::iterator iter2); map<vector<int>::iterator, int, my_predicate_pointer_type> with_using(&int_vector_iter_comp); // Testing vector<int> v = {1, 2, 3}; default_comparison.insert(pair<vector<int>::iterator, int>({v.end(), 0})); default_comparison.insert(pair<vector<int>::iterator, int>({v.begin(), 0})); default_comparison.insert(pair<vector<int>::iterator, int>({v.begin(), 1})); default_comparison.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1})); cout << "size: " << default_comparison.size() << endl; for (auto& p : default_comparison) { cout << *(p.first) << ": " << p.second << endl; } basic.insert(pair<vector<int>::iterator, int>({v.end(), 0})); basic.insert(pair<vector<int>::iterator, int>({v.begin(), 0})); basic.insert(pair<vector<int>::iterator, int>({v.begin(), 1})); basic.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1})); cout << "size: " << basic.size() << endl; for (auto& p : basic) { cout << *(p.first) << ": " << p.second << endl; } with_decltype.insert(pair<vector<int>::iterator, int>({v.end(), 0})); with_decltype.insert(pair<vector<int>::iterator, int>({v.begin(), 0})); with_decltype.insert(pair<vector<int>::iterator, int>({v.begin(), 1})); with_decltype.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1})); cout << "size: " << with_decltype.size() << endl; for (auto& p : with_decltype) { cout << *(p.first) << ": " << p.second << endl; } with_typedef.insert(pair<vector<int>::iterator, int>({v.end(), 0})); with_typedef.insert(pair<vector<int>::iterator, int>({v.begin(), 0})); with_typedef.insert(pair<vector<int>::iterator, int>({v.begin(), 1})); with_typedef.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1})); cout << "size: " << with_typedef.size() << endl; for (auto& p : with_typedef) { cout << *(p.first) << ": " << p.second << endl; } }