L'iteratore di un contenitore può produrre qualcosa di diverso da un lvalue?

Question

Ho più o meno giunto alla conclusione che è impossibile scrivere un contenitore conforme il cui valore_tipo non è stato memorizzato direttamente nel contenitore. Penso che questo sia sfortunato, perché spesso finisco per desiderare di avere contenitori in cui il tipo di valore è parzialmente calcolato o assemblato da pezzi non contigui (esempi sotto, ma non direttamente rilevanti per la domanda). So come scrivere degli iteratori che usano oggetti proxy, anche se è piuttosto fastidioso. Ma ora mi chiedo se c'è davvero spazio nello standard C++ per tali animali. Probabilmente c'è troppa verbosità qui; la versione tl; dr è semplice: cosa significano veramente i paragrafi 1 e 6 di § 24.2.5 e fino a che punto violando il significato apparente si rompono gli algoritmi standard? O, per dirla in altro modo, come possono essere interpretati per consentire iteratori proxy?

Come sottolinea Pete Becker, non c'è davvero nulla che costringa i miei contenitori a conformarsi ai requisiti stabiliti per i contenitori standard delle biblioteche. Ma per usare un contenitore con molti algoritmi standard, deve avere un iteratore conforme con almeno uno forward_iterator_tag, o deve mentire su questo, ma comunque riuscire a soddisfare i requisiti operativi (se non formali) che il particolare algoritmo impone al suo iteratori.

Ecco il mio ragionamento:

Tabella 96 (§ 23.2.1), requisiti relativi al serbatoio, include:

Expression  Return type   Assertion/note 
------------ -------------  --------------------- 
X::iterator iterator type  any iterator category 
       whose value   that meets the 
       type is T   forward iterator 
            requirements. 
            Convertible to 
            const_iterator. 

a.begin()  iterator; 
       const_iterator for 
       constant a. 

Ora, iteratore in avanti:

§ 24.2.5, parà. 1:

Un tipo di puntatore o classe X soddisfa i requisiti di un iteratore di inoltro se & hellip;

- se X è un iteratore mutabile, reference è un riferimento a T; se X è un iteratore const, reference è un riferimento ad const T

È vero che non v'è alcun requisito diretto per *a restituire reference (dove a è di tipo X). I requisiti sono:

dalla tabella 107 (iterators ingresso) *a deve essere "trasformabile in T" se a è dereferencable.

da tavolo 106 (iteratori) *r deve avere tipo reference dove r è di tipo X& ed è dereferencable.

Tuttavia, la tabella 106 specifica inoltre che ++r rendimenti X&, così *++r devono essere reference. Inoltre, (come da Tabella 107), *a++ deve essere reference, sebbene (Tabella 109) a[n] debba essere solo "convertibile in riferimento". Devo dire che non vedo come è X e *r dove r è di tipo X& potrebbe essere diverso, ma forse mi manca qualche sottigliezza.

Forse c'è un po 'di oscillazione qui, ma non molto; a un certo punto, devi essere pronto a creare uno T, se non ne hai uno nel contenitore, in modo che tu possa fornire un riferimento ad esso.

Ma la cosa peggiore è

§ 24.2.5, par. 6 (a e b sono valori di tipo X): Se a e b sono entrambi dereferenceable, quindi a == b se e solo se *a e *b sono legati allo stesso oggetto.

non riesco a trovare una definizione formale di bound to, ma mi sembra che la solita strategia per fare iteratori di oggetti non indirizzabili è quello di creare un oggetto proxy, generalmente memorizzati all'interno del iteratore stesso. In questo caso, richiederebbe una comprensione estremamente generosa di ciò che "legato a" significa interpretare 24.2.5/6 in un modo diverso da quello di proibire confronti di uguaglianza che si succedono tra due diversi oggetti iteratori, anche se indicano logicamente la stessa posizione nel contenitore.

D'altra parte, rilevo che Dietmar Kühl, che dovrebbe sapere, nella sua risposta a this question dice che:

C++ 2011 ha ottenuto i requisiti rilassato e iteratori non sono necessariamente necessarie per ottenere un lvalue

Quindi, un iteratore può restituire un proxy oppure no? Se è possibile, qual è la natura di tale proxy? Dove fallisce il mio ragionamento secondo il quale un tale iteratore non è conforme?

---

Come promesso, alcuni contenitori il cui value_types efficace non verrebbero memorizzate contiguo nel contenitore:

1) Un contenitore associativo compatto cui chiave e tipi valore può essere memorizzato in modo più efficiente in due vettori separati. (Mantenendo le chiavi in ​​un vettore può anche migliorare cache simpatia, oltre a ridurre allocazione sovraccarico.)

2) A vector<T> che si maschera come map<integer_type, T>, semplificando l'interoperabilità con altri tipi map<X, T>.

3) Un contenitore logico formato da zippare diversi altri contenitori, producendo un valore logico value_type che è un tuple di riferimenti ai tipi di valore dei contenitori compressi. (In alcune applicazioni, uno o più dei contenitori compressi potrebbero essere interamente calcolati, in funzione degli altri valori o come numero di sequenza.)

4) Una vista di un contenitore di un tipo aggregato che ha solo alcuni dei valori. (Molto probabilmente, sia il contenitore sottostante che la vista sono tuple in cui l'elenco dei tipi di tuple della vista è un sottoinsieme, possibilmente in un ordine diverso, dei tipi dei contenitori sottostanti).

Sono sicuro che altre persone potrebbero facilmente aggiungere a questa lista; questi sono solo quelli che ho violato in un modo o nell'altro negli ultimi due mesi.

Answer 1

Non limitarti a pensare a un "contenitore conforme": non c'è nulla nello standard che dipende dall'avere uno.Pensa ai requisiti del contenitore come a una modalità stenografica per descrivere i requisiti per i contenitori definiti nello standard. Niente di più. Finché gli iteratori prodotti dal tuo contenitore sono validi, stai bene con tutti gli algoritmi corrispondenti e, presumibilmente, con gli algoritmi che scrivi tu stesso.

Answer 2

Il modello migliore è std::vector<bool>. È il più vicino a essere il più possibile conforme, eppure i suoi iteratori producono dei proxy.

Lo standard specifica anche che std::vector<bool>::reference è una classe. Tuttavia, la tabella dei requisiti del contenitore specifica che X::reference produce "lvalue di T." Pertanto è rigorosamente non conforme.

Ma gli iteratori non sono associati a T. L'iteratore value_type deve essere T e consultare i requisiti di iteratore di input, reference deve essere convertito in value_type.

Come menziona Pete Becker, le tabelle dei requisiti sono coperte piuttosto ampie e i singoli algoritmi specificano ciò di cui hanno bisogno. Solo un algoritmo che richiede che reference diventi un riferimento si interromperà, il che equivale a dire semplicemente l'ovvio.