How to implement std::map with case-insensitive keys (C++98, C++11)
This article explains how to implement a map with case-insensitive string keys. What do I mean by that? Let's look at the situation below. Imagine, I have a map storing precipitation of individual U.S. states. For simplicity I only enter three states, the key is the name of the state, the value is the precipitation in inches.
Iowa 34.0
Delaware 45.7
Colorado 15.9
Look at the code below. I create a map representing the above-mentioned data. Now, I would like to change the value for the state Colorado, however, I write the key all in capital letters. As you can see from the output, the map does not recognize the key and now I have two values for the state Colorado in my map!
int main()
{
std::map<std::string, double> precipMap;
precipMap["Iowa"] = 34.0;
precipMap["Delaware"] = 45.7;
precipMap["Colorado"] = 15.9;
precipMap["COLORADO"] = 14.8;
for (std::map<string,double>::iterator it = precipMap.begin();
it != precipMap.end(); ++it){
std::cout << it->first << " " << it->second << '\n';
}
return 0;
}
COLORADO 14.8
Colorado 15.9
Delaware 45.7
Iowa 34.0
Now you could argue that I could perform a check before I enter the data into my map. But I would have to do this every time I try to do anything with the map. Let's say I would like to use the method std::map::find(). As you can see below, I would have the same problem.
std::cout << precipMap.find("DELAWARE")->second << '\n';
The above-mentioned implementation does not recognize the key DELAWARE and instead of printing the value 45.7, it prints the following nonsense:
3.76929e-306
Note: These situations do happen. For example, if your application stores some default settings and a user is allowed to change those settings via an external file, the application might end up not recognizing the keys simply because you assumed case sensitivity.
In the following, I am going to describe the solution for both C++98 and C++11. The general idea is the same. We need to inform our map on how to treat the keys once and forever. This is in general accomplished with the help of the third template argument of the map, called the comparison object. You can see this below. The map object uses the comparison object to determine both the order of the elements and whether two-element keys are equivalent.
std::map<string, double, Comparator> precipMap;
The function object - C++98 implementation
So what is a function object? A function object is an object that can be called like a function and to that end, it defines the operator(). You can see the object that we are going to use below. The operator() takes two const string parameters which represent arbitrary map elements that the map needs to sort or decide whether they are equivalent. To compare the equivalence of two strings I use the function std::transform(). I chose to transform both strings to lower case in order to compare them, but choosing the upper case would also work just fine.
struct Comparator {
bool operator() (const std::string& s1, const std::string& s2) const {
std::string str1(s1.length(),' ');
std::string str2(s2.length(),' ');
std::transform(s1.begin(), s1.end(), str1.begin(), tolower);
std::transform(s2.begin(), s2.end(), str2.begin(), tolower);
return str1 < str2;
}
};
Warning: If you added using namespace std at the top of your source code, you have to use ::tolower rather than tolower. This is because we want to use ::tolower from the global namespace (indicated by the scope operator ::) rather than std::tolower from what would be the current namespace (std).std::transform(s1.begin(), s1.end(), str1.begin(), ::tolower);
std::transform() applies certain unary operation to each of the elements in the input range. In our case, this operation is tolower. The first two parameters of the std::transform() are the input range, the third parameter is the beginning of the destination range. Notice that, in this case, we cannot modify the input range, since s1 and s2 were declared as const. As a result, we have to create new strings to represent the destination. Because std::transform() requires an iterator to the beginning of the destination range ( str1.begin() or str2.begin() ), I cannot leave the new strings (str1, str2) empty, but initialize them to some values and length.
Note: std::transform() requires to #include <algorithm>
The unary operation that performs the conversion to lower case is the ::tolower from the global namespace which acts on individual characters of the string and converts them to their lowercase equivalents.
std::transform(s1.begin(), s1.end(), str1.begin(), tolower);
Finally, let's look at the last line of operator(), namely the return statement return str1 < str2; The less-than operator on strings performs a lexicographical comparison and enables a dictionary-like string ordering. Notice, that the output is alphabetically ordered. Below you can see the code in action:
#include <iostream>
#include <map>
#include <algorithm>
struct Comparator {
bool operator() (const std::string& s1, const std::string& s2) const {
std::string str1(s1.length(),' ');
std::string str2(s2.length(),' ');
std::transform(s1.begin(), s1.end(), str1.begin(), tolower);
std::transform(s2.begin(), s2.end(), str2.begin(), tolower);
return str1 < str2;
}
};
int main()
{
std::map<std::string, double, Comparator> precipMap;
precipMap["Iowa"] = 34.0;
precipMap["Delaware"] = 45.7;
precipMap["Colorado"] = 15.9;
precipMap["COLORADO"] = 14.8;
for (std::map<std::string,double>::iterator it = precipMap.begin();
it != precipMap.end(); ++it){
std::cout << it->first << " " << it->second << '\n';
}
return 0;
}
Colorado 14.8
Delaware 45.7
Iowa 34.0
The lambda expression - C++11 implementation
There are only a few changes for the C++11 implementation. The function object is replaced by a lambda expression. A lambda expression is, in fact, a syntactic shortcut for a function object.
A lambda expression
[captures] (parameter list) -> return-type
{
lambda body;
}
You can see that the parameter list and the return type of the expression are the same as in the C++98 implementation with the function object. The lambda expression has no captures. The body of the lambda expression differs - I used another lambda expression for conversion to lowercase. This is, strictly speaking, not necessary. The old solution would have worked just fine.
auto comparator = [](const std::string& s1, const std::string& s2) -> bool {
std::string str1(s1.length(),' ');
std::string str2(s2.length(),' ');
auto myLambda = [](char c) -> char { return tolower(c);};
std::transform(s1.begin(), s1.end(), str1.begin(), myLambda);
std::transform(s2.begin(), s2.end(), str2.begin(), myLambda);
return str1 < str2;
};
Below you can see the entire implementation. Notice the map's constructor which contains decltype().
#include <iostream>
#include <map>
#include <algorithm>
int main()
{
auto comparator = [](const std::string& s1, const std::string& s2) -> bool {
std::string str1(s1.length(),' ');
std::string str2(s2.length(),' ');
auto myLambda = [](char c) -> char { return tolower(c);};
std::transform(s1.begin(), s1.end(), str1.begin(), myLambda);
std::transform(s2.begin(), s2.end(), str2.begin(), myLambda);
return str1 < str2;
};
std::map<std::string, double, decltype(comparator) precipMap(comparator);
precipMap = { {"Colorado", 15.9}, {"Delaware", 45.7}, {"Iowa", 34.0}};
precipMap["COLORADO"] = 14.8;
for(auto const &ent : precipMap)
std::cout << ent.first << " " << ent.second << '\n';
return 0;
}
Colorado 14.8
Delaware 45.7
Iowa 34.0
The decltype() is here because we cannot use lambda in unevaluated context. We firstly have to define lambda with 'auto' elsewhere and then only use it in the map's parameters with decltype(). The following wouldn't have worked:
std::map<std::string, double, [](const std::string& s1, const std::string& s2) -> bool {
std::string str1(s1.length(),' ');
std::string str2(s2.length(),' ');
auto myLambda = [](char c) -> char { return tolower(c);};
std::transform(s1.begin(), s1.end(), str1.begin(), myLambda);
std::transform(s2.begin(), s2.end(), str2.begin(), myLambda);
return str1 < str2;}> precipMap;
Note: The compilation error that the statement above would have produced would look like this: type/value mismatch at argument 3 in template parameter list for 'template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map'.
That's it! As an exercise try to find the value for all uppercase key 'DELAWARE'.
Tagged: C++