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
          , array_type::iterator            // Base (the internal array) (this paramater does not compile! -- says expected a type, got 'std::vector::iterator'???)
          , boost::use_default              // Value
          , boost::random_access_traversal_tag?    // CategoryOrTraversal
          >

    class iterator_proxy {
          ???
    };

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

};