Gibt es eine einfache Möglichkeit, ein Array von char * 's zu sortieren? C ++

Question

Ich habe eine Reihe von char* in einer Datei einsehen. Die Firma, die ich für speichert Daten in flachen Dateien arbeiten .. Manchmal werden die Daten sortiert, aber es ist manchmal nicht. Ich möchte die Daten in den Dateien sortieren.

Jetzt konnte ich den Code schreiben, dies zu tun, von Grund auf neu. Gibt es einen einfacheren Weg?

Natürlich ein direktes Art wäre die beste Option sein. Ich arbeite an großen Dateien und haben wenig RAM. Aber ich werde alle Möglichkeiten in Betracht ziehen.

Alle Saiten sind gleich lang.

Dies ist einige Beispieldaten:

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

Dies würde drei Aufzeichnungen Länge 28. Die App kennt die Länge. Jeder Datensatz endet mit CRLF (\r\n), obwohl es nicht für diese Art sollte Angelegenheit.

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

Mit dem GNU Sortierprogramm (extern), wenn Sie nicht die Daten in dem Arbeitsspeicher passen. Es wird Art beliebig große Dateien und je größer die Datei, desto kleiner ist die zusätzlichen Kosten für den Prozess der Erstellung

Answer 3

Sie können die Algorithmen in der STL auf Arrays nativen Datentypen verwenden, nicht nur auf STL-Containern. Der andere Vorschlag std verwenden :: sort wird jedoch nicht als gebucht arbeiten, weil strcmp einen Wert zurückgibt, die für alle Vergleiche zu true ausgewertet, wenn die Saiten nicht gleich sind, nicht nur, wenn die linke Seite ist kleiner als die rechte Seite - das ist, was std :: sort will; ein binäres Prädikat gilt für die linke Seite zurückkehrt geringer ist als die die rechte Seite.

Das funktioniert:

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 kann es tun:

// 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); 

Bearbeiten : Die Saiten sind nicht nullterminierten:

// 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

Wahrscheinlich ist der einfachste Weg, um die alte stdlib.h Funktion qsort verwendet. Dies sollte funktionieren:

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

Bitte beachten Sie, dass dies ist Standard C und funktioniert nur zuverlässig mit englischem Text.

Wenn Sie eine Liste von String-Objekten haben, dann sind andere Dinge möglich in C ++.

Wenn Sie auf Linux sind und ein gtk oder Qt-Anwendung zu schreiben, dann würde ich vorschlagen, dass Sie einen Blick auf diesen Bibliotheken haben vorher.

Answer 6

Wenn die Dateien groß sind und passen nicht in RAM, können Sie ist / Eimer Art der Daten in kleinere Dateien aufteilen und aggregieren schließlich die Stücke in einer Ergebnisdatei. Andere Antworten zeigen Ihnen, wie jede einzelne Schaufel Datei sortieren.

Answer 7

Die kanonische Weise eine Reihe von Zeichenketten in C zu sortieren, und daher eine zur Verfügung, aber nicht unbedingt Weise empfohlen so in C ++ zu tun, verwendet einen Dereferenzierungsebene 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

Ein paar Dinge in den Sinn kommen:

1. Wenn Ihre Daten zu groß sind, in dem Speicher zu passen, die Sie gerade mögen vielleicht einen Index im Speicher von Dateioffsets aufbauen, dann Speicher-Mapping die Datei mit den Strings zugreifen (abhängig von Ihrem O).
2. In-Ort wird ein Los von Speicherkopien verlangen. Wenn Sie können, eine Shell-Art verwenden. Dann, wenn Sie den letzten Auftrag, es ist viel einfacher, die Saiten an Ort und Stelle in linearer Zeit neu anordnen.
3. Wenn die Saiten alle die gleiche Länge haben, Sie wirklich eine Radixsort wollen. Wenn Sie nicht vertraut mit einer Radixsort sind, ist hier die Grundidee: Vergleich basierte Sortierung (was std::sort, qsort, und andere allgemeine Zwecke Sortierung) immer O erfordert (N log N) Zeit. Radix Sortieranlage zu einem Zeitpunkt eine einzelne Ziffer vergleicht (ab str[0] und endend bei str[K-1] für einen K-lenth string), und kann insgesamt nur OS (N) Zeit zur Ausführung erfordern.

finden Sie in der Internetfor eine viel bessere detaillierte Beschreibung von Radix Sortieralgorithmen, als ich zur Verfügung stellen kann. Abgesehen von dem, was ich gesagt habe, würde ich alle anderen Lösungen vermeiden, den Standard libarary Sortieranlagen verwenden. Sie sind einfach nicht Ihr Problem entworfen, leider.

Answer 9

Sie wollen wahrscheinlich in den Speicher sehen Mapped-Dateien (siehe http: //en.wikipedia. org / wiki / Memory-mapped_file ), mmap () Funktion ( http: // en. wikipedia.org/wiki/Mmap ) auf POSIX-Beschwerde OSes. Sie werden im Wesentlichen einen Zeiger auf zusammenhängenden Speicher erhalten den Inhalt der Datei darstellt.

Die gute Seite ist, dass die OS Pflege Laden Teile der Datei in den Speicher übernehmen und sie wieder entladen, je nach Bedarf.

Ein Nachteil ist, dass Sie in irgendeine Form von Dateibeschädigung zu vermeiden Sperren müssen lösen, wenn mehr als ein Prozess die Datei wahrscheinlich zuzugreifen ist.

Ein weiterer Nachteil ist, dass dies nicht eine gute Leistung garantiert - das zu tun, werden Sie einen Sortieralgorithmus benötigen, die ständig Be- und Entladen von Seiten zu vermeiden versucht (außer natürlich, Sie genügend Speicher haben die gesamte Datei in den Speicher zu laden ).

Hope hat dies Ihnen einige Ideen gegeben!