使用boost :: iterator

Question

我写了一个稀疏的矢量类(参见#1,#2.)

我想提供两种迭代器:

第一个集合,即常规迭代器,可以指向任何元素,无论是设置还是未设置.如果它们被读取,它们将返回设置值,或者value_type(),如果它们被写入,则它们创建元素并返回左值引用.因此,它们是:

随机访问遍历迭代器和可读和可写迭代器

第二个集合,即稀疏迭代器,仅迭代set元素.由于他们不需要懒惰地创建写入的元素,因此它们是:

随机访问遍历迭代器和可读和可写和左值迭代器

我还需要两者的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;

Answer 1

我不确定你真的想iterator_adaptor在你的情况下使用- 你可能想要使用iterator_facade.

更彻底的解释:iterator_adaptors当你有一个现有的迭代器(比方说std::list<int>::iterator)并且想要为迭代器重用它的行为时使用它,例如.你的迭代器将返回列表中值的两倍,但重用原始迭代器中的遍历代码.或者反过来说:您可能需要一个迭代器来跳过原始列表中的一些元素,但返回值不变.我不确定你是否想要将你的迭代器(如在重用代码中)作为你的底层结构的迭代器,但是对我来说,我不会特别在nonsparse迭代器的情况下,因为你可能想要创建一些引用的代理,这意味着你不能使用任何底层的迭代器dereference()代码,并且遍历可能很容易.但是,您可以sparse_iterator根据需要使用一些迭代器来迭代数组的实际现有元素.

代理方法存在问题,因此不要指望它在没有经历过许多环节的情况下完美运行.首先,nonsparse迭代器的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&() 用于const用途
• reference_proxy::operator const value_type&() 用于非常规用途

• reference_proxy::foo()对于foo()value_type的任何成员函数(否则像(*it).foo()AFAIK 这样的表达式将不起作用)

• class pointer_proxy 同

• pointer_proxy::operator* (返回reference_proxy)
• pointer_proxy::operator-> (做一些明智的事,见上文)

迭代器外观模板的参数应该是:

• Reference: reference_proxy
• Pointer: pointer_proxy

稀疏版本更简单:如果底层迭代器是合理的(即匹配您想要的行为)并正确实现,您可以省略参数iterator_adaptor(前两个除外),并采取所有实现.

"不编译"问题:插入typename.