How can I write a custom STL iterator for a class type without using raw pointers? Is there a practical advantage to this?

Question

The title of this question used to be: Are there practical advantages to creating an iterator class compared to returning raw pointers from begin and end functions?

Recently I have been working on a code base which uses MFC and objects such as CArray<T, U>.

Some parts of new code which has been written make use of the STL and <algorithm> library.

For example

CArray<int int> carray;
carray // do stuff
std::vector<int> stlvector(begin(carray), end(carray));
stlvector.dostuff() // do stuff

I recently asked a question about creating iterators for a class such as CArray, which I do not have access to.

I now have some further questions about this. The first question can be found here. Here is my second question:

Should the begin and end functions return raw pointers or iterators?

In the linked question above, an example was provided as an answer which returns raw pointers. This answer was very similar to the implementation I used.

template<typename T, typename U>
auto begin(const CArray<T, U> &array>)
{
    return &array[0];
}

template<typename T, typename U>
auto end(const CArray<T, U> &array>)
{
    return (&array[array.GetCount() - 1]) + 1;
}

These functions return raw pointers. However I attempted to implement an iterator solution. So far I have not been successful.

The main reference which I used during my research can be found here:

https://internalpointers.com/post/writing-custom-iterators-modern-cpp

First attempt

This is the first attempt that I made in finding a solution.

You can play with this code here.

#include <iostream>
#include <iterator>
#include <algorithm>

template <typename U>
class CArrayForwardIt
{
    
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = U;
    using pointer = U*;
    using reference = U&;
    
public:

    CArrayForwardIt(pointer ptr)
        : m_ptr(ptr)
    {
    }
    
    // = default?
    //CArrayForwardIt(CArrayForwardIt<U> other)
    //      : m_ptr(ptr)
    // {
    // }
    
    reference operator*() const
    {
        return *m_ptr;
    }
    
    // what does this do, don't understand why operator-> is needed
    // or why it returns a U* type
    pointer operator->()
    {
        return m_ptr;
    }
    
    CArrayForwardIt& operator++()
    {
        ++ m_ptr;
        return *this;
    }
    
    CArrayForwardIt operator++(int)
    {
        CArrayForwardIt tmp(*this);
        ++ (*this);
        return tmp;
    }
    
