La stringa C++ si presenta come un essere umano?

Question

Vorrei ordinare stringhe alfanumeriche nel modo in cui un essere umano le ordina. Ad esempio, "A2" viene prima di "A10", e "a" viene sicuramente prima di "Z"! C'è un modo per fare senza scrivere un mini parser? Idealmente avrebbe anche messo "A1B1" prima di "A1B10". Vedo la domanda "Natural (human alpha-numeric) sort in Microsoft SQL 2005" con una possibile risposta, ma utilizza varie funzioni di libreria, come fa "Sorting Strings for Humans with IComparer".

seguito è un banco di prova che attualmente non riesce:

#include <set> 
#include <iterator> 
#include <iostream> 
#include <vector> 
#include <cassert> 

template <typename T> 
struct LexicographicSort { 
    inline bool operator() (const T& lhs, const T& rhs) const{ 
    std::ostringstream s1,s2; 
    s1 << toLower(lhs); s2 << toLower(rhs); 
    bool less = s1.str() < s2.str(); 
    //Answer: bool less = doj::alphanum_less<std::string>()(s1.str(), s2.str()); 
    std::cout<<s1.str()<<" "<<s2.str()<<" "<<less<<"\n"; 
    return less; 
    } 

    inline std::string toLower(const std::string& str) const { 
    std::string newString(""); 
    for (std::string::const_iterator charIt = str.begin(); 
     charIt!=str.end();++charIt) { 
      newString.push_back(std::tolower(*charIt)); 
     } 
     return newString; 
     } 
}; 


int main(void) { 
    const std::string reference[5] = {"ab","B","c1","c2","c10"}; 
    std::vector<std::string> referenceStrings(&(reference[0]), &(reference[5])); 

    //Insert in reverse order so we know they get sorted 
    std::set<std::string,LexicographicSort<std::string> > strings(referenceStrings.rbegin(), referenceStrings.rend()); 

    std::cout<<"Items:\n"; 
    std::copy(strings.begin(), strings.end(), std::ostream_iterator<std::string>(std::cout, "\n")); 
    std::vector<std::string> sortedStrings(strings.begin(), strings.end()); 
    assert(sortedStrings == referenceStrings); 
} 

Answer 1

C'è un modo per fare senza scrivere un mini parser?

Lascia che sia qualcun altro a farlo?

Sto usando questa implementazione: http://www.davekoelle.com/alphanum.html, l'ho modificato anche per supportare wchar_t.

Answer 2

Esiste un modo per farlo senza scrivere una mini parser? Penserei che la risposta sia no. Ma scrivere un parser non è così difficile. Ho dovuto farlo un po 'di tempo fa per ordinare i numeri di borsa della nostra azienda. Fondamentalmente basta scansionare il numero e trasformarlo in un array. Controlla il "tipo" di ogni personaggio: alfa, numero, forse hai altri di cui hai bisogno per occuparti di speciali. Come se dovessi trattare i trattini speciali perché volevamo che A-B-C fosse ordinato prima di AB-A. Quindi inizia a staccare i caratteri. Finché sono dello stesso tipo del primo personaggio, entrano nello stesso secchio. Una volta che il tipo cambia, si inizia a metterli in un secchio diverso. Quindi è necessaria anche una funzione di confronto che paragona bucket-by-bucket. Quando entrambi i bucket sono alfa, basta fare un confronto alfa normale. Quando entrambe sono cifre, converti entrambe in numeri interi e fai un confronto tra interi, o tampona il più corto alla lunghezza del più lungo o qualcosa di equivalente. Quando sono di tipo diverso, avrete bisogno di una regola per il confronto, come fa A-A prima o dopo A-1?

Non è un lavoro banale e devi trovare le regole per tutti i casi strani che possono sorgere, ma penserei che potresti metterlo insieme in poche ore di lavoro.

Answer 3

Senza alcuna analisi, non c'è modo di confrontare i numeri scritti umani (valori alti prima con gli zero iniziali rimossi) e i caratteri normali come parte della stessa stringa.

L'analisi non deve necessariamente essere terribilmente complessa. Una semplice tabella hash per gestire elementi come la distinzione tra maiuscole e minuscole e la rimozione di caratteri speciali ('A' = 'a' = 1, 'B' = 'b' = '2, ... o' A '= 1,' a ' = 2, 'B' = 3, ..., '-' = 0 (strip)), rimappare la stringa su una matrice dei valori hash, quindi troncare i casi numerici (se si incontra un numero e l'ultimo carattere era un numero, moltiplicare l'ultimo numero per dieci e aggiungere il valore corrente ad esso).

Da lì, ordinare come normale.

Answer 4

Dipende davvero da cosa intendi per "parser". Se vuoi evitare di scrivere un parser, penso che dovresti avvalerti delle funzioni di libreria.

• Tratta la stringa come una sequenza di sottosequenze che sono uniformemente alfabetiche, numeriche o "altro".
• Ottieni la sequenza alfanumerica successiva di ogni stringa utilizzando isalnum e il controllo di backtrack per + o - se è un numero. Utilizzare strtold sul posto per trovare la fine di una sottosequenza numerica.
• Se uno è numerico e uno è alfabetico, viene prima la stringa con la sottosequenza numerica.
• Se una stringa ha esaurito i caratteri, viene prima.
• Utilizzare strcoll per confrontare sottosequenze alfabetiche all'interno delle impostazioni internazionali correnti.
• Utilizzare strtold per confrontare sottosequenze numeriche all'interno delle impostazioni internazionali correnti.
• Ripeti fino al termine con una o entrambe le stringhe.
• Rompere i legami con strcmp.

Questo algoritmo ha una certa debolezza nel confrontare stringhe numeriche che superano la precisione di long double.