Iterator / Range design, un iteratore di input leggero implementato con il modello iteratore di C ++ / java?

-1

Mi piacerebbe capire meglio le decisioni sul design di Iterator / Range (concentrandomi su InputIterators).

Fondamentalmente, questo è il modello java:

while (iter.hasNext()) {
    Object o = iter.next();
    // do something with o
}

Ma ecco una citazione di James Kanze:

Not that Java's iterators are perfect, either. The merge access and incrementing---as did the USL iterators. By the time Java was being developed, we'd already established that this wasn't a good idea, so it's hard to understand why they did it.

Afferma che la fusione dell'accesso e dell'incremento non è una buona idea. Stavo cercando di scoprire il "perché", ma non ho trovato nulla.

L'iteratore "fisso" assomiglia a questo (che è l'iteratore GoF):

while (!iter.isDone()) {
    Object o = iter.element();
    // do something with o
    iter.next();
}

Per C ++ 1z, potremmo avere il nuovo modello di gamma. Per InputRange, end() potrebbe restituire un tipo sentinella speciale, quindi la gestione della condizione di fine flusso può essere ottimizzata in modo ottimale.

Ora, supponiamo di voler creare un InputRange (che è un intervallo leggero: non memorizza l'elemento di lettura), che legge le righe da un file / socket. Qui, la condizione di fine flusso viene scoperta solo dopo aver provato a leggere. Un modello iteratore "ottimale" potrebbe essere questo:

string line;
while (iter.getNext(line)) {  // getNext returns false at end-of-stream
    // do something with line
}

Questo iteratore differisce da uno qualsiasi dei precedenti.

Le mie domande sono:

  • quali sono gli aspetti negativi dell'accesso di Java + modello di iteratore incrementale (puoi dare un esempio di questo)?
  • è possibile implementare l'iteratore leggero desiderato con uno dei tipi di iteratore menzionati (java / GoF / C ++)? In caso contrario, quali sono i vantaggi degli altri modelli iteratori, quindi non viene utilizzato il mio modello iteratore "ottimale"? O in altre parole, quali possono essere gli aspetti negativi del mio modello iteratore "ottimale", quindi non viene generalmente utilizzato?
posta geza 15.09.2017 - 18:28
fonte

1 risposta

4

what are the cons of Java's access+increment iterator model (can you give an example of that)?

Bene, c'è l'ovvio: il fatto che non puoi incrementare senza accedere.

Diciamo che hai un iteratore su un array. E vuoi saltare i primi 5 elementi. Ciò richiede l'accesso a questi elementi, anche se vuoi semplicemente saltarli. Ecco 5 extra dereferenze, quando tutto ciò di cui avevi bisogno era di incrementare un puntatore 5 volte.

O incrementa un puntatore di 5 una volta.

can my desired lightweight iterator be implemented with any of the mentioned iterator-types (java/GoF/C++)?

Può essere implementato in C ++, ma solo nel senso che è possibile aggiungere tale funzione al proprio tipo di iteratore o che è possibile creare una funzione di supporto che prende un InputIterator ed esegue tale operazione su di esso.

Non puoi forzare qualcuno a usare i tuoi InputIterator in questo modo. Lo standard C ++ ha definito il concetto InputIterator, ed è quello che usano le funzioni della libreria standard.

If not, then what are the pros of the other iterator models, so not my "optimal" iterator model is used instead?

Il modello di iteratore C ++ analizza gli iteratori con i puntatori: una posizione specifica in una sequenza di cose. Un puntatore sa come arrivare al prossimo iteratore e sa come ottenere ciò a cui punta.

Ma non sa se il prossimo iteratore punta a un oggetto legittimo. Un puntatore può incrementare, ma non sa se il prossimo puntatore è valido.

Questo è il motivo per cui C ++ usa coppie di iteratori; l'iteratore finale ti dice dove fermarti.

Avere un iteratore che sa quando fermarsi richiede che l'iteratore contenga anche le informazioni per sapere quando fermarsi. Oh certo, per un InputIterator basato su file, lo hai già. Ma per quanto riguarda l'inserimento da una stringa che hai già?

Considera std::copy_n . Esegue n copie / incrementi dall'iteratore di input all'iteratore di output. Ma non controlla mai se l'iteratore di input abbia effettivamente un altro valore; ci si aspetta che tu fornisca un iteratore che contiene almeno n di elementi. Se non lo fai, ottieni UB.

Con il tuo tipo di iteratore, ottieni n di copie, ma anche n controlla la condizione di chiusura. E ancora, per un InputIterator basato su file, dovresti farlo comunque. Ma per altri tipi di iteratori, è inutile lavoro aggiuntivo.

A C ++ piace l'idea che tu non paghi ciò che non usi. E se non hai bisogno di un punto finale per un iteratore, non dovresti averlo come parte del tuo modello iteratore.

Or in other words, what can be the cons of my "optimal" iterator model, so it is not generally used?

Il fatto che, come modello, non è ottimale. Potrebbe essere ottimale in un caso specifico, ma richiede un sovraccarico che il concetto C ++ InputIterator non richiede.

Inoltre, c'è il fatto che il value_type che viene iterato deve essere Assegnabile in qualche modo (dal momento che getNext deve assegnargli il nuovo valore). Il che significa anche che la funzione getNext copia / si sposta nell'oggetto.

Inoltre, il tipo deve anche avere un costruttore predefinito o uno stato altrimenti "vuoto", poiché è necessario costruirlo prima per leggere i dati in esso.

Il modello di iteratore C ++ non impone tali requisiti su value_type .

Dai commenti:

If you add the read object into the iterator, it can be much more heavyweight. For example, if you read lines, then it will contain a string (allocation happen, etc.). For "my" iterator, it doesn't have to.

Eppure, entrambi hanno ancora l'onere di avere quel string in giro. Nel modello, il chiamante deve fornire string . Nel modello iteratore / intervallo STL, l'iteratore / intervallo lo fornisce. Quindi, mentre si potrebbe dire che un iteratore / intervallo STL è più costoso, ci si aspetta che qualcuno debba pagare in entrambi i modi.

Quindi nessuno dei due è più efficiente dell'altro. Facendo pagare al costo questo modello iteratore / intervallo, consente a tali oggetti di lavorare senza stato esterno.

    
risposta data 15.09.2017 - 20:15
fonte

Leggi altre domande sui tag