C++ map Comparator

The following code sorts a map by keys in ascending order, during creation of the map:

The output is:

The actual code for the comparator here, is “less<char>”, in the map template specialization. The following code sorts a map by keys in descending order, during creation of the map:

The output is:

The actual code for the comparator here is “greater<char>” in the map template specialization.

For the above code samples, the map library is included in the program. The default comparator form is less. So, it could have been omitted in the previous code to have,

for the map template specialization.

If the programmer is not satisfied with the comparator offered by C++, the programmer can write his own. This article explains how the programmer can apply his own comparator to the map. Normal comparison of string keys is case-sensitive. The example of case-insensitive comparison is used.

Article Content

• Normal Comparison of String Keys
• Custom Case Insensitive Comparison Operator
• Comparison Template Specialization
• Main Function for Custom Comparator
• Conclusion

Normal Comparison of String Keys

Consider a class of five students, for a map of first names against marks, in a test, as follows:

A C++ map for the default comparator, less is in the program:

The output is:

The comparison is case-sensitive. The program begins with the inclusion of the iostream library for the cout object. Next, the map library is included; and then the string library is also included. The statement that follows ensures that any name used in the program is from the standard namespace unless otherwise indicated.

In the main() function, the map is declared with initialization. The next code segment in the main() function displays the sorted result (by key).

Custom Case Insensitive Comparison Operator

The less-than (<) operator of the string class of the C++ standard library is case-sensitive. If the programmer needs a case insensitive string literal less-than operator, he has to right his own operator function. An operator is actually a function that begins in a special way.

From the user’s point of view, the less-than operation is:

where left and right are operands. This operation yields true if the left operand is less than the right operand. If it happens that the left operand is the same as the right operand or is greater, it yields false. This operator is used for sorting in ascending order.

A custom case insensitive less-than comparison operator, for the string literal, is:

Here, the symbol for the operator is not <; it is (), which is coded to mean <. The arguments, left and right, are for the left and right operands, respectively. “char const*” means the content characters cannot be changed. “const” just after the parameter list, means the key value (string) referenced, in the map, cannot be changed, relative to the key/value pair. This does not mean that the order of each key/value pair element in the map cannot be changed.

Despite the fact that the targeted less-than operator has been defined as (), < is still used within the code.

The for-loop compares the left and right string literals, character-by-character, beginning from the left-most-character. It checks if the first characters of each operand are the same when both are in lowercase (case insensitive). If they are not the same, then true is returned if the left character is less than the right character; otherwise, false is returned; and the operator function stops iteration because the answer has been gotten. If they are the same, then iteration continues with the second corresponding pair of characters.

Before comparison continues to the second corresponding pair of characters, the code checks if the corresponding characters were the same but of different cases; and if the string literals were of the same length and have reached their ends. If all these are true, then the ”, can be written for descending order sorting, but that will not be addressed in this article.

Comparison Template Specialization

In simple terms, the template parameter list for the map is:

Notice the default comparator of less<Key>. For the above map, mp, and for the case insensitive comparison, the specialization would be:

where cicomp is the comparator, and it is a type. This type is the name of a struct or the name of a class. The struct or class typically has just one member, which is the above operator function definition. In this specialization, “const char*” has been used instead of the string type.

With the struct type, members not preceded with the specifier, “public:” are by default, public. With the class type, the above operator function has to be a public member. So the struct type definition, would be:

The main difference between the two definitions is the use of the specifier, “public:”. The class type definition would be:

The program for this comparator should begin with:

The cctype library is for the tolower() function.

Main Function for Custom Comparator

The following C++ main() function is for either the struct type or class type:

The output is,

for the case insensitive string literal comparator. Note that the template specialization for the iterator is the same as the template specialization for the map.

Conclusion

The default comparator for map sorting is less. Comparator is a type whose name is the third argument of the map declaration, of the map template specialization. This type can be a struct or a class, whose possibly only member, is a custom operator definition. This article has shown the case for a custom, less-than operator. Other comparison operators can similarly be defined.