Блог пользователя rating_dont_even_matter

How C++ std::map works internally ?
Автор rating_dont_even_matter, история, 7 лет назад, По-английски

Does anyone know how C++ STL map works internally for keys like string? I tried googling, but didn't find much. Does it hash the string for matching or does it match character by character?

30441799 In this code of problem D of last contest (434), he used a map with string as key, it got TLE.

30461043 In this code, he just turned the map into unordered_map, and AC with 2276ms.

Why map and unordered_map differs that much ?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

map uses the string as a key for a red-black tree. Everything is done character by character.

unordered_map uses hashes for its operations.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

since we are talking maps here , can someone tell me why this code doesn't work , the vectors don't get sorted .

map<int,vector<int> > m ;
...
	for(auto d:m){
		sort(d.second.begin(),d.second.end());
	}
→ Ответить