[c++] Classe Map scansione chiave

[aleRomatre]

Ciao a tutti,

Ho una classe Alunno in cui definisco il tipo alunno a cui è associato un numero di DNI (documento di identità di tipo string).
Nel main() di prova della classe Alunno ho creato una mappa(<DNI, Aunno>) con 1000 alunni:

chiave => (String) DNI
valore => Alunno

A questo punto devo ricercare, sfruttando potenzialità e metodi della classe map( count ad esempio ??) il numero di occorrenze delle chiavi (DNI) presenti nella mappa, che iniziano per 3;

ho scritto questo :

cout << "Sono presenti nella mappa "  << m.count("3") << " DNI che cominciano per 3." << endl;

ma naturalmente questo mi restituisce 0 in quanto cerca le chiavi esattamente uguali alla stringa "3" e non le stringhe che cominciano per 3, dovrei scansionare la chiave e fare un confronto solo sul primo carattere ... come posso fare ? Grazie mille

[MItaly]

Usa il metodo lower_bound per cercare il primo elemento che inizia con 3, e incrementa l'iteratore finché la chiave continua ad iniziare con il prefisso; la cosa si può facilmente incapsulare in un paio di funzioni.

bool startswith(const std::string &s, const std::string &prefix) {
    return s.rfind(prefix, 0)==0;
}

template<typename VT>
std::size_t count_prefix(const std::map<std::string, VT> &m, const std::string &prefix) {
    std::size_t count=0;
    std::map<std::string, VT>::const_iterator it = m.lower_bound(prefix), end=m.end();
    while(it!=end && startswith(it->first, prefix)) {
        ++it;
        ++count;
    }
    return count;
}

[aleRomatre]

Ragionandoci un attimo ho visto che il problema era molto semplice .... ero io che non lo guardavo nel verso giusto :

int count=0;
    mapa::iterator it;
    for(it= m.begin(); it!=m.end(); ++it){

        int s = it->first[0];

        if (s == 51)  //en decimales 3 ==> en codigo ASCII es 51;
            count++;
    }

Ringrazio comunque MItaly per aver tentato di darmi una mano. Come sempre questo forum si dimostra prezioso e pieno di gente educata.

[MItaly]

Uhm, ma non stai sfruttando il fatto che la mappa ha lookup O(log n) sulle chiavi, tu stai facendo una ricerca lineare come se fosse un vettore (O(n)). Come già detto, il sistema giusto è usare lower_bound (che ti restituisce un iteratore al primo elemento >= della chiave passata) in tempo logaritmico.

Inoltre, perché scrivi 51? Basta scrivere '3'...

[aleRomatre]

Il 51 l'ho scritto in quanto scrivendo "3" come una stringa eclipse mi dava errore... non ho provato con l'apice '3'.
Mi sa allora che non ho ben capito il tuo metodo... puoi spiegarmelo per favore in maniera più approfondita?
Cosa sono size_t e prefix? Perchè usi template( non sono molto esperto)? La funzione rfind su s che fa? Grazie mille

[MItaly]

Il 51 l'ho scritto in quanto scrivendo "3" come una stringa eclipse mi dava errore... non ho provato con l'apice '3'.

"3" è la stringa C "3", ovvero un array di due caratteri ('3' seguito dal carattere di terminazione 0); '3' è il carattere 3, ovvero un modo comodo per scrivere 51 (sulle piattaforme dove si usa ASCII) o comunque il codice carattere corrispondente sulle altre piattaforme (per dire, su EBCDIC il '3' è 243).

Mi sa allora che non ho ben capito il tuo metodo... puoi spiegarmelo per favore in maniera più approfondita?
Cosa sono size_t e prefix? Perchè usi template( non sono molto esperto)? La funzione rfind su s che fa? Grazie mille

È che ho scritto la funzione in maniera un po' più generica, in modo che possa essere usata su qualunque mappa da stringa a qualche tipo di elemento, con prefissi di qualunque lunghezza.
size_t è un tipo intero senza segno che si usa normalmente per indicare numeri di elementi; di fatto su macchine a 32 bit puoi usare int senza remore.
prefix è il prefisso da cercare (nel tuo caso sarà "3"); la roba della rfind è sostanzialmente un modo convoluto ma compatto per vedere se una stringa inizia con un'altra.
Il template serve per fare in modo che la funzione possa operare per le mappe da stringhe a qualunque altro tipo.

In ogni caso, tolte tutte queste finezze si può semplicemente aggiustare il tuo codice per usare la lower_bound:

    int count=0;
    for(mapa::iterator it=m.lower_bound("3");
        it!=m.end() && it->first[0]=='3';
        ++it) {
        count++;
    }

[aleRomatre]

Grande! Grazie mille. Complimenti per la chiarezza dell'esposizione.