2010-05-12 2 views
11

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

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

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

Random Access Traversal Итератор и Читаемые и Writable Итератор

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

Random Access Traversal Итератор и Читаемые и 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; 

ответ

19

Я не уверен, что вы действительно хотите использовать 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&() для неконстантных использует
  • reference_proxy::foo() для любых foo() член функции стоимости e_type (в противном случае такие выражения, как (*it).foo() AFAIK не будет работать)

  • class pointer_proxy с

  • pointer_proxy::operator* (возвращают reference_proxy)
  • pointer_proxy::operator-> (сделать что-то толковое, смотри выше)

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

  • Reference: reference_proxy
  • Pointer: pointer_proxy

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

Проблема «не скомпилирована»: вставьте typename.

+0

да, я думаю, что вы правы для одного из итераторов ... Я обновил вопрос. –

+0

То, что вы описываете, именно то, что я хочу, да. –

+0

Как мне увеличить это количество раз? :) –