Как написать произвольный итератор произвольного доступа, который можно использовать с алгоритмами STL?

Question

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

template <typename T>
class _iterator
{
    T* ptr;

public:

    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using reference         = T&;
    using pointer           = T*;
    using difference_type   = unsigned long long;

    _iterator(T* ptr) : ptr(ptr) {}

    reference operator* () { return *ptr; }
    pointer   operator->() { return  ptr; }

    _iterator& operator++() { ptr++; return *this; }
    _iterator& operator--() { ptr--; return *this; }

    difference_type operator-(const _iterator& it) { return this->ptr - it.ptr; }

    _iterator operator+(const difference_type& diff) { return _iterator(ptr + diff); }
    _iterator operator-(const difference_type& diff) { return _iterator(ptr - diff); }

    bool operator==(const _iterator& it) { return this->ptr == it.ptr; }
    bool operator!=(const _iterator& it) { return this->ptr != it.ptr; }
    bool operator< (const _iterator& it) { return this->ptr <  it.ptr; }

    operator _iterator<const T>() const { return _iterator<const T>(ptr); }
};

template <typename T>
class X
{
    std::vector<T> data;

public:

    using iterator = _iterator<T>;
    using const_iterator = _iterator<const T>;

    void push_back(T t)
    {
        data.push_back(t);
    }

    iterator begin()
    {
        return iterator(&data[0]);
    }

    iterator end()
    {
        return iterator(&data[0] + data.size());
    }
};

int main()
{
    X<int> x;

    for (int i = 9; i >= 0; i--)
        x.push_back(i);

    // 1 ------------------------------------------------------------------------

    // C2780    'void std::_Sort_unchecked(_RanIt,_RanIt,iterator_traits<_Iter>::difference_type,_Pr)': expects 4 arguments - 3 provided
    // C2672    '_Sort_unchecked': no matching overloaded function found
    // C2678    binary '-': no operator found which takes a left - hand operand of type 'const _RanIt' (or there is no acceptable conversion)

    std::sort(x.begin(), x.end());


    // 2 ------------------------------------------------------------------------

    // C2666    '_iterator<T>::operator -': 2 overloads have similar conversions
    // C2512    '_iterator<T>': no appropriate default constructor available

    for (X<int>::iterator it = x.end() - 1; it >= x.begin(); --it)
        std::cout << *it << ' ';
    std::cout << std::endl;
}

Я пытаюсь написать итератор произвольного доступа для пользовательского контейнера. Я столкнулся с парой проблем:

1. Невозможно использовать алгоритмы STL для пользовательского контейнера.
2. Если я вычитаю число из итератора, я получаю сообщение об ошибке, сообщающее, что у меня 2 перегрузки.

Ошибки записываются над каждым фрагментом кода, соответствующим ему. Также я не уверен, является ли способ, которым я определяю iterator и const_iterator, правильный путь или нет. Что я тут не так делаю и как их исправить?

Answer 1

// C2678    binary '-': no operator found which takes a left - hand operand of type 'const _RanIt' (or there is no acceptable conversion)

Если вы пометите следующую функцию как const:

difference_type operator-(const _iterator& it) const { return this->ptr - it.ptr; }

Вы начнете исправлять некоторые проблемы. Я не проверял, охватывал ли это все случаи. Но в целом создание всего, что вы можете const, очень помогает.

Answer 2

Мне нужно было отметить функции и операторы как const, а также написать определение для operator[]. По желанию я могу обеспечить сброс реляционных операторов (>, >=, <=) на случай, если я захочу их использовать. Вот рабочий код:

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

template <typename T>
class _iterator
{
    T* ptr;

public:

    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using reference         = T&;
    using pointer           = T*;
    using difference_type   = unsigned long long;

    _iterator(T* ptr) : ptr(ptr) {}

    reference operator* () const { return *ptr; }
    pointer   operator->() const { return    ptr; }

    _iterator& operator++() { ptr++; return *this; }
    _iterator& operator--() { ptr--; return *this; }

    difference_type operator-(const _iterator& it) const { return this->ptr - it.ptr; }

    _iterator operator+(const difference_type& diff) const { return _iterator(ptr + diff); }
    _iterator operator-(const difference_type& diff) const { return _iterator(ptr - diff); }

    reference operator[] (const difference_type& offset) const { return *(*this + offset); }

    bool operator==(const _iterator& it) const { return this->ptr == it.ptr; }
    bool operator!=(const _iterator& it) const { return this->ptr != it.ptr; }
    bool operator< (const _iterator& it) const { return this->ptr <  it.ptr; }
    bool operator> (const _iterator& it) const { return this->ptr >  it.ptr; }
    bool operator>=(const _iterator& it) const { return !(this->ptr <  it.ptr); }
    bool operator<=(const _iterator& it) const { return !(this->ptr >  it.ptr); }

    operator _iterator<const T>() const { return _iterator<const T>(ptr); }
};

template <typename T>
class X
{
    std::vector<T> data;

public:

    using iterator = _iterator<T>;
    using const_iterator = _iterator<const T>;

    void push_back(T t)
    {
        data.push_back(t);
    }

    iterator begin()
    {
        return iterator(&data[0]);
    }

    iterator end()
    {
        return iterator(&data[0] + data.size());
    }
};

int main()
{
    X<int> x;

    for (int i = 0; i < 10; i++)
        x.push_back(i);

    std::sort(x.begin(), x.end(), std::greater<>());

    for (X<int>::iterator it = x.end() - 1; it >= x.begin(); --it)
        std::cout << *it << ' ';
    std::cout << std::endl;
}

Вывод:

0 1 2 3 4 5 6 7 8 9