Generalized iterator ranges

From: Kevin S. Van Horn (kevin.vanhorn_at_[hidden])
Date: 2001-10-26 11:15:22

On Fri, 26 Oct 2001, Ben Cooling wrote:

> >How about generalizing even further: instead of specifying the end of
> >range by an iterator, allow an arbitrary function that takes
> >an iterator
> >as argument.
>
> And a reference to the container, of course.

No, since generic algorithms don't know and shouldn't know about
containers; they only know about iterator ranges.  In some cases, there is
no container object (input iterators, arrays).  As an example of what I'm
talking about, here's what the copy algorithm would look like:

--- begin code ---

template <typename InputIterator, typename OutputIterator,
          typename IterTest>
OutputIterator copy(InputIterator src, IterTest srcend,
                    OutputIterator dst)
{
  for ( ; !endrange(src,srcend); ++src, ++dst)
    *dst = *src;
}

--- end code ---

where

--- begin code ---

template <typename T, typename U>
inline bool endrange(T it, U x)
{
  return endrange_aux<T,U>::fct(it, x);
}

template <typename T, typename U>
struct endrange_aux {
  static bool fct(T it, U x) { return x(it); }
};

template <typename T>
struct endrange_aux<T,T> {
  static bool fct(T it, T itend) { return it == itend }
};

--- end code ---

This scheme allows us to copy an array of char's using

  copy(src, src + n, dst);  // copy n characters

or

  copy(src, test_null<char const *>, dst);  // copy C-style string

or

  copy(src, count(n), dst); // copy n characters

where

--- begin code ---

template <typename Iterator> inline
bool test_null(Iterator it)
{
  return *it == 0;
}

class count {
  unsigned cnt;
public:
  count(unsigned n)
    : cnt(n) { }
  template <typename Iterator>
  bool operator()(Iterator it)
  {
    return cnt-- == 0;
  }
};

--- end code ---