Q:

Sort List based on dynamically generated numbers in C++

I have a list of objects ("Move"'s in this case) that I want to sort based on their calculated evaluation. So, I have the List, and a bunch of numbers that are "associated" with an element in the list. I now want to sort the List elements with the first element having the lowest associated number, and the last having the highest. Once the items are order I can discard the associated number. How do I do this?
This is what my code looks like (kind've):
list<Move> moves = board.getLegalMoves(board.turn);

for(i = moves.begin(); i != moves.end(); ++i)
{
    //...
    a = max; // <-- number associated with current Move
}

A:

I would suggest a Schwartzian transform sort. Make a new vector (I recommend vector for more efficient sorting) of pairs of the associated value, and a pointer to its item. Sort the vector of pairs and then regenerate the list from the sorted vector. Since operator< is defined on a std::pair to be comparison by the first item of the pair and then the second, you will get a proper ordering.
Example:
#include <algorithm> // gives you std::sort
#include <utility>   // gives you std::pair

typedef double CostType;
typedef std::pair<CostType, Move*> Pair;

// Create the vector of pairs
std::vector<Pair> tempVec;
tempVec.reserve(moves.size());
for (std::list<Move>::iterator i = moves.begin(); i != moves.end(); ++i)
{
    CostType cost   = calcCost(*i);
    Move*    ptrToI = &(*i);
    tempVec.push_back(Pair(cost, ptrToI));
}

// Now sort 'em
std::sort(tempVec.begin(), tempVec.end());

// Regenerate your original list in sorted order by copying the original
// elements from their pointers in the Pair.
std::list<Move> sortedMoves;
for (std::vector<Pair>::iterator i = tempVec.begin(); i != tempVec.end(); ++i)
{
    sortedMoves.push_back(*(i->second));
}

Note that you will need a calcCost function that I have assumed here. This approach has an advantage over creating a comparison function if your comparison value calculation is time consuming. This way, you only pay the cost for calculating the comparison N times instead of 2 * N * log(N).

A:

You could make a comparison function that compares the two elements in the way that you would like.
bool compare_m (const Move &first,const Move &second)
{
  if (first.thing_you_are_comparing_on() < second.thing_you_are_comparing_on()) return true;
  else return false;
}

Where "thing_you_are_comparing_on" is some member of the Move class that gives you the ordering you want. We use const here to make sure that we are only comparing and not  actually changing the objects in the comparison function. You can then call the sort method on the list with compare_m as the comparison function:
moves.sort(compare_m)

Something to note is that if the calculation of the comparison function is particularly expensive it may be worthwhile to precompute all the associated rank numbers before sorting.
This would require adding something to the move class to store the rank for use later:
class Move{
    //rest of move class

    public:
    int rank;
};

list<Move>::iterator iter;

for(iter = moves.begin(); iter != moves.end(); ++iter)
{
    //...
    (*iter).rank = max; // store the number associated with current Move
}

bool compare_rank (const Move &first,const Move &second)
{
  if (first.rank < second.rank) return true;
  else return false;
}

