Ha senso implementare iteratori per contenitori che non hanno una fine ovvia - ad es. alberi?

Question

Sto scrivendo un modello di albero di ricerca binario per due motivi: l'apprendimento del C ++ e l'apprendimento degli algoritmi e delle strutture dati più comuni.
Quindi, ecco la domanda: finché voglio implementare gli iteratori, mi sembra che non ci sia una definizione rigorosa per dove finisce l'albero. Quali sono i tuoi suggerimenti? Come posso farlo?

Answer 1

Per gli alberi, esistono degli standard per l'attraversamento dell'albero, ovvero l'enumerazione dei nodi: attraversamento preordine, attraversamento in ordine e attraversamento postordine. Invece di descriverli tutti qui, ti reindirizzerò a http://en.wikipedia.org/wiki/Tree_traversal . I concetti si applicano principalmente agli alberi binari, ma è possibile estendere l'idea agli alberi arbitrari aggiungendo più casi: efficacemente, gestire un nodo quindi ricorrere, ricorrere quindi gestire un nodo, gestire tutti i bambini quindi ricorrere in ciascuno ... ecc. Non esiste una categorizzazione canonica di questo approccio di cui sono a conoscenza.

Answer 2

Devi scrivere qualcosa di chiaro quando scrivi un iteratore: un iteratore per una struttura di dati fornisce l'accesso a una raccolta come una sequenza lineare di elementi. Alcune raccolte, come matrici, elenchi e code, sono naturalmente compatibili con l'essere trattate come una sequenza lineare. Altri tipi di raccolte - alberi, dizionari, grafici - non hanno necessariamente una semplice interpretazione come un elenco lineare. In effetti, le interpretazioni multiple sono generalmente valide.

Quello che devi veramente fare quando scrivi un iteratore per una raccolta come un albero è affrontare le seguenti preoccupazioni:

1. Dove inizia l'iterazione della raccolta (root? leaves?)
2. Come procede l'iterazione all'elemento successivo (infix? postfix? suffix? breadth?)
3. Quando termina l'iterazione (lascia? root? nodo finale?)

Qualunque cosa tu scelga, dovresti essere molto chiaro su come nominare (e documentare) il tuo iteratore per rendere ovvio come visiterà ed emetterà nodi.

Potrebbe essere necessario scrivere più iteratori per i diversi tipi di traverali che intendi supportare. Ci sono alcuni buoni articoli qui che dicuss

Se per "rigoroso" intendi: una singola definizione onnicomprensiva, hai ragione, non ce n'è una.

Ma 'end' per gli alberi è molto ben definito, anche se dipende dal metodo di attraversamento che stai scegliendo.

• Se si esegue una traversata in ordine (o simmetrica), l'elemento più a destra sarebbe end .
• in preordine (o prima in profondità), l'elemento più a destra sarebbe end , ecc.
• in postordine, l'elemento radice sarebbe end , ecc.

Metodi traversal tree più comuni.

La tua definizione di iteratore è leggermente sbagliata. Gli iteratori non vanno da inizio a fine , né fronte a indietro . Invece vanno attraverso tutti i membri di quella struttura.

Se chiedi l'iterazione su una struttura ordinata, ad esempio un array, un elenco collegato, ecc. (di solito) i tuoi membri verranno restituiti in ordine.

Per gli oggetti non ordinati, ad esempio un set, li otterrai in qualunque ordine il set-iteratore voglia darti, ma li otterrai tutti e uno alla volta, proprio come faresti tu con un array-iteratore.

Per quanto riguarda gli alberi, altre persone hanno già menzionato: hanno nozioni ben definite di ordine totale, devi solo sceglierne uno :)

Dipende da cosa vuoi fare con l'albero - forse sarebbe bello avere, ad esempio, iteratori Breadth-First-Search o Depth-First-Search (o entrambi).

Se hai un modo particolare di setacciare l'albero, allora in effetti hai un inizio e una fine. Non è così ovvio come le relazioni lineari in elenchi e insiemi, ma è lì se vuoi imporre qualche ordine su di esso.

Ha senso specialmente in casi del genere, perché offre agli utenti della tua classe un modo per camminare facilmente su tutti gli elementi in modi diversi a seconda della situazione. Senza di loro, gli utenti devono scrivere da soli modi complicati, solitamente ricorsivi. Rispetto ad es. vettori in cui gli iteratori stanno digitando più che usando for (i = 0; i     

Penso in iteratore in un modo più astratto. Nel modello iteratore non vedo nulla che dica davvero che c'è un inizio o una fine! Quindi, perché essere vincolati a quella visione. Possiamo immaginare un iteratore che riguarda solo l'elemento successivo, tutto qui. Voglio dire, ho affrontato (specialmente in elaborazione di massa) situazioni in cui fin dall'inizio non conosciamo l'estensione della collezione, non sappiamo se un giorno finirà, o non abbiamo tutto il loro elementi caricati in memoria, e non ci interessa. Ci preoccupiamo solo di ottenere il prossimo elemento. In una di queste implementazioni il nodo successivo viene creato subito dopo la chiamata del metodo dell'elemento successivo. Possiamo aprire le nostre menti e pensare a infinite raccolte (alla fine una raccolta è un tipo di insieme matematico) come le raccolte di tutti i numeri, la raccolta di tutti i numeri casuali. Non devi avere effettivamente tutti gli elementi in memoria (questo è ovvio per infinite collezioni). Naturalmente non si tratta di esempi pratici, ma il mio messaggio è che un utente di un Iteratore non deve fare affidamento sulla struttura o sull'estensione effettiva di una raccolta. DAMMI SOLO IL PROSSIMO (SE LO AVETE).

Answer 3

Answer 4

Answer 5

Answer 6

Se per "rigoroso" intendi: una singola definizione onnicomprensiva, hai ragione, non ce n'è una.

Ma 'end' per gli alberi è molto ben definito, anche se dipende dal metodo di attraversamento che stai scegliendo.

• Se si esegue una traversata in ordine (o simmetrica), l'elemento più a destra sarebbe end .
• in preordine (o prima in profondità), l'elemento più a destra sarebbe end , ecc.
• in postordine, l'elemento radice sarebbe end , ecc.

Answer 7

Metodi

Answer 8

La tua definizione di iteratore è leggermente sbagliata. Gli iteratori non vanno da inizio a fine , né fronte a indietro . Invece vanno attraverso tutti i membri di quella struttura.

Se chiedi l'iterazione su una struttura ordinata, ad esempio un array, un elenco collegato, ecc. (di solito) i tuoi membri verranno restituiti in ordine.

Per gli oggetti non ordinati, ad esempio un set, li otterrai in qualunque ordine il set-iteratore voglia darti, ma li otterrai tutti e uno alla volta, proprio come faresti tu con un array-iteratore.

Per quanto riguarda gli alberi, altre persone hanno già menzionato: hanno nozioni ben definite di ordine totale, devi solo sceglierne uno :)

Answer 9

Dipende da cosa vuoi fare con l'albero - forse sarebbe bello avere, ad esempio, iteratori Breadth-First-Search o Depth-First-Search (o entrambi).

Se hai un modo particolare di setacciare l'albero, allora in effetti hai un inizio e una fine. Non è così ovvio come le relazioni lineari in elenchi e insiemi, ma è lì se vuoi imporre qualche ordine su di esso.

Answer 10

Ha senso specialmente in casi del genere, perché offre agli utenti della tua classe un modo per camminare facilmente su tutti gli elementi in modi diversi a seconda della situazione. Senza di loro, gli utenti devono scrivere da soli modi complicati, solitamente ricorsivi. Rispetto ad es. vettori in cui gli iteratori stanno digitando più che usando for (i = 0; i     

Answer 11

Penso in iteratore in un modo più astratto. Nel modello iteratore non vedo nulla che dica davvero che c'è un inizio o una fine! Quindi, perché essere vincolati a quella visione. Possiamo immaginare un iteratore che riguarda solo l'elemento successivo, tutto qui. Voglio dire, ho affrontato (specialmente in elaborazione di massa) situazioni in cui fin dall'inizio non conosciamo l'estensione della collezione, non sappiamo se un giorno finirà, o non abbiamo tutto il loro elementi caricati in memoria, e non ci interessa. Ci preoccupiamo solo di ottenere il prossimo elemento. In una di queste implementazioni il nodo successivo viene creato subito dopo la chiamata del metodo dell'elemento successivo. Possiamo aprire le nostre menti e pensare a infinite raccolte (alla fine una raccolta è un tipo di insieme matematico) come le raccolte di tutti i numeri, la raccolta di tutti i numeri casuali. Non devi avere effettivamente tutti gli elementi in memoria (questo è ovvio per infinite collezioni). Naturalmente non si tratta di esempi pratici, ma il mio messaggio è che un utente di un Iteratore non deve fare affidamento sulla struttura o sull'estensione effettiva di una raccolta. DAMMI SOLO IL PROSSIMO (SE LO AVETE).