按 unordered_map 内的结构数据排序

Question

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

Answer 1

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

创建 std::vector 个迭代器：

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

Answer 2

我觉得id的vector可以直接排序如下，

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

我想知道这是否比排序 town_data 的向量更有效，不是吗？

按 unordered_map 内的结构数据排序

Sorting by struct data inside unordered_map

c++

vector

time-complexity

unordered-map