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?
CodePudding user response:
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;
});
CodePudding user response:
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?