12. Vectors of objects

12.1. Composition

By now we have seen several examples of composition (the ability to combine language features in a variety of arrangements). One of the first examples we saw was using a function invocation as part of an expression. Another example is the nested structure of statements: you can put an if statement within a while loop, or within another if statement, etc.

Having seen this pattern, and having learned about vectors and objects, you should not be surprised to learn that you can have vectors of objects. In fact, you can also have objects that contain vectors (as instance variables); you can have vectors that contain vectors; you can have objects that contain objects, and so on.

In the next two chapters we will look at some examples of these combinations, using Card objects as a case study.

12.2. Card objects

If you are not familiar with common playing cards, now would be a good time to get a deck, or else this chapter might not make much sense. There are 52 cards in a deck, each of which belongs to one of 4 suits and one of 13 ranks. The suits are Clubs, Diamonds, Hearts and Spades (in ascending order in Bridge). The ranks are 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace. Depending on what game you are playing, the rank of Ace may be higher than King or lower than 2.

If we want to define a new object to represent a playing card, it is pretty obvious what the instance variables should be: rank and suit. It is not as obvious what type the instance variables should be. One possibility is strings, containing things like “Spade” for suits and “Queen” for ranks. One problem with this implementation is that it would not be easy to compare cards to see which had a higher rank or suit.

An alternative is to use integers to encode the ranks and suits. By “encode,” we do not mean what some people thin, which is to encrypt, or translate into a secret code. What a computer scientist means by “encode” is something like “define a mapping between a sequence of numbers and the things we want to represent.” For example,

\[ \begin{align}\begin{aligned}None \mapsto 0\\Clubs \mapsto 1\\Diamonds \mapsto 2\\Hearts \mapsto 3\\Spades \mapsto 4\end{aligned}\end{align} \]

The symbol \(\mapsto\) is mathematical notation for “maps to.” The obvious feature of this mapping is that the suits map to integers in order, so we can compare suits by comparing integers. The mapping for ranks is fairly obvious; each of the numerical ranks maps to the corresponding integer, and for face cards:

\[ \begin{align}\begin{aligned}Jack \mapsto 11\\Queen \mapsto 12\\King \mapsto 13\\Ace \mapsto 14\end{aligned}\end{align} \]

The reason we are using mathematical notation for these mappings is that they are not part of the C++ program. They are part of the program design, but they never appear explicitly in the code. The structure definition for the Card type looks like this:

struct Card
{
    int suit, rank;

    Card();
    Card(int s, int r);
};

Card::Card() {
    suit = 0; rank = 0;
}

Card::Card(int s, int r) {
    suit = s; rank = r;
}

There are two constructors for Cards. You can tell they are constructors because they have no return type and their name is the same as the name of the structure. The first constructor takes no arguments and initializes the instance variables to a useless value (the zero of clubs).

The second constructor is more useful. It takes two parameters, the suite and rank of the card.

The following code creates an object named three_of_clubs that represents the 3 of Clubs:

Card three_of_clubs(1, 3);

The first argument, 1, represents the suit Clubs, the second, naturally, represents the rank 3.

12.3. The to_string function

When you create a new type, the first step is usually to declare the instance variables and write constructors. The second step is often to write a function that will allow the object to be printed in human-readable form.

In the case of Card objects, “human-readable” means that we have to map the internal representation of rank and suit onto words. A natural way to do that is with strings. You can create a vector of strings the same way you create a vector of other types:

vector<string> suit_strings = {"None", "Clubs", "Diamonds",
                               "Hearts", "Spades"};

Of course, in order to use vectors and strings, you will have to include the header files for both, and the using namespace std; statement, since both vector and string are in the std namespace.

We can build a similar vector to decode the ranks. Then we can select the appropriate elements using the suit and rank as indices. Finally, we can write a function called to_string that returns a string representation of the card on which it is invoked:

string Card::to_string() const
{
    vector<string> suit_strings = {"None", "Clubs", "Diamonds",
                                   "Hearts", "Spades"};
    vector<string> rank_strings = {"Joker", "2", "3", "4", "5", "6", "7",
                                   "8", "9", "10", "Jack", "Queen", "King",
                                   "Ace"};

    if (rank == 0) return rank_strings[rank];
    return rank_strings[rank] + " of " + suit_strings[suit];
}

The expression rank_strings[rank] means “use the instance variable suit from the current object as an index into the vector named suit_strings, and select the appropriate string.”

