Summary
In the STL there exist numerous concepts such as Random Access Containers, and Back Insertion Sequences. Boost has introduced several improved Range concepts. I've got a new one for the list, the Iterable concept.

---

Advertisement

As the description of Random Access Containers and Back Insertion Sequences at SGI.com will reveal, the C++ STL concepts are very complex. Boost has improved the situation somewhat with the introduction of the Range concepts and library.

All of these concepts are built on the idea of iterator pairs, representing a range of values. This framework, which while being extremely powerful and flexible, is more complex than is needed in some (many?) scenarios. When studying Scala -- which is arguably the only truly multi-paradigm language -- I realized that a Generic Programming framework can be built for collections from a single concept, which, for lack of a better name, I am currently calling the Iterable concept. An Iterable concept is as follows (written in imaginary-Heron):

concept Iterable {
  types {
    value_type;
  }
  signature {
    for_each[Procedure[value_type] P](P proc);
  }
}

In pseudo-C++ this translates to roughly:

concept Iterable  {
  public {
    typedef value_type;
    template<typename Procedure>
    void for_each(Procedure proc);
  }
}

The Procedure concept is simply a void function which takes only parameter, a reference to value_type.

This is an exceedingly simple concept. In order to model the Iterable concept a class has to only provide one typedef, and one member function. However, don't let the simplicity fool you. By taking lessons from functional techniques (mixed with value mutation), you can achieve very sophisticated code with relatively little work.

Example 1: Outputting all Elements from an Iterable

struct putter {
  putter(std::ostream& o, char delim = ' ') : out(x) { }
  template<typename T> void operator()(T& x) { 
    out << x << delim;  
  }
  std::ostream& out;
};

putter put(std::ostream& o) {
  return putter(o);
}

template<typename Iterable>
void print_iterable(Iterable& i) {
  i.for_each(put(std::cout));
}

Example 2: Concatenation of Iterable Collections

It is easy to concatenate two completely different Iterable collections, to create a new type which can be used whereever a Iterable is called for.

template<typename Iterable1, typename Iterable>
struct cat {
  cat(Iterable1& i1, Iterable2& i2)  
    : iterable1(i1), iterable2(i2) 
  { }
  template<typename Procedure>
  void for_each(Procedure proc) {
    iterable1.for_each(proc);
    iterable2.for_each(proc);
  }  
  typedef typename Iterable1::value_type value_type;
  Iterable1& iterable1;
  Iterable2& iterable2;
};

Example 3: Adapting a Container to an Iterable

Any class modeling a Container concept, can be trivially converted to an Iterable concept:

template<typename Container>
struct container_to_iterable {
  container_to_iterable(Container& x) : 
    container(x) 
  { }
  template<typename Procedure>
  for_each(Procedure p) {
    typename Container::iterator iter = container.begin();
    typename Container::iterator last = container.end();
    while (iter != last) {
      p(*iter++);
    }
  }
  Container& container;
}

Talk Back!

Have an opinion? Readers have already posted 16 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Christopher Diggins adds a new entry to his weblog, subscribe to his RSS feed.

Digg | del.icio.us | Reddit

About the Blogger

Christopher Diggins is a software developer and freelance writer. Christopher loves programming, but is eternally frustrated by the shortcomings of modern programming languages. As would any reasonable person in his shoes, he decided to quit his day job to write his own ( www.heron-language.com ). Christopher is the co-author of the C++ Cookbook from O'Reilly. Christopher can be reached through his home page at www.cdiggins.com.