    friend bool operator==(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
    {
        return lhs.m_ptr == rhs.m_ptr;
    }
    
    friend bool operator!=(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
    {
        return !(lhs == rhs);
    }
    
private:

    pointer m_ptr;
    
};


template<typename T, typename U>
auto begin(const CArray<T, U> &array)
{
    return CArrayForwardIt<U>(&array[0]);
}

template<typename T, typename U>
auto end(const CArray<T, U> &array)
{
    return CArrayForwardIt<U>((&array[array.GetCount() - 1]) + 1);
}

int main()
{
    
    CArray<int, int> c;
    // do something to c
    std::vector<int> v(begin(c), end(c));
    

    return 0;
}

This is what happens when I try to compile this (with Visual Studio 2019 Pro).

no instance of constructor "std::vector<_Ty, _Alloc>::vector [with _Ty=int, _Alloc=std::allocator<int>]" matches argument list
'<function-style-cast>': cannot convert from 'contt TYPE*' to 'std::CArrayForwardIt<U>'
'std::vector<int, std::allocator<int>>::vector(std::vector<int, std::allocator<int>> &&, const _Alloc &) noexcept(<expr>)': cannot convert from argument 1 from 'void' to 'const unsigned int'

Being more familiar with gcc, I have little knowledge of how to understand this.

Second attempt

I made another two further attempts at this but they were quite similar.

One was to change my class CArrayForwardIt to inherit from iterator<std::forward_iterator_tag, std::ptrdiff_t, U, U*, U&>, and to remove the using... lines at the top of the class. This didn't seem to get me any closer to a solution.

In addition, I looked at the constructor definition for std::vector. See here.

I may be misunderstanding here, but it looks like std::vector requires a InputIt type argument.

Therefore I tried to change my class to be something like this:

#include <iostream>
#include <iterator>
#include <algorithm>

template <typename U>
class forward_iterator
{
    
    using iterator_category = std::forward_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = U;
    using pointer = U*;
    using reference = U&;
    
public:

    forward_iterator(pointer ptr)
        : m_ptr(ptr)
    {
    }
    
    // = default?
    //forward_iterator(forward_iterator<U> other)
    //      : m_ptr(ptr)
    // {
    // }
    
    reference operator*() const
    {
        return *m_ptr;
    }
    
    // what does this do, don't understand why operator-> is needed
    // or why it returns a U* type
    pointer operator->()
    {
        return m_ptr;
    }
    
    forward_iterator& operator++()
    {
        ++ m_ptr;
        return *this;
    }
    
    forward_iterator operator++(int)
    {
        forward_iterator tmp(*this);
        ++ (*this);
        return tmp;
    }
    
    friend bool operator==(const forward_iterator& lhs, const forward_iterator& rhs)
    {
        return lhs.m_ptr == rhs.m_ptr;
    }
    
    friend bool operator!=(const forward_iterator& lhs, const forward_iterator& rhs)
    {
        return !(lhs == rhs);
    }
    
private:

    pointer m_ptr;
    
};


template<typename T, typename U>
auto begin(const CArray<T, U> &array)
{
    return forward_iterator<U>(&array[0]);
}

template<typename T, typename U>
auto end(const CArray<T, U> &array)
{
    return forward_iterator<U>((&array[array.GetCount() - 1]) + 1);
}


int main()
{
    
    CArray<int, int> c;
    // do something to c
    std::vector<int> v(begin(c), end(c));
    

    return 0;
}

This, perhaps unsurprisingly, did not compile either. At this point I became confused. std::vector appears to demand an InputIt type, which forward_iterator should work for, but it doesn't seem to make sense to redefine what forward_iterator is, even if I write this class outside of namespace std.

Question

I am fairly sure there should be a way to write an iterator class for the MFC CArray, which can be returned by begin and end functions. However, I am confused as to how to do this.

Further to the question of writing a working solution, I am beginning to wonder if there are any practical advantages to doing this? Does what I am trying to do even make sense? The raw pointer solution clearly works, so are there any advantages of investing the effort to write an iterator based solution? Can iterator solutions provide more sophisticated bounds checking, for example?

Relevant: C++ std::vector<>::iterator is not a pointer, why?. — Daniel Langr
– Daniel Langr, Commented Dec 13, 2021 at 11:36
You didn't copy paste the code online correctly, did you? (if Visual Studio really give these error messages, they're terribly unhelpful. Anyway, just compile the code with onlinegdb or whatever, and see the error messages and fix yourself) — user202729
– user202729, Commented Dec 13, 2021 at 11:40
@user202729 Unfortunately where I am working it is impossible to copy and paste. These are the errors VS gave me, I copied them from one computer screen to another. As far as I know the code is copied directly - if there is a mistake somewhere then perhaps pointing to what you think the mistake is would be more helpful than simply asserting that I copied it wrong. — user2138149
– user2138149, Commented Dec 13, 2021 at 12:32

user2138149 · Accepted Answer · 2021-12-14 10:58:35Z

Since I managed to get this working I wanted to post a solution, hopefully I don't make too many errors transcribing it.

One thing that was not shown in the above code snippet is the fact that all these class and function definitions existed inside of namespace std. I posted another question about this earlier, and was informed that these things should not be inside namespace std. Correcting this seems to have resolved some problems and made the solution a step closer.

You can find that question here.

This is what I have so far: This is how to write an iterator for an external class which the programmer does not have access to. It also works for your own custom types or containers which you do have access to.

// How to write an STL iterator in C++
// this example is specific to the MFC CArray<T, U> type, but
// it can be modified to work for any type, note that the
// templates will need to be changed for other containers

#include <iterator>
#include <mfc stuff...>

template<typename T, typename U>
class CArrayForwardIt : public std::iterator<std::forward_iterator_tag, std::ptrdiff_t, U, U*, U&>
{
    // the names used in this class are described in this list
    // using iterator_category = std::forward_iterator_tag;
    // using difference_type = std::ptrdiff_t;
    // using value_type = U;
    // using pointer = U*;
    // using reference = U&;

public:
    
    CArrayForwardIt(CArray<T, U> &array_ref, const std::size_t index)
        : m_array_ref(array_ref)
        , m_index(index)
    {
    }

