12.8. Searching

Container sizes and ordinary indices use std::size_t from <cstddef>. This search returns std::ptrdiff_t, the signed difference type from the same header, because -1 means "not found." Check that result before using it as an index. These examples assume the deck's size fits in std::ptrdiff_t. C++20's std::ssize from <iterator> provides a signed size when we need to subtract one, including for an empty deck.

The next function I want to write is find, which searches through a vector of playing_cards to see whether it contains a certain card. It may not be obvious why this function would be useful, but it gives me a chance to demonstrate two ways to go searching for things, a linear search and a bisection 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.

std::ptrdiff_t find (const playing_card& card, const std::vector<playing_card>& deck) {
  for (std::size_t i = 0; i < deck.size(); i++) {
    if (equals (deck[i], card)) return static_cast<std::ptrdiff_t>(i);
  }
  return -1;
}

The loop here is exactly the same as the loop in print_deck. In fact, when I wrote the program, I copied it, which saved me from having to write and debug it twice.

Inside the loop, we compare each element of the deck to card. The function returns as soon as it discovers the card, which means that 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, I wrote the following:

std::vector<playing_card> deck = build_deck ();

std::ptrdiff_t index = find (deck[17], deck);
std::cout << "I found the card at index = " << index << std::endl;

The output of this code is

I found the card at index = 17

The code below searches for a particular card in a standard deck of 52 cards. It returns the index that the card was located at.

Example c192_12_8

#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

struct playing_card {
    int suit, rank;

    playing_card ();
    playing_card (int s, int r);
    void print () const;
};

std::vector<playing_card> build_deck();

bool equals (const playing_card& c1, const playing_card& c2){
    return (c1.rank == c2.rank && c1.suit == c2.suit);
}

void print_deck(const std::vector<playing_card>& deck);

std::ptrdiff_t find (const playing_card& card, const std::vector<playing_card>& deck);

int main() {
    std::vector<playing_card> deck = build_deck();
    playing_card card (3, 6);
    std::cout << find(card, deck);
}

Say we have standard deck of cards. According to our find() function, the for loop will execute a minimum of times, and a maximum of times while searching for a particular card.

Check answer

build_euchre_deck() returns the deck of Euchre cards defined on the previous page. If we run the following code, what is returned?

int main() {
   EuchreDeck = build_euchre_deck();
   playing_card card (3, 6);
   find(card, EuchreDeck);
 }

.

Check answer