Нечувствительные к регистру контейнеры STL (например, std :: unordered_set) - PullRequest
Новая
       14

Нечувствительные к регистру контейнеры STL (например, std :: unordered_set)

8 голосов
/ 25 декабря 2011

Какой самый короткий, самый кроссплатформенный способ сделать контейнер std :: unordered_set CASE-INSENSITIVE? 

my_set.insert("Apples");  
my_set.insert("apples"); //Insert doesn't occur because of duplicate item

Я знаю, что STL предоставляет Хэш и Pred . Каким должен быть Hash ? Каким должен быть Pred ? если они не являются встроенными, то, пожалуйста, предоставьте для них код вместе с примером их использования (т.е. как мне объявить std::unordered_set?).

В связи с критикой я подробно остановлюсь на том, что я пытаюсь сделать. Мне нужен высокопроизводительный прозрачный прокси-сервер HTTP, одна из вещей, которую он делает, - это быстрый поиск полей заголовка HTTP. Поля HTTP-заголовка определены без учета регистра, поэтому мне нужен контейнер без учета регистра.

Ответы [ 3 ]

12 голосов
/ 25 декабря 2011

Определение unordered_set равно 

  template <class Value,
            class Hash = hash<Value>,
            class Pred = std::equal_to<Value>,
            class Alloc = std::allocator<Value> >
  class unordered_set;

Если вы предоставите функторы Hash и Pred , которые не чувствительны к регистру, набор также станет таким.

Это простой пример, строка хеш-функция упрощена c , но вы можете изменить ее в соответствии со своими потребностями 

struct MyHash
{
    size_t operator()(const std::string& Keyval) const
    {
        //You might need a better hash function than this
        size_t h = 0;
        std::for_each( Keyval.begin() , Keyval.end() , [&](char c )
        {
            h += tolower(c);
        });
        return h;
    }
};

struct MyEqual
{
    bool operator()(const std::string& Left, const std::string& Right) const
    {
        return Left.size() == Right.size() 
             && std::equal ( Left.begin() , Left.end() , Right.begin() ,
            []( char a , char b )
        {
            return tolower(a) == tolower(b); 
        }
        );
    }
};


int main()
{
    std::unordered_set< std::string , MyHash , MyEqual > m;

    m.insert( "Apple" );
    m.insert( "apple" );

    return 0;
}
1 голос
/ 25 декабря 2011

Лично я бы определил тип значения, который не чувствителен к регистру и который превращается в строку по простейшей подсказке.Таким образом, я могу использовать стандартные модели хешей и предикатов. 

#include <string>
#include <unordered_set>
#include <iostream>
#include <algorithm>
#include <iterator>

class LCString
{
    std::string  data;

    public:
        operator std::string&()             {return data;}
        operator std::string const&() const {return data;}

        LCString(char const* init)
        {
            std::transform(init, init + strlen(init),
                           std::back_inserter(data), &::tolower);
        }
};

int main()
{
    typedef std::unordered_set<LCString, 
                               std::hash<std::string>, 
                               std::equal_to<std::string> >  MySet;
    MySet  data;
    data.insert("Apples");
    data.insert("apples");

    std::copy(data.begin(), data.end(),
              std::ostream_iterator<std::string>(std::cout, " - "));
    std::cout << "\n";
}

Таким образом, мы помещаем в набор только строчные значения: 

> g++ pl.cpp
> ./a.out
apples -
>

Редактирование Сохранение регистра: 

class LCStringOriginalPreserved
{
    std::string  original;
    std::string  data;

    public:
        operator std::string&()             {return data;}
        operator std::string const&() const {return data;}

        std::string& getOriginal()          {return original;}

        LCString(char const* init)
          : original(init)
        {
            std::transform(original.begin(), original.end(),
                           std::back_inserter(data), &::tolower);
        }
};
0 голосов
/ 25 декабря 2011

Мне нравится это лучше.

Работает в Linux. 

#include <strings.h>
#include <ctype.h>

#include <string>
#include <functional>
#include <tr1/functional_hash.h>

struct iequal_to : public std::binary_function <std::string,std::string,bool>
{
  bool operator() (const std::string& x, const std::string& y) const
  {
    return (!strcasecmp(x.c_str(), y.c_str()));
  }
};

const std::string LC(const std::string& x)
{
  std::string ret(x);
  std::string::size_type i;
  for(i = 0; i < x.size(); ++i)
    ret[i] = tolower(x[i]);
  return ret;
}

struct ihash : public std::unary_function <std::string,size_t>
{
  size_t ihash::operator() (const std::string& x) const
  {
    return std::tr1::hash<std::string>()(LC(x));
  }
};
...