Click here to Skip to main content
15,112,232 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hi everyone,

I am currently working on a project that implies stacks of playing cards.
And I have trouble deciding on which container(s) to use in order to represent them.

Here are the basic requirements that I can list:

- the stack shall be sequential because the cards order is important. Leads me to Sequence containers.

- the size of the stack is not fixed. Cards can be taken out from random places, in any number, and same for card adding. Leads me to std::list.

- As move orders on stacks are given from the outside (users), I need to check whether or not a card (or a subset of the stack) is contained by the stack. Leads me to Associative containers for fast access to a random place.

- We shall be able to shuffle the stack.

- It is not possible to add twice the same card in the stack. The cards are flag with unique ID's, so technically, I can have two Kings of Spades in the same stack, but not with the same ID (if you merge two card packs for playing).

I know there is no a unique answer, but if you have any clue to help me deciding the final structure of my playing card stack it would be great !

What I have tried:

I have already provide several representations.

First I represent the stack by a vector of cards.
This solution works for every constraints, but it is slow to check if a card or a subset of card is contained by the stack.
It is also expensive to add or remove a card in a random place.

I then used a combination of a list of card and an unordered_map.
Both are synchronized by the adding and removal operations.
The list is used for sequenciality, size flexibility and random adding/removal.
The unordered_map is used for random access (method contains).

Then, I realized that it is not possible to use std::shuffle on a list. So for the moment, I am using a vector and an unordered_map. Going back to the random adding/removal issue...
Posted
Updated 21-Sep-16 5:15am

1 solution

std::vector should really be your default, especially for a small number of items (I presume you have at most 54 cards (13x4 + 2 jokers).

Lists have the ability to insert easily, but at the cost of almost everything else. Realistically, unless you are choosing a really stupid representation of each card, you should be able to have the whole stack in your CPU cache, so even shifting at most 53 cards by one place for insertion is no big deal.

Similarly, the cost of searching a list of 54 items is not likely to be expensive.

As recommended by Stroustrup: Are lists evil?[^]
   
Comments
FredBienvenu 21-Sep-16 10:42am
   
Thank you rob for your answer.
Actually it is true that the card number in my stacks will stay quite small.

Also, what do you think of having an unordered_map synchronized in order to check if the stack contains a card ?
Rob Grainger 21-Sep-16 11:12am
   
There should be no need - again, the overhead of searching such a small vector is minimal - the card will likely be in CPU cache, and take a minuscule amount of time to find.

Obviously, the recommendations change if the item held in the list is large, but that shouldn't be the case here.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900