Czegoś nie rozumiem? [std::unordered_map]

Question

Na wstępie dodam, że dopiero uczę się działania tego typu kontenerów. I przepraszam za taki chaotyczny opis, jestem trochę zmęczony :)

Otóż napisałem sobie taki programik:

#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <string>
#include <cctype>

struct ci_char_traits : public std::char_traits<char> {

  using std::char_traits<char>::char_type;

  static bool eq(char_type lhs, char_type rhs) noexcept {
    return std::tolower(lhs) == std::tolower(rhs);
  }

  static bool lt(char_type lhs, char_type rhs) noexcept {
    return std::tolower(lhs) < std::tolower(rhs);
  }

  static int compare(const char_type* lhs, const char_type* rhs, std::size_t size) {
    while(size--) {
      if(lt(*lhs, *rhs)) return -1;
      if(lt(*rhs, *lhs)) return 1;
      ++lhs;
      ++rhs;
    }
    return 0;
  }

  static const char_type* find(const char_type* str, std::size_t size, const char_type& target) {
    while(size--) {
      if(eq(*str, target)) return str;
      ++str;
    }
    return nullptr;
  }

};

// ci_string to typ stringu, w którym wielkość liter nie ma znaczenia, tzn.
// ci_string("ABC") == ci_string("abC")
typedef std::basic_string<char, ci_char_traits> ci_string;

struct ci_string_hash {

  typedef std::size_t result_type;
  typedef ci_string argument_type;

  result_type operator()(const argument_type& arg) const {
    return std::hash<std::string>()(std::string(arg.data(), arg.size()));
  }

};

inline std::ostream& operator<<(std::ostream& os, const ci_string& cs) {
  return os << std::string(cs.data(), cs.size());
}

int main() {

  std::unordered_map<ci_string, double, ci_string_hash> constants;

  constants["pi"] = 3.14159;

  // Wyświetlono 0, spodziewano się 3.14159
  std::cout << constants["PI"] << std::endl;

}

Jak widać w funkcji main umieściłem w kontenerze std::unordered_map wartość liczby PI z kluczem 'pi'. Typ będący kluczem to ci_string. Nie korzysta on ze standardowych cech (chyba mogę tak powiedzieć) std::char_traits tylko ze specjalnej struktury ci_char_traits. Jakie są skutki korzystania z tych cech? Otóż klasa ta ignoruje wielkość liter, tzn. znaki 'A' i 'a' traktuje tak samo. Zgodnie z tym, taki kod powinien pokazać na ekranie 'true':

std::cout << std::boolalpha << (ci_string("PI") == ci_string("pi")); // Jest 'true'? Jest.

Jednak mojemu kontenerowi chyba to nie pasuje. Skoro 'PI' i 'pi' to jest to samo, to dlaczego przy wyświetlaniu pokazuje mi 0 (tj. tworzy nowy element)? Przecież klucz jest identyczny!

Moje pytanie brzmi: dlaczego tak się dzieje?

Answer 1

Na pierwszy rzut oka, to ci_string_hash wciąż generuje hash z oryginalnego stringa. Czyli i tak będziesz porównywał hash("pi") z hash("PI"), które będą różne.

Taka wersja działa poprawnie. Zauważ brak trzeciego argumentu szablonu dla unordered_map, jest niepotrzebny bo kompilator sam znajdzie specjalizację std::hash którą zdefiniowałem.

typedef std::basic_string<char, ci_char_traits> ci_string;

namespace std {
	template<>
	struct hash<ci_string> {
		typedef std::size_t result_type;
		typedef ci_string argument_type;

		result_type operator()(const argument_type& arg) const {
			ci_string other = arg;
			// zamiana na lowercase
			std:transform(other.begin(), other.end(), other.begin(), ::tolower);
			return std::hash<std::string>()(std::string(other.data(), other.size()));
		}
	};
}

int main() {
  std::unordered_map<ci_string, double> constants;
  constants["pi"] = 3.14159;
  std::cout << constants["PI"] << std::endl;
}

 

(zakładam że potrzebujesz ci_string z dodatkowych powodów i nie możesz się go pozbyć)

Comments

Faktycznie, kompletnie o tym zapomniałem (jak mówiłem, dopiero się uczę). A co do specjalizacji std::hash to po prostu nie chciało mi się w to bawić :) Co do funkcji zrobiłem, ją trochę inaczej, ale rezultat jest identyczny:

result_type operator()(const argument_type& arg) const {
    std::string other;
    std::for_each(arg.begin(), arg.end(), [&](char c){ other.push_back(std::tolower(c)); });
    return std::hash<std::string>()(other);
  }

 

---

To też jest ok. Z wydajnościowego punktu widzenia pewnie najlepsze byłoby:

result_type operator()(const argument_type& arg) const {
	std::string other(arg.data(), arg.size());
	std::transform(other.begin(), other.end(), other.begin(), ::tolower);
	return std::hash<std::string>()(other);
}