Lecture Notes for Advanced Programming II

16 October 2001 - An Instructional Story

Internet Addresses

• This story is based on true e-mail.

• An Internet address can be either

  • a fully qualified domain name

    www.monmouth.edu

  • or a dotted quad.

    192.100.64.7

• Write a program to find dotted quads.

First Cut

• This code has a problem.

  bool found = false;
  vector<char *> tkns = split(addr, ".");
  
  if (tkns.size() == 4) {
    vecIter = tkns.begin();
    while(vecIter != tkns.end()) {
      for (nIdx = 0; nIdx < strlen(*vecIter); nIdx++)
        if (!isdigit(*vecIter[nIdx]))
          goto exit_fun;
      vecIter++;
      }
    found = true;
    }
  

• What's wrong?

  • * has lower precedence than [].

    *vecIter[nIdx] is *(vecIter[nIdx]).

• But what's vecIter[nIdx]?

  • Remember - iterators are like pointers.

    vecIter[nIdx] is *(vecIter + nIdx).

  • Random iterators only.

Generic Algorithms to the Rescue

• We can solve this problem with generic algorithms.

  bool found = false;
  vector<char *> tkns = split(addr, ".");
  
  if (tkns.size() == 4) {
  
    vector<char *>::iterator vecIter = tkns.begin();
  
    while (vecIter != tkns.end()) {
  
      char * ep = *vecIter + strlen(*vecIter);
  
      if (find_if(*vecIter, ep, not1(ptr_fun(isdigit))) != ep)
        goto exit_fun;
  
      vecIter++;
      }
  
    found = true;
    }
  

• not1() and ptr_fun() are function adapters.

But Wait - There's More

• We're not done yet.

  static bool is_number(const char * cp) {
  
    const char * ep = cp + strlen(cp);
  
    return find_if(cp, ep, not1(ptr_fun(isdigit))) == ep;
    }
  
  
  bool dotted_quad(const string & addr) {
  
    vector<char *> tkns = split(addr, ".");
  
    if (tkns.size() == 4) {
  
      const vector<char *>::iterator e = tkns.end();
  
      if (find_if(tkns.begin(), e, not1(ptr_fun(is_number))) != e) {
        // Found a non number.
        }
      else {
        // They're all numbers.
        }
      }
    }
  

• No more loops, no more iterator variables.

• Developed the handy predicate is_number().

Lessons to Learn

• Know and use your generic algorithms.

  • Even the trivial ones.

• Use generic algorithms to eliminate loops.

  • Less work, less risk.

• Eliminate iterator variables.

  • Easier to understand, avoid invalidation problems.

This page last modified on 6 December 2001.