[C++] Sort utilizzando strutture

[kirakira93]

Salve ragazzi, sto studiando il sort con le strutture, in particolare non capisco questo esempio:

// ***

bool compare_intervalli(const Intervallo &a, const Intervallo &b)
{
if (a.fine < b.fine)
    return true;
else
    return false;
}


// ***

Intervallo giri[1000];
sort(giri,giri+N,compare_intervalli);

// ***

non riesco a capire perchè come secondo paramentro viene passato giri + N, giri + N identifica un'area di memoria che non corrisponde all'ultimo elemento dell'array, non sarebbe più sensato scrivere giri + N*sizeof(Intervallo) ?

Grazie in anticipo!

[ramy89]

Forse voleva ordinare solo una porzione dell' array, posta tutto il codice che vediamo meglio.

[kirakira93]

Ho provato, in effetti il codice ordina correttamente tutti gli elementi, quindi non so se serve postarlo, eccolo cmq per curiosità, l'ho riscritto:

#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

int N;

typedef struct struttura
    {
    int inizio;
    int fine;  
    };
    
struttura giri [1000];

bool cmp (const struttura & a, const struttura & b)
{
if (a.fine < b.fine)
    return true;
else 
    return false;
}

int main(int argc, char *argv[])
{
    ifstream in("input.txt");
    in >> N;
    for(int i = 0; i < N; i++)
        { 
        in >> giri[i].inizio >> giri[i].fine;
        }
    in.close();
    ///////////////////////////////
    
    sort(giri, giri + N, cmp);
    
    int fine_corr = giri[0].fine;
    int caramelle = 1;
    
    for(int i = 1; i < N; i++)
        {
        if(fine_corr < giri[i].inizio)
            {
            caramelle++;
            fine_corr = giri[i].fine;
            }    
        }
    ///////////////////////////////
    ofstream out("output.txt");
    
    out << caramelle;
    
    out.close();
    return EXIT_SUCCESS;
}

il codice serve per risolvere (correttamente) il problema:

Olimpiadi di Informatica - Selezione Regionale 2007
problema Giri sulla Scopa Nimbus3000 (NIMBUS)

ma poco conta ai fini del mio problema

[shodan]

Originariamente inviato da kirakira93
il codice serve per risolvere (correttamente) il problema:

Mmm, ci sono 1001 bug

[MItaly]

In ogni caso, N è il numero di elementi effettivamente impiegati nell'array, per cui è corretto limitare l'ordinamento ai soli primi N elementi.

[kirakira93]

Grazie..solo che mi sembrava più logico inserire direttamente il numero degli elementi.

@Shodan...perchè dici che il codice è pieno di bug?? è perfetto

[shodan]

Non ho scritto che è pieno di bug, ma che ci sono 1001 bug.
Il che si riferisce al fatto che dai per scontato che un ipotetico utente inserisca meno di 1000 in questa istruzione:

in >> N;

per poi effettuare un ciclo e un ordinamento usando quel numero, su un array di massimo 1000 elementi.

struttura giri [1000];

Se il tuo utente inserisce 1001 ( o al limite proprio 1000) il programma va in crash.
Dovresti inserire un controllo sul numero massimo che si può inserire.

[kirakira93]

Tutto controllato
Nei testi dei giochi accertano che l'input è compreso tra determinati valori, questo perchè a seconda dei diversi possibili input è meglio adottare strategie diverse.

Ad esempio se gli input fossero stati minori di 20, convenivaa usare la ricorsione che è più semplice da implementare.

Bisogna stare solo attenti nei casi limite ma in questo caso se non sbaglio 1000 non era tra i possibili input e 999 funziona alla grande!

[ramy89]

Ma N lo legge dal file ...