[C++] Discussione Esercizio

[starsuper]

#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

struct anagrams { //usata probabilmente per tenere tutto public
    class iterator {// dichiaro come elemento la classe iterator (ma non era prevista di default, in stile vettore?)
        std::string s;
        bool has_next;
        iterator() {
            has_next = false; //dichiaro costruttore vuoto per la classe iterator
        }
        iterator(std::string a) : s(a) { //costruttore due, inzi. s=a
            has_next = s.size() > 0;
            sort(s.begin(), s.end());//quando creo il costruttore con la stringa passata, la ordino anche
        }
        friend anagrams;//dichiaro che la struct anagram è amica e puo accedere ai valori privati della classe
        public:
        bool operator != (const iterator& it) { //dichiaro overloading operatore !=
            return has_next != it.has_next;
        }
        iterator& operator++() {//dichiaro operatore incremento.
            has_next = next_permutation(s.begin(), s.end());
            return *this;}
        
        string& operator*() { //dichiaro operatore accesso al valore iteratore
            return s;
        }
    };
    
private: //private relativo alla struct
    string s;
    iterator end_iter;
    
public: //public della struct
    anagrams(std::string a) : s(a) { } //dichiaro costruttore di una stringa
    iterator begin() { //funzione begin per la classe iteraotr?
        return iterator(s);
    }
    iterator& end() { //funzione end x la classe iterator
        return end_iter;
    }
};


int main() {
    anagrams a("anna");
    for (anagrams::iterator it = a.begin(); it != a.end(); ++it)
        cout << *it << std::endl;
    return 0;
}

Salve a tutti, sto preparando un esame di c++ e con sommo dispiacere non sono riuscito a risolvere questo esercizio e ho dovuto ricorrere alla soluzoine del prof.
L'esame fornisce solamente il main, il resto va fatto da noi studenti. Allora, brevemente, cerco di chiedervi quello che non mi è tornato.
Il testo prevede di :
Write a class anagrams such that the following code fragment prints all anagrams of word "anna":


Innanzitutto, perche usare struct anagram e non una classe? Forse per fare in modo che tutto cio senza identifier sia pubblico?

iterator() {        has_next = false    }