Because to_string is a Card member function, it can refer to the instance variable of the current object implicitly (without having to use dot notation to specify the object). The output of this code:

Card card(2, 11);
cout << card.to_string() << endl;

is Jack of Diamonds.

You might have noticed that we are taking a different approach here than we did in the print section. There we wrote a print member function for Time objects that printed them directly (by using cout in the function). Here we are writing to_string to return a string to the calling function. This approach makes it easier to use our human-readable Card representation together with other output in our program.

You may also have noticed we used an empty string as the first element in rank_strings as a placeholder so that the mapping of the numbered ranks “lines up” with their encoded value. From the point of view of the user, it doesn’t matter what the encoding is, since all input and output uses human-readable formats. On the other hand, it is often helpful for the programmer if the mappings are easy to remember.

12.4. The equals function

In order for two cards to be equal, they have to have the same rank and the same suit. While C++ supports operator overloading, which would allow us to create a member function to overload the == opertor for user defined types like our Card objects, we will postpone a discussion of how to do that for now. Instead, we will write a member function called equals that will compare two Cards.

It is clear that the return value from equals should be a boolean that indicates whether the cards are the same. It is also clear that there should be two Cards as parameters. But we have one more choice: should equals be a member function or a free-standing function?

As a member function, it looks like this:

bool Card::equals(const Card& c2) const
{
    return (rank == c2.rank && suit == c2.suit);
}

To use this function, we have to invoke it on one of the cards and pass the other as an argument:

Card card1(1, 11);
Card card2(1, 11);

if (card1.equals(card2)) {
    cout << "Yup, that's the same card." << endl;
}

It could be argued that since the equals relationship is symmetric, meaning that if “A equals B”, then “B equals A”, it would be more appropriate to write equals as a free-standing function. It will be left as an exercise to do that.

12.5. The is_greater function

For basic types like int and double, there are comparison operators that compare values and determine when one is greater or less than another. These operators (< and > and others) don’t work without overloading for user-defined types. Just as we did for the == operator, we will write a comparision function that plays the role of the > operator. Later, we will use this function to sort a deck of cards.

Some sets are totally ordered, which means that you can compare any two elements and tell which is bigger. For example, the integers and floating-point numbers are totally ordered. Some sets are unordered, which means that there is no meaningful way to say that one element is greater than another. For example, the fruits are unordered, which is why you can’t compare apples and oranges. As another example, the bool type should be unordered; we should not be able to say that true is greater than false. In C++, however, we can:

#include <iostream>
using namespace std;

int main()
{
    bool p = true;
    bool q = false;

    if (p > q) {
        cout << "Truth prevails over falsehood." << endl;
    }

    return 0;
}

In other languages, like Java, this would not be allowed.

The set of playing cards is partially ordered, which means that sometimes we can compare cards and sometimes not. For example, we know that the 3 of Clubs is higher than the 2 of Clubs because it has a higher rank, and the 3 of Diamonds is higher than the 3 of Clubs because it has a higher suit. But which is better, the 3 of Clubs or the 2 of Diamonds? One has a higher rank, but the other has a higher suit.

In order to make cards comparable, we have to decide which is more important, rank or suit. To be honest, the choice is completely arbitrary. For the sake of choosing, we will say that suit is more important, because when you buy a new deck of cards, it comes sorted with all the Clubs together, followed by all the Diamonds, and so on.

With that decided, we can write is_greater. Again, the arguments (two Cards) and the return type (bool) are obvious, and again we have to choose between a member function and a nonmember function. This time the arguments are not symmetric (“A is greater than B” is not the same as “B is greater than A”), making the case for a member function stronger. Here’s is_greater as a member function:

bool Card::is_greater(const Card& c2) const
{
    // first check the suits
    if (suit > c2.suit) return true;
    if (suit < c2.suit) return false;

    // if suits are equal, check ranks
    if (rank > c2.rank) return true;
    if (rank < c2.rank) return false;
    // this last statement can be omitted without changing the
    // behavior of the function, but making it arguably less readable

    // if ranks are equal too, 1st card is not greater than the 2nd
    return false;
}

Since we made is_greater a member function, it is obvious from the syntax which which of the two possible comparisons we intend:

Card card1(2, 11);
Card card2(1, 11);

if (card1.is_greater(card2)) {
    cout << card1.to_string() << " is greater than " << card2.to_string();
    cout << endl;
}

You can almost read it like English: “If card1 is_greater card2 …” The output of the program is:

Jack of Hearts is greater than Jack of Diamonds

12.6. Vectors of cards

