rating_dont_even_matter's blog

How C++ std::map works internally ?
By rating_dont_even_matter, history, 7 years ago, In English

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 ?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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());
	}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Use 'auto &d'. Otherwise it is just copied to variable d and change isn't reflected in actual vector.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Try auto &d

    → Reply