¿Hay una manera fácil de ordenar una serie de char * 's? C ++

Question

Tengo una matriz de char * en un archivo. La empresa para la que trabajo almacena datos en archivos planos. A veces los datos se ordenan, pero a veces no. Me gustaría ordenar los datos en los archivos.

Ahora podría escribir el código para hacer esto, desde cero. hay una manera mas facil?

Por supuesto, una ordenación in situ sería la mejor opción. Estoy trabajando en archivos grandes y tengo poca RAM. Pero consideraré todas las opciones.

Todas las cadenas tienen la misma longitud.

Estos son algunos datos de muestra:

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

Esto representaría tres registros de longitud 28. La aplicación conoce la longitud. Cada registro termina con CRLF ( \ r \ n ), aunque no debería importar para este 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

Utilice el programa de clasificación GNU (externamente) si no puede ajustar los datos en la RAM: clasificará archivos de tamaño arbitrario y cuanto mayor sea el archivo, menor será el costo adicional de crear el proceso.

Answer 3

Puede usar los algoritmos en STL en tipos de datos nativos de matrices, no solo en contenedores STL. Sin embargo, la otra sugerencia para usar std :: sort no funcionará como se publicó, porque strcmp devuelve un valor que se evalúa como verdadero para todas las comparaciones cuando las cadenas no son las mismas, no solo si el lado izquierdo es menor que el derecho lado de la mano, que es lo que quiere std :: sort; un predicado binario que devuelve verdadero del lado izquierdo es menor que el lado derecho.

Esto funciona:

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 puede hacerlo:

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

Editar : las cadenas no tienen terminación nula:

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

Probablemente la forma más fácil es usar la antigua función stdlib.h qsort. Esto debería funcionar:

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

Tenga en cuenta que este es el estándar C y solo funciona de manera confiable con texto en inglés.

Si tiene una lista de objetos String, entonces otras cosas son posibles en C ++.

Si está en Linux y escribe una aplicación gtk o Qt, le sugiero que eche un vistazo a estas bibliotecas de antemano.

Answer 6

Si los archivos son grandes y no caben en la RAM, puede usar bin / bucket ordenar para dividir los datos en archivos más pequeños y finalmente agregar las piezas en un archivo de resultados. Otras respuestas le muestran cómo ordenar cada archivo de depósito individual.

Answer 7

La forma canónica de ordenar una matriz de cadenas de caracteres en C, y por lo tanto una forma disponible pero no necesariamente recomendada de hacerlo en C ++, utiliza un nivel de indirección 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

Algunas cosas me vienen a la mente:

1. Si sus datos son demasiado grandes para caber en la memoria, es posible que desee crear un índice en la memoria de las compensaciones de los archivos, luego mapear la memoria del archivo para acceder a las cadenas (depende de su sistema operativo).
2. In-place requerirá un lote de copias de memoria. Si puede, use un tipo de shell. Luego, una vez que conozca el orden final, es mucho más fácil reordenar las cadenas en su lugar en tiempo lineal.
3. Si las cadenas son todas de la misma longitud, realmente quieres una clasificación de radix. Si no está familiarizado con una ordenación por radix, aquí está la idea básica: ordenación basada en la comparación (que es lo que std :: sort , qsort , y cualquier otro general- clasificación de propósito) siempre requiere tiempo O (N log N). La clasificación por radix compara un solo dígito a la vez (comenzando en str [0] y terminando en str [K-1] para una cadena K-lenth), y en general puede requiere solo O (N) tiempo para ejecutarse.

Consulte Internet para obtener una descripción mucho mejor detallada de los algoritmos de clasificación de radix que la que puedo proporcionar. Aparte de lo que he dicho, evitaría todas las otras soluciones que usan instalaciones de clasificación de biblioteca estándar. Simplemente no están diseñados para su problema particular, desafortunadamente.

Answer 9

Probablemente desee examinar los archivos mapeados en memoria (consulte http: //en.wikipedia. org / wiki / Memory-mapped_file ), función mmap () ( http: // es. wikipedia.org/wiki/Mmap ) en sistemas operativos de reclamos POSIX. Básicamente, obtendrá un puntero a la memoria contigua que representa el contenido del archivo.

El lado bueno es que el sistema operativo se encargará de cargar partes del archivo en la memoria y descargarlas nuevamente, según sea necesario.

Una desventaja es que deberá resolver alguna forma de bloqueo de archivos para evitar daños si es probable que más de un proceso acceda al archivo.

Otra desventaja es que esto no garantiza un buen rendimiento: para ello, necesitará un algoritmo de clasificación que intente evitar cargar y descargar páginas constantemente (a menos que, por supuesto, tenga suficiente memoria para cargar todo el archivo en la memoria ).

¡Espero que esto te haya dado algunas ideas!