Use of templates with templated Deck class

Question

I have previous revisions of my deck of cards project, but I may not need to link them here since the emphasis is on the use of templates.

I've never used them before until now, and I like how intuitive my implementation has become. However, I'm also aware that there are many pitfalls in C++ templates. Although I don't think this implementation uses them heavily, I'd still like to know if I'm at a good start before I use them again.

I'm also a bit unsure about some of my naming now, considering this is a template class. For instance, I've changed add()'s parameter from card to item because it cannot be assumed that the user will only use cards. Although it makes sense to just use cards (or anything representing cards), it would not seem practical to limit the implementation to just that usage. I would prefer this to be reusable.

Of course, I'm okay with any other improvements that can be made.

Deck.hpp

#ifndef DECK_HPP
#define DECK_HPP

#include <algorithm>
#include <stdexcept>
#include <vector>

template <class T> class Deck
{
private:
    std::vector<T> original;
    std::vector<T> playable;

public:
    typedef typename std::vector<T>::size_type SizeType;

    void add(T const&);
    T draw();
    void reset();
    void shuffle();
    SizeType size() const { return playable.size(); }
    bool empty() const { return playable.empty(); }
};

template <class T> void Deck<T>::add(T const& item)
{
    original.push_back(item);
    playable.push_back(item);
}

template <class T> T Deck<T>::draw()
{
    if (playable.empty())
    {
        throw std::out_of_range("deck empty");
    }

    T top(playable.back());
    playable.pop_back();
    return top;
}

template <class T> void Deck<T>::reset()
{
    playable = original;
}

template <class T> void Deck<T>::shuffle()
{
    if (!playable.empty())
    {
        std::random_shuffle(playable.begin(), playable.end());
    }
}

#endif

Answer 1

Bottom line: your code here is focused and solid. It's a well-written introductory use of templates. However I'm not sure it's a great scenario in which to use them. First I'll talk about ways to improve its reusability, and then I'll say more about why I think it's a questionable scenario.

As you start trying to implement your own templatized data structure, there are a lot of concerns to think about. Above all else you need to consider how your data structure will be used; what operations will consumers of it expect, what limitations will they have to put up with, and whether any of the data structure's implementation choices lock them into bad patterns. In general I would say you would do well to follow the lead of the STL data structures unless you have specific reasons not to. Here are a few of the places where you currently differ:

void Deck<T>::add(T const &)

This one actually is pretty much spot on. But I want to talk about the implications of how it's implemented. You are requiring T to be copyable. Thus if a consumer of this class needs to compare cards, T will need to compare itself through means other than by its address. This isn't particularly unusual, but I just wanted to be clear that comparing T instances by address is invalidated by Deck<T>'s implementation.

The biggest question mark here is the lack of a range insertion, perhaps via constructor or add(InputIterator first, InputIterator last). Similarly there's no index-based insertion, but that wouldn't mix well with the two vectors that are often out of sync.

T Deck<T>::draw()

Before C++11 introduced move semantics, there was not necessarily a low cost way to examine and remove an item from a data structure. This is why vector and other data structures let you examine the front or back, but don't return the removed item on a pop_back(). While it's perfectly good to wrap the functionality of the underlying storage, as the cost of copying T goes up, so does the cost of this implementation of draw(). Implementing it in some other fashion (typically as two separate methods for peeking and removing) is suggested before C++11.

Taking into account what Corbin and Loki Astari point out, it's more relevant to consider weak and strong exception guarantees (essentially the ability to reason about correctness in unusual situations) instead of the cost of copying (thanks especially to RVO). Whether you need to care about either is still completely dependent on your use case in practice, and thus only of extreme importance in general purpose data structures, or in ones you know need to offer it.

Inside draw()

Your implementation of draw() verifies that the playable deck has items remaining. This is certainly good for catching errors, but leads to repeated checks for the same data. Either the calling code will look like while (true) { ::: draw(); ::: } and will have to use a try/catch to find out when the deck was empty, or it will look like while (!deck.empty()) { ::: draw(); ::: }. The former is a questionable way to use exceptions, as an empty deck is hardly an unexpected condition, but the latter means both the caller and callee are repeating the empty check. It's also possible that the caller knows this in other ways, such as having put 52 cards in the deck and then looping 52 times to empty it.

As an aside, it can still be useful to have this sort of check available by another name (consider the difference between vector<T>::operator[] and vector<T>::at), or available through a compile-time option (such as a DEBUG build). But it's typically good to make an unchecked version available (vector's operator[] case).

void Deck<T>::reset()

I'm lumping a couple comments in here, and this is less about following the STL's lead. Like in draw(), as the cost of copying T goes up or the size of your deck goes up, so does the cost of reset(); is it possible that you don't need to save the original order? If you don't, then perhaps it would be better to consider a different implementation: one vector<T> containing the order of the deck, one vector<T>::const_iterator or vector<T>::size_type containing the index/iterator through which you've already played. This would have a lot of repercussions, so I'm going to show the methods that it would impact, assuming the class has a size_type deck_top, and that we remove original. I like the shorter code, but that has less to do with the index and more to do with the other changes.

template <class T> bool Deck<T>::empty() const
{
    return deck_top >= playable.size();
}

template <class T> T const & Deck<T>::draw() // note we can now return a reference
{
    return playable[deck_top++];
}

template <class T> void Deck<T>::reset()
{
    deck_top = 0;
}

template <class T> void Deck<T>::shuffle()
{
    std::random_shuffle(playable.begin() + deck_top, playable.end());
}

This of course has multiple tradeoffs besides the ones I already mentioned. Perhaps the biggest is that there's still no way to remove cards (temporarily or permanently), so it's hard to model a game that shuffles a partial deck while people are still holding some cards in their hands. I think you will rapidly find that it's hard to make this data structure usable for all the scenarios you think you want it to support without making it almost as generic as vector itself. At which point you will have to consider whether it's worth reusing the data structure, or if it's really just for a single program's use.

Final notes

As a generic comment, I'm undecided on card vs. item. I think card conveys the intended use better, and doesn't really get in the way if someone wants, say, a "Deck" of tiles instead. But I do agree in general with the point about not boxing yourself in by your parameter names.

Answer 2

The usage of a template parameter named T is generally idiomatic when there are no restrictions on what you can use when instantiating the template; for example, when using container classes T is used as it could potentially be anything. If the parameter is more limited however, you should give it a more descriptive name. In this example, an obvious choice would be Card:

template <typename Card>
class Deck
{
    ...
}

Answer 3

The only additional point I have is the use of class:

template <class T> class Deck 
    //    ^^^^^^
          This one.

Its technically valid. But the implications that T should be some class type (or user defined type) make me dislike this form. I prefer the modern version:

template <typename T>  // PS. I also prefer line break here.
class Deck             //     It makes the class look like a normal class

Answer 4

• I did have access to C++11 when writing this code, but I never found a use for it at the time. I am now aware that there's a better replacement for std::random_shuffle() available in C++11 which doesn't utilize rand (now considered harmful): std::shuffle().

  This requires a third parameter, a random number engine, supplied as such:

  static std::random_device rd;
  static std::mt19937 engine(rd());
  

  (The new C++11 library <random> is required for this.)

  In shuffle(), I can now replace std::random_shuffle() with std::shuffle():

  std::shuffle(playable.begin(), playable.end(), engine);
  

  With this, I can also now remove std::srand() from the driver.

• Since neither size() nor empty() throw exceptions, I can add noexcept for both of them to make this clear:

  SizeType size() const noexcept { return playable.size(); }
  bool empty() const noexcept { return playable.empty(); }
  

• I can now use type aliasing for the type std::vector<T>:

  using Cards = std::vector<T>;
  

  This would allow me to change the type in just one place:

  Cards original;
  Cards playable;
  

• Due to templating issues and a possible lack of size_type for a different container class, I can remove SizeType and have size() return auto (in C++14):

  auto size() const noexcept { return playable.size(); }