Cadena de clasificación C++ como un ser humano?

Question

Me gustaría ordenar las cadenas alfanuméricas de la forma en que un ser humano las clasificaría. Es decir, "A2" viene antes que "A10", y "a" ciertamente viene antes de "Z"! ¿Hay alguna forma de hacerlo sin escribir un mini-analizador? Idealmente, también pondría "A1B1" antes de "A1B10". Veo la pregunta "Natural (human alpha-numeric) sort in Microsoft SQL 2005" con una posible respuesta, pero usa varias funciones de la biblioteca, al igual que "Sorting Strings for Humans with IComparer".

A continuación se muestra un caso de prueba que en la actualidad no:

#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

¿Hay alguna forma de hacerlo sin escribir un mini-analizador?

¿Alguien más puede hacer eso?

Estoy usando esta implementación: http://www.davekoelle.com/alphanum.html, la he modificado para que sea compatible con wchar_t, también.

Answer 2

¿Hay alguna manera de hacerlo sin tener que escribir un mini analizador? Yo pensaría que la respuesta es no. Pero escribir un analizador no es tan difícil. Tuve que hacer esto hace un tiempo para ordenar los números de inventario de nuestra compañía. Básicamente solo escanee el número y conviértalo en una matriz. Compruebe el "tipo" de cada personaje: alfa, número, tal vez usted tiene otros con los que debe tratar especial. Como si tuviera que tratar guiones especiales porque quería que A-B-C ordene antes que AB-A. Luego comienza a quitar los personajes. Siempre que sean del mismo tipo que el primer personaje, entran en el mismo cubo. Una vez que el tipo cambia, empiezas a ponerlos en un cubo diferente. Entonces también necesita una función de comparación que compare cubeta por cubeta. Cuando ambos cubos son alfa, simplemente haces una comparación alfa normal. Cuando ambos son dígitos, conviértalos en enteros y haz una comparación de enteros, o rellena el más corto con la longitud de la más larga o algo equivalente. Cuando son tipos diferentes, necesitarás una regla sobre cómo se comparan, al igual que A-A antes o después de A-1.

No es un trabajo trivial y tienes que idear reglas para todos los casos extraños que puedan surgir, pero creo que podrías conseguirlo en unas pocas horas de trabajo.

Answer 3

Sin ningún tipo de análisis, no hay forma de comparar números escritos humanos (valores altos primero con ceros iniciales despojados) y caracteres normales como parte de la misma cadena.

Sin embargo, el análisis no tiene que ser terriblemente complejo. Una tabla de hash simple para manejar cosas como sensibilidad de mayúsculas y minúsculas y caracteres especiales ('A' = 'a' = 1, 'B' = 'b' = '2, ... o' A '= 1,' a ' = 2, 'B' = 3, ..., '-' = 0 (franja)), reasigne su cadena a una matriz de valores hash, luego trunque casos numéricos (si se encuentra un número y el último carácter fue un número, multiplicar el último número por diez y agregarle el valor actual).

A partir de ahí, ordena de forma normal.

Answer 4

Realmente depende de lo que quiere decir con "analizador". Si quiere evitar escribir un analizador, creo que debería aprovechar las funciones de la biblioteca.

• Trate la cadena como una secuencia de subsecuencias que son uniformemente alfabéticas, numéricas u "otras".
• Obtenga la siguiente secuencia alfanumérica de cada cadena usando isalnum y retrocede la verificación para + o - si es un número. Use strtold en contexto para encontrar el final de una subsecuencia numérica.
• Si uno es numérico y uno es alfabético, la cadena con la subsecuencia numérica es lo primero.
• Si una cadena se ha quedado sin caracteres, es lo primero.
• Utilice strcoll para comparar las subsecuencias alfabéticas dentro de la configuración regional actual.
• Use strtold para comparar subsecuencias numéricas dentro de la configuración regional actual.
• Repita hasta que termine con una o ambas cadenas.
• Romper lazos con strcmp.

Este algoritmo tiene una debilidad en la comparación de cadenas numéricas que exceden la precisión de long double.