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

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

不，这不是没有错误。 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;});

Answer 2

@fas 在评论中写道：

Elements in vector are moved during sort, so their pointers also change and scores_map becomes invalid, isn't it?

没错。您不应将指针用作 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]
}

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

Sorting a vector by unordered map of the elements pointers as keys

c++

sorting

unordered-map

vector

选项 1

选项 2