Implementing custom iterator to work with std::sort

Question

My aim is to learn how to write a custom iterator from scratch. I have written the following iterator:

#include <iterator>

template<class D>
class SpanIterator final : public std::iterator<std::random_access_iterator_tag, D>
{
private:
    D* _data;

public:
    explicit SpanIterator(D* data) :
        _data{ data }
    {
    }

    SpanIterator(const SpanIterator& itertator) = default;

    SpanIterator& operator=(const SpanIterator& iterator) = default;

    SpanIterator& operator=(D* data)
    {
        _data = data;

        return *this;
    }

    operator bool() const
    {
        return _data != nullptr;
    }

    bool operator==(const SpanIterator& itertator) const
    {
        return _data == itertator._data;
    }

    bool operator!=(const SpanIterator& itertator) const
    {
        return _data != itertator._data;
    }

    SpanIterator& operator+=(const std::ptrdiff_t& movement)
    {
        _data += movement;

        return *this;
    }

    SpanIterator& operator-=(const std::ptrdiff_t& movement)
    {
        _data -= movement;

        return *this;
    }

    SpanIterator& operator++()
    {
        ++_data;

        return *this;
    }

    SpanIterator& operator--()
    {
        --_data;

        return *this;
    }

    SpanIterator operator++(int)
    {
        auto temp = *this;

        ++_data;

        return temp;
    }

    SpanIterator operator--(int)
    {
        auto temp = *this;

        --_data;

        return temp;
    }

    SpanIterator operator+(const std::ptrdiff_t& movement)
    {
        auto oldPtr = _data;

        _data += movement;

        auto temp = *this;

        _data = oldPtr;

        return temp;
    }

    SpanIterator operator-(const std::ptrdiff_t& movement)
    {
        auto oldPtr = _data;

        _data -= movement;

        auto temp = *this;

        _data = oldPtr;

        return temp;
    }

    D& operator*()
    {
        return *_data;
    }

    const D& operator*() const
    {
        return *_data;
    }

    D& operator->()
    {
        return _data;
    }
};

Which I am testing like so:

#include <iostream>
#include <array>

int main()
{
    std::array<double, 3> values = { 1, 2, 1 };

    SpanIterator<double> begin{ values.data() };
    SpanIterator<double> end{ values.data() + values.size() };

    std::sort(begin, end);

    return EXIT_SUCCESS;
}

However it fails to compile, giving the following errors:

Error C2666 'SpanIterator::operator -': 2 overloads
Error C2780 'void std::_Sort_unchecked1(_RanIt,_RanIt,_Diff,_Pr &)': expects 4 arguments - 3 provided

If I remove SpanIterator operator-(const std::ptrdiff_t& movement) I get different errors:

'void std::_Guess_median_unchecked(_RanIt,_RanIt,_RanIt,_Pr &)': could not deduce template argument for '_RanIt' from 'int'
'_Guess_median_unchecked': no matching overloaded function found
Error C2100 illegal indirection

score 6 · Accepted Answer · edited May 23 '17 at 11:58

You're missing operators to support the following operations (where a and b are values of your iterator type SpanIterator<...>):

b - a
a < b (and the remaining comparisons, although most implementations of std::sort don't use them).

For example, you could provide the following member operator overloads:

std::ptrdiff_t operator-(SpanIterator const&) const;
bool operator<(SpanIterator const&) const;
// etc.

(Note that non-member overloads are often preferred: Operator overloading)

In addition, your operator bool should be explicit to avoid ambiguous overloads for the a + n, n + a and b - a operations (where n is a value of your difference type i.e. std::ptrdiff_t).

Adding explicit to `operator bool` and adding the two operators you mentioned has done the trick - thank you kindly :-) — keith, Jul 25 '16 at 09:36

Implementing custom iterator to work with std::sort

1 Answers1