Использование boost::iterator

Question

Я написал разреженный векторный класс (см. № 1, № 2.)

Я хотел бы предоставить два вида итераторов:

Первый набор, обычные итераторы, может указывать на любой элемент, установленный или не заданный. Если они читаются из, они возвращают либо установленное значение, либо value_type() Если они записаны, они создают элемент и возвращают ссылку lvalue. Таким образом, они являются:

Итератор обхода произвольного доступа и читаемый и записываемый итератор

Второй набор, разреженные итераторы, перебирают только элементы набора. Поскольку им не нужно лениво создавать элементы для записи, они:

Итератор обхода с произвольным доступом, читаемый и записываемый итератор Lvalue

Мне также нужны константные версии обоих, которые не доступны для записи.

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

Вот что у меня так далеко:

template<typename T>
class sparse_vector {
public:
    typedef size_t size_type;
    typedef T value_type;

private:
    typedef T& true_reference;
    typedef const T* const_pointer;
    typedef sparse_vector<T> self_type;
    struct ElementType {
        ElementType(size_type i, T const& t): index(i), value(t) {}
        ElementType(size_type i, T&& t): index(i), value(t) {}
        ElementType(size_type i): index(i) {}
        ElementType(ElementType const&) = default;
        size_type index;
        value_type value;
    };
    typedef vector<ElementType> array_type;

public:
    typedef T* pointer;
    typedef T& reference;
    typedef const T& const_reference;

private:
    size_type                                   size_;
    mutable typename array_type::size_type      sorted_filled_; 
    mutable array_type                          data_;

// lots of code for various algorithms...

public:    
    class sparse_iterator
        : public boost::iterator_adaptor<
          sparse_iterator                   // Derived
          , typename array_type::iterator            // Base (the internal array)
          , value_type              // Value
          , boost::random_access_traversal_tag    // CategoryOrTraversal
          > {...}

    class iterator_proxy {
          ???
    };

    class iterator
        : public boost::iterator_facade<
          iterator                          // Derived
          , ?????                           // Base
          , ?????              // Value
          , boost::??????    // CategoryOrTraversal
          > {
    };
};

Кроме того, это незаконно?

typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator;

Answer 1

Я не уверен, что вы действительно хотите использовать iterator_adaptor в вашем случае - вы можете использовать iterator_facade вместо.

Более подробное объяснение: iterator_adaptors используются, когда у вас есть существующий итератор (скажем, std::list<int>::iterator) и хотите повторно использовать его поведение для вашего итератора, например. Ваш итератор будет возвращать в два раза больше значения из списка, но повторно использовать код обхода из исходного итератора. Или наоборот: вам может понадобиться итератор, который пропустит некоторые элементы в исходном списке, но вернет значения без изменений. Я не уверен, хотите ли вы основывать свой итератор (как в коде повторного использования) на итераторах ваших базовых структур, но, выступая за меня, я бы не стал особенно в случае не разреженного итератора, поскольку вы, вероятно, захотите создать какой-то прокси для ссылки, что означает, что вы не можете использовать любой итератор dereference() код, и обход, вероятно, легко. Вы можете, однако, основать свой sparse_iterator на каком-то итераторе, который перебирает фактически существующие элементы массива, если хотите.

Есть проблемы с прокси-подходом, поэтому не ожидайте, что он будет работать без нареканий, не пройдя через много обручей. С одной стороны, константная версия не разреженного итератора должна все еще возвращать value_type(), что означает такие выражения, как iter->foo() следует перевести на value_type().foo() если соответствующая запись не существует. Но это создает трудности, что pointer_proxy::operator->() должен вернуть что-то с operator->желательно указатель (точно нет value_type()). Что приводит к решающему вопросу: указатель на что? Есть возможность решить эту проблему (например, если ваши объекты управляются boost::shared_pointerВы можете просто вернуть shared_pointer к newинстанция).

Для не разреженного итератора вам необходимо реализовать:

• class reference_proxy с
• reference_proxy::operator& (это, вероятно, вернет указатель прокси)
• reference_proxy::operator value_type&() для постоянного использования
• reference_proxy::operator const value_type&() для неконстантного использования

• reference_proxy::foo() для любого foo() функция-член value_type (в противном случае выражения типа (*it).foo() AFAIK не сработает)

• class pointer_proxy с

• pointer_proxy::operator* (вернуть reference_proxy)
• pointer_proxy::operator-> (сделать что-нибудь разумное, см. выше)

Параметры шаблона фасада итератора должны быть следующими:

• Reference: reference_proxy
• Pointer: pointer_proxy

Разреженная версия проще: если лежащий в основе итератор является разумным (т.е. соответствует поведению, которое вы хотите) и правильно реализован, вы можете просто опустить параметры в iterator_adaptor (кроме первых двух), и принять все реализации.

Проблема "не компилируется": вставка typename,