[boost] [iterators] Proof-of-concept for a sentinel iterator adapter

13 May 2009

      Attached is proof-of-concept code for a sentinel iterator adapter. It 
turns a pointer to sentinel terminated sequence, such as a C-style 
string, into a forward iterator with a conforming end iterator.

This is more efficient than doing a separate sequence traversal just to 
find the end.

I'm a little surprised that Boost doesn't already have such an iterator 
adapter. Or am I just missing it?

Would a production version of this iterator adapter be a worthwhile 
addition to Boost.Iterators?

Any other comments appreciated,

--Beman

//  sentinel terminated sequence iterator proof-of-concept
//  Copyright Beman Dawes, 2009

#include <cassert>

  //  sentinel terminated sequence iterator

  template < class T, T Sentinel = T() >
  class sentinel_iterator
  {
  public:
    sentinel_iterator() : m_ptr(0) {}  // construct end iterator

    sentinel_iterator( T * p ) : m_ptr( (p && *p != m_sentinel) ? p : 0 ) {}

    sentinel_iterator & operator++()
    {
      assert(m_ptr);
      if ( *++m_ptr == m_sentinel ) m_ptr = 0;
      return *this;
    }

    T & operator*() const
    {
      assert(m_ptr);
      return *m_ptr;
    }

    bool operator==( const sentinel_iterator & rhs ) const
    {
      return m_ptr == rhs.m_ptr;
    }

    bool operator!=( const sentinel_iterator & rhs ) const
    { 
      return m_ptr != rhs.m_ptr;
    }

  private:
    T * m_ptr;  // 0 == the end iterator
    static const T m_sentinel = Sentinel;
  };

int main()
{
  // test cases using default sentinel

  sentinel_iterator<char> it( "abc" );

  assert( it != sentinel_iterator<char>() );
  assert( *it == 'a' );
  assert( *++it == 'b' );
  assert( *++it == 'c' );
  assert( ++it == sentinel_iterator<char>() );

  sentinel_iterator<char> it2( "" );
  assert( it2 == sentinel_iterator<char>() );

  sentinel_iterator<char> it3( 0 );
  assert( it3 == sentinel_iterator<char>() );

  // test cases using non-default sentinel

  typedef sentinel_iterator<unsigned, -1> my_iter_type;

  unsigned data[] = { 0, 1, -1 };
  my_iter_type my_it( data );

  assert( my_it != my_iter_type() );
  assert( *my_it == 0 );
  assert( *++my_it == 1 );
  assert( ++my_it == my_iter_type() );

  unsigned my_sentinel = -1;
  my_iter_type my_it2( &my_sentinel );
  assert( my_it2 == my_iter_type() );

  my_iter_type my_it3( 0 );
  assert( my_it3 == my_iter_type() );

  return 0;
}