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

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());
   

Answer 2

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 3

You can store the data in a vector. You can store the data as a structure or pair in the vector. If you use a pair then,

vector< pair< string, map<int,int> > > needToSort;

Then you can call the std::sort in it.

sort(needToSort.begin(), needToSort.end(), compareFunction);

The compareFunction is,

bool compareFunction( pair< string, map<int,int> > firstElement, pair< string, map<int,int> > secondElement)
{
    string firstString = firstElement.first;
    string secondString = secondElement.first;
    for(int i=0;i<firstString.size();i++)
        firstString[i] = toLower(firstString [i]);

    for(int i=0;i<secondString.size();i++)
        secondString [i] = toLower(secondString[i]);

   return firstString < secondString;
}

and then you can print the vector which should give you the desired result.

Answer 4

I think the usual way to do this is to create an index of iterators to the elements to be displayed:

// Return a range of iterators to the elements
// of the given range.
template <typename Range>
auto make_index(Range& range)
  -> vector<decltype(range.begin())> {
  vector<decltype(range.begin())> index;
  for (auto i = begin(range), e = end(range); i != e; ++i) {
    index.push_back(i);
  }
  return index;
}

and sort the iterators according to the display criteria:

auto index = make_index(tokens);
using iterator = decltype(tokens.begin());
sort(begin(index), end(index), [](iterator a, iterator b){
  return boost::algorithm::ilexicographical_compare(a->first, b->first);
});

remembering to dereference the iterators for display:

cout << "Sorted:\n";
for (auto&& i : index) {
  cout << i->first << ':';
  for (auto const& j : i->second) {
    cout << ' ' << j.first << ':' << j.second;
  }
  cout << '\n';
}

(See it all live at Coliru).

I've used boost::algorithm::ilexicographical_compare, Boost's case-insensitive locale-dependent string comparison, to save some typing.

Answer 5

If you want a custom "case aware" comparator, as proposed by Mark Ransom, that follows the alphabetical order of your language (or even your own alphabetical order implementation) with Unicode, you can use std::collate or boost::collator.

struct CaseAwareCompare
{        
    operator()(const std::string& strLeft, const std::string& strRight) const
    {
        using namespace boost::locale;

        std::locale loc;

        // Quaternary level : consider all case, accents, and punctuation.
        // The words must be identical in terms of Unicode representation.
        if (-1 == use_facet<collator<char> >(loc).compare(collator_base::quaternary,                                                               strLeft.begin(),
                                                          strLeft.end(),
                                                          strRight.begin(),
                                                          strRight.end())) {
    
            return true;
        }

        return false;
    }    
};

Note: you could need to use the collator_base::identical level or use normalized Unicode strings depending on your application.
As an example, with two different strings (non-matching code points) but with the same Unicode representation (displayed to the user).
"señor" : with ñ.
"señor" : with n + ◌̃.  

• Without normalization and with collator_base::quaternary, the two strings would be in the same map element.

• Without normalization and with collator_base::identical, the two strings would be in different map elements, but if you display the map elements to the user, he could not understand why there is twice the same string.

• With all the strings normalized in your application, the two strings would not be different anymore and you can use collator_base::quaternary without worries.