Assignment ANO() Code Review

Lecture Notes for Advanced Programming II

29 November 2001 - An Instructional Story

Two Similar Data Structures

Some software was using two similar data structures.

typedef std::pair<word, word>    msg;

static inline word waiter_tag(const waiter & w) {
  return w.second; 
  }

static  std::list<msg>           mpool;
typedef std::list<msg>::iterator mpool_iter;


typedef std::pair<process::id, word> waiter;

static inline process::id waiter_id(const wlist_iter & wi) {
  return wi->first;
  }

static  std::list<waiter>            waiters;
typedef std::list<Kwaiter>::iterator  wlist_iter;

Warning 1 - duplicated code is bad code.

Looking For List Members

Search the list for specific members.

static bool msg_match(const msg m, word t) {
  return msg_tag(m) == t;
  }

static bool find_msg(word t, m_iter & mi) {

  const m_iter & e = mpool.end();
  const m_iter & b = mpool.begin();

  mi = std::find_if(b, e, bind2nd(ptr_fun(msg_match), t));

  return mi != e;
  }


static bool waiter_match(const waiter w, process::id t) {
  return waiter_id(w) == t;
  }

static bool find_waiter(process::id t, w_iter & wi) {

  const w_iter & e = waiters.end();
  const w_iter & b = waiters.begin();

  wi = std::find_if(b, e, bind2nd(ptr_fun(waiter_match), t));

  return wi != e;
  }

Warning 2 - duplicated code is bad code.

Why is The Code Not Identical?

What are the different things?
- The containers - list<msg>, list<waiters>.
- The predicates - msg_match(), waiter_match().
- The search value.
- The reference iterator.
What are the types involved?
- The container type - container_type.
- The search-value type - tag_type.
- The reference iterator is a container iterator.
  - It has type container_type::iterator.
- The predicate has return type bool.
  - One argument is a container value.
    - It has type container_type::value_type.
  - The other argument is the search value.
    - It has type tag_type.

How Should The Code Be Unduplicated?

It's a function, so maybe templates.

What are the template parameters?

The container type.
The tag type.

The match function type.

Derivable from the container and tag types.
Accepts container_type::value type.
Accepts tag_type.

Returns bool

The found iterator type.

Derivable from the container type.
It type container_type::iterator.

A First Step

Two template parameters, four function parameters.

It might be better to go slow at first.

$ cat t.cc
#include 

template < typename container_type>
bool find_value(const container_type & values) {
  return true;
  }

int main() {
  std::vector ivec;
  find_value(ivec);
  }

$ g++ -c -ansi -pedantic -Wall t.cc

$

The Next Step

Look for a value next.

$ cat t.cc
#include <vector>
#include <algorithm>

template<typename container_type, typename tag_type>
bool find_value(
  const container_type & values,
  const tag_type & value) 
  {
   const container_type::const_iterator e = values.end();
   return std::find(values.begin(), e, value) != e;
  }

int main() {
  std::vector<int> ivec;
  find_value(ivec, 3);
  }

$ g++ -c -ansi -pedantic -Wall t.cc
t.cc: In function bool find_value(const container_type&, 
      const tag_type&):
t.cc:9: parse error before e
t.cc: In function bool find_value(const container_type&, 
      const tag_type&) [with container_type = std::vector<int, 
      std::allocator<int> >, tag_type = int]:
t.cc:15:   instantiated from here
t.cc:10: e undeclared (first use this function)
t.cc:10: (Each undeclared identifier is reported only once 
         for each function it appears in.)

$

Oops

What's wrong?
C++ parsing is so complicated, the compiler can't do it alone.
- It can't tell what is a type and what isn't.
- It can't tell that container_type::iterator is a type.
- This is similar to the typedef problem in lexing-parsing.
The programmer has to help the compiler identify types.
- The typename keyword indicates a type.
- This is separate from typename in template lists.

Using `typename`

Adding typename solves the problem.

$ cat t.cc
#include <vector>
#include <algorithm>

template<typename container_type, typename tag_type>
bool find_value(
  const container_type & values,
  const tag_type & value) 
  {
   const typename container_type::const_iterator e = values.end();
   return std::find(values.begin(), e, value) != e;
  }

int main() {
  std::vector<int> ivec;
  find_value(ivec, 3);
  }

$ g++ -c -ansi -pedantic -Wall t.cc

$

Now What?

Let's add the value iterator.

$ cat t.cc
#include <vector>
#include <algorithm>

template < typename container_type, typename tag_type >
bool find_value(
  const container_type & values,
  container_type::const_iterator & vi,
  const tag_type & value) 
  {
   const typename container_type::const_iterator e = values.end();
   vi = std::find(values.begin(), e, value);
   return vi != e;
  }

int main() {
  std::vector<int> ivec;
  std::vector<int>::const_iterator vi;
  find_value(ivec, vi, 3);
  }

$ g++ -c -ansi -pedantic -Wall t.cc
t.cc:7: type specifier omitted for parameter
t.cc:7:   perhaps you want typename container_type::const_iterator 
        to make it a type
t.cc:7: parse error before & token
t.cc: In function int main():
t.cc:18: no matching function for call to find_value(std::vector<int, 
   std::allocator<int> >&, std::__normal_iterator<const int*, 
   std::vector<int, std::allocator<int> > >&, int)

$

One More Time

Another error, another typename.

$ cat t.cc
#include 
#include 

template
bool find_value(
  const container_type & values,
  typename container_type::const_iterator & vi,
  const tag_type & value) 
  {
   const typename container_type::const_iterator e = values.end();
   vi = std::find(values.begin(), e, value);
   return vi != e;
  }

int main() {
  std::vector ivec;
  std::vector::const_iterator vi;
  find_value(ivec, vi, 3);
  }

cl g++ -c -ansi -pedantic -Wall t.cc

$

The Result

template<typename container_type, typename tag_type>
bool find_value(
  container_type & values,
  bool (* match)(typename container_type::value_type, tag_type),
  tag_type tag,
  typename container_type::iterator & vi)
 {
  typename container_type::iterator e = values.end();
  typename container_type::iterator b = values.begin();
  vi = std::find_if(b, e, bind2nd(ptr_fun(match), tag));
  return vi != e;
  }

static bool msg_match(const msg m, word t) {
  return msg_tag(m) == t;
  }

static bool find_msg(word t, mpool_iter & mi) {
  return find_value(mpool, msg_match, t, mi);
  }

static bool waiter_match(const waiter w, process::id t) {
  return waiter_id(w) == t;
  }

static bool find_waiter(process::id t, wlist_iter & wi) {
  return find_value(waiters, waiter_match, t, wi);
  }

Points to Remember

Duplicated code is bad code.
- Almost duplicated code is worse.
typename helps the compiler recognize type names.
- This is a dreadful hack to get c++ to compile.
- When you have to help the compiler over the humps,
  something sucks.
Don't write complicated template functions.
- "Complicated" means lots of types, lots of parameters.
- Hard to write, hard to use, hard to fix.
- This is a bad example - from simple duplication to complex templates.
Develop template functions (and classes) incrementally.
- Little by little does the trick.

This page last modified on 19 December 2001.