Sorting by struct data inside unordered_map

user_11098708 0
Viewed 93

I have an std::unordered_map<id, town_data> data, where town_data is a struct of different information - name (string), taxes collected (int) and distance from capital town (int). I'm supposed to build a std::vector<id>, which is sorted by beforementioned distance, lowest to high. I'm quite struggling to figure out how can this be done efficiently. I suppose I could simply loop through the data, create std::map<distance, id> through that loop/insertion, sort it by distance unless maps are sorted by default, and copy it key by key to new vector, std::vector<id>. But this seems really wasteful approach. Am I missing some shortcut or more efficient solution here?

unordered-map vector time-complexity c++
2 Answers

You could create a std::vector of iterators into the map and then sort the iterators according to your sorting criteria. After sorting, you could transform the result into a std::vector<id>.

Create a std::vector of iterators:

    std::vector<decltype(data)::iterator> its;
    its.reserve(data.size());
    for(auto it = data.begin(); it != data.end(); ++it)
        its.push_back(it);

Sort that std::vector:

#include <algorithm> // std::sort, std::transform

    std::sort(its.begin(), its.end(),
              [](auto& lhs, auto&rhs) {
                  return lhs->second.distance < rhs->second.distance;
              });

And finally, transform it into a std::vector<id>:

#include <iterator> // std::back_inserter

    std::vector<id> vec;
    vec.reserve(its.size());
    std::transform(its.begin(), its.end(), std::back_inserter(vec),
                   [](auto it) {
                       return it->first;
                   });
user_75822470

I think that the vector of id can be sorted directly as below,

std::vector<decltype(decltype(data)::value_type::second_type::id)> vec;
vec.reserve(data.size());
for(auto it = data.begin(); it != data.end(); ++it)
    vec.push_back(it->second.id);
std::sort(vec.begin(), vec.end(), [&data](auto lhs, auto rhs) { return data[lhs].distance < data[rhs].distance; });

I'm wondering if is this more efficient than sorting a vector of town_data, isn't it?

user_120142660
Related