Sorted List and Comparators

Sometimes you have a list that you would like to sort on some key. However, either the object doesn't support relational operators, or the object doesn't support the relational operators you want.

One solution to this problem is to write a Comparator class, which allows you to compare two objects (call them one and two) and determine whether one < two, one == two, or one > two.

We will implement a comparator class for C++-strings. Strings already have comparison operators. However, they are case-sensitive. Suppose you would like to have a sorted array where the comparison is case-insensitive.

Header File

#ifndef STRING_COMPARATOR_H
#define STRING_COMPARATOR_H

#include <string>

class StringComparator {
  // Note: no data members
public:
  int operator()( const std::string & first, 
                  const std::string & second ) const;
};

#endif

StringComparator is a function object. What's that? It's an object where the operator() is overloaded.

For example, suppose you declare a StringComparator object.

  StringComparator comp ;

The only method for this object is the overloaded operator(), which expects two string objects as arguments (of course, you can pick the number of parameters for the method when you choose to overload, but for the project, we use two objects of the same type).

  StringComparator comp ;
  string s1 = "cat", s2 = "CAT" ;

  if ( comp( s1, s2 ) == 0 ) // tests if the two strings are the same
     cout << "EQUAL" << endl ;

If we implement operator() correctly, it will print "EQUALS".

Again, it looks unusual. comp is an object, yet, it's being called like a function.

Implementation (.cpp)

#include <iostream>
#include <string>
#include <algorithm>
#include "StringComparator.h"

using namespace std;

int StringComparator::operator()( const string & one, 
                                  const string & two ) const
{
  string first = one, second = two ;  // copy the string

  transform( first.begin(), first.end(), first.begin(), tolower ) ;
  transform( second.begin(), second.end(), second.begin(), tolower ) ;

  if ( first < second )
    return -1 ;
  else if ( first > second )
    return 1 ;
  else
    return 0 ;
}

Notice this method behaves like strcmp, which returns three values.

Thus, this method returns -1 if one < two, 1 if one > two, and 0 if equal.

Three-valued returns for comparisons are good because you can do comparisons such as > or >= more easily.

Using in Your Project

A Comparator object is going to be a data member of SortedList. Use this object to do comparisons in your locate() method.

Thus, you can declare a SortedList<string, StringComparator which now sorts case-insensitive, instead of case-sensitive.

Writing your own comparators allows you to sort on classes in the way you want to sort, rather than based on the built-in behavior of the relational operators for the class (which you may not have written).

This is how you would declare a SortedList of strings using a StringComparator class to do comparison.

  SortedList<string, StringComparator>  list ;

  list.add( "DOG" ) ;
  list.add( "cat" ) ;
  list.add( "ElK" ) ;

If you were to print the list in order, it would be "cat", "DOG", "ElK", i.e., in sorted order, case-insensitive. Of course, you would need a StringComparator class, and need to #include "StringComparator.h".

Web Accessibility