The reason we chose Cards as the objects for this chapter is that there is an obvious use for a vector of cards - a deck. Here is some code that creates a new deck of 52 cars:

vector<Card> deck(52);

Here is the state diagram for this object:

The three dots represent the 48 cards we didn’t feel like drawing. Keep in mind that we haven’t initialized the instance variables of the cards yet. In some environments, they will get initialized to zero, as shown in the figure, but in others they could contain any possible value.

One way to initialize them would be to pass a Card as a second argument to the constructor:

Card ace_of_spades(3, 1);
vector<Card> deck(52 ace_of_spades);

This code builds a deck with 52 identical cards, like a special deck for a magic trick. Of course, it makes more sense to build a deck with 52 different cards in it. To do that, we use a nested loop.

The outer loop enumerates the suits, from 0 to 3. For each suit, the inner loop enumerates the ranks, from 1 to 13. Since the outer loop iterates 4 times, and the inner loop iterates 13 times, the total number of times the body is executed is 52 (13 times 4).

int i = 0;
for (int suit = 0; suit <= 3; suit++) {
    for (int rank = 1; rank <= 13; rank++) {
        deck[i].suit = suit;
        deck[i].rank = rank;
        i++;
    }
}

We used the variable i to keep track of where in the deck the next card should go.

Notice that we can compose the syntax for selecting an element from a vector (the [] operator) with the syntax for selecting an instance variable from an object (the dot operator). The expression deck[i].suit means “the suit of the ith card in the deck”.

12.7. print_deck function

Whenever you are working with vectors, it is convenient to have a function that prints the contents of the vector. We have seen the pattern for traversing a vector several times, so the following function should be familiar:

void print_deck(const vector<Card>& deck)
{
    for (int i = 0; i < deck.size(); i++) {
        cout << deck[i].to_string() << endl;
    }
}

By now it should come as no surprise that we can compose the syntax for vector access with the syntax for invoking a function.

Since deck has type vector<Card>, an element of deck has type Card. Therefore, it is legal to invoke to_string on deck[i].

12.8. Searching

The next function we want to write is find_card, which searches through a vector of Cards to see whether it contains a certain card. It may not be obvious why this function would be useful, but it gives us a chance to demonstrate two ways to go searching for things, a linear search and a binary search.

Linear search is the more obvious of the two; it involves traversing the deck and comparing each card to the one we are looking for. If we find it we return the index where the card appears. If it is not in the deck, we return -1.

int find_card(const Card& card, const vector<Card>& deck)
{
    for (int i = 0; i < deck.size(); i++) {
        if (deck[i].equals(card)) return i;
    }
    return -1;
}

The loop here is exactly the same as the loop in print_deck.

Inside the loop, we compare each element of the deck to card. The function returns as soon as it discovers the card, which means we do not have to traverse the entire deck if we find the card we are looking for. If the loop terminates without finding the card, we know the card is not in the deck and return -1.

To test this function, we could write:

vector<Card> deck = build_deck();
int index = find_card(deck[17], deck);
cout << "Your card was found at index " << index << "." << endl;

Assuming you have finished writing build_deck, the output of this code is:

Your card was found at index 17.

12.9. Binary search

If the cards in the deck are not in order, there is no way to search that is faster than the linear search. We have to look at every card, since otherwise there is no way to be certain the card we want is not there.

But when you look for a word in a dictionary, you don’t search linearly through every word. The reason is that the words are in alphabetical order. As a result, you probably use an algorithm that is similar to a binary search:

1. Start in the middle somewhere.

2. Choose a word on the page and compare it to the word you are looking for.

3. If you found the word you are looking for, stop.

4. The the word you are looking for comes after the word on the page, flip to somewhere later in the dictionary and go to step 2.

5. The the word you are looking for comes befor the word on the page, flip to somewhere earlier in the dictionary and go to step 2.

If you ever get to the point where there are two adjacent words on the page and your word comes between them, you can conclude that your word is not in the dictionary. The only alternative is that your word has been misfiled somewhere, but that contradicts our assumption that the words are in alphabetical order.

In the case of a deck of cards, if we know that the cards are in order, we can write a version of find that is much faster. The best way to write a binary search is with a recursive function. That’s because the bisection method it employs is naturally recursive.

The trick is to write a function called bin_search that has two indices as parameters, l and h (for “low” and “high”), indicating the segment of the vector that should be searched (including both l and h).

1. To search the vector, choose an index mid way between l and h, and call it m. Compare the card at m to the card you are looking for.

