C'è un modo semplice per ordinare un array di caratteri *? C ++

Question

Ho un array di char * in un file. L'azienda per cui lavoro archivia i dati in file flat .. A volte i dati vengono ordinati, ma a volte no. Vorrei ordinare i dati nei file.

Ora potrei scrivere il codice per farlo, da zero. C'è un modo più semplice?

Naturalmente un ordinamento sul posto sarebbe l'opzione migliore. Sto lavorando su file di grandi dimensioni e ho poca RAM. Ma prenderò in considerazione tutte le opzioni.

Tutte le stringhe hanno la stessa lunghezza.

Questi sono alcuni dati di esempio:

the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt

Ciò rappresenterebbe tre record di lunghezza 28. L'app conosce la lunghezza. Ogni record termina con CRLF ( \ r \ n ), anche se non dovrebbe importare per questo tipo.

Answer 1

template<size_t length> int less(const char* left, const char* right) {
    return memcmp(left, right, length) < 0;
}

std::sort(array, array + array_length, less<buffer_length>);

Answer 2

Usa il programma di ordinamento GNU (esternamente) se non riesci ad adattare i dati alla RAM: ordina i file di dimensioni arbitrarie e più grande è il file, minore è il costo aggiuntivo di creazione del processo.

Answer 3

È possibile utilizzare gli algoritmi in STL su tipi di dati nativi di array, non solo su contenitori STL. L'altro suggerimento di usare std :: sort non funzionerà come pubblicato, perché strcmp restituisce un valore che risulta vero per tutti i confronti quando le stringhe non sono uguali, non solo se il lato sinistro è inferiore a quello destro lato della mano - che è ciò che vuole std :: sort; un predicato binario che ritorna vero sul lato sinistro è inferiore al lato destro.

Funziona:

struct string_lt : public std::binary_function<bool, char, char>
{
    bool operator()(const char* lhs, const char* rhs)
    {
        int ret = strcmp(lhs, rhs);
        return ret < 0;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    char* strings [] = {"Hello", "World", "Alpha", "Beta", "Omega"};
    size_t numStrings = sizeof(strings)/sizeof(strings[0]);

    std::sort(&strings[0], &strings[numStrings], string_lt());

    return 0;
}

Answer 4

boost :: bind può farlo:

// ascending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) < 0); 

// descending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) > 0); 

Modifica : le stringhe non sono nulle:

// ascending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) < 0); 

// descending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) > 0); 

Answer 5

Probabilmente il modo più semplice è usare la vecchia funzione stdlib.h qsort. Questo dovrebbe funzionare:

qsort( array, num_elements, sizeof( char* ), strcmp )

Nota: questo è lo standard C e funziona in modo affidabile solo con il testo inglese.

Se hai un elenco di oggetti String, allora altre cose sono possibili in C ++.

Se sei su Linux e stai scrivendo un'applicazione gtk o Qt, ti suggerirei di dare un'occhiata a queste librerie in anticipo.

Answer 6

Se i file sono di grandi dimensioni e non si adattano alla RAM, è possibile utilizzare bin / bucket ordina per dividere i dati in file più piccoli e infine aggregare i pezzi in un file di risultati. Altre risposte mostrano come ordinare ogni singolo file bucket.

Answer 7

Il modo canonico di ordinare una matrice di stringhe di caratteri in C, e quindi un modo disponibile ma non necessariamente raccomandato per farlo in C ++, utilizza un livello di riferimento indiretto a strcmp () :

static int qsort_strcmp(const void *v1, const void *v2)
{
    const char *s1 = *(char * const *)v1;
    const char *s2 = *(char * const *)v2;
    return(strcmp(s1, s2));
}

static void somefunc(void)   // Or omit the parameter altogether in C++
{
    char **array = ...assignment...
    size_t num_in_array = ...number of char pointers in array...
    ...
    qsort(array, num_in_array, sizeof(char *), qsort_strcmp);
    ...more code...
}

Answer 8

Alcune cose vengono in mente:

1. Se i tuoi dati sono troppo grandi per adattarsi alla memoria, potresti voler semplicemente creare un indice in memoria degli offset dei file, quindi mappare la memoria del file per accedere alle stringhe (dipende dal tuo sistema operativo).
2. Sul posto richiederà un lotto di copie di memoria. Se puoi, usa un ordinamento di shell. Quindi, una volta che conosci l'ordine finale, è molto più facile riordinare le stringhe sul posto in tempo lineare.
3. Se le stringhe hanno tutte la stessa lunghezza, davvero si desidera un ordinamento radix. Se non hai familiarità con un ordinamento radix, ecco l'idea di base: ordinamento basato sul confronto (che è ciò che std :: sort , qsort e qualsiasi altro generale- ordinamento) richiede sempre il tempo O (N log N). L'ordinamento Radix confronta una singola cifra alla volta (a partire da str [0] e termina a str [K-1] per una stringa K-lenth), e nel complesso può richiede solo O (N) tempo per l'esecuzione.

Consulta Internet per una descrizione molto migliore e dettagliata degli algoritmi di ordinamento Radix di quanto io possa fornire. A parte quello che ho detto, eviterei tutte le altre soluzioni che utilizzano le strutture standard di ordinamento libarario. Purtroppo non sono stati progettati per il tuo problema particolare.

Answer 9

Probabilmente vuoi esaminare i file mappati in memoria (vedi http: //en.wikipedia. org / wiki / Memory-mapped_file ), funzione mmap () ( http: // it. wikipedia.org/wiki/Mmap ) su sistemi operativi con reclamo POSIX. In pratica otterrai un puntatore alla memoria contigua che rappresenta il contenuto del file.

Il lato positivo è che il sistema operativo si occuperà di caricare parti del file in memoria e scaricarle di nuovo, se necessario.

Un aspetto negativo è che dovrai risolvere una qualche forma di blocco dei file per evitare la corruzione se è probabile che più di un processo acceda al file.

Un altro aspetto negativo è che ciò non garantisce buone prestazioni: per farlo, avrai bisogno di un algoritmo di ordinamento che tenti di evitare il caricamento e lo scaricamento costante delle pagine (a meno che, ovviamente, non si disponga di memoria sufficiente per caricare l'intero file in memoria ).

Spero che questo ti abbia dato alcune idee!