CODEWITHSUNDEEP
c++sortingvectorunordered-map
Baraa
Baraa

Reputation: 1526

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

I have a vector of elements std::vector<T> my_vec. At some point in my code I assign a score for each element of the vector using an unordered map. After that, I would like to sort the vector by the scores of its elements with the minimum code possible.

I came up with this solution, define the map as follows: std::unordered_map<const T*, float> scores_map. For score assignment, insert the score to the map as follows: 

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

Then I sort using:

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

Is this considered a bug-free and good practice, if not any idea how to make it so?

Upvotes: 0

Views: 788

Answers (2)

R Sahu
R Sahu

Reputation: 206617

@fas wrote in a comment:

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

That is correct. You should not use pointers as keys in scores_map.

Option 1

If the vector contains unique items, you may use the T as the key type.

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

Then sort using:

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

Option 2

If the vector does not contain unique elements, you may use the following strategy.

  1. Use indices as the key of my_map.
  2. Create a helper std::vector<size_t> object that contains just indices.
  3. Sort the vector of indices.
  4. Use the sorted indices vector to fetch the elements from 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]
}

Upvotes: 2

Thomas Sablik
Thomas Sablik

Reputation: 16448

No, this not bug-free. std::sort will change the addresses of the elements.

You could store the score with each element in a pair:

std::pair<float, T>

and sort the vector

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

Upvotes: 2

Related Questions