Range-checked list class?

[DragonOsman]

How do I make a list class range-checked? The code I'm using is here: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb (too long to put in here, I think - I could be wrong, though).

For an exercise in the C++ intro book Programming: Principles and Practice Using C++ 2nd Edition, I have to add range-checking to the class. But I don't know how to add it in the iterator. I was thinking of adding range-checking in advance(), but that might not be enough.

Also, I'm using Visual Studio with the Visual Leak Detector, so that I can see if there are memory leaks. And right now there is one, due to the call to insert on line 56 (even though VLD is indicating line 57 which is the call to std::for_each).

[helios]

Consider this:

list<int> l;
//populate
assert(l.size() >= 2);
auto it = l.end();
--it;
++it; //valid?
++it; //valid?
it = l.begin();
++it;
--it; //valid?
--it; //valid? 

[DragonOsman]

So I add checks in my iterator ++ and -- operators for whether or not curr->succ and curr->prev, respectively, are valid? That's all?

And what about that leak? What should I do to fix it?

[JLBorges]

Also add checks for the dereference and indirection operators to verify that the iterator 'points' to a dereferencible element.

A generic approach towards range-checked iterators could look something like this:

#include <iostream>
#include <stdexcept>
#include <iterator>
#include <type_traits>

namespace range_checked
{
    template < typename BASE > struct bidirectional_iterator
    {
        using value_type = typename std::remove_reference< decltype( *std::declval<BASE>() ) >::type ;
        using reference = decltype( *std::declval<BASE>() ) ;
        // etc.
        using iterator_category = std::bidirectional_iterator_tag ;

        static_assert( std::is_convertible< typename std::iterator_traits<BASE>::iterator_category,
                                            std::bidirectional_iterator_tag >::value,
                       "adaptee must be at least a bidirectional iterator" ) ;

        bidirectional_iterator( BASE current, BASE begin, BASE end )
            : current(current), begin(begin), end(end) {}

        decltype(auto) operator* () { return *dereferencable_current() ; }
        decltype(auto) operator-> () { return &**this ; }

        bidirectional_iterator& operator++() { ++dereferencable_current() ; return *this ; }
        bidirectional_iterator operator++(int) { auto temp(*this) ; ++*this ; return temp ; }

        bidirectional_iterator& operator--() { --decrementable_current() ; return *this ; }
        bidirectional_iterator operator--(int) { auto temp(*this) ; --*this ; return temp ; }

        bool operator== ( const bidirectional_iterator& that ) const { return current == that.current ; }
        bool operator!= ( const bidirectional_iterator& that ) const { return !(*this==that) ; }

        private:

            BASE current ;
            BASE begin ;
            BASE end ;

            auto& dereferencable_current()
            {
                if( current == end ) throw std::out_of_range( "not dereferencable/incrementable" ) ;
                return current ;
            }

            auto& decrementable_current()
            {
                if( current == begin ) throw std::out_of_range( "not decrementable" ) ;
                return current ;
            }
    };

    template < typename CNTR > auto begin( CNTR& cntr )
    {
        auto b = std::begin(cntr) ;
        return bidirectional_iterator< decltype(b) > { b, b, std::end(cntr) } ;
    }

    template < typename CNTR > auto end( CNTR& cntr )
    {
        auto e = std::end(cntr) ;
        return bidirectional_iterator< decltype(e) > { e, std::begin(cntr), e } ;
    }

    template < typename CNTR > auto cbegin( const CNTR& cntr )
    {
        auto b = std::begin(cntr) ;
        return bidirectional_iterator< decltype(b) > { b, b, std::end(cntr) } ;
    }

    template < typename CNTR > auto cend( const CNTR& cntr )
    {
        auto e = std::end(cntr) ;
        return bidirectional_iterator< decltype(e) > { e, std::begin(cntr), e } ;
    }

    template < typename CNTR > auto begin( const CNTR& cntr ) { return cbegin(cntr) ; }
    template < typename CNTR > auto end( const CNTR& cntr ) { return cend(cntr) ; }

    // likewise for rbegin, rend, crbegin, crend (use std::rbegin, std::rend)
}

int main()
{
      int a[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;

      try { for( auto iter = range_checked::begin(a) ; ; ++iter ) std::cout << *iter << ' ' ; }
      catch( const std::out_of_range& ) { std::cout << "reached end\n" ; }

      try { for( auto iter = --range_checked::cend(a) ; ; --iter ) std::cout << *iter << ' ' ; }
      catch( const std::out_of_range& ) { std::cout << "reached begin\n" ; }
}

http://coliru.stacked-crooked.com/a/57ac51dce2ae25b0

[DragonOsman]

How about this?

template<typename Elem>
list<Elem>::iterator &list<Elem>::iterator::operator++() 
{ 
	if (!curr->succ)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ; 
	return *this; 
}

template<typename Elem>
list<Elem>::iterator &list<Elem>::iterator::operator--() 
{ 
	if (!curr->prev)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev; 
	return *this; 
}

template<typename Elem>
list<Elem>::const_iterator &list<Elem>::const_iterator::operator++()
{
	if (!curr->succ)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this;
}

template<typename Elem>
list<Elem>::const_iterator &list<Elem>::const_iterator::operator--()
{
	if (!curr->prev)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this;
}

template<typename Elem>
list<Elem>::iterator list<Elem>::iterator::operator++(int) 
{ 
	auto ret = *this; 
	if (!curr->succ)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ; 
	return ret; 
}

template<typename Elem>
list<Elem>::iterator list<Elem>::iterator::operator--(int) 
{ 
	auto ret = *this; 
	if (!curr->prev)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev; 
	return ret; 
}

template<typename Elem>
list<Elem>::const_iterator list<Elem>::const_iterator::operator++(const int) 
{ 
	auto ret = *this; 
	if (curr->succ)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ; 
	return ret; 
}

template<typename Elem>
list<Elem>::const_iterator list<Elem>::const_iterator::operator--(const int) 
{ 
	auto ret = *this; 
	if (curr->prev)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev; 
	return ret; 
}

I need an easier way to implement the check for the iterator being dereference-able.

And again, how do I fix the memory leak?

[JLBorges]

The checks should be:
increment: curr != nullptr
decrement: curr not pointing to the node at the beginning of the list
dereferenceable: curr != nullptr

[DragonOsman]

So I shouldn't check for cur->succ being nullptr in increment?

I fixed the memory leak already, by the way.

Edit: I added the specified checks.

template<typename Elem>
typename list<Elem>::iterator &list<Elem>::iterator::operator++() 
{ 
	if (curr != nullptr)
	{
		curr = curr->succ;
	}
	return *this; 
}

template<typename Elem>
typename list<Elem>::iterator &list<Elem>::iterator::operator--() 
{ 
	if (curr != first)
	{
		curr = curr->prev;
	}
	return *this; 
}

template<typename Elem>
typename list<Elem>::const_iterator &list<Elem>::const_iterator::operator++()
{
	if (curr != nullptr)
	{
		curr = curr->succ;
	}
	return *this;
}

template<typename Elem>
typename list<Elem>::const_iterator &list<Elem>::const_iterator::operator--()
{
	if (curr != first)
	{
		curr = curr->prev;
	}
	return *this;
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::iterator::operator++(int) 
{ 
	auto ret = *this; 
	if (curr != nullptr)
	{
		curr = curr->succ;
	}
	return ret; 
}

template<typename Elem>
typename list<Elem>::iterator list<Elem>::iterator::operator--(int) 
{ 
	auto ret = *this; 
	if (curr != first)
	{
		curr = curr->prev;
	}
	return ret; 
}

template<typename Elem>
typename list<Elem>::const_iterator list<Elem>::const_iterator::operator++(const int) 
{ 
	auto ret = *this; 
	if (curr != nullptr)
	{
		curr = curr->succ;
	}
	return ret; 
}

template<typename Elem>
typename list<Elem>::const_iterator list<Elem>::const_iterator::operator--(const int) 
{ 
	auto ret = *this; 
	if (curr != first)
	{
		curr = curr->prev;
	}
	return ret; 
}

Is it fine like this, or should I something else other than just returning in case of error? Like, for example, would it be a good idea to throw an "out of range" exception after all?