C++ Custom compare function for list::sort

Question

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.

On a side note, your code would be much simpler if you didn't store pointers to Card's, but just had std::list<Card>. — GManNickG
– GManNickG, Commented Sep 12, 2009 at 17:17

Khaled Alshaya · Accepted Answer · 2009-09-12 21:12:22Z

10

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;

edited Sep 12, 2009 at 21:12

answered Sep 12, 2009 at 17:20

Khaled Alshaya

97.5k41 gold badges183 silver badges238 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

xtofl Over a year ago

In which case you can't use sort... (it's not a strict weak ordering)

eliocs Over a year ago

Thanks didn't know there was a stl shuffle algorythm.

eliocs Over a year ago

cant use: random_shuffle(cards.begin(), cards.end()); with a list :(

UncleBens Over a year ago

"cant use: random_shuffle(cards.begin(), cards.end()); with a list :(" - Consider switching to std::vector then. Use a container that suits your needs. :)

Khaled Alshaya Over a year ago

@eliocs I am not sure why you have to use a list? I'll post a piece of code as an example of what I have in my mind :)

Logan Capaldo · Accepted Answer · 2009-09-12 17:16:31Z

7

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.

answered Sep 12, 2009 at 17:16

Logan Capaldo

40.5k5 gold badges66 silver badges79 bronze badges

1 Comment

xtofl Over a year ago

Neat. Now I can delete my answer :)

agsamek · Accepted Answer · 2009-09-12 17:22:20Z

6

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

answered Sep 12, 2009 at 17:22

agsamek

9,14411 gold badges40 silver badges43 bronze badges

Comments

xtofl · Accepted Answer · 2009-09-12 20:22:31Z

3

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

edited Sep 12, 2009 at 20:22

answered Sep 12, 2009 at 17:29

xtofl

41.7k13 gold badges112 silver badges203 bronze badges

1 Comment

Kirill V. Lyadvinsky Over a year ago

There is no std::shuffle, only std::random_shuffle.

Community · Accepted Answer · 2017-05-23 12:19:07Z

2

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

edited May 23, 2017 at 12:19

CommunityBot

11 silver badge

answered Sep 12, 2009 at 17:22

Kirill V. Lyadvinsky

100k25 gold badges146 silver badges215 bronze badges

1 Comment

rlbond Over a year ago

Except that this won't really "shuffle" things correctly. Without a pure predicate, sort will not behave predictably, but that doesn't mean that you're getting any sort of halfway decent random distribution.

rlbond · Accepted Answer · 2009-09-12 21:20:35Z

0

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

answered Sep 12, 2009 at 21:20

rlbond

68.4k56 gold badges182 silver badges233 bronze badges

Collectives™ on Stack Overflow

C++ Custom compare function for list::sort

6 Answers 6

5 Comments

1 Comment

Comments

1 Comment

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

5 Comments

1 Comment

Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related