C++ Printing a map in a case-insensitive, alphabetical order

Question

I have a:

map<string, map<int,int>>

Is there a way to print the contents of this map in alphabetical order, but case insensitive? For example, have it print in the following order:

A : 1:1, 2:2
a : 3:1
an : 2:1
And : 4:1
and : 3:1

Currently, I am printing using the following:

for (auto it = tokens.begin(); it != tokens.end(); ++it){
    cout << it->first << " : ";
    auto const &internal_map = it->second;
    for (auto it2 = internal_map.begin(); it2 != internal_map.end(); ++it2){
        if (it2 != internal_map.begin())
            cout << " , ";
        cout << it2->first << ":" << it2->second;
    }       
    cout << endl;
}

This prints everything, however, it goes through all uppercase first, followed by all lowercase. For example:

A : 1:1, 2:2
And : 4:1
a : 3:1
an : 2:1
and : 3:1

Answer 1

As stated in the accepted answer, you want to use a map with a custom comparison function. The trick is getting the proper comparison. You don't want a totally case-insensitive comparison or "And" and "and" would be equal, allowing only one of them in the map. Your sample data doesn't cover all cases; for example what would be the order of "An", "And", "AN", "AND"? The following comparison function orders them "AN", "An", "AND", "And" - shorter strings are always less than longer strings of the same characters, and the first character that has different case is a tie-breaker with upper-case before lower-case.

struct CaseAwareCompare
{
    bool operator()(const char * left, const char * right) const
    {
        bool tied = true, tiebreaker = false;
        for (int i = 0; left[i] != 0; ++i)
        {
            if (right[i] == 0)
                return false;
            if (tolower(left[i]) != tolower(right[i]))
                return tolower(left[i]) < tolower(right[i]);
            if (tied && left[i] != right[i])
            {
                tied = false;
                tiebreaker = left[i] < right[i];
            }
        }
        return (right[i] != 0) || (!tied && tiebreaker);
    }

    bool operator()(const string & left, const string & right) const
    {
        return operator()(left.c_str(), right.c_str());
    }
};

I struggled with what to call this; it's not a case-insensitive comparison because it differentiates between inputs with different case. I finally decided it should be called a case-aware comparison.

Answer 2

Is there a way to print the contents of this map in alphabetical order, but case insensitive?

Yes.

1. You will have to create a custom compare functor that compares two strings in a case insensitive manner.

   struct cicompare
   {
      bool operator()(std::string const& lhsIn, std::string const& rhsIn) const
      {
        char const* lhs = lhsIn.c_str();
        char const* rhs = rhsIn.c_str();
        for ( ; *lhs != '\0' && *rhs != '\0'; ++lhs, ++rhs )
        {
           if ( tolower(*lhs) != tolower(*rhs) )
           {
              return ( tolower(*lhs) < tolower(*rhs) );
           }
           else if ( *lhs != *rhs)
           {
              if ( *(lhs+1) == '\0' && *(rhs+1) == '\0' )
              {
                 return (*lhs < *rhs);
              }
           }
        }
        return (tolower(*lhs) < tolower(*rhs));
      }
   };
   

2. Use the case insensitive compare functor to create the map.

   map<string, map<int,int>, cicompare> mymap;
   

3. If you don't want to store your map ordered in a case insensitive manner, create a copy of the original map using cicompare just before printing and print the new map.

   map<string, map<int,int>, cicompare> mapForPrinting;
   mapForPrinting.insert(originalMap.start(), originalMap.end());