An Instructional Story</<p><hr><p> <h2><a name="toc_anchor_0"></a></h2>  > </head> <BODY>  <h2><a name="toc_anchor_1">Lecture Notes for Advanced Programming II</a></h2>   <h3><a name="toc_anchor_2">12 November 2002 - An Instructional Story</a></h3>  <p><hr><p> <h2><a name="toc_anchor_3">Internet Addresses</a></h2>  <ul> <p><li> This story is based on true e-mail. <p><li> An Internet address can be either <ul> <p><li> a fully qualified domain name <p><pre> www.monmouth.edu </pre><p> <p><li> or a dotted quad. <p><pre> 192.100.64.7 </pre><p> </ul> <p><li> Write a program to find dotted quads. </ul> <p><hr><p>  <h2><a name="toc_anchor_4">First Cut</a></h2>  <ul> <p><li> This code has a problem. <p><pre> 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 </pre><p> <p><li> What's wrong? <ul> <p><li> <code>*</code> has lower precedence than <code>[]</code>. <p> <code>*i[nIdx]</code> is <code>*(i[nIdx])</code>. </ul> <p><li> But what's <code>i[nIdx]</code>? <ul> <p><li> Remember - iterators are like pointers. <p> <code>i[nIdx]</code> is <code>*(i + nIdx)</code>. <p><li> Random iterators only. </ul> </ul> <p><hr><p>  <h2><a name="toc_anchor_5">Generic Algorithms to the Rescue</a></h2>  <ul> <p><li> We can solve this problem with generic algorithms. <p><pre> 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), * cp = find_if(*i, ep, not1(ptr_fun(isdigit))) if cp != ep goto exit_fun i++ found = true </pre><p> <p><li> <code>not1()</code> and <code>ptr_fun()</code> are function adapters. </ul> <p><hr><p>  <h2><a name="toc_anchor_6">But Wait - There's More</a></h2>  <ul> <p><li> We're not done yet. <p><pre> 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. </pre><p> <p><li> No more loops, no more iterator variables. <p><li> Developed the handy predicate <code>is_number()</code>. </ul> <p><hr><p>  <h2><a name="toc_anchor_7">Lessons to Learn</a></h2>  <ul> <p><li> Know and use your generic algorithms. <ul> <p><li> Even the trivial ones. </ul> <p><li> Use generic algorithms to eliminate loops. <ul> <p><li> Less work, less risk. </ul> <p><li> Eliminate iterator variables. <ul> <p><li> Easier to understand, avoid invalidation problems. </ul> </ul> <p><hr><p> This page last modified on 12 November 2002. </BODY> </HTML>