Thinking In C++. Volume 2: Practical Programming

The simple assumption we’re after is, of course, that the secret number is within the current active range of unguessed numbers, beginning with the range [1, 100]. Suppose we label the endpoints of the range with the variables low and high. Each time you pass through the loop you need to make sure that if the number was in the range [low, high] at the beginning of the loop, you calculate the new range so that it still contains the number at the end of the current loop iteration^.

The goal is to express the loop invariant in code so that a violation can be detected at runtime. Unfortunately, since the computer doesn’t know the secret number, you can’t express this condition directly in code, but you can at least make a comment to that effect:

while (!guessed) {

  // INVARIANT: the number is in the range [low, high]

  …

}

If we were to stop this thread of discussion right here, we would have accomplished a great deal if it helps clarify how you design loops. Fortunately, we can do better than that. What happens when the user says that a guess is too high when it isn’t or that it’s too low when it in fact is not? The deception will in effect exclude the secret number from the new subrange. Because one lie always leads to another, eventually your range will diminish to nothing (since you shrink it by half each time and the secret number isn’t in there). We can easily express this condition concretely, as the following program illustrates^.

//: C02:HiLo.cpp

// Plays the game of Hi-lo to illustrate a loop invariant

#include

#include

#include

using namespace std;

int main() {

  cout << "Think of a number between 1 and 100\n";

cout << "I will make a guess; ";

cout << "tell me if I'm (H)igh or (L)ow\n";

  int low = 1, high = 100;

  bool guessed = false;

  while (!guessed) {

    // Invariant: the number is in the range [low, high]

    if (low > high) {  // Invariant violation

      cout << "You cheated! I quit\n";

      return EXIT_FAILURE;

    }

    int guess = (low + high) / 2;

    cout << "My guess is " << guess << ". ";

    cout << "(H)igh, (L)ow, or (E)qual? ";

    string response;

    cin >> response;

    switch(toupper(response[0])) {

      case 'H':

        high = guess - 1;

        break;

      case 'L':

        low = guess + 1;

        break;

      case 'E':

        guessed = true;

        break;

      default:

        cout << "Invalid response\n";

        continue;

    }

  }

  cout << "I got it!\n";

  return EXIT_SUCCESS;

} ///:~

The violation of the invariant is easily detected with the condition if (low > high), because if the user always tells the truth, we will always find the secret number before we run out of numbers to guess from. (See the last paragraph of the text that follows the program extractCode.cpp at the end of Chapter 3 for an explanation of the macros EXIT_FAILURE and EXIT_SUCCESS)^.

Assertions

The condition in the Hi-lo program depends on user input, so you’re powerless to always prevent a violation of the invariant. Most often, however, invariants depend only on the code you write, so they will always hold, if you’ve implemented your design correctly. In this case, it is clearer to make an assertion, which is a positive statement that reveals your design decisions^.

For example, suppose you are implementing a vector of integers, which, as you know, is an expandable array that grows on demand. The function that adds an element to the vector must first verify that there is an open slot in the underlying array that holds the elements; otherwise, it needs to request more heap space and copy the existing elements to the new space before adding the new element (and of course deleting the old array). Such a function might look like the following:^.

void MyVector::push_back(int x) {

   if (nextSlot == capacity)

      grow();

   assert(nextSlot < capacity);

   data[nextSlot++] = x;

}

In this example, data is a dynamic array of ints with capacity slots and nextSlot slots in use. The purpose of grow( ) is to expand the size of data so that the new value of capacity is strictly greater than nextSlot. Proper behavior of MyVector depends on this design decision, and it will never fail if the rest of the supporting code is correct, so we assert the condition with the assert( ) macro (defined in the header )^.

The Standard C library assert( ) macro is brief, to the point, and portable. If the condition in its parameter evaluates to non-zero, execution continues uninterrupted; if it doesn’t, a message containing the text of the offending expression along with its source file name and line number is printed to the standard error channel and the program aborts. Is that too drastic? In practice, it is much more drastic to let execution continue when a basic design assumption has failed. Your program needs to be fixed^.