C++ Custom compare function for list::sort

问题:

Hi I'm having trouble compiling a simple piece of code. I am creating a class which implements a Deck of cards, and I want to create a shuffle method using the list::short method.

Relevant code:

deck.h

#ifndef _DECK_H
#define _DECK_H

#include <list>
#include <ostream>

#include "Card.h"
#include "RandomGenerator.h"

using namespace std;

class Deck {
private:
    static const int CARD_NUMBER = Card::CARDS_PER_SUIT*Card::SUIT_NUMBER;
    list<Card *> *cards;
    RandomGenerator rg;

public:
    Deck();
    ~Deck();
    void shuffle();
private:
    bool const compareRandom(const Card *a, const Card *b);

};

#endif  /* _DECK_H */

deck.cc:

#include "Deck.h"

/**
 * Fills the deck with a set of 52 cards
 */
Deck::Deck() {
    cards = new list<Card *>();
    for(int i = 0; i < CARD_NUMBER; i++)
        cards->push_back(
                new Card(
                    Card::Suit(int(i/Card::CARDS_PER_SUIT)),
                    i%Card::CARDS_PER_SUIT)
        );
}

Deck::~Deck() {
    gather();
    for(list<Card *>::iterator c = cards->begin(); c != cards->end(); c++)
        delete *c;
    delete cards;
}

bool const Deck::compareRandom(const Card *a, const Card *b) {
    return rg.randomBool();
}

void Deck::shuffle() {
    cards->sort(compareRandom);
}

The compiler shows the next message (ignore line numbers):

Deck.cc: In member function ‘void Deck::shuffle()’:
Deck.cc:66: error: no matching function for call to ‘std::list<Card*, std::allocator<Card*> >::sort(<unresolved overloaded function type>)’
/usr/include/c++/4.3/bits/list.tcc:303: note: candidates are: void std::list<_Tp, _Alloc>::sort() [with _Tp = Card*, _Alloc = std::allocator<Card*>]
/usr/include/c++/4.3/bits/list.tcc:380: note:                 void std::list<_Tp, _Alloc>::sort(_StrictWeakOrdering) [with _StrictWeakOrdering = const bool (Deck::*)(const Card*, const Card*), _Tp = Card*, _Alloc = std::allocator<Card*>]

The problem has to be on the compareRandom reference that I'm not using correctly, I cant find googling the answer to this problem.

Thanks in advance.

回答1:

Can I say something :)

First, don't store a pointer to Card, just store the cards directly in the container. If you insist on storing pointers to them for any reason, use shared_ptr<Card> from Boost. Second, you can use std::random_shuffle and pass your random-number-generator to it instead of implementing your your shuffle function.

---

May I say something again :)

This is what I have in mind, unless you have to use list for whatever reason, although I don't see that reason.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

class Card
{
// ...
};

int main()
{
    typedef std::vector<Card> Deck;
    Deck deck;

    // ... fill deck with cards.

    // There is an optional third parameter,
    // if you need to pass YOUR random-number-generator!
    // If you do, I recommend Boost implementation.
    std::random_shuffle(deck.begin(), deck.end());
}

I like to deal with containers directly in C++, though you may not like it. Also, if you see that std::vector has performance issues in your case, you could just replace the typedef with std::deque:

typedef std::deque<Card> Deck;

回答2:

compareRandom is a member function, it has type bool (Deck::*)(const Card*, const Card*) which means you can't call it like f(a,b), which is how sort will be calling it. You can make compareRandom a static or standalone function, or use a functor to adapt it to a specific instance of Deck.

回答3:

BTW - You cannot shuffle using sort :) Sort makes some assumptions on compare function.

回答4:

Apart from what others said: you can use std::shuffle std::random_shuffle (something I learned today, hurray!), I might add you cannot use a random function as a sort criterion.

sort takes a strict weak ordering as comparator, meaning that if a < b (or compareRandom(a,b) returns false, then b < a (compareRandom(b,a) returns true) and b == a should return false, which you can never guarantee with a random function. The behaviour of sort is undefined in this case. I don't know if it even ends...

回答5:

The reason of the error in Logan Capaldo's answer. Now you could replace compareRandom with functor in the following way:

...
private:
struct compareRandom {
  // it shouldn't give a random compare result. 
  // sort will not work (in Visual C++ 2008 it gives runtime assert)
  bool operator()(const Card *a, const Card *b) { return rg.randomBool(); }
};
...

Then use it

void Deck::shuffle() {
    cards->sort( compareRandom() );
}

回答6:

I urge you to use std::random_shuffle instead. It won't work on a list but it will work on a deque or vector, so unless you need list properties, I suggest you use another container. If you must use a list, try this:

void Deck::shuffle()
{
    vector<Card*> temp(cards->begin(), cards->end());
    random_shuffle(temp.begin(), temp.end());
    cards->assign(temp.begin(), temp.end());
}