Lecture Notes for Advanced Programming II

7 March 2002 - 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) {
    i = tkns.begin();
    while(i != tkns.end()) {
      for (nIdx = 0; nIdx < strlen(*i); nIdx++)
        if (!isdigit(*i[nIdx]))
          goto exit_fun;
      i++;
      }
    found = true;
    }
  

• What's wrong?

  • * has lower precedence than [].

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

• But what's i[nIdx]?

  • Remember - iterators are like pointers.

    i[nIdx] is *(i + 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 i = tkns.begin();
  
    while (i != tkns.end()) {
  
      char * ep = *i + strlen(*i);
      char * cp = find_if(*i, ep, not1(ptr_fun(isdigit)));
      if (cp != ep)
        goto exit_fun;
  
      i++;
      }
  
    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);
    const char * fp = 
      find_if(cp, ep, not1(ptr_fun(isdigit)));
  
    return fp == ep;
    }
  
  
  bool dotted_quad(const string & addr) {
  
    vector<char *> tkns = split(addr, ".");
  
    if (tkns.size() == 4) {
  
      const vector<char *>::iterator e = tkns.end();
      const vector<char *>::iterator f = 
        find_if(tkns.begin(), e, not1(ptr_fun(is_number)));
  
      if (f != 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 2 April 2002.