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

Question

Это заголовочный файл для контейнера, включающий попытку реализовать итераторы произвольного доступа:

using namespace std;
template <class Element, class Compare = std::equal_to<Element>>
class UniqueArray {

public:
    Element** data;
    unsigned int curr_size;
    unsigned int max_size;
    int* availability_array;

    explicit UniqueArray(unsigned int size);
    UniqueArray(const UniqueArray& other);
    ~UniqueArray();
//    UniqueArray& operator=(const UniqueArray&) = delete;
    unsigned int insert(const Element& element);
    bool getIndex(const Element& element, unsigned int& index) const;
    const Element* operator[] (const Element& element) const;
    bool remove(const Element& element);
    unsigned int getCount() const;
    unsigned int getSize() const;

    class Filter {
    public:
        virtual bool operator() (const Element&) const = 0;
    };
    UniqueArray filter(const Filter& f) const;

    class UniqueArrayIsFullException{};

    typedef Element ua_iterator;
    typedef const Element ua_const_iterator;

    ua_iterator begin(){
        return **data;
    }
    ua_const_iterator begin() const {
        return **data;
    }
    ua_iterator end(){
        return *(*data + max_size);
    }
    ua_const_iterator end() const {
        return *(*data + max_size);
    }
};

Сводка полученных ошибок:

error: no match for ‘operator++’

error: no match for ‘operator*’

error: no type named ‘value_type’ in ‘struct std::iterator_traits<MtmParkingLot::Vehicle>

error: no match for ‘operator!=’

error: no match for ‘operator-’

В моей реализации Element получает Vehicle и все эти пропущенные операторы относятся к Vehicle

Я не совсем уверен, как работать с этими ошибками, потому что, например, вычитание Vehicles не имеет смысла ..

Answer 1

Если вы хотите, чтобы итератор возвращал ссылку на объект при разыменовании, вы должны определить специальный класс Iterator, чтобы сделать это. С boost::indirect_iterator это довольно просто:

#include <boost/iterator/indirect_iterator.hpp>

template <class Element, class Compare = std::equal_to<Element>>
class UniqueArray {
    // ...

    auto begin() {
        return boost::indirect_iterator<Element**, Element>(data_);
    }

    auto end() {
        return boost::indirect_iterator<Element**, Element>(data_ + curr_size);
    }
};

Простая демонстрация

---

Если вы хотите закодировать ее самостоятельно, Идея такова:

template<class Element>
class UniqueArray {
public:
    //...

    class Iterator {
    public:
        using iterator_category = std::random_access_iterator_tag;
        using value_type = Element;
        using reference = Element&;
        // ...

        Iterator(Element** d) : data(d) { }

        reference operator*() {
            return **data;
        }

        Iterator& operator++() {
            ++data;
            return *this;
        } 

        friend bool operator!=(Iterator it1, Iterator it2) {
            return it1.data != it2.data;
        }

        // ...

    private:
        Element** data;        
    };

    Iterator begin() {
        return Iterator(data);
    }

    Iterator end() {
        return Iterator(data + curr_size);
    }
};

Обратите внимание, что итератор полного произвольного доступа требует реализации многих других функций-членов и не-членов. Возможно, вы захотите сделать его прямым итератором , чтобы немного упростить ситуацию.

Простая демонстрация

Answer 2

Если вы напишите это без псевдонимов типов, вы получите определения, такие как

Element begin(){
    return **data;
}

, и используйте как

UniqueArray<Vehicle>::ua_iterator it = something.begin();
it++;

, становится

Vehicle it = something.begin();
it++;

, что делает причина ошибок более очевидна - вы пытаетесь применить операции итератора к вашему типу элемента.

Если вы хорошо справляетесь с итерацией, производящей Element*, простое решение -

typedef Element** ua_iterator;

ua_iterator begin(){
    return data;
}
ua_iterator end(){
    return data + curr_size;
}

и аналогичные для константных версий.

Тогда вы могли бы написать

UniqueArray<Vehicle>::ua_iterator it = something.begin();
Vehicle* v = *it;

Если вы хотите, чтобы итерация производила Element&, вам нужно написать класс итератора с соответствующими перегрузками и признаками .
Это не очень сложно, но становится утомительным.