Iteratori in C++ (stl) vs Java, c'è una differenza concettuale?

StackOverflow https://stackoverflow.com/questions/56347

  •  09-06-2019
  •  | 
  •  

Domanda

Sto tornando al C++ dopo essere stato via per un po' e aver provato a rispolverare il vecchio melone.

In Java Iterator è un'interfaccia per un contenitore con metodi:hasNext(), next() e rimuovi().La presenza di hasNext() lo significa ha il concetto di limite per il contenitore da attraversare.

//with an Iterator
Iterator<String> iter = trees.iterator();
while (iter.hasNext()) 
{
    System.out.println(iter.next());
}

Nella libreria di modelli standard C++, gli iteratori sembrano rappresentare un tipo di dati o una classe che supporta operator++ e operator== ma ha nessun concetto di limite integrato, quindi è necessario effettuare un confronto prima di passare all'elemento successivo.Il limite deve essere controllato dall'utente confrontando due iteratori nel caso normale, il secondo iteratore è l'estremità del contenitore.

vector<int> vec;
vector<int>::iterator iter;

// Add some elements to vector
v.push_back(1);
v.push_back(4);
v.push_back(8);

for(iter= v.begin(); iter != v.end(); iter++)
{
    cout << *i << " "; //Should output 1 4 8
}

La parte interessante qui è che in C++ un puntatore è un iteratore di un array.Il STL ha preso ciò che esisteva e ha costruito delle convenzioni attorno ad esso.

C'è qualche ulteriore sottigliezza in questo che mi sfugge?

È stato utile?

Soluzione

Sì, c'è una grande differenza concettuale.C++ utilizza diverse "classi" di iteratori.Alcuni sono usati per l'accesso casuale (a differenza di Java), altri sono usati per l'accesso diretto (come Java).Mentre anche altri vengono utilizzati per scrivere dati (da utilizzare, ad esempio, con transform).

Vedere il concetto di iteratori nel file Documentazione C++:

  • Iteratore di input
  • Iteratore di output
  • Iteratore in avanti
  • Iteratore bidirezionale
  • Iteratore ad accesso casuale

Questi sono molto più interessanti e potenti rispetto ai deboli iteratori di Java/C#.Si spera che queste convenzioni vengano codificate utilizzando C++0x Concetti.

Altri suggerimenti

Forse un po' più teorico.Matematicamente, le raccolte in C++ possono essere descritte come un intervallo semiaperto di iteratori, vale a dire un iteratore che punta all'inizio della raccolta e un iteratore che punta proprio dietro l'ultimo elemento.

Questa convenzione apre una serie di possibilità.Per il modo in cui funzionano gli algoritmi in C++, tutti possono essere applicati a sottosequenze di una raccolta più ampia.Per far funzionare una cosa del genere in Java, devi creare un wrapper attorno a una raccolta esistente che restituisca un iteratore diverso.

Un altro aspetto importante degli iteratori è già stato menzionato da Frank.Esistono diversi concetti di iteratori.Gli iteratori Java corrispondono agli iteratori di input di C++, ovverosono iteratori di sola lettura che possono essere incrementati solo un passo alla volta e non possono tornare indietro.

All'estremo opposto, ci sono puntatori C che corrispondono esattamente al concetto C++ di iteratore ad accesso casuale.

Tutto sommato, il C++ offre un concetto molto più ricco e puro che può essere applicato a una varietà molto più ampia di attività rispetto ai puntatori C o agli iteratori Java.

Come accennato, gli iteratori Java e C# descrivono una posizione (stato) e un intervallo (valore) mescolati, mentre gli iteratori C++ separano i concetti di posizione e intervallo.Gli iteratori C++ rappresentano "dove sono adesso" separatamente da "dove posso andare?".

Gli iteratori Java e C# non possono essere copiati.Non è possibile recuperare una posizione precedente.Gli iteratori C++ comuni possono farlo.

Prendere in considerazione questo esempio:

// for each element in vec
for(iter a = vec.begin(); a != vec.end(); ++a){
  // critical step!  We will revisit 'a' later.
  iter cur = a; 
  unsigned i = 0;
  // print 3 elements
  for(; cur != vec.end() && i < 3; ++cur, ++i){
      cout << *cur << " ";
  }
  cout << "\n";
}

Fare clic sul collegamento precedente per visualizzare l'output del programma.

Questo ciclo piuttosto stupido attraversa una sequenza (usando solo la semantica dell'iteratore diretto), stampando ciascuna sottosequenza contigua di 3 elementi esattamente una volta (e un paio di sottosequenze più brevi alla fine).Ma supponendo N elementi e M elementi per riga invece di 3, questo algoritmo sarebbe ancora O(N*M) incrementi dell'iteratore e O(1) spazio.

Gli iteratori in stile Java non hanno la capacità di memorizzare la posizione in modo indipendente.Lo farai neanche tu

  • perdere O(1) spazio, utilizzando (ad esempio) un array di dimensione M per memorizzare la cronologia durante l'iterazione
  • dovrà attraversare l'elenco N volte, ottenendo un tempo O(N^2+N*M).
  • oppure utilizzare un tipo Array concreto con la funzione membro GetAt, perdendo il genericismo e la possibilità di utilizzare tipi di contenitori di elenchi collegati.

Poiché in questo esempio sono stati utilizzati solo i meccanismi di iterazione in avanti, sono stato in grado di scambiare un elenco con nessun problema.Ciò è fondamentale per la creazione di algoritmi generici, come ricerca, inizializzazione e valutazione ritardate, ordinamento, ecc.

L'incapacità di conservare lo stato corrisponde più da vicino all'iteratore di input STL C++, su cui sono costruiti pochissimi algoritmi.

Un puntatore a un elemento dell'array è infatti un iteratore nell'array.

Come dici tu, in Java, un iteratore ha più conoscenza del contenitore sottostante che in C++.Gli iteratori C++ sono generali e a paio di iteratori può denotare qualsiasi intervallo:questo può essere un sottointervallo di un contenitore, un intervallo su più contenitori (vedi http://www.justsoftwalutions.co.uk/articles/pair_iterators.pdf O http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html) o anche una serie di numeri (vedi http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/counting_iterator.html)

Le categorie dell'iteratore identificano cosa puoi e cosa non puoi fare con un dato iteratore.

Per me la differenza fondamentale è che gli iteratori Java puntano tra gli elementi, mentre gli iteratori STL C++ puntano agli elementi.

Gli iteratori C++ sono una generalizzazione del concetto di puntatore;lo rendono applicabile a una gamma più ampia di situazioni.Significa che possono essere usati per fare cose come definire intervalli arbitrari.

Gli iteratori Java sono enumeratori relativamente stupidi (anche se non così male come quelli di C#;almeno Java ha ListIterator e può essere utilizzato per modificare la raccolta).

Gli iteratori sono equivalenti ai puntatori solo nel caso banale di scorrere il contenuto di un array in sequenza.Un iteratore potrebbe fornire oggetti da un numero qualsiasi di altre fonti:da un database, da un file, dalla rete, da qualche altro calcolo, ecc.

Gli iteratori della libreria C++ (la parte precedentemente nota come STL) sono progettati per essere compatibili con i puntatori.Java, senza l'aritmetica dei puntatori, aveva la libertà di essere più facile da programmare.

In C++ finisci per dover utilizzare una coppia di iteratori.In Java usi un iteratore o una raccolta.Gli iteratori dovrebbero essere il collante tra l'algoritmo e la struttura dei dati.Il codice scritto per 1.5+ raramente necessita di menzionare gli iteratori, a meno che non stia implementando un particolare algoritmo o struttura dati (cosa che la stragrande maggioranza dei programmatori non ha bisogno di fare).Poiché Java utilizza sottoinsiemi di polimorfismo dinamico e simili sono molto più facili da gestire.

Ci sono molte buone risposte sulle differenze, ma ho sentito che la cosa che mi infastidisce di più con gli iteratori Java non è stata enfatizzata: non puoi leggere il valore corrente più volte.Ciò è davvero utile in molti scenari, soprattutto quando si uniscono gli iteratori.

In C++, hai un metodo per far avanzare l'iteratore e leggere il valore corrente.La lettura del suo valore non fa avanzare l'iterazione;così puoi leggerlo più volte.Questo non è possibile con gli iteratori Java e finisco per creare wrapper che lo fanno.

Una nota a margine:un modo semplice per creare un wrapper è utilizzarne uno esistente:PeekingIterator da Guava.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top