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

Subject: Re: [boost] [iterators] Proof-of-concept for a sentinel iterator adapter
From: Peter Dimov (pdimov_at_[hidden])
Date: 2009-05-13 11:19:00

> 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.

No, it is not. :-)

PS:

#include <boost/functional/hash.hpp>
#include <algorithm>
#include <iostream>
#include <windows.h>

static size_t test_strlen( char const * s );
static size_t test_sentinel( char const * s );

int main()
{
    int const N = 10000000;

    DWORD t1 = timeGetTime();

    size_t m1 = 0;

    for( int i = 0; i < N; ++i )
    {
        m1 += test_strlen( "This is a test." );
    }

    DWORD t2 = timeGetTime();

    size_t m2 = 0;

    for( int i = 0; i < N; ++i )
    {
        m2 += test_sentinel( "This is a test." );
    }

    DWORD t3 = timeGetTime();

    std::cout << t2 - t1 << " (" << m1 << "); " << t3 - t2 << " (" << m2 << 
")\n";
}

static size_t test_strlen( char const * s )
{
    return boost::hash_range( s, s + strlen( s ) );
}

//  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;
  };

static size_t test_sentinel( char const * s )
{
    return boost::hash_range( sentinel_iterator< char const >( s ), 
sentinel_iterator< char const >() );
}