Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
985 views
in Technique[技术] by (71.8m points)

sorting - Why STL unordered_map and unordered_set cannot be sorted by STL algorithms?

I'll start by illustrating a simple use case example:

  • Consider the problem of a social security ID database, where in C++ code is modelled as a std::unordered_map where its key is the social security ID of a person and its value is a std::string with the full-name of that person (e.g., std::unordered_map<int, std::string> DB;).

  • Consider also, that there's a request for printing this database sorted in ascending order based on the person's ID (i.e., std::unordered_map's key).

  • Naively, one would think to use std::sort in order to sort the std::unordered_map according to the requested criteria and then print it, like the example code below:


   std::sort(DB.begin(), DB.end());
   for(auto p : DB) std::cout << "ID(" << p.first
                              << ") - " 
                              << p.second 
                              << std::endl;

  • However, this is not the case, because use of std::sort with a range of either a std::unordered_map or a std::unordered_set will raise a compiler error.

Questions:

  1. Why STL's unordered containers cannot be sorted by std::sort?
  2. Is there a legitimate and efficient way to sort either a std::unordered_map or a std::unordered_set?
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

unordered containers store internally hashed data and thus it's not possible to order them after the hash has been generated.

In order to sort the data you can use an additional non-hashed container (e.g. map or set) and either use them along with the unordered version (so you can use the normal one to sort the data and the unordered one to have fast per-item access) or you can do something like

std::map<int, int> ordered(unordered.begin(), unordered.end());
for(auto it = ordered.begin(); it != ordered.end(); ++it)
     std::cout << it->second;

I recommend not to do the above often (unordered containers have slow sequential access)

https://stackoverflow.com/a/6212709/1938163


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...