    // the only way I could get this to work was to make the return type
    // an explicit U&, I don't know why this is required, as using
    // reference operator*() const did not seem to work
    U& operator*() const
    {
        if(m_index < m_array_ref.GetCount())
        {
            return m_array_ref[m_index];
        }
        else
        {
            throw std::out_of_range("Out of range Exception!");
        }
    }

    CArrayForwardIt& operator++()
    {
        ++ m_index;
        return *this;
    }

    CArrayForwardIt operator++(int)
    {
        CForwardArrayIt tmp(*this);
        ++(*this);
    }

    friend bool operator==(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
    {
        if(&(lhs.m_array_ref) == &(rhs.m_array_ref))
        {
            return lhs.m_index == rhs.m_index;
        }
        return false;
    }

    friend bool operator!=(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
    {
        return !(lhs == rhs);
    }

private:

    std::size_t m_index;
    CArray<T, U> &m_array_ref;

};


template<typename T, typename U>
auto begin(CArray<T, U> &array)
{
    return CArrayForwardIt<T, U>(array, 0);
}


template<typename T, typename U>
auto end(CArray<T, U> &array)
{
    return CArrayForwardIt<T, U>(array, array.GetCount());
}


int main()
{

    CArray<int, int> array;
    // do stuff to array

    // construct vector from elements of array in one line
    std::vector<int> vector(begin(array), end(array));

    // also works with other STL algorithms

}

Note my comment about the U& operator* which produced some compiler error when written as reference operator* which might be a Visual Studio compiler bug. I'm not sure about this.

I would suggest that although this method is more difficult to implement (but not much when you know how to do it) it has the advantage of not using raw pointers which means that the iterator functions can provide proper exception throwing statements when illegal operations are attempted. For example, incrementing the iterator when it is already at the end.

Useful references:

user2138149 · Accepted Answer · 2021-12-15 12:36:25Z

0

For completeness, here is the simpler solution using raw pointers.

template<typename T, typename U>
auto begin(CArray<T, U> &array)
{
    return &(array[0]);
}

template<typename T, typename U>
auto end(CArray<T, U> &array)
{
    // get address of last element then increment
    // pointer by 1 such that it points to a memory
    // address beyond the last element. only works for
    // storage containers where higher index elements
    // are guaranteed to be at higher value memory
    // addresses
    if(array.GetCount() > 0)
    {
        return &(array[array.GetCount() - 1]) + 1;
    }
    else
    {
        return &(array[0]) + 1;
    }
}

You can use these in the same way as demonstrated in the other answer, however there is also a way to use STL vector without the begin and end functions:

CArray<int, int> array; // ... do something to array
std::vector<int> vec(&array[0], &(array[array.GetCount() - 1]) + 1);
// note only works if elements guaranteed to be in continuous
// packed memory locations

but it also works with begin and end which is nicer

std::vector<int> vec(begin(array), end(array));

edited Dec 15, 2021 at 12:36

answered Dec 14, 2021 at 10:54

user2138149

18.7k32 gold badges161 silver badges322 bronze badges

5 Comments

IInspectable Over a year ago

CArray::GetCount can return zero, causing the end() implementation to overflow. Since unsigned overflow is undefined in C++, so is the implementation of end().

user2138149 Over a year ago

@IInspectable A very valid point, I will have a think about a solution

j6t Over a year ago

&m_count[0] triggers an MFC assertion failure when the array is empty, because there is no element 0. Just use GetData() and GetData() + GetCount() for begin and end, respectively.

user2138149 Over a year ago

@j6t Yes, fair point. I've changed to using that in my actual code.

user2138149 Over a year ago

There's actually another bug here. When the size is zero, begin and end do not return the same memory address. end still returns an address which is equal to begin + 1.

Collectives™ on Stack Overflow

How can I write a custom STL iterator for a class type without using raw pointers? Is there a practical advantage to this?

The title of this question used to be: Are there practical advantages to creating an iterator class compared to returning raw pointers from begin and end functions?

First attempt

Second attempt

Question

2 Answers 2

Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

The title of this question used to be: Are there practical advantages to creating an iterator class compared to returning raw pointers from begin and end functions?

First attempt

Second attempt

Question

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related