2. If you found it, stop.

3. If the card at m is higher than your card, search in the range from l to m-1.

4. If the card at m is lower than your card, search in the range from m+1 to h.

Steps 3 and 4 look suspiciously like recursive invocations. Here’s what this all looks like translated into C++:

int bin_search(const Card& card, const vector<Card>& deck, int l, int h) {
    int m = (l + h) / 2;

    if (deck[m].equals(card)) return mid;

    if (deck[m].is_greater(card))
        return bin_search(card, deck, l, m-1)
    else
        return bin_search(card, deck, m+1, h);
}

Although this code contains the kernal of a binary search, it is still missing a piece. As it is currently written, if the card is not in the deck, it will recurse forever. We need a way to detect this condition and deal with it properly (by returning -1).

The easiest way to tell that your card is not in the deck is if there are no cards in the deck, which is the case if h is less than l. Well, there are still cards in the deck, of course, but what we mean is that there are no cards in the segment of the deck indicated by l and h. So to fix our bin_search function, add the following as the first line of its body:

if (h < l) return -1;

We can add another line at the beginning to enable us to watch the sequence of recursive calls and convince ourselves that it will eventually reach the base case.

cout << l << ", " << h;

Running:

index = bin_search(deck[23], deck, 0, 51);
cout << "Card found at index " << index << endl;

yields:

0, 51
0, 24
13, 24
19, 24
22, 24
Card found at index 23

Creating a fake card that is not in the deck (the 15 of Diamonds) and tesing with:

Card fake_card(2, 15);
index = bin_search(fake_card, deck, 0, 51);
cout << "Card found at index " << index << endl;

yields:

0, 51
26, 51
26, 37
26, 30
26, 27
26, 25
Card found at index -1

These tests don’t prove that the program is correct. In fact, no amount of testing can prove that a program is correct. On the other hand, by looking at a few cases and examining the code, you might be able to convince yourself.

The number of recursive calls is fairly small, typically 6 or 7. That means we only had to call equals and is_greater 6 or 7 times, compared to up to 52 times if we did a linear search. In general, binary search is much faster than a linear search, especially for large vectors.

Two common errors in recursive programs are forgetting to include a base case and writing the recursive call to that the base case is never reached. Either error will cause an infinite recursion, in which case C++ will (eventually) generate a run-time error.

12.10. Decks and subdecks

Looking at the interface to bin_search:

int bin_search(const Card& card, const vector<Card>& deck, int l, int h)

it might make sense to treat three of the parameters, deck, l, and h, as a single parameter that specifies a subdeck.

This kind of thing is quite common, and you could think of it as an abstract parameter. By “abstract”, we mean something that is not literally part of the program text, but which describes the function of the program at a higher level.

For example, when you call a function and pass a vector and the bounds l and h, there is nothing that prevents the called function from accessing parts of the vector that are out of bounds. So you are not literally sending a subset of the deck; you are really sending the whole deck. But as long as the recipient plays by the rules, it makes sense to think of it, abstractly, as a subdeck.

There is one other example of this kind of abstraction that you might have noticed in the Structures chapter when we referred to an “empty” data structure in the Fill-in functions section. The reason “empty” is in quotation marks was to suggest that it is not literally accurate. All variables have values all the time. When you create them, they are given default values. So there is no such thing as an empty object.

But if the program guarantees that the current value of a variable is never read before it is written, then the current value is irrelevant. Abstractly, it makes sense to think of such a variable as “empty.”

This kind of thinking, in which a program comes to take on meaning beyond what is literally encoded, is a very important part of thinking like a computer scientist. Sometimes, the word “abstract” gets used so often in so many contexts that it is hard to interpret. Nevertheless, abstraction is a central idea in computer science (as well as many other fields).

A more general definition of abstraction is “The process of modeling a complex system with a simplified description in order to suppress unnecessary details while capturing relevant behavior.”

12.11. Glossary

abstraction

The process of modeling a complex system with a simplified description in order to supress unnecessary details while capturing relevant behavior.

binary search

An algorithm for finding an element in an ordered list of values in logarithmic time by comparing the search value with the middle element of the list and then recursively repeating this process with either the lower or upper half of the remaining values depending on the result of the comparision.

encode

To prepresent one set of values using another set of values, by constructing a mapping between them.

ear search A method for finding an element in a list by sequentially checking each element in order starting with the first. Also called a sequential search.

12.12. Exercises

• Chapter 12 Exercise Set 0: Chapter Review