Case-insensitive STL containers (e.g. std :: unordered_set)

Question

What is the shortest, most cross-platform way to make a CASE-INSENSITIVE std :: unordered_set container?

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

I know that STL provides Hash and Pred . What should be a hash ? What should be Pred ? if they are not inline, please provide the code for them along with an example of their use (i.e. how to declare std::unordered_set ?).

Due to criticism, I will talk about what I'm trying to do. I need a high performance transparent HTTP proxy, one of the things it does is quickly scan the HTTP header fields. HTTP header fields are defined as case-insensitive, so I need a case-insensitive container.

Answer 1

unordered_set definition is

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

If you provide Hash and Pred functors that are case insensitive, then the set will also become so.

This is a simple example, the string hash function is simplified by c , but you can change it to your needs

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

Answer 2

Personally, I would determine the type of value that was case insensitive and which was divided by the string with the least hint. That way I can use standard hash models and predicate models.

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

Thus, we only enter string values ​​into the set:

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

Change flag safety:

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

Answer 3

I like it better.

It runs on 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)); } };