Sort a vector on a value calculated on each element, without performing the calculation multiple times per element

Question

Hi chaps, can anyone recommend a nice and tidy way to achieve this:

float CalculateGoodness(const Thing& thing);

void SortThings(std::vector<Thing>& things)
{
    // sort 'things' on value returned from CalculateGoodness, without calling CalculateGoodness more than 'things.size()' times
}

Clearly I could use std::sort with a comparison function that calls CalculateGoodness, but then that will get called several times per Thing as it is compared to other elements, which is no good if CalculateGoodness is expensive. I could create another std::vector just to store the ratings and std::sort that, and rearrange things in the same way, but I can't see a tidy way of doing that. Any ideas?

Edit: Apologies, I should have said without modifying Thing, else it's a fairly easy problem to solve :)

Answer 1

You can have a call to CalculateGoodness that you call for each element before sorting, and then CalculateGoodness simply updates an internal member variable. Then you can sort based on that member variable.

Another possibility if you can't modify your type, is storing some kind of std::map for your objects and their previously calculated values. Your sort function would use that map which acts as a cache.

Answer 2

I'd create pairs of ratings and things, calling CalculateGoodness once per thing, and sort that on the rating. if applicable you could also move this to a map from rating to thing

the other option would be to cache CalculateGoodness in the Thing itself either as a simple field or by making CalculateGoodness a method of Thing (making sure the cache is mutable so const Things still works)

Answer 3

Perhaps a tidy way of doing the separate vector thing is to actually create a vector< pair<float, Thing*> >, where the second element points to the Thing object with the corresponding float value. If you sort this vector by the float values, you can iterate over it and read the Thing objects in the correct order, possibly playing them into another vector or list so they end up stored in order.

Answer 4

I can think of a simple transformation (well two) to get what you want. You could use std::transform with suitable predicates.

• std::vector<Thing> to std::vector< std::pair<Result,Thing> >
• sort the second vector (works because a pair is sorted by it first member)
• reverse transformation

Tadaam :)

EDIT: Minimizing the number of copies

• std::vector<Thing> to std::vector< std::pair<Result,Thing*> >
• sort the second vector
• transform back into a secondary vector (local)
• swap the original and local vectors

This way you would only copy each Thing once. Notably remember that sort perform copies so it could be worth using.

And because I am feeling grant:

typedef std::pair<float, Thing*> cached_type;
typedef std::vector<cached_type> cached_vector;

struct Compute: std::unary_function< Thing, cached_type >
{
  cached_type operator()(Thing& t) const
  {
    return cached_type(CalculateGoodness(t), &t);
  }
};

struct Back: std::unary_function< cached_type, Thing >
{
  Thing operator()(cached_type t) const { return *t.second; }
};


void SortThings(std::vector<Thing>& things)
{
  // Reserve to only allocate once
  cached_vector cache; cache.reserve(things.size());

  // Compute Goodness once and for all
  std::transform(things.begin(), things.end(),
                 std::back_inserter(cache), Compute());

  // Sort
  std::sort(cache.begin(), cache.end());

  // We have references inside `things` so we can't modify it
  // while dereferencing...
  std::vector<Thing> local; local.reserve(things.size());

  // Back transformation
  std::transform(cache.begin(), cache.end(),
                 std::back_inserter(local), Back());

  // Put result in `things`
  swap(things, local);
}

Provided with the usual caveat emptor: off the top of my head, may kill kittens...

Answer 5

I've upvoted Brian's answer because it clearly best answers what you're looking for. But another solution you should consider is just write it the easy way. Processors are getting more powerful every day. Make it correct and move on. You can profile it later to see if CalculateGoodness really is the bottleneck.