Сортировка вектора по неупорядоченной карте указателей элементов в виде ключей

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