Existe-t-il un moyen facile de trier un tableau de char *? C ++

Question

J'ai un tableau de char * dans un fichier. La société pour laquelle je travaille stocke les données dans des fichiers plats. Parfois, les données sont triées, mais parfois non. J'aimerais trier les données dans les fichiers.

Maintenant, je pourrais écrire le code pour le faire, à partir de zéro. Y a-t-il un moyen plus facile?

Bien sûr, un tri sur place serait la meilleure option. Je travaille sur de gros fichiers et dispose de peu de RAM. Mais je considérerai toutes les options.

Toutes les chaînes ont la même longueur.

Voici quelques exemples de données:

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

Cela représenterait trois enregistrements de longueur 28. L'application connaît la longueur. Chaque enregistrement se termine par CRLF ( \ r \ n ), bien que cela ne devrait pas avoir d’importance.

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

Utilisez le programme de tri GNU (en externe) si vous ne pouvez pas adapter les données à la RAM: il triera les fichiers de taille arbitraire. Plus le fichier est volumineux, plus le coût supplémentaire de création du processus sera réduit.

Answer 3

Vous pouvez utiliser les algorithmes de la STL sur les types de données natifs des matrices, pas seulement sur les conteneurs de la STL. L’autre suggestion d’utiliser std :: sort ne fonctionnera pas comme elle a été signalée, car strcmp renvoie une valeur qui vaut true pour toutes les comparaisons lorsque les chaînes ne sont pas identiques, et pas seulement si le côté gauche est inférieur au côté droit. side - ce que std :: sort veut; un prédicat binaire retournant vrai du côté gauche est inférieur au côté droit.

Ceci fonctionne:

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 peut le faire:

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

Modifier : les chaînes ne sont pas terminées par un caractère null:

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

Le moyen le plus simple consiste probablement à utiliser l'ancienne fonction qsort de stdlib.h. Cela devrait fonctionner:

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

Notez que ceci est la norme C et fonctionne uniquement avec le texte anglais.

Si vous avez une liste d'objets String, d'autres choses sont possibles en C ++.

Si vous êtes sous Linux et que vous écrivez une application gtk ou Qt, je vous suggère de jeter un coup d'œil à ces bibliothèques auparavant.

Answer 6

Si les fichiers sont volumineux et ne tiennent pas dans la RAM, vous pouvez utiliser bin / bucket trier pour diviser les données en fichiers plus petits et enfin agréger les éléments dans un fichier de résultat. D’autres réponses vous expliquent comment trier chaque fichier de compartiment.

Answer 7

Le moyen canonique de trier un tableau de chaînes de caractères en C, et donc un moyen disponible mais pas nécessairement recommandé de le faire en C ++, utilise un niveau d'indirection vers 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

Quelques points me viennent à l’esprit:

1. Si vos données sont trop volumineuses pour tenir en mémoire, vous pouvez simplement créer un index en mémoire des décalages de fichier, puis mapper en mémoire le fichier pour accéder aux chaînes (dépend de votre système d'exploitation).
2. Sur place, il faudra un lot de copies en mémoire. Si vous le pouvez, utilisez une sorte de shell. Ensuite, une fois que vous connaissez la commande finale, il est beaucoup plus facile de réorganiser les chaînes sur place en temps linéaire.
3. Si les chaînes ont toutes la même longueur, vous voulez vraiment un tri de base. Si vous n'êtes pas familier avec un tri de base, voici l'idée de base: le tri basé sur la comparaison (qui est ce que std :: sort , qsort et tout autre type général- le tri des fins) nécessite toujours un temps O (N log N). Le tri de base compare un chiffre à la fois (commençant à str [0] et se terminant à str [K-1] pour une chaîne K-lenth), et peut globalement nécessite seulement un temps d'exécution (N).

Consultez Internet pour une description bien plus détaillée des algorithmes de tri de bases que celle que je peux fournir. Outre ce que j'ai dit, j'éviterais toutes les autres solutions qui utilisent des installations de tri de bibliothèque standard. Malheureusement, ils ne sont pas conçus pour votre problème particulier.

Answer 9

Vous voudrez probablement rechercher dans les fichiers mappés en mémoire (voir http: //en.wikipedia. org / wiki / Memory-mapped_file ), fonction mmap () ( http: // en. wikipedia.org/wiki/Mmap ) sur les systèmes d’exploitation POSIX. Vous obtiendrez essentiellement un pointeur sur la mémoire contiguë représentant le contenu du fichier.

L’avantage, c’est que le système d’exploitation se chargera de charger en mémoire des parties du fichier et de les décharger à nouveau, si nécessaire.

Un inconvénient est que vous devrez résoudre le problème du verrouillage de fichier pour éviter toute corruption si plusieurs processus sont susceptibles d'accéder au fichier.

Un autre inconvénient est que cela ne garantit pas de bonnes performances. Pour ce faire, vous aurez besoin d'un algorithme de tri qui évite le chargement et le déchargement constants des pages (à moins que vous ne disposiez naturellement de suffisamment de mémoire pour charger l'intégralité du fichier en mémoire. ).

J'espère que cela vous a donné quelques idées!