Defining a range-checked iterator for vector

[Frank14]

Hi all,

The exercise 18 of chapter 20 of the book Programming Principle and Practice Using C++ says this: Define a range-checked iterator for vector (a random access iterator).
https://s2.postimg.org/wyjwt43ll/image.png

I think we should define a class named Iterator that has an std::vector as a data member and define all the features of a random-access iterator has (a long list of features):
http://www.cplusplus.com/reference/iterator/

And I think the code I'm working on now, (below), is not exactly the answer of the exercise. Do you too think so?

#include <std_lib_facilities_4.h>
using namespace std;

template<class T> class rg_ch_vector {

public:
	class Iterator;

	rg_ch_vector<T>() = default;  // Default construtor

	rg_ch_vector<T>(initializer_list<T> N) {     // Constructor with initializers
		for (const auto& l : N)
			push_back(l);
	}

	rg_ch_vector& operator=(const rg_ch_vector& N) {    // Copy assignment operator
		vec = N.vec;
		return *this;
	}

	rg_ch_vector(const rg_ch_vector& N) {     // Copy constructor (deep copy)
		vec = N.vec;
	}

	size_t size() const { return vec.size(); }

	Iterator begin() const { return (T*)(vec.data()); }
	// iterator to the first element

	Iterator end() const { return (T*)(vec.data()+vec.size());}
	// iterator to one beyond the last element

	void push_back(const T& v) { vec.push_back(v); }  // insert v at end

	T& operator[] (std::size_t pos) { return vec[pos]; }
	const T& operator[] (std::size_t pos) const { return vec[pos]; }

protected:
	vector<T> vec;
};

//****************************************

template<class T>
class rg_ch_vector<T>::Iterator {

private:
	T* iter = nullptr;
	friend class rg_ch_vector<T>;

public:
	Iterator(T* p) : iter(p) {  }

	Iterator& operator++() { iter++; return *this; } // forward
	Iterator& operator--() { iter--; return *this; } // backward

	T& operator*() { return *iter; } // get value (dereference)

	bool operator==(const Iterator& b) const { return iter == b.iter; }
	bool operator!=(const Iterator& b) const { return iter != b.iter; }
};

//****************************************************************************

int main()
{
	rg_ch_vector<int> v1;
	v1.push_back(3);
	v1.push_back(5);

	rg_ch_vector<int> v2 = { 10, 24, 36, 45 };

	for (auto p = v1.begin(); p != v1.end(); ++p)
	    cout << *p << ' ';
	cout << endl;

	for (const auto& v : v2)
		cout << v << ' ';
	cout << endl;

	system("pause");
	return 0;
}

I like to write the code myself, please guide me by explaining the exercise.

[JLBorges]

> I think we should define a class named Iterator that has an std::vector as a data member

An iterator certainly shouldn't be holding a copy of the vector: at best it should hold a reference to the vector.
Holding iterators representing the begin and end of the sequence would be a more flexible approach.


> and define all the features of a random-access iterator has (a long list of features):

Yes, a lot of boiler plate. Using boost's iterator helper would be a good idea.
http://www.boost.org/doc/libs/1_65_1/libs/utility/operators.htm#iterator


Here's a range-checked iterator adapter which uses the second approach (holds iterators representing the begin and end of the sequence being iterated over). For brevity, this range-checked iterator is only a bidirectional iterator:

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

namespace debug
{
    template < typename ITERATOR > struct range_checked_iterator
    {
        static_assert( std::is_convertible< typename std::iterator_traits<ITERATOR>::iterator_category,
                                            std::bidirectional_iterator_tag >::value,
                       "the iterator being adapted must be at least a bidirectional iterator" ) ;

        using iterator_category = std::bidirectional_iterator_tag ;
        using value_type = typename std::iterator_traits<ITERATOR>::value_type ;
        using difference_type = typename std::iterator_traits<ITERATOR>::difference_type ;
        using pointer = typename std::iterator_traits<ITERATOR>::pointer ;
        using reference = typename std::iterator_traits<ITERATOR>::reference ;

        range_checked_iterator( ITERATOR current, ITERATOR begin, ITERATOR end )
            : begin(begin), end(end), current(current) {}

        reference operator*() const { return *current ; }
        pointer operator->() const { return &**this ; }

        range_checked_iterator& operator++() { ++throw_if(end) ; return *this ; }
        range_checked_iterator operator++(int) { const auto prev(*this) ; ++*this ; return prev ; }

        range_checked_iterator& operator--() { --throw_if(begin) ; return *this ; }
        range_checked_iterator operator--(int) { const auto prev(*this) ; --*this ; return prev ; }

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

        private:
            const ITERATOR begin, end ;
            ITERATOR current ;

            ITERATOR& throw_if( ITERATOR x )
            {
                if( current == x ) throw std::out_of_range( "range checked iterator: out of range" ) ;
                return current ;
            }
    };
}

