6

I have been trying to write a custom container with its own iterator which can be used as a range and with std::span. I am new to ranges, so please be kind.

The following example fails to compile, because my container class cannot be converted to a std::span

#include<span>
#include<vector>
#include<cstdint>


template<class T, class Allocator = std::allocator<T>>
class MyContainer
{
public:
    class ConstIterator
    {
    public:
        using iterator_category = std::random_access_iterator_tag;
        using value_type = T;
        using difference_type = size_t;
        using pointer = T* const;
        using reference = const T&;
        
        ConstIterator() = default;
        ConstIterator(const ConstIterator &other) = default;
        
        
        ConstIterator(pointer ptr)
            : m_ptr(ptr) 
        {}

        reference operator*() const
        {
            return *m_ptr;
        }
        pointer operator->()
        {
            return m_ptr;
        }
        // Prefix increment
        ConstIterator& operator++()
        {
            m_ptr++;
            return *this;
        }
        // Postfix increment
        ConstIterator operator++(int)
        {
            Iterator tmp = *this;
            ++(*this);
            return tmp;
        }
        // Prefix decrement
        ConstIterator& operator--()
        {
            m_ptr--;
            return *this;
        }
        // Postfix decrement
        ConstIterator operator--(int)
        {
            Iterator tmp = *this;
            --(*this);
            return tmp;
        }
        ConstIterator& operator+=(const difference_type offset) noexcept
        {
            m_ptr += offset;
            return *this;
        }

        ConstIterator operator+(const difference_type offset) const noexcept
        {
            ConstIterator tmp = *this;
            tmp += offset;
            return tmp;
        }

        ConstIterator& operator-=(const difference_type offset) noexcept
        {
            return *this += -offset;
        }

        ConstIterator operator-(const difference_type offset) const noexcept
        {
            ConstIterator tmp = *this;
            tmp -= offset; 
            return tmp;
        }

        difference_type operator-(const ConstIterator& right) const noexcept
        {
            compatible(right);
            return m_ptr - right.m_ptr;
        }

        reference operator[](const difference_type offset) const noexcept
        {
            return *(*this + offset);
        }
        bool operator==(const ConstIterator& right) const noexcept
        {
            return (*this == right);
        }
        bool operator!=(const ConstIterator& right) const noexcept
        {
            return !(*this == right);
        }

        bool operator<(const ConstIterator& right) const noexcept
        {
            compatible(right);
            return m_ptr < right.m_ptr;
        }

        bool operator>(const ConstIterator& right) const noexcept
        {
            return right < *this;
        }

        bool operator<=(const ConstIterator& right) const noexcept
        {
            return !(right < *this);
        }

        bool operator>=(const ConstIterator& right) const noexcept
        {
            return !(*this < right);
        }
    protected:
        T* m_ptr;
    };
    class Iterator : public ConstIterator
    {
    public:
        using iterator_category = std::random_access_iterator_tag;
        using value_type = T;
        using difference_type = size_t;
        using pointer = T*;
        using reference = T&;
        
        Iterator() = default;
        Iterator(const Iterator &other) = default;

        Iterator(pointer ptr)
            : ConstIterator(ptr)
        {}

        reference operator*() const
        {
            return *ConstIterator::m_ptr;
        }
        pointer operator->()
        {
            return ConstIterator::m_ptr;
        }
        // Prefix increment
        Iterator& operator++()
        {
            ConstIterator::m_ptr++;
            return *this;
        }
        // Postfix increment
        Iterator operator++(int)
        {
            Iterator tmp = *this;
            ++(*this);
            return tmp;
        }
        // Prefix decrement
        Iterator& operator--()
        {
            ConstIterator::m_ptr--;
            return *this;
        }
        // Postfix decrement
        Iterator operator--(int)
        {
            Iterator tmp = *this;
            --(*this);
            return tmp;
        }
        Iterator& operator+=(const difference_type offset) noexcept
        {
            ConstIterator::_Verify_offset(offset);
            ConstIterator::m_ptr += offset;
            return *this;
        }

        Iterator operator+(const difference_type offset) const noexcept
        {
            Iterator tmp = *this;
            tmp += offset;
            return tmp;
        }

        Iterator& operator-=(const difference_type offset) noexcept
        {
            return *this += -offset;
        }

        Iterator operator-(const difference_type offset) const noexcept
        {
            Iterator tmp = *this;
            tmp -= offset;
            return tmp;
        }

        difference_type operator-(const ConstIterator& right) const noexcept
        {
            compatible(right);
            return ConstIterator::m_ptr - right.m_ptr;
        }

        reference operator[](const difference_type offset) const noexcept
        {
            return *(*this + offset);
        }
    };
public:
    using value_type = T;
    using allocator_type = Allocator;
    using pointer = typename std::allocator_traits<Allocator>::pointer;
    using const_pointer = typename std::allocator_traits<Allocator>::const_pointer;
    using reference = value_type &;
    using const_reference = const value_type &;
    using size_type = typename std::vector<T>::size_type;
    using difference_type = typename std::vector<T>::difference_type;
    using iterator = Iterator;
    using const_iterator = ConstIterator;
    using reverse_iterator = typename std::reverse_iterator<iterator>;
    using const_reverse_iterator = typename std::reverse_iterator<const_iterator>;

    MyContainer()
    {
        m_data.resize(10);
    }
    iterator begin()
    {
        return iterator(&m_data[0]);
    }
    iterator end()
    {
        return iterator(&m_data[0]+m_data.size());
    }
    const_iterator begin() const
    {
        return const_iterator(&m_data[0]);
    }
    const_iterator end() const
    {
        return const_iterator(&m_data[0]+m_data.size());
    }
   /*
    //These versions of begin() and end() work
    T* begin()
    {
        return &m_data[0];
    }
    T* end()
    {
        return &m_data[0]+m_data.size();
    }
    T* const begin() const
    {
        return &m_data[0];
    }
    T* const end() const
    {
        return &m_data[0]+m_data.size();
    }*/
private:
    std::vector<value_type> m_data;
};

int getSum(std::span<int const>s)
{
    int result =0;
    for (int val : s)
        result += val;
    return result;
}

int main()
{
    MyContainer<int> data;
    int sum = getSum(data);
}

Sorry this is a long minimal example, but my understanding is that a custom iterator needs to provide all the appropriate functionality to work with std::span.

The compilation error I am getting from clang is

<source>:282:12: error: no matching function for call to 'getSum'
        int sum = getSum(data);
                  ^~~~~~
<source>:271:5: note: candidate function not viable: no known conversion from 'MyContainer<int>' to 'std::span<const int>' for 1st argument
int getSum(std::span<int const>s)
    ^
1 error generated.

Or from VS2019

<source>(282): error C2664: 'int getSum(std::span<const int,18446744073709551615>)': cannot convert argument 1 from 'MyContainer<int,std::allocator<int>>' to 'std::span<const int,18446744073709551615>'
<source>(282): note: No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
<source>(271): note: see declaration of 'getSum'

Clang was initially giving me errors about not satisfying the requirements for all of the various range types, up to and including input and output ranges and it referred to _Begin. But when I stripped the code back to this example, the message got less detailed.

This led me to think I have a problem with my iterator. If instead of returning my custom iterator I just return a raw pointer, then the code compiles fine.

Is there a way I can work out why my code is not working? I am struggling to even find a proper guide to all this that is penetrable to someone new to ranges.

3
  • I like that the prefix increment performs a postfix increment. Commented Sep 20, 2021 at 13:00
  • At a glance: (1) Your Iterator::difference_type is unsigned, which means nonsense when a < b and we do a - b. (2) Your addition (and subtraction) operation is not symmetric for difference_type. (3) Some methods aren't const qualified even though they can and should be. (4) iterator_category should be std::contiguous_iterator_tag as a span requires... There's probably gonna be more that needs done after, but that's all I can see. Commented Sep 20, 2021 at 13:29
  • Sidenote: Are you sure you want using pointer = T* const;? It seems using pointer = T const*; would be more fitting Commented Sep 20, 2021 at 13:52

1 Answer 1

4

For anyone doing again in the future, the way I debugged my iterator was to set up a set of static asserts to check at which point my iterator was failing the requirements. Because the iterator types form a hierarchy where each iterator must also satisfy the requirements of the one further down the hierarchy (other than input and output which are on par), I started with

    using cType = sci::MyContainer<int>;
    using iType = cType::Iterator;
    static_assert(std::input_iterator<iType>, "failed input iterator");
    static_assert(std::output_iterator<iType, int>, "failed output iterator");
    static_assert(std::forward_iterator<iType>, "failed forward iterator");
    static_assert(std::input_iterator<iType>, "failed input iterator");
    static_assert(std::bidirectional_iterator<iType>, "failed bidirectional iterator");
    static_assert(std::random_access_iterator<iType>, "failed random access iterator");
    static_assert(std::contiguous_iterator<iType>, "failed contiguous iterator");

Then I started with the first error, fount the code for that concept and set up static_asserts for the sub-concepts. For example, when I got a "failed input iterator" error I set up the static asserts

    static_assert(std::weakly_incrementable<iType>, "Failed the weakly incrementable test");
    static_assert(std::movable<iType>, "Failed the moveable test");
    static_assert(std::default_initializable<iType>, "Failed the default initializable test");

This allowed me to find (as noted by @Unslander Monica) that I had an unsigned difference_type when it needed to be signed, I did not have operators for Iterator operator+(const difference_type offset, const Iterator &iter), I needed a element_type and for my non-const iterator I needed a const pointer operator->() const.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.