Utilizzando boost :: iterator

Question

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

Vorrei fornire due tipi di iteratori:

il primo set, gli iteratori regolari, può puntare qualsiasi elemento, se impostato o non impostato. Se vengono letti, restituiscono il valore impostato o value_type(), se sono scritti, creano l'elemento e restituiscono il riferimento lvalue. Pertanto, esse sono:

Random Access Traversal Iterator e leggibile e scrivibile Iterator

La seconda serie, gli iteratori sparse, iterare 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 scrivibili e lvalue Iterator

ho anche bisogno versioni const di entrambi, che non sono scrivibili.

Posso compilare gli spazi vuoti, ma non sono sicuro di 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 
      > { 
    }; 
}; 

anche, è 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ù dettagliata: iterator_adaptors vengono utilizzati quando si ha un iteratore esistente (diciamo std::list<int>::iterator) e si desidera riutilizzarne il comportamento per l'iteratore, ad es. il tuo iteratore restituirà il doppio del valore di ciò che è nella lista, ma riutilizzerà il codice trasversale dall'iteratore originale. O viceversa: potresti desiderare un iteratore che salterà alcuni degli elementi nell'elenco originale, ma restituirà i valori invariati. Non sono sicuro se vuoi basare il tuo iteratore (come nel codice di riutilizzo di) su iteratori delle tue strutture sottostanti, ma parlando per me, non lo farei specialmente nel caso di iteratore non spigoloso come vorresti probabilmente creare proxy per il riferimento, il che significa che non è possibile utilizzare alcun codice iteratore sottostante dereference() e l'attraversamento è probabilmente semplice. Puoi, tuttavia, basare il tuo sparse_iterator su un iteratore che itera su elementi effettivamente esistenti dell'array, se lo desideri.

Ci sono problemi con l'approccio proxy, quindi non aspettatevi che funzioni in modo impeccabile senza passare attraverso molti circuiti. Per prima cosa, la versione const dell'iteratore sparse dovrebbe ancora restituire value_type(), il che significa che espressioni come iter->foo() devono essere convertite in value_type().foo() se la voce corrispondente non esiste. Ma questo pone una difficoltà, che pointer_proxy::operator->() dovrebbe restituire qualcosa con operator->, preferibilmente un puntatore (sicuramente non value_type()). Il che porta alla domanda cruciale: un puntatore a cosa?Ci sono possibilità di risolvere questo problema (per esempio, se i tuoi oggetti sono gestiti da boost::shared_pointer, puoi semplicemente restituire un shared_pointer a un'istanza di new).

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 const utilizza
• reference_proxy::operator const value_type&() per i non-const utilizza

• reference_proxy::foo() per qualsiasi funzione membro di valore foo() E_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 deve essere:

• Reference: il reference_proxy
• Pointer: il pointer_proxy

La versione rada è semplice: Se l'iteratore sottostante è ragionevole (es. corrisponde al comportamento desiderato) e implementato correttamente, puoi semplicemente omettere i parametri allo iterator_adaptor (tranne i primi due) e prendere tutta l'implementazione.

Il problema "non viene compilato": inserire typename.