Использование 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 'd).

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

• 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.