按 unordered_map 内的结构数据排序

Question

我有一个std::unordered_map<id, town_data> data，其中town_data 是struct不同的信息 - 名称（字符串）、征收的税款（整数）和距首都城镇的距离（整数）。我应该构建一个std::vector<id>，它按前面提到的距离从低到高排序。我很难弄清楚如何才能有效地完成这项工作。我想我可以简单地循环data，通过该循环/插入创建std::map<distance, id>，按距离排序，除非默认情况下对地图进行排序，然后将其逐键复制到新向量std::vector<id>。但这看起来确实是一种浪费的做法。我在这里缺少一些捷径或更有效的解决方案吗？

Answer 1

std::vector您可以在映射中创建一个迭代器，然后根据您的排序标准对迭代器进行排序。排序后，您可以将结果转换为std::vector<id>.

创建一个std::vectorof 迭代器：

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

排序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;
              });

最后，将其转换为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;
                   });