Using boost::iterator

Question

I wrote a sparse vector class (see #1, #2.)

I would like to provide two kinds of iterators:

The first set, the regular iterators, can point any element, whether set or unset. If they are read from, they return either the set value or value_type(), if they are written to, they create the element and return the lvalue reference. Thus, they are:

Random Access Traversal Iterator and Readable and Writable Iterator

The second set, the sparse iterators, iterate over only the set elements. Since they don't need to lazily create elements that are written to, they are:

Random Access Traversal Iterator and Readable and Writable and Lvalue Iterator

I also need const versions of both, which are not writable.

I can fill in the blanks, but not sure how to use boost::iterator_adaptor to start out.

Here's what I have so far:

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
          > {
    };
};

also, is this illegal?

typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator;

Answer 1

I'm not sure that you really want to use iterator_adaptor in your case - you might want to use iterator_facade instead.

More thorough explanation: iterator_adaptors are used when you have an existing iterator (let's say std::list<int>::iterator) and want to reuse its behaviour for your iterator, eg. your iterator will return twice the value of what is in the list, but reuse traversal code from the original iterator. Or the other way around: you might want an iterator that will skip some of the elements in the original list, but return the values unchanged. I'm not sure whether you want to base your iterator (as in reuse code of) upon iterators of your underlying structures, but speaking for me, I wouldn't especially in the case of nonsparse iterator as you would probably want to create some proxy for the reference which means you can't use any underlying iterator dereference() code, and traversal is probably easy. You can, however, base your sparse_iterator on some iterator that iterates over actually existing elements of the array if you want.

There are problems with the proxy approach, so don't expect it to work flawlessly without going through many hoops. For one thing, the const version of the nonsparse iterator should still return value_type(), which means expressions like iter->foo() should translate to value_type().foo() if the corresponding entry doesn't exist. But this poses a difficulty, that pointer_proxy::operator->() should return something with operator->, preferably a pointer (definitely not value_type()). Which leads to the crucial question: A pointer to what? There are possibilities to solve this (for one, if you have your objects managed by boost::shared_pointer, you can just return a shared_pointer to a new'd instance).

For the nonsparse iterator, you need to implement:

• class reference_proxy with
• reference_proxy::operator& (that will probably return a pointer proxy)
• reference_proxy::operator value_type&() for const uses
• reference_proxy::operator const value_type&() for non-const uses

• reference_proxy::foo() for any foo() member function of value_type (otherwise expressions like (*it).foo() AFAIK won't work)

• class pointer_proxy with

• pointer_proxy::operator* (return a reference_proxy)
• pointer_proxy::operator-> (do something sensible, see above)

The parameters to the iterator facade template should be:

• Reference: the reference_proxy
• Pointer: the pointer_proxy

The sparse version is simpler: If the underlying iterator is sensible (ie. matches the behaviour you want) and properly implemented, you can just omit the parameters to the iterator_adaptor (except for the first two), and take all the implementation.

The "doesn't compile" problem: insert typename.