# 13. Objects of vectors¶

## 13.1. Enumerated types¶

In Card objects we talked about mappings between real-world values like rank and suit, and internal representations like integers and strings. Although we created a mapping between ranks and integers, and between suits and integers, we pointed out that the mapping itself does not appear as part of the program.

Actually, C++ provides a feature called an **enumerated type** that makes it
possible to (1) include a mapping as part of the program, and (2) define the
set of values that make up the mapping. For example, here is the definition of
the enumerated types `Suit`

and `Rank`

:

```
enum Suit {CLUBS, DIAMONDS, HEARTS, SPADES};
enum Rank {ACE=1, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT,
NINE, TEN, JACK, QUEEN, KING};
```

By default, the first value in the enumerated type maps to 0, the second to 1,
and so on. Within the `Suit`

type, the value `CLUBS`

is represented by the
integer 0, `DIAMONDS`

is represented by 1, etc. By convention, the values in
enumerated types have names with all capital letters.

The definition of `Rank`

overrides the default mapping and specifies that
`ACE`

should be represented by the integer 1. The other values follow in the
usual way.

If you are splitting up your source code like we did in Header files,
you sould put these `enum`

definitions in the `.h`

file, so that they will
be available to each file that includes the header file.

With these types defined, we can use them anywhere. For example, the instance
variables `rank`

and `suit`

can be declared with type `Rank`

and
`Suit`

:

```
struct Card
{
Rank rank;
Suit suit;
Card(Suit s, Rank r);
};
```

Notice that the types of the parameters for the constructor have changed, too. Now, to create a card, we can use the values from the enumerated types as arguments:

```
Card card(DIAMONDS, JACK);
```

This code is much clearer than our previous alternative using integers.

Because we know that the values in the enumerated types are represented as
integers, we can use them as indices for a vector. Therefore the old
`to_string`

function will work without modification. We have to make some
changes in `build_deck`

though:

```
vector<Card> build_deck()
{
vector<Card> deck(52);
int i = 0;
for (Suit suit = CLUBS; suit <= SPADES; suit = Suit(suit+1)) {
for (Rank rank = ACE; rank <= KING; rank = Rank(rank+1)) {
deck[i].suit = suit;
deck[i].rank = rank;
i++;
}
}
return deck;
}
```

In some ways, using enumerated types makes this code more readable, but there
is one complication. Strictly speaking, we are not allowed to do arithmetic
with enumerated types, so `suit++`

is not legal. On the other hand, in the
expression `suit+1`

, C++ automatically converts the enumerated type to an
integer. Then we can take the result and typecast it back to the enumerated
type:

```
suit = Suit(suit+1);
rank = Rank(rank+1);
```

This could be improved by overloading the `++`

operator for our enumerated
types, but we aren’t going to do that now.

## 13.2. `switch`

statement¶

It’s hard to mention enumerated types without mentioning `switch`

statements,
because they often go hand in hand. A `switch`

statement is an alternative
to a chained conditional that is syntactically prettier and often more
efficient. It looks like this:

```
switch(symbol) {
case '+':
perform_addition();
break;
case '*':
perform_multiplication();
break;
default:
count << "I can only add and multiply" << endl;
}
```

This `switch`

statement is equivalent to the following chained conditional:

```
if (symbol == '+') {
perform_addition();
} else if (symbol == '*') {
perform_multiplication();
} else {
count << "I can only add and multiply" << endl;
}
```

The `break`

statements are necessary in each branch in a `switch`

statement
because otherwise the flow of execution “falls through” to the next case.
Without the `break`

statements, the symbol `+`

would make the program
perform addition, and then perform multiplication, and then print the error
message. Occasionally this feature is useful, but most of the time it is a
source of errors when people forget the `break`

statements.

`switch`

statements work with integers, characters, and enumerated types.
For example, to convert a `Suit`

to the corresponding string, we could use
something like:

```
switch(suit) {
case CLUBS: return "Clubs";
case DIAMONDS: return "Diamonds";
case HEARTS: return "Hearts";
case SPADES: return "Spades";
default: return "Not a valid suit";
}
```

In this case we don’t need `break`

statements because the `return`

statements cause the flow of execution to return to the caller instead of
falling through to the next case.

In general, it is good style to include a `default`

case in every `switch`

statement, to handle errors or unexpected values.

## 13.3. Decks¶

In Vectors of objects, we worked with a vector of objects, but
we also mentioned that it is possible to have an object that has a vector as
an instance variable. In this chapter we are going to create a new object,
called a `Deck`

, that contains a vector of `Card`

s.

The struct definition and constructor look like this:

```
struct Deck {
vector<Card> cards;
Deck(int n);
};
Deck::Deck(int size)
{
vector<Card> temp(size);
cards = temp;
}
```

The name of the instance variable is `cards`

to help distinguish the `Deck`

object from the vector of `Card`

s that it contains.

For now there is only one constructor. It creates a locat variable named
`temp`

, which it initializes by invoking the constructor for the `vector`

class, passing the size as a parameter. Then it copies the vector from
`temp`

inthe the instance variable `cards`

.

We can now create a deck of cards like this:

```
Deck deck(52);
```

Here is a state diagram showing what a `Deck`

object looks like:

The object named `deck`

has a single instance variable named `cards`

, which
is a vector of `Card`

objects. To access the cards in a deck we have to
compose the syntax for accessing an instance variable and the syntax for
selecting an element from a vector. For example, the expression
`deck.cards[i].suite`

is its suit. The following loop

```
for (int i = 0; i < 52; i++) {
cout << deck.cards[i].to_string() << endl;
}
```

demonstrates how to traverse the deck and output each card.

## 13.4. Another constructor¶

Now that we have a `Deck`

object, it would be useful to initialize the cards
in it. From Objects of vectors we have a function called
`build_deck`

that we could use (with a few adaptations), but it might be
more natural to write a second `Deck`

constructor.

```
Deck::Deck()
{
vector<Card> temp(52);
cards = temp;
int i = 0;
for (Suit suit = CLUBS; suit <= SPADES; suit = Suit(suit+1)) {
for (Rank rank = ACE; rank <= KING; rank = Rank(rank+1)) {
cards[i].suit = suit;
cards[i].rank = rank;
i++;
}
}
}
```

Notice how similar this function is to `build_deck`

, except that we had to
change the syntax to make it a constructor. Now we can create a standard
52-card deck with the simple declaration `Deck deck;`

## 13.5. `Deck`

member functions¶

Now that we have a `Deck`

object, it makes sense to put all the functions
that pertain to `Deck`

s in the `Deck`

structure definition. Looking at the
functions we have written so far, one obvious candidate is the one introduced
in the print_deck function section. Here’s how it looks, rewritten as a
`Deck`

member function:

```
void Deck::print() const
{
for (int i = 0; i < cards.size(); i++) {
cout << cards[i].to_string() << endl;
}
}
```

As usual, we can refer to the instance variables of the current object without using dot notation.

For some of the other functions, it is not obvious whether they should be
member functions of `Card`

, member functions of `Deck`

, or nonmember
functions that take `Card`

s and `Deck`

s as arguments. For example,
the version of `find_card`

we wrote in Searching has a `Card`

and
a `Deck`

as parameters, but you could reasonably make it a member function
of either type.

Writing `find`

as a `Card`

member function is a little tricky. Here it is:

```
int Card::find(const Deck& deck) const
{
for (int i = 0; i < deck.cards.size(); i++) {
if (deck.cards[i].equals(*this)) return i;
}
return -1;
}
```

The first trick is that we have to use the keyword `this`

to refer to the
`Card`

the function is invoked on.

The second trick is getting around the fact that C++ does not make it easy to write two structure definitions that refer to each other. The problem is that when the compiler is reading the first structure definition, it doesn’t know about the second one yet.

One solution is to declare `Deck`

is a structure, without defining it, by
adding:

```
// declare that Dec is a structure, without defining it
struct Deck;
```

*before* the declaration of the `Card`

struct, so that we can refer to it
in the declaraton of `find`

:

```
int find(const Deck& deck) const;
```

## 13.6. Shuffling¶

For most card games you need to be able to shuffle the deck; that is, put the cards in a random order. In Random numbers we saw how to generate random numbers, but it is not obvious how to use them to shuffle a deck.

One possibility is to model the way humans shuffle, which is usually by dividing the deck into two and then reassembling the deck by choosing alternately from each half deck. Since humans usually don’t shuffle perfectly, after about 7 iterations the order of the deck is pretty well randomized. But a computer program would have the annoying property of doing a perfect shuffle every time, which is not really very random. In fact, after 8 perfect shuffles, you would find the deck back in the same order you started in.

A better shuffling algorithm is to traverse the deck on card at a time, and at each iteration choose two cards and swap them.

Here is an outline of how this algorithm works. To sketch the program, we are
using a combination of C++ statements and English words that is sometimes
called **pseudocode**:

```
for (int i = 0; i < cards.size(); i++) {
// choose a random number between i and cards.size()
// swap the ith card and the randomly-chosen card
}
```

The nice thing about using pseudocode is that it often makes it clear what
functions you are going to need. In this case, we need something like
`random_between`

, which chooses a random integer between the parameters `l`

and `h`

, and `swap_cards`

which takes two indices and switches the cards
at the indicated positions.

You can probably figure out how to write `random_between`

by looking back at
Random numbers, although you will have to be careful about possibly
generating indices that are out of range. You can also figure out the
`swap_cards`

function yourself, and we will leave the implementation of these
functions as exercises.

With `random_between`

and `swap_cards`

to help, we can add a `shuffle`

member function to `Deck`

:

```
void Deck::shuffle()
{
for (int i = 0; i < cards.size(); i++) {
int rand_card = random_between(0, cards.size() - 1);
swap_cards(i, rand_card);
}
}
```

## 13.7. Sorting¶

Now that we have messed up the deck, we need a way to put it back in order. Ironically, there is an algorithm for sorting that is very similar to the algorithm for shuffling, called a selection sort.

As with `shuffle`

, we are going to traverse the deck and at each location
choose another card and swap. The only difference is that this time instead of
choosing the other card at random, we are going to find the lowest card
remaining in the deck.

By “remaining in the deck”, we mean cards that are at or to the right of the
index `i`

.

```
for (int i = 0; i < cards.size(); i++) {
// find the lowest card at or to the right of i
// swap the ith card and the lowest card
}
```

Again, the pseudocode helps with the design of **helper functions**. In this
case we can use the `swap_cards`

that we have already written, so we only
need one new member function, which we’ll name `find_lowest`

.

This process, using pseudocode to figure out what helper functions are needed
is sometimes called **top-down design**, in contrast to the bottom-up design
discussed in Counting.

With your growing skill in writting member functions, we will leave writting
`find_lowest`

and `sort`

as exercises.

## 13.8. Hands¶

How should we represent a hand or some other subset of a full deck? One easy
choice is to make a `Deck`

object that has fewer than 52 cards.

We might want a function, `subdeck`

, that takes a vector of cards and a
range of indices, and returns a new vector of cards that contains the specified
subset of the deck:

```
Deck Deck::subdeck(int l, int h) const
{
Deck sub(h-l+1);
for (int i = 0; i < sub.cards.size(); i++) {
sub.cards[i] = cards[l+i];
}
return sub;
}
```

To create the local variable named `sub`

we are using the `Deck`

constructor that does not initialize the cards. The cards get initialized
when they are copied from the original deck.

The size of the subdeck is `h-l+1`

because both the low card and high card
are included. This sort of computation can be confusing, and lead to
**off-by-one errors**. Drawing a picture is usually the best way to avoid
them.

We will also want to be able to add and remove cards to our subdecks after they
are created. Let’s add `Deck`

member functions, `add_card`

, and
`remove_card`

to take care of that.

C++ vectors have member functions push_back and pop_back that do just what we need.

`push_back`

has the following prototype:

```
void push_back(const value_type& val);
```

It adds a new element, `val`

, to the end of the vector, increasing its size
by 1. `pop_back`

is a `void`

function that removes the last element from
the vector and decreases its size by 1.

We can use these to write `add_card`

and `remove_card`

.

```
void Deck::add_card(const Card& c)
{
cards.push_back(c);
}
Card Deck::remove_card()
{
Card card = cards[cards.size()-1];
cards.pop_back();
return card;
}
```

## 13.9. Shuffling and dealing¶

In the Shuffling section, we wrote pseudocode for a shuffling algorithm.
Assuming that you completed the exercise and we have a `Deck`

member function
called `shuffle`

, we can use it to create hands:

```
Deck deck;
deck.shuffle();
Deck hand1 = deck.subdeck(0, 4);
Deck hand2 = deck.subdeck(5, 9);
Deck pack = deck.subdeck(10, 51);
```

This code puts the first 5 cards in one hand, the next 5 cards in the other, and the rest into the pack.

When you though about dealing, did you think we should give out one card at a time to each player in the round-robin sytle that is common in real card games? We could write code to do that, but it is unnecessary for our computer program. The round-robin convention is intended to mitigate imperfect shuffling and make it more difficult for the dealer to cheat. Neither of these is an issue for our program.

This example is a useful reminder of one of the dangers of engineering metaphors: sometimes we impose restrictions on computers that are unnecessary, or expect capabilities that are lacking, because we unthinkingly extend a metaphor past its breaking point. Beware of misleading analogies

## 13.10. Merge sort¶

In the Sorting section, we saw a simple sorting algorithm that turns out not to be very efficient. In order to sort \(n\) items, it has to traverse the vector \(n\) times, and each traversal takes an amount of time that is proportional to \(n\). The total time, therefore, is proportional to \(n^2\).

In this section, we will sketch a more efficient algorithm, called merge sort. To sort \(n\) items, merge sort takes time proportional to \(n log n\). That may not seem impressive, but as \(n\) gets bit, the difference between \(n^2\) and \(n log n\) can be enormous. Try out a few values of \(n\) and see.

The basic idea behind merge sort is this: if you have two subdecks, each of which has been sorted, it is easy (and fast) to merge them into a single, sorted deck. Try this out with a deck of cards:

For two subdecks with about 10 cards each and sort them so that when they are face up the lowest cards are on top. Place both decks face up in front of you.

Compare the top card from each deck and choose the lower one. Flip it over and add it to the merged deck.

Repeast step two until one of the decks is empty. Then take the remaining cards and add them to the merged deck.

The result should be a single sorted deck. Here’s what this looks like in pseudocode:

```
Deck merge(const Deck& d) const
{
// creates a new deck big enough for all the cards
Deck result(cards.size() + d.cards.size());
// use index i for place in first deck, j for place in second deck
int i = 0;
int j = 0;
// k traverses the result deck
for (int k = 0; k < result.cards.size(); k++) {
// if this is empty, d wins, if d is empty, this wins;
// otherwise, compare the two cards on top
// add winner to the new deck
}
return result;
}
```

The best way to test `merge`

is to build and shuffle a deck, use subdeck to
form two (small) hands, then use the sort routine you wrote as an exercise to
sort the two halves. Then you can pass the two halves to `merge`

to see if it
works.

Once you get that working, try a simple implementation of `merge_sort`

:

```
Deck Deck::merge_sort() const
{
// find the midpoint of the deck
// divide the deck into two subdecks
// sort the subdecks using sort
// merge the two halves and return the result
}
```

Notice that the current object is declared `const`

because `merge_sort`

does not modify it. Instead, it creates and returns a new `Deck`

object.

If you can get that version working, the real fun begins! The magical thing
about merge sort is that it is recursive. At the point where you sort the
subdecks, why should you involve the old, slow selection sort? Why not invoke
the spiffy new `merge_sort`

you are in the process of writing?

Not only is that a good idea, it is *necessary* in order to achieve the
promised performance advantage. In order to make it work, though, you have to
add a base case so that it doesn’t recurse forever. A simple base case is a
subdeck with 0 or 1 cards. If `merge_sort`

receives such a small subdeck, it
can return it unmodified, since it is already sorted.

The recursive version of `merge_sort`

should look something like this:

```
Deck Deck::merge_sort() const
{
// if the deck is 0 or 1 cards, return it
// find the midpoint of the deck
// divide the deck into two subdecks
// sort the subdecks using merge_sort
// merge the two halves and return the result
}
```

As usual, there are two ways to think about recursive programs: you can think through the entire flow of execution, or you can make the “leap of faith.” We have deliberately contructed this example to encourage you to make the leap of faith.

When you were using `sort`

to sort the subdecks, you didn’t feel compelled
to follow the flow of execution, right? You just assumed that the `sort`

function would work because you already debugged it. All you did to make
`merge_sort`

recursive was replace one sort algorithm with another. There is
no reason to read the program differently.

Well, actually you have to give some thought to getting the base case right and making sure that you reach it eventually, but other than that, writing the recursive version should be no problem. Good luck!

## 13.11. Glossary¶

- pseudocode
A way of designing programs by writing rough drafts in a combination of English and C++.

- helper function
A small function that does not do anything enormously useful by itself, but which helps another, more useful, function.

- merge sort
An algorithm for sorting a collection of values. Mergesort is faster than…

## 13.12. Exercises¶

Rewrite the

`find_card`

function from Searching as a`Deck`

member function that has a`Card`

parameter.Reread the discussion in Random numbers and use that to write a function named

`random_between`

. Create a header file,`random.h`

, with the following:// Returns positive pseudorandom integer between l and h inclusive or // -1 if l or h is negative or h <= l int random_between(int l, int h);

Then create a

`random.cpp`

that has the body of the function. The parameters`l`

and`h`

represent the lower and upper ends of a range or integers. Your function should return random integers between`l`

and`h`

inclusive.Write a

`main.cpp`

that has`#include "random.h"`

at the top and has several calls to`random_between`

designed to test it.Handle the case where

`l`

is equal to`h`

, which will cause a run time error (since it will divide by zero) if you don’t check for it. Calling`random_between(5, 5)`

should just return 5.Finally, in the case where

`l`

is greater than`h`

, swap`l`

and`h`

that both`random_between(3, 6)`

and`random_between(6, 3)`

return an integer between 3 and 6 inclusive.Add a modifier member function to the

`Deck`

structure named`swap_cards`

that takes integers as arguments (the indices of the two cards) and swaps the cards at these indices.Add a member function to the

`Deck`

structure with prototype:int find_lowest(int l, int h);

that returns the index of the lowest card in the deck between

`l`

and`h`

inclusive.Add a modifier member function to the

`Deck`

structure named`sort`

that uses the selection sort algorithm sketched out in the Sorting section to put the decks cards into sorted order.Complete the

`merge`

function sketched out in the Merge sort section. Then use it to complete the first version of`merge_sort`

described in the section.