Utilizzando boost :: iterator

Question

ho scritto una classe vettore sparse (vedi # 1 , # 2 .)

Vorrei fornire due tipi di iteratori:

Il primo set, iteratori regolari, può puntare qualsiasi elemento, sia inserita o disinserita. Se in cui vengono letti, tornano sia il valore impostato o value_type(), se sono scritti a, creano l'elemento e restituiscono il riferimento lvalue. Pertanto, esse sono:

Random Access Traversal Iterator e leggibile e scrivibile Iterator

La seconda serie, i iteratori sparse, iterate sopra solo gli elementi impostati. Dal momento che non c'è bisogno di creare pigramente elementi che vengono scritti, che sono:

Random Access Traversal Iterator e leggibile e scrivibile e lvalue Iterator

Ho anche bisogno versioni const di entrambi, che non sono modificabili.

posso riempire gli spazi vuoti, ma non sapete come usare boost :: iterator_adaptor per iniziare.

Ecco quello che ho finora:

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

Inoltre, è questo illegale?

typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator;

Answer 1

Non sono sicuro che si vuole veramente utilizzare iterator_adaptor nel tuo caso -. Si potrebbe desiderare di utilizzare iterator_facade invece

spiegazione più approfondita: iterator_adaptors vengono utilizzati quando si dispone di un iteratore esistente (diciamo std::list<int>::iterator) e si vuole riutilizzare il suo comportamento per il vostro iteratore, per esempio. il vostro iteratore restituirà il doppio del valore di ciò che è nella lista, ma il riutilizzo del codice attraversamento dalla iteratore originale. O viceversa: si potrebbe desiderare un iteratore che salterà alcuni degli elementi della lista originale, ma restituire i valori invariati. Non sono sicuro se si desidera basare l'iteratore (come il riutilizzo del codice di) su iteratori delle vostre strutture sottostanti, ma parlando per me, non vorrei soprattutto nel caso di iteratore non di tipo sparse, come si sarebbe probabilmente desidera creare qualche proxy per il riferimento che significa che non è possibile utilizzare qualsiasi sottostante iteratore codice dereference(), e attraversamento è probabilmente facile. È possibile, tuttavia, base vostro sparse_iterator su alcuni iteratore che scorre sopra in realtà elementi dell'array esistente se si desidera.

Non ci sono problemi con l'approccio proxy, quindi non aspettatevi di lavorare senza problemi senza passare attraverso molti cerchi. Per prima cosa, la versione const del non di tipo sparse iteratore deve ancora tornare value_type(), il che significa che espressioni come iter->foo() dovrebbero tradurre in value_type().foo() se la voce corrispondente non esiste. Ma questo pone una difficoltà, che pointer_proxy::operator->() deve restituire qualcosa con operator->, preferibilmente un puntatore (sicuramente non value_type()). Che porta alla domanda cruciale: Un puntatore a che cosa? Ci sono possibilità per risolvere questo (per uno, se avete i vostri oggetti gestiti da boost::shared_pointer, si può semplicemente restituire un shared_pointer a un'istanza new'd).

Per l'iteratore non di tipo sparse, è necessario implementare:

• class reference_proxy con
• reference_proxy::operator& (che probabilmente restituire un proxy puntatore)
• reference_proxy::operator value_type&() per usi const
• reference_proxy::operator const value_type&() per usi non-const

• reference_proxy::foo() per qualsiasi funzione membro foo() di value_type (altrimenti espressioni come (*it).foo() per quanto ne so non funzionerà)

• class pointer_proxy con

• pointer_proxy::operator* (restituire un reference_proxy)
• pointer_proxy::operator-> (fare qualcosa di sensato, vedi sopra)

I parametri per il modello di facciata iteratore dovrebbero essere:

• Reference: il reference_proxy
• Pointer: il pointer_proxy

La versione rada è più semplice: se il sottostante iteratore è sensibile (. Cioè corrisponde al comportamento che si desidera) e correttamente applicato, si può semplicemente omettere i parametri al iterator_adaptor (tranne che per i primi due), e prendere tutto l'implementazione .

Il "non compila" problema:. Inserto typename