How to Make the Map::Find Operation Case Insensitive

How can I make the map::find operation case insensitive?

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

how to make stl::map key case insensitive

Use a custom comparator:

struct comp { 
    bool operator() (const std::string& lhs, const std::string& rhs) const {
        return stricmp(lhs.c_str(), rhs.c_str()) < 0;
    }
};

std::map<std::string, int, comp> st;

Edit :
If you're not able to use stricmp or strcasecmp use :

#include<algorithm>
//...
string tolower(string s) {
    std::transform(s.begin(), s.end(), s.begin(), ::tolower );
    return s;
}
struct comp { 
    bool operator() (const std::string& lhs, const std::string& rhs) const {
        return  tolower(lhs) < tolower(rhs);
    }
};

std::map<std::string, int, comp> st;

Lookup substring in map, case-insensitive

You can avoid expensive string construction by using a CharBuffer as key type:

Map<CharBuffer, MyType> lookup = new TreeMap<>(Comparator
    .comparingInt(CharBuffer::remaining)
    .thenComparing((cb1,cb2) -> {
        for(int p1 = cb1.position(), p2 = cb2.position(); p1 < cb1.limit(); p1++, p2++) {
            char c1 = cb1.get(p1), c2 = cb2.get(p2);
            if(c1 == c2) continue;
            c1 = Character.toUpperCase(c1);
            c2 = Character.toUpperCase(c2);
            if(c1 != c2) return Integer.compare(c1, c2);
        }
        return 0;
    }));
lookup.put(CharBuffer.wrap("RETURN"), MyType.KEYWORD_RETURN);

boolean lookupIdentifier(
    CharBuffer buffer, int offset, int length, Map<CharBuffer, MyType> lookupTable) {

    int currentPos = buffer.position(), currLimit = buffer.limit();
    buffer.clear().position(offset).limit(offset + length);
    boolean result = lookupTable.containsKey(buffer);
    buffer.clear().position(currentPos).limit(currLimit);
    return result;
}

The comparator uses a cheap length comparison before performing a case insensitive character comparison. This assumes that you stay with keywords like RETURN, which have a simple case mapping.

For a map with 50 keywords, using log₂ comparisons for a lookup might still yield reasonable performance. Mind that each comparison stops at the first mismatch.

---

You can use hashing with a dedicated wrapper object:

final class LookupKey {
    final CharBuffer cb;
    LookupKey(CharBuffer cb) {
        this.cb = cb;
    }
    @Override public int hashCode() {
        int code = 1;
        for(int p = cb.position(); p < cb.limit(); p++) {
            code = Character.toUpperCase(cb.get(p)) + code * 31;
        }
        return code;
    }
    @Override public boolean equals(Object obj) {
        if(!(obj instanceof LookupKey)) return false;
        final LookupKey other = (LookupKey)obj;
        CharBuffer cb1 = this.cb, cb2 = other.cb;
        if(cb1.remaining() != cb2.remaining()) return false;
        for(int p1 = cb1.position(), p2 = cb2.position(); p1 < cb1.limit(); p1++, p2++) {
            char c1 = cb1.get(p1), c2 = cb2.get(p2);
            if(c1 == c2) continue;
            c1 = Character.toUpperCase(c1);
            c2 = Character.toUpperCase(c2);
            if(c1 != c2) return false;
        }
        return true;
    }
}

Map<LookupKey, MyType> lookup = new HashMap<>();
lookup.put(new LookupKey(CharBuffer.wrap("RETURN")), MyType.KEYWORD_RETURN);

boolean lookupIdentifier(
    CharBuffer buffer, int offset, int length, Map<LookupKey, MyType> lookupTable) {

    int currentPos = buffer.position(), currLimit = buffer.limit();
    buffer.clear().position(offset).limit(offset + length);
    boolean result = lookupTable.containsKey(new LookupKey(buffer));
    buffer.clear().position(currentPos).limit(currLimit);
    return result;
}

The construction of a lightweight object like the LookupKey, which unlike String construction doesn’t need to copy character contents, is negligible. But note that hashing, unlike a comparator, has to process all characters upfront, which can turn out to be more expensive than the log₂ comparisons of a small TreeMap.

If these keywords are unlikely to change, an explicit lookup code, i.e. a switch over invariant properties of the key strings, can be even more efficient. E.g. start with switching over the length, if most keywords differ in length, then over a character which is different for most keywords (include case labels for uppercase and lowercase variant). Another alternative is a hierarchical lookup structure for these properties.

How to check for key in a Map irrespective of the case?

Not with conventional maps.

"abc" is a distinct string from "ABC", their hashcodes are different and their equals() methods will return false with respect to each other.

The simplest solution is to simply convert all inputs to uppercase (or lowercase) before inserting/checking. You could even write your own Map wrapper that would do this to ensure consistency.

If you want to maintain the case of the key as provided, but with case-insensitive comparison, you could look into using a TreeMap and supplying your own Comparator that will compare case-insensitively. However, think hard before going down this route as you will end up with some irreconcilable inconsistencies - if someone calls map.put("abc", 1) then map.put("ABC", 2), what case is the key stored in the map? Can you even make this make sense? Are you comfortable with the fact that if someone wraps your map in a standard e.g. HashMap you'll lose functionality? Or that if someone happens to be iterating through your keyset anyway, and does their own quick "contains" check by using equals() you'll get inconsistent results? There will be lots of other cases like this too. Note that you're violating the contract of Map by doing this (as key equality is defined in terms of the equals() method on the keys) so it's really not workable in any sense.

Maintaining a strict uppercase map is much easier to work with and maintain, and has the advantage of actually being a legal Map implementation.

How to look for values based on case insensitive keys in HashMap using Javascript

Had to loop through keys in myMap... but the following should work providing you dont have any keys whose only difference is case... Basically just created normalized keys by using .toLowerCase();

export const modifyKeys = (obj: {[x: string]: any;}, myMap: any) => {
  Object.keys(obj).forEach(key => {
    var normalizedKey = key.toLowerCase();
    if (myMap !== undefined) {
      var mapKeys = Object.keys(myMap);
      var keyFound = false;
      for (var index = 0; index < mapKeys.length && !keyFound; index++) {
        var mapKey = mapKeys[index];
        var normalizedMapKey = mapKey.toLowerCase();
        if (normalizedMapKey == normalizedKey) {
          var fieldName = myMap[mapKey];
          obj[fieldName] = obj[key];
          delete obj[key];
          if (typeof obj[fieldName] === 'object') {
            modifyKeys(obj[fieldName], myMap);
          }
          keyFound = true;
        }
      }
      if (!keyFound) {
        delete obj[key];
      }
    }
  });
}

MongoDB: Is it possible to make a case-insensitive query?

You could use a regex.

In your example that would be:

db.stuff.find( { foo: /^bar$/i } );

I must say, though, maybe you could just downcase (or upcase) the value on the way in rather than incurring the extra cost every time you find it. Obviously this wont work for people's names and such, but maybe use-cases like tags.

How to create a case insensitive map in Go?

Edit: My initial code actually still allowed map syntax and thus allowed the methods to be bypassed. This version is safer.

You can "derive" a type. In Go we just say declare. Then you define methods on your type. It just takes a very thin wrapper to provide the functionality you want. Note though, that you must call get and set with ordinary method call syntax. There is no way to keep the index syntax or optional ok result that built in maps have.

package main

import (
    "fmt"
    "strings"
)

type ciMap struct {
    m map[string]bool
}

func newCiMap() ciMap {
    return ciMap{m: make(map[string]bool)}
}

func (m ciMap) set(s string, b bool) {
    m.m[strings.ToLower(s)] = b
}

func (m ciMap) get(s string) (b, ok bool) {
    b, ok = m.m[strings.ToLower(s)]
    return
}

func main() {
    m := newCiMap()
    m.set("key1", true)
    m.set("kEy1", false)
    k := "keY1"
    b, _ := m.get(k)
    fmt.Println(k, "value is", b)
}

Case insensitive find on std::set

The equality operation is only used when the hashes compare equal. If the hashes don't compare equal, then the two strings won't be checked for exact equality. Otherwise, we'd just have to check every hash bucket - who cares if the hashes match or not? That would defeat the constant look up time of the hashed set.

You'll need to make a custom hash function that ignores case.

Given a hash set S, its hash function H(x), its equality operation x == y, and the hash equality H(x) == H(y): For all x and y that are valid elements of S, if x == y, then it must also be true that H(x) == H(y), otherwise S is said to be "totally jank".

---

Related Topics