我想提供两种迭代器：
第一个集合，常规迭代器，可以指向任何元素，无论是设置的还是未设置的。如果它们被读取，它们返回设置值，或者value_type()，如果它们被写入，它们创建元素并返回左值引用。因此，它们是：
随机访问遍历迭代器和可读可写迭代器
第二个集合，稀疏迭代器，仅迭代集合元素。由于它们不需要懒惰地创建写入的元素，因此它们是：
随机访问遍历迭代器和可读可写和左值迭代器
我还需要两者的 const 版本，它们是不可写的。
我可以填空，但不确定如何使用 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;