通过元素指针作为键的无序映射对向量进行排序

Question

我有一个元素std::vector<T> my_vec的向量。在我的代码中的某个时刻，我使用无序映射为向量的每个元素分配一个分数。在那之后，我想用可能的最小代码，根据向量元素的分数对向量进行排序。

我提出了这个解决方案，定义映射如下：std::unordered_map<const T*, float> scores_map。对于分数分配，将分数插入地图，如下所示：

for (const auto& el : my_vec)
scores_map[&el] = calc_score(el);

然后我使用进行排序

std::sort(my_vec.begin(), my_vec.end(), 
[&my_map](const auto& a, const auto& b){return my_map[&a] > my_map[&b];});

如果不知道如何做到这一点的话，这是否被认为是一种没有错误的良好做法？

Answer 1

@fas在评论中写道：

矢量中的元素在排序过程中被移动，所以它们的指针也会发生变化，scores_map也会无效，不是吗？

这是正确的。您不应该在scores_map中使用指针作为键。

选项1

如果矢量包含唯一项，则可以使用T作为键类型。

for (const auto& el : my_vec)
scores_map[el] = calc_score(el);

然后使用进行排序

std::sort(my_vec.begin(), my_vec.end(), 
[&my_map](const auto& a, const auto& b){return my_map[a] > my_map[b];});

选项2

如果矢量不包含唯一元素，则可以使用以下策略。

1. 使用索引作为my_map的密钥
2. 创建一个仅包含索引的辅助对象std::vector<size_t>
3. 对索引的矢量进行排序
4. 使用排序后的索引向量从my_vec中提取元素

for (size_t i = 0; i < my_vec.size(); ++i )
scores_map[i] = calc_score(my_vec[i]);
// Create the vector of indices
std::vector<size_t> indices_vec(my_vec.size());
for ( size_t i = 0; i < indices_vec.size(); ++i )
{
indices_vec[i] = i;
}
// Sort the vector of indices
std::sort(indices_vec.begin(), indices_vec.end(), 
[&my_map](size_t a, size_t b){return my_map[a] > my_map[b];}); 

for (auto index : indices_vec)
{
// Use my_vec[index]
}

Answer 2

不，这不是没有错误的。std::sort将改变元素的地址。

你可以将每个元素的分数存储在一对中：

std::pair<float, T>

并对矢量进行排序

std::vector<std::pair<float, T> > my_vec

带有

std::sort(my_vec.begin(), my_vec.end(), 
[](const auto& a, const auto& b){return a.first > b.first;});