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

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

向量中的元素在排序过程中移动，因此它们的指针也发生变化，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

如果向量不包含唯一元素，则可以使用以下策略。
将索引用作my_map的键。
创建仅包含索引的助手std::vector<size_t>对象。
对索引向量进行排序。
使用排序的索引向量从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::pair<float, T>

并对向量排序

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

with

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