iterator(std::string a) : s(a) { // inzializza poi s=a
            has_next = s.size() > 0;
            sort(s.begin(), s.end());/

Dichiaro i due costruttori per gli iteratori, il primo vuoto che dichiara in auto che non ha elementi e il secondo che prende una stringa in ingresso, la inizializza e la ordina.

Ma mi chiedo, come mai devo dichiarare la classe iterator? In altri esercizi l'ho usata su Stringhe e Vector senza doverla dichiarare! Perche qui sono stato costretto a dichiararla?

A questo punto inizia l'overloading operatori, innanzitutto, cosa si fa qui?

 bool operator != (const iterator& it) { 
            return has_next != it.has_next;
        }

Si fa l'overloading del diverso ma controllo se la variabile has_next di it è vera o falsa? Non capisco!

  iterator& operator++() {
            has_next = next_permutation(s.begin(), s.end());
            return *this;} 

Overloading del post incremento. Salvo e restituisco la prossima permutazione, ok. Non prendo parametri perche viene chiamata direttamente sull'operatore ? La scelta di restituire un reference è arbitraria o si potrebbe anche restituire il value?

String& operator*()
{return s};
{

overloading dell'operatore accesso al reference. Ma perche restituisco s?

 
anagrams(string a) : s(a) { } 
    iterator begin() { 
        return iterator(s);
    }

Crea la funzione begin per la classe iterator. Ma perche la dichiaro qui e non nella classe iterator?
Inoltre, tutto ciò che fare è restituire un iterator della stringa s passata?

anagrams::iterator it 

quando nel main faccio questo, che costruttore richiamo?


Scusate la lunghezza e la poca chiarezza ma non è facile scrivere codice cosi. Grazie a chiunque risponderà

[apatriarca]

Devi implementare una classe iterator perché è un tipo non standard creato da te. Nel caso di vector e string questa classe è già fornita dalla libreria standard.

[starsuper]

Ok ho risolto un po' di punti dell'esercizio. i miei dubbi sono a questo punto

- Overloading di !=, che fa? restituisce true se it punta ad un oggetto differente da quello del nostro iteratore,false altimenti!
Vediamo in dettaglio:
Nel for del main, avrò

it!=a.end()

quindi finche il nostro operatore it non arriva alla fine della stringa esso restituisce true. False significa che i due indirizzi coincidono?

-

has_next=next_permutation(s.begin(),s.end());

has_next è booleana come fa a contenere una stringa?


Grazie

[apatriarca]

La funzione next_permutation modifica la stringa, non ne restituisce una nuova. Il valore di ritorno è uguale a true finché la successiva permutazione è diversa dalla stringa ordinata. Il codice corrispondente senza l'offuscamento dovuto alla creazione della classe e dell'iteratore sarebbe quindi il seguente:

int main() {
    std::string s = "anna";
    std::sort(s.begin(), s.end());
    do {
        cout << s << std::endl;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

In pratica la stringa viene ordinata e quindi si usa la funzione next_permutation per ottenere tutte le permutazioni finché la stringa non torna quella ordinata di partenza e si esce dal ciclo.

L'operatore != serve per poter fare il confronto it != a.end().. Siccome la condizione da verificare è il valore di ritorno della funzione, questo valore viene salvato e usato nel confronto con la condizione di uscita "valore di ritono è false".

[starsuper]

"apatriarca":La funzione next_permutation modifica la stringa, non ne restituisce una nuova. Il valore di ritorno è uguale a true finché la successiva permutazione è diversa dalla stringa ordinata. Il codice corrispondente senza l'offuscamento dovuto alla creazione della classe e dell'iteratore sarebbe quindi il seguente:

int main() {
    std::string s = "anna";
    std::sort(s.begin(), s.end());
    do {
        cout << s << std::endl;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

In pratica la stringa viene ordinata e quindi si usa la funzione next_permutation per ottenere tutte le permutazioni finché la stringa non torna quella ordinata di partenza e si esce dal ciclo.

Quindi ogni ++it, del for non fa altro che eseguire una nuova permutazione sulla stessa stringa s in ingresso. Ma con it=a.begin() e it!=a.end() cosa controllo? Non abbiamo detto che si esce dal ciclo quando non ci sono piu permutazioni da fare?

L'operatore != serve per poter fare il confronto it != a.end().. Siccome la condizione da verificare è il valore di ritorno della funzione, questo valore viene salvato e usato nel confronto con la condizione di uscita "valore di ritono è false".

Ma la stringa a essendo della classe String ha un suo iteratore che una volta richiamata s.begin() restituisce il primo elemento della stringa e noi cosi ci inizializziamo il nostro iteratore it? Io ho sempre associato ad un indice come a qualcosa che scorre ma qui facendo ++it faccio una nuova permutazione non riesco ad immaginamelo.

it punterà ad ogni passo ad una nuova permutazione che poi verrà stampata tramite il cout ?

[vict85]

Io penso che lo stesso professore non abbia ragionato troppo sul problema che vi ha proposto (e non solo perché il suo main è scritto in un C++ un po' datato[nota]Quel c++ ancora si usa perché ci sono casi in cui ti trovi a programmare su compilatori datati, ma questa è un'altra storia.[/nota]).

Venendo al tuo problema io vedo tre criticità:
[list=1][*:206tsw7b] la classe iterator non dovrebbe cambiare lo stato della classe anagrams. Quindi in particolare iterator dovrebbe contenere una copia della stringa di anagrams o dovrebbe costruirla quanto si usa l'operatore *.[/*:m:206tsw7b]
[*:206tsw7b] Le permutazioni della parola "anna" non sono uguali alle permutazioni della stessa parola. Infatti anna ha solo 6 anagrammi ma 24 permutazioni ( aann, anan, anna, naan, nana, nnaa). Quindi non puoi usare next_permutation ma dovresti costruirne una tua versione simile. Cosa non troppo difficile ma che richiede una certa cura e anche un po' di tempo.[/*:m:206tsw7b]
[*:206tsw7b] in quasi tutte le librerie e nell'idea del tuo professore, end() dovrebbe costruire un iteratore all'elemento successivo all'ultimo valido. Trovo quindi che questo sia un esempio in cui l'approccio usando l'iteratori non sia l'ideale (a meno di generare tutte gli anagrammi durante il costruttore di anagrams[nota]Per risparmiare spazio è possibile raccogliere gli anagrammi in qualche struttura dati, ma certamente è una operazione impegnativa.[/nota] e usare un semplice puntatore per l'iteratore). Se non trovi chiaro questo punto posso spiegarlo meglio.[/*:m:206tsw7b][/list:o:206tsw7b]

Considerando che è un compito d'esame, suppongo che il professore avesse in mente che voi doveste generare tutte gli anagrammi nel costruttore di anagrams e usare iterator come un semplice iteratore a quel vettore (o qualche altro container standard).

[vict85]

Scusa, non avevo notato che stavi commentando la "soluzione" del docente e che a quanto sembra next_permutation tiene conto delle ripetizioni, si impara sempre qualcosa di nuovo sulla Standard library. Continuo comunque a pensare che l'implementazione usando gli iteratori sia un modo di approcciare il problema piuttosto discutibile: il test che fai sul != infatti serve solo a far funzionare la logica dell'iteratore (per questo lo trovi poco intuitivo).

[starsuper]

Vi ringrazio per le risposte. Essendo neofita in effetti ero piuttosto tranquillo sugli iteratori in quanto li avevo visti usare sempre su string o vector in maniera standard, ma una volta affonrtato questo esercizio mi ha letteralmente confuso le idee.

Visto che hai alzato l'argomento ti chiedo, per quanto riguarda next_permutation, non è obbligatorio crearlo in i++? Come avrei potuto metterlo nel costruttore ?

anagrams (string a)
{
    std::string s = a;
    std::sort(s.begin(), s.end());
    do {
          s=next_permutation(s.begin(), s.end()); 
    while (next_permutation(s.begin(), s.end()));
}
} 

In questo modo non appena creavo l'oggetto anagrams a("anna")avevo al suo interno già tutte le permutazioni? Avrei dovuto fare l'overload dell'operatore * comunque?



-------------------------

la classe iterator non dovrebbe cambiare lo stato della classe anagrams. Quindi in particolare iterator dovrebbe contenere una copia della stringa di anagrams o dovrebbe costruirla quanto si usa l'operatore *.

Che significa?

[apatriarca]

Dopo ogni ciclo perdi l'anagramma precedente.. Non è insomma vero che dopo aver lanciato quel codice hai tutte le permutazioni.