template < typename SEQ >
auto range_checked_begin( SEQ& seq ) -> debug::range_checked_iterator< decltype( std::begin(seq) ) >
{ return { std::begin(seq), std::begin(seq), std::end(seq) } ; }

template < typename SEQ >
auto range_checked_end( SEQ& seq ) -> debug::range_checked_iterator< decltype( std::end(seq) ) >
{ return { std::end(seq), std::begin(seq), std::end(seq) } ; }

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

int main()
{
    const int arr[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
    std::copy( range_checked_begin(arr), range_checked_end(arr), std::ostream_iterator<int>( std::cout, " ") ) ;
    std::cout << '\n' ;

    std::vector<std::string> vec { "1.abc", "2.defg", "3.hijklm", "4.nopqrst" } ;
    std::copy( range_checked_begin(vec), range_checked_end(vec), std::ostream_iterator<std::string>( std::cout, " ") ) ;
    std::cout << '\n' ;

    auto begin = range_checked_begin(vec), end = range_checked_end(vec) ;
    using reverse_iterator = std::reverse_iterator< decltype(begin) > ;
    auto rbegin = reverse_iterator(end), rend = reverse_iterator(begin) ;
    std::copy( rbegin, rend, std::ostream_iterator<std::string>( std::cout, " ") ) ;
    std::cout << '\n' ;

    std::reverse( range_checked_begin(vec), range_checked_end(vec) ) ;
    std::copy( range_checked_begin(vec), range_checked_end(vec), std::ostream_iterator<std::string>( std::cout, " ") ) ;
    std::cout << '\n' ;

    // these should throw
    try { --range_checked_begin(arr) ; } catch( const std::exception& e ) { std::cout << e.what() << '\n' ; }
    try { ++range_checked_end(vec) ; } catch( const std::exception& e ) { std::cout << e.what() << '\n' ; }
    try { --rbegin ; } catch( const std::exception& e ) { std::cout << e.what() << '\n' ; }
    try { ++rend ; } catch( const std::exception& e ) { std::cout << e.what() << '\n' ; }
}

http://coliru.stacked-crooked.com/a/f520f6468b8ad951

[Frank14]

Thanks but it's really too complicated and advanced for a learner of C++ that has learnt only those 20 chapters of that book.

Do you think I should change the code I offered?
By the way, it's only the base and if it's fine I add extra features to that to meet the requirements of a random access iterator.

[JLBorges]

> Do you think I should change the code I offered?

Yes.

A range checked iterator would report an error if we try to access an element which is not in the vector
or if we try to move an iterator beyond [begin,end] of the vector.

So the iterator should:
a. keep track of the element in the vector it is currently 'pointing' to
b. be aware of the bounds of the valid range.


A sketch of one possible way of implementing it:
(note: this does not meet the requirements of an iterator as defined by the standard library.)

#include <vector>
#include <stdexcept>

template < typename T > struct rc_iterator
{
    rc_iterator( std::vector<T>& vec, std::size_t pos ) : vec(vec), pos(pos) {}

    // range check: report an error if this is an attempt at out of range access
    T& operator*() const { if( pos >= vec.size() ) error() ; return vec[pos] ; }

    // range check: report an error if this is an attempt to increment beyond end
    rc_iterator& operator++ () { if( pos >= vec.size() ) error() ; ++pos ; return *this ;}
    T operator++(int) const { auto prev = *this ; ++*this ; return prev ; }

    // range check: report an error if this is an attempt to decrement beyond begin
    rc_iterator& operator-- () { if( pos == 0 ) error() ; --pos ; return *this ;}
    T operator--(int) const { auto prev = *this ; --*this ; return prev ; }

    // other range-checked operations

    bool operator== ( const rc_iterator& that ) const
    {
        // true if a. both iterators are iterating over the same the vector
        //         b. both iterators are 'pointing' to the same element in the vector
        return std::addressof(vec) == std::addressof(that.vec) && pos == that.pos ;
    }

    bool operator!= ( const rc_iterator& that ) const { return !( *this == that ) ; }

private:

    std::vector<T>& vec; // the vector over which this iterator iterators
    std::size_t pos ; // the position of the 'pointed to' element in the vector

    void error() const { throw std::out_of_range( "rc_iterator: range error" ) ; }
};

template < typename T >
rc_iterator<T> rc_begin( std::vector<T>& vec ) { return { vec, 0 } ; }

template < typename T >
rc_iterator<T> rc_end( std::vector<T>& vec ) { return { vec, vec.size() } ; }

#include <iostream>

int main()
{
    std::vector<int> vec { 0, 1, 2, 3, 4, 5 } ;

    for( auto iter = rc_begin(vec) ; iter != rc_end(vec) ; ++iter ) std::cout << *iter << ' ' ;
    std::cout << '\n' ;

    auto begin = rc_begin(vec) ;

    try { --begin ; } // error: out of range
    catch( const std::out_of_range& e ) { std::cout << "error: " << e.what() << '\n' ; }

    ++begin ; // fine
    std::cout << *begin << '\n' ; // fine: prints 1

    auto end = rc_end(vec) ;

    try { std::cout << *end << '\n' ; } // error: out of range
    catch( const std::out_of_range& e ) { std::cout << "error: " << e.what() << '\n' ; }

    try { ++end ; } // error: out of range
    catch( const std::out_of_range& e ) { std::cout << "error: " << e.what() << '\n' ; }

    --end ; // fine
    std::cout << *end << '\n' ; // fine: prints 5
}

http://coliru.stacked-crooked.com/a/a24771e43637e01d

[Frank14]

This return type in:
rc_iterator<T> rc_begin( std::vector<T>& vec ) { return { vec, 0 } ; }

is new for me. I "understand" it but how is it possible to have vec and 0 for returning and while the return type is of the function is something else?

[JayhawkZombie]

Unless I misunderstand your question, rc_iterator can be constructed using a reference to a vector and an index using:
rc_iterator( std::vector<T>& vec, std::size_t pos ) (line 6 in JLBorges example above). vec is the vector being referenced and 0 is the position, so it's returning one of your custom iterators pointing to the first element (hence the "begin" in the name).

[Frank14]

I changed:
T operator++(int) const { auto prev = *this ; ++*this ; return prev ; }
to
rc_iterator& operator++(int) { return ++*this ;}

[JLBorges]

Change it to:
rc_iterator operator++(int) { auto prev = *this ; ++*this ; return prev ; }
And likewise for operator-- (int)

[Frank14]

Why do we need a reference type return in:
rc_iterator& operator++ () { if( pos >= vec.size() ) error() ; ++pos ; return *this ;}
Do we want to somewhere use ++begin; as an lvalue?

And why your version above is better than:
rc_iterator& operator++(int) { return ++*this ;}
please?

[JLBorges]

> Why do we need a reference ... Do we want to somewhere use ++begin; as an lvalue?

The user of a random access iterator would expect the prefix increment of an iterator to:
a. move the iterator to 'point' to the next element in the sequence b. yield an lvalue


> And why your version above is better than: rc_iterator& operator++(int) { return ++*this ;}

rc_iterator& operator++(int) { return ++*this ;} would be semantically incorrect;
it would imply that there is no difference between the expressions ++i and i++


In short, correctly implemented prefix-increment and postfix-increment operators should mimic the semantics of the built-in prefix-increment and postfix-increment operators:

Pre(fix)-increment and pre(fix)-decrement operators increments or decrements the value of the object and returns a reference to the result.

Post(fix)-increment and post(fix)-decrement creates a copy of the object, increments or decrements the value of the object and returns the copy from before the increment or decrement.

http://en.cppreference.com/w/cpp/language/operator_incdec

[Frank14]

Thank you very much for your guidance.