Making map::find operation case insensitive

Question

Does the map::find method support case insensitive search?
I have a map as follows

map<string,vector<string> > directory;

and want the below search to ignore case.

directory.find(search_string);

Answer 1

No, you can not do that using find as in that case there will be multiple matches. For example, while inserting lets you have done something like map["A"] = 1 and map["a"] = 2 and now if you want a case insensitive map.find("a") what is the expected return value? The simplest way to solve this would be insert the string into map in only one case (either upper or lower case) and then using the same case while doing the find.

Answer 2

The Compare element of the map template defaults to a binary comparison class "less". Look at the implementation:

http://www.cplusplus.com/reference/std/functional/less/

You can likely create your own class that derives from binary_function (the parent class to less) and do the same comparison without case sensitivity.

Answer 3

It does not by default. You will have to provide a custom comparator as a third argument. Following snippet will help you...

  /************************************************************************/
  /* Comparator for case-insensitive comparison in STL assos. containers  */
  /************************************************************************/
  struct ci_less : std::binary_function<std::string, std::string, bool>
  {
    // case-independent (ci) compare_less binary function
    struct nocase_compare : public std::binary_function<unsigned char,unsigned char,bool> 
    {
      bool operator() (const unsigned char& c1, const unsigned char& c2) const {
          return tolower (c1) < tolower (c2); 
      }
    };
    bool operator() (const std::string & s1, const std::string & s2) const {
      return std::lexicographical_compare 
        (s1.begin (), s1.end (),   // source range
        s2.begin (), s2.end (),   // dest range
        nocase_compare ());  // comparison
    }
  };

Use it like std::map< std::string, std::vector<std::string>, ci_less > myMap;

NOTE: std::lexicographical_compare has some nitty-gritty details. String comparison isn't always straightforward if you consider locales. See this thread on c.l.c++ if interested.

HTH,

Answer 4

You can instantiate std::map with three parameters: type of keys, type of values, and comparison function -- a strict weak ordering (essentially, a function or functor behaving like operator< in terms of transitivity and anti-reflexivity) of your liking. Just define the third parameter to do "case-insensitive less-than" (e.g. by a < on the lowercased strings it's comparing) and you'll have the "case-insensitive map" you desire!

Answer 5

Implement std::less function and compare by changing both to same case.

Answer 6

In case you don't want to touch the map type (to keep it's original simplicity and efficiency), but don't mind using a slower case-insensitive find function (O(N)):

string to_lower(string s) {
 transform(s.begin(), s.end(), s.begin(), (int(*)(int)) tolower );
 return s;
}

typedef map<string, int> map_type;

struct key_lcase_equal {
 string lcs;
 key_lcase_equal(const string& s) : lcs(to_lower(s)) {}
 bool operator()(const map_type::value_type& p) const {
  return to_lower(p.first) == lcs;
 }
};

map_type::iterator find_ignore_case(map_type& m, const string& s) {
 return find_if(m.begin(), m.end(), key_lcase_equal(s));
}

PS: Maybe it was Roger Pate's idea, but not sure, since some details were a bit off (std::search?, direct string comparator?)

Answer 7

I use the following:

bool str_iless(std::string const & a, 
               std::string const & b)
{
    return boost::algorithm::lexicographical_compare(a, b,  
                                                     boost::is_iless());
}
std::map<std::string, std::string, 
         boost::function<bool(std::string const &, 
                              std::string const &)> 
         > case_insensitive_map(&str_iless);

Answer 8

Here are some other alternatives, including one which performs significantly faster.

#include    <map>
#include    <string>
#include    <cstring>
#include    <iostream>
#include    <boost/algorithm/string.hpp>

using std::string;
using std::map;
using std::cout;
using std::endl;

using namespace boost::algorithm;

// recommended in Meyers, Effective STL when internationalization and embedded
// NULLs aren't an issue.  Much faster than the STL or Boost lex versions.
struct ciLessLibC : public std::binary_function<string, string, bool> {
    bool operator()(const string &lhs, const string &rhs) const {
        return strcasecmp(lhs.c_str(), rhs.c_str()) < 0 ? 1 : 0;
    }
};

// Modification of Manuel's answer
struct ciLessBoost : std::binary_function<std::string, std::string, bool>
{
    bool operator() (const std::string & s1, const std::string & s2) const {
        return lexicographical_compare(s1, s2, is_iless());
    }
};

typedef map< string, int, ciLessLibC> mapLibc_t;
typedef map< string, int, ciLessBoost> mapBoost_t;

int main(void) {
    mapBoost_t cisMap; // change to test other comparitor 

    cisMap["foo"] = 1;
    cisMap["FOO"] = 2;

    cisMap["bar"] = 3;
    cisMap["BAR"] = 4;

    cisMap["baz"] = 5;
    cisMap["BAZ"] = 6;

    cout << "foo == " << cisMap["foo"] << endl;
    cout << "bar == " << cisMap["bar"] << endl;
    cout << "baz == " << cisMap["baz"] << endl;

    return 0;
}