Sort List based on dynamically generated numbers in C++

Question

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
}

Answer 1

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).

Answer 2

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

Answer 3

std::sort is used to sort STL collections. If the elements in the collection you are sorting can be compared simply by calling operator< and the collection in question is a vector, then sorting is very simple:

std::sort(collection.begin(), collection.end());

If the collection in question is not a vector but a list as in your case, then you can't use the general version of std::sort, but you can use std::list's version instead:

list<int> numbers;
numbers.sort();

STL's sort, along with most other algorithms in the STL, come in two flavors. One is the simple version we have already seen, which just uses operator< to do the comparison of two elements. The other is a 'predicated' version, which instead of using operator< uses a comparison functor you provide. This is what you need to use in your case. There is a predicated version of sort for list, and this is what you need to use in your case.

You can create a functor in a number of ways, but one of the most useful is to derive a class from std::unary_function or from std::binary_function, depending on how many arguments your functor will take -- in your case, two. Override the function-call operator, operator() and add the code that compares two elements:

class compare_functor : public std::binary_function<Move, Move, bool>
{
public:
  bool operator(const Move& lhs, const Move& rhs) const
  {
    int left_val = lhs.Value();
    int right_val = rhs.Value();
    return left_val < right_val;
};

Here is a complete working example that puts everything together. In this program, instead of having a list of Moves, I have a list of 10 strings. Each string is 6 random characters. The list is populated by the call to generate_n, which uses the functor generator to create each random string. Then I dump that list of strings, along with their values, by calling copy and passing an output iterator that dumps the values to stdout (ostream_iterator). The value of each string is simply a sum of the numeric value of each character, computed by the function strng_val.

Then I sort the list using list's predicated version of sort. The comparison predicate used by sort is evaluator. Then I finally dump the resulting list and the string values to the screen again as above:

#include <cstdlib>
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
#include <ctime>
#include <sstream>

using namespace std;

class generator 
{
public:
    generator() { srand((unsigned)time(0)); }
    string operator()() const 
    {
        string ret;
        for( int i = 0; i < 6; ++i )
            ret += static_cast<char>((rand()/(RAND_MAX/26)) + 'A');
        return ret;
    }
};

unsigned string_val(const string& rhs)
{
        unsigned val = 0;
        for( string::const_iterator it = rhs.begin(); it != rhs.end(); ++it )
            val += (*it)-'A'+1;
        return val;
};

class evaluator : public std::binary_function<string,string,bool>
{
public:
    bool operator()(const string& lhs, const string& rhs) const
    {
        return string_val(lhs) < string_val(rhs);
    }
};

class string_dumper : public std::unary_function<string, string>
{
public:
    string operator()(const string& rhs) const
    {
        stringstream ss;
        ss << rhs << " = " << string_val(rhs);
        return ss.str();
    }
};

int main() 
{
    // fill a list with strings of 6 random characters
    list<string> strings;
    generate_n(back_inserter(strings), 10, generator());
    // dump it to the screen
    cout << "Unsorted List:\n";
    transform(strings.begin(), strings.end(), ostream_iterator<string>(cout, "\n"), string_dumper());

    // sort the strings according to their numeric values computed by 'evaluator'
    strings.sort(evaluator());  // because this is a 'list', we are using list's 'sort'
    // dump it to the screen
    cout << "\n\nSorted List:\n";
    transform(strings.begin(), strings.end(), ostream_iterator<string>(cout, "\n"), string_dumper());
    return 0;

}