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.