How can I make the 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

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.

UPDATE: With C++11 std::binary_function is deprecated and is unnecessary as the types are deduced automatically.

  struct ci_less
  {
    // case-independent (ci) compare_less binary function
    struct nocase_compare
    {
      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
    }
  };

Answer 2

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 ;
    }
};

// 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;
}

Answer 3

For C++11 and beyond:

#include <strings.h>
#include <map>
#include <string>

namespace detail
{

struct CaseInsensitiveComparator
{
    bool operator()(const std::string& a, const std::string& b) const noexcept
    {
        return ::strcasecmp(a.c_str(), b.c_str()) < 0;
    }
};

}   // namespace detail


template <typename T>
using CaseInsensitiveMap = std::map<std::string, T, detail::CaseInsensitiveComparator>;



int main(int argc, char* argv[])
{
    CaseInsensitiveMap<int> m;

    m["one"] = 1;
    std::cout << m.at("ONE") << "\n";

    return 0;
}

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

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 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

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 8

I'd like to present a short solution without using Boost or templates. Since C++11 you can also provide a lambda expression as custom comparator to your map. For a POSIX-compatible system, the solution could look as follows:

auto comp = [](const std::string& s1, const std::string& s2) {
    return strcasecmp(s1.c_str(), s2.c_str()) < 0;
};
std::map<std::string, std::vector<std::string>, decltype(comp)> directory(comp);

Code on Ideone

For Window, strcasecmp() does not exist, but you can use _stricmp() instead:

auto comp = [](const std::string& s1, const std::string& s2) {
    return _stricmp(s1.c_str(), s2.c_str()) < 0;
};
std::map<std::string, std::vector<std::string>, decltype(comp)> directory(comp);

Note: Depending on your system and whether you have to support Unicode or not, you might need to compare strings in a different way. This Q&A gives a good start.

Answer 9

Tested:

template<typename T>
struct ci_less:std::binary_function<T,T,bool>
  { bool operator() (const T& s1,const T& s2) const { return boost::ilexicographical_compare(s1,s2); }};

...

map<string,int,ci_less<string>> x=boost::assign::map_list_of
        ("One",1)
        ("Two",2)
        ("Three",3);

cout << x["one"] << x["TWO"] <<x["thrEE"] << endl;

//Output: 123

Answer 10

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 11

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

Answer 12

This is the cross-platform standard c++ solution unlike strcasecmp (which is only available for posix), without using any external libraries like boost, that I have personally written. It takes advantage of the comparison function of std::map.

#include <algorithm>                                                            
#include <cctype>                                                               
#include <iostream>                                                             
#include <map>                                                                  
#include <string>                                                               
                                                                                
bool caseInsensitiveCompare(const std::string& a, const std::string& b) {       
  std::string aLower = a;                                                       
  std::string bLower = b;                                                       
  std::transform(aLower.begin(), aLower.end(), aLower.begin(), [](unsigned char c){ return std::tolower(c); });
  std::transform(bLower.begin(), bLower.end(), bLower.begin(), [](unsigned char c){ return std::tolower(c); });
  return aLower < bLower;                                                       
};                                                                              
                                                                                
int main()                                                                      
{                                                                               
  std::map<std::string, std::string, decltype(&caseInsensitiveCompare)> myMap(&caseInsensitiveCompare);
  myMap.insert({"foo", "foo"});                                                 
  myMap.insert({"bar", "bar"});                                                 
  myMap.insert({"baz", "baz"});                                                 
                                                                                
  auto it = myMap.find("FoO");                                                  
  if (it != myMap.end()) std::cout << "Found FoO: " << it->second << std::endl;      
  else std::cout << "Not found FoO" << std::endl;                              
                                                                                
  it = myMap.find("foo");                                                       
  if (it != myMap.end()) std::cout << "Found foo: " << it->second << std::endl;    
  else std::cout << "Not found foo" << std::endl;                            
                                                                                
  it = myMap.find("not contained");                                                       
  if (it != myMap.end()) std::cout << "Found not contained: " << it->second << std::endl;    
  else std::cout << "Not found notcontained" << std::endl;                            
                                                                                                                                                                          
  return 0;                                                                     
}