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

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

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

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

Итератор с отслеживанием случайного доступа и Читаемый и Writable Итератор

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

Итератор с отслеживанием случайного доступа и Readable и Writable и 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;

Ответы

Ответ 1

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

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

Есть проблемы с прокси-подходом, поэтому не ожидайте, что он будет работать безупречно, не пройдя много обручей. Во-первых, версия const нетерапевтического итератора должна возвращать 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&() для не-const использует

  • reference_proxy::foo() для любой функции foo() member_type (иначе выражения типа (*it).foo() AFAIK не будут работать)

  • class pointer_proxy с

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

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

  • Reference: reference_proxy
  • Pointer: pointer_proxy

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

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