如何使 map::find 操作不区分大小写？

Question

map::find 方法是否支持不区分大小写的搜索？我有一张地图如下：

map<string, vector<string> > directory;

并希望以下搜索忽略大小写：

directory.find(search_string);

Answer 1

默认情况下不会。您必须提供自定义比较器作为第三个参数。以下代码片段将帮助您...

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

像 std::map使用它std::string、std::vector、ci_less > myMap;

注意：std::lexicographyal_compare 有一些具体细节。如果考虑区域设置，字符串比较并不总是那么简单。如果有兴趣，请参阅 clc++ 上的此主题。

更新：对于 C++11，std::binary_function 已弃用，并且没有必要，因为类型是自动推导的。

  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

这里有一些其他的替代方案，其中包括一种执行速度明显更快的方案。

#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

对于 C++11 及更高版本：

#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

您可以使用三个参数实例化std::map：键类型、值类型和比较函数——严格的您喜欢的弱排序（本质上，函数或函子在传递性和反自反性方面表现得像operator<）。只需定义第三个参数来执行“不区分大小写的小于”（例如，通过比较的小写字符串上的 < ），您将获得所需的“不区分大小写的映射”！

Answer 5

我使用以下内容：

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

如果您不想接触地图类型（以保持其原始的简单性和效率），但不介意使用较慢的不区分大小写的查找函数（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：也许这是 Roger Pate 的想法，但不确定，因为一些细节有点偏离（std::search？，直接字符串比较器？）

Answer 7

不，您不能使用 find 来做到这一点，因为在这种情况下会有多个匹配项。例如，插入时可以让您执行诸如 map["A"] = 1 和 map["a"] = 2 之类的操作，现在如果您想要不区分大小写map.find("a") 预期返回值是多少？解决此问题的最简单方法是将字符串仅以一种情况（大写或小写）插入到映射中，然后在查找时使用相同的情况。

Answer 8

我想提出一个不使用 Boost 或模板的简短解决方案。自 C++11 起，您还可以提供 lambda 表达式 作为地图的自定义比较器。对于 POSIX 兼容系统，解决方案可能如下所示：

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

Ideone 上的代码

对于 Window，strcasecmp() 不存在，但您可以使用_stricmp() 改为：

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

注意：根据您的系统以及是否必须支持 Unicode，您可能需要以不同的方式比较字符串。 此问答提供了一个良好的开端。

Answer 9

映射模板的 Compare 元素默认为二进制比较类“less”。看一下实现：

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

您可以创建自己的派生自binary_function（less的父类）的类，并在不区分大小写的情况下进行相同的比较。

Answer 10

测试：

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 11

实现 std::less 函数并通过将两者更改为相同的大小写进行比较。

Answer 12

这是跨平台的标准 C++ 解决方案，与 strcasecmp（仅适用于 posix）不同，没有使用我亲自编写的任何外部库（如 boost）。它利用了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;                                                                     
}