If the keys are constant-pointers-to-characters, the map is sorted by the key pointers, and not by the key string literals. This is hardly what anybody wants. Consider the following key/value pairs of fruits and their outer colors:
"blackberry" => "dark blue-black"
"watermelon" => "green"
"apricot", => "orange"
"papaya" => "orange"
"banana" => "yellow"
The fruits are the keys, and the colors are the values. This list of elements (key/value pairs) is not sorted. The following program creates a map of this list as it is and displays it as it is, unsorted by string literals:
#include <map>
using namespace std;
int main()
{
map<const char*, const char*> mp;
mp["plum"] = "purple";
mp["blackberry"] = "dark blue-black";
mp["watermelon"] = "green";
mp["apricot"] = "orange";
mp["papaya"] = "orange";
mp["banana"] = "yellow";
for (map<const char*, const char*>::iterator it = mp.begin(); it != mp.end(); it++)
cout << it->first << " => " << it->second << endl;
return 0;
}
The output is:
blackberry => dark blue-black
watermelon => green
apricot => orange
papaya => orange
banana => yellow
unsorted by string literals, but sorted by pointers. To use a map in a C++ program, the map library has to be included with an include directive.
Another way of creating the above simple map, is as follows:
#include <map>
using namespace std;
int main()
{
map<const char*, const char*> mp({{"plum","purple"}, {"blackberry","dark blue-black"}, {"watermelon","green"}, {"apricot","orange"}, {"papaya","orange"}, {"banana","yellow"}});
for (map<const char*, const char*>::iterator it = mp.begin(); it != mp.end(); it++)
cout << it->first << " => " << it->second << endl;
return 0;
}
The output is:
blackberry => dark blue-black
watermelon => green
apricot => orange
papaya => orange
banana => yellow
unsorted by string literals, though sorted by pointers. If the keys were integers, the output would have been sorted by keys. In practice, the keys of many maps are string literals. This article explains how keys of string literals can sort a map.
Article Content
- Sorted During Creation
- Producing a Range Descending
- Comparing two Elements by Key
- Sorting of Map created with Initializer List
- Conclusion
Sort During Creation
The full template for the map construction is:
The classes, Compare and Allocator, have default values. That is, they have default specialization, which does not have to be typed in the map declarations (instantiations). What is of interest here is the comparison class. The name of the class is Compare, and the default specialization is “less<Key>”. “less<Key” means sort in ascending order. Another option is “greater<Key>”, which means sort descending.
A map is normally created sorted by keys during creation. If the keys are const char*, then the pointers to the quoted literal strings will be sorted, not the literal texts. To have strings as keys sorted during creation, the strings have to be literals of string objects instantiated from the string class. This means the string library has to be included, as well as the map library.
Creating Ascending
In the following program, the map is created, sorted ascending:
#include <map>
#include <string>
using namespace std;
int main()
{
map<string, const char*, less<string>> mp;
mp["plum"] = "purple";
mp["blackberry"] = "dark blue-black";
mp["watermelon"] = "green";
mp["apricot"] = "orange";
mp["papaya"] = "orange";
mp["banana"] = "yellow";
for (map<string, const char*>::iterator it = mp.begin(); it != mp.end(); it++)
cout << it->first << " => " << it->second << endl;
return 0;
}
The output is:
banana => yellow
blackberry => dark blue-black
papaya => orange
plum => purple
watermelon => green
Even if less<string> were omitted from the template, the sorting would still have been ascending because less is the default.
Creating Descending
In order to create a map, such that it is sorted in descending order by keys, the Compare specialization has to be coded. The following program illustrates this:
#include <map>
#include <string>
using namespace std;
int main()
{
map<string, const char*, greater<string>> mp;
mp["plum"] = "purple";
mp["blackberry"] = "dark blue-black";
mp["watermelon"] = "green";
mp["apricot"] = "orange";
mp["papaya"] = "orange";
mp["banana"] = "yellow";
for (map<string, const char*>::iterator it = mp.begin(); it != mp.end(); it++)
cout << it->first << " => " << it->second << endl;
return 0;
}
The output is:
plum => purple
papaya => orange
blackberry => dark blue-black
banana => yellow
apricot => orange
Producing a Range Descending
A range of a map can be produced in descending order. This involves creating a second map, which is a range from the first map. The following program illustrates this:
#include <map>
#include <string>
using namespace std;
int main()
{
map<string, const char*> mp;
mp["plum"] = "purple";
mp["blackberry"] = "dark blue-black";
mp["watermelon"] = "green";
mp["apricot"] = "orange";
mp["papaya"] = "orange";
mp["banana"] = "yellow";
map<string, const char*>::iterator itB = mp.begin();
itB++;
map<string, const char*>::iterator itE = mp.end();
itE--;
map<string, const char*, greater<string>> mpR(itB, itE);
for (map<string, const char*>::iterator it = mpR.begin(); it != mpR.end(); it++)
cout << it->first << " => " << it->second << endl;
return 0;
}
The output is:
papaya => orange
blackberry => dark blue-black
banana => yellow
The first map object has six elements which are:
banana => yellow
blackberry => dark blue-black
papaya => orange
plum => purple
watermelon => green
The range considered is:
blackberry => dark blue-black
papaya => orange
plum => purple
watermelon => green
In the code, “itB++” points to {“banana”, “yellow”} and “itE–” points to {“watermelon”, “green”} for the range. When handling a range in C++, the final element is not involved in the manipulation. And so the output has four elements with {“watermelon”, “green”} omitted.
The specialization of the Compare template parameter of the second map is greater<string>. If it were less<string> or omitted, the range would have resulted in ascending order.
Comparing two Elements by Key
key_compare key_comp() const
This member function returns a copy of the comparison object used by the map container to compare keys. A comparison object is a function object. It would take two keys as arguments and return true if the left key is less than right. With that, the code segment should be:
bool bl = kc("watermelon", "apricot");
key_compare is not recognized by the compiler. Eliminating key_compare in this code segment, by substituting for kc in the second statement, results in:
The following program illustrates the use of key_comp().
#include <map>
#include <string>
using namespace std;
int main()
{
map<string, const char*> mp;
mp["plum"] = "purple";
mp["blackberry"] = "dark blue-black";
mp["watermelon"] = "green";
mp["apricot"] = "orange";
mp["papaya"] = "orange";
mp["banana"] = "yellow";
bool bl = mp.key_comp()("watermelon", "apricot");
cout << bl << endl;
return 0;
}
The output is 0 for false.
The real problem with the above code segment is, that the namespace for key_compare, was not well expressed. If the segment was,
bool bl = kc("watermelon", "apricot");
It would have worked (accepted by the compiler).
value_compare value_comp() const
This member function is similar to key_comp(). Note: here, it is not the value of the key/value pair that is referred to; it is the element of the key/value pair. So, the two arguments for the value_compare function object are iterator elements. The following program uses value_comp(), in comparing the first and last elements, {“apricot”, “orange”} and {“watermelon”, “green”} :
#include <map>
#include <string>
using namespace std;
int main()
{
map<string, const char*, less<string>> mp;
mp["plum"] = "purple";
mp["blackberry"] = "dark blue-black";
mp["watermelon"] = "green";
mp["apricot"] = "orange";
mp["papaya"] = "orange";
mp["banana"] = "yellow";
map<string, const char*>::iterator itB = mp.begin();
map<string, const char*>::iterator itE = mp.end();
itE--;
map<string, const char*>::value_compare vc = mp.value_comp();
bool bl = vc(*itB, *itE);
cout << bl << endl;
return 0;
}
The output is 1, for true. The iterators itB and itE were dereferenced to have their elements, with the indirection operator.
Sorting of Map Created with Initializer List
In the following program, where sorting is descending, the keys are string objects, instantiated from the string class:
#include <string>
#include <map>
using namespace std;
int main()
{
map<string, const char*, greater<string>> mp({{"plum","purple"}, {"blackberry","dark blue-black"}, {"watermelon","green"}, {"apricot","orange"}, {"papaya","orange"}, {"banana","yellow"}});
for (map<string, const char*>::iterator it = mp.begin(); it != mp.end(); it++)
cout << it->first << " => " << it->second << endl;
return 0;
}
The output is:
plum => purple
papaya => orange
blackberry => dark blue-black
banana => yellow
apricot => orange
Conclusion
A map is created sorted by keys, ascending. Ascending is the default order. To have it descending, add the template parameter specialization, greater as the third argument, into the template argument list. Note: if the keys are strings, they must be instantiated from the string class, as illustrated above. String keys as const-char* or char-arr[], end up with their pointers sorted and not their literals.
