Existe uma maneira fácil de classificar uma matriz de char * 's? C ++

Question

Eu tenho uma série de char* em um arquivo. A empresa que eu trabalho para armazena dados em arquivos simples .. Às vezes, os dados são classificados, mas às vezes não é. Eu gostaria de classificar os dados em arquivos.

Agora eu poderia escrever o código para fazer isso, a partir do zero. Existe uma maneira mais fácil?

É claro que um tipo no local seria a melhor opção. Eu estou trabalhando em arquivos grandes e têm pouca RAM. Mas eu vou considerar todas as opções.

Todas as strings têm o mesmo comprimento.

Este é alguns dados de exemplo:

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

Isso representaria três registros de comprimento 28. O aplicativo sabe o comprimento. Cada extremidades recordes com CRLF (\r\n), embora não deveria 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

Use o programa espécie GNU (externamente), se você não pode caber os dados em RAM:. It arquivos de tamanho vai tipo arbitrárias e quanto maior o arquivo, menor o custo adicional de criar o processo

Answer 3

Você pode usar os algoritmos da STL em matrizes tipos de dados nativos, não apenas em contêineres STL. A outra sugestão para uso std :: sort não funcionará como postado no entanto, porque os retornos STRCMP um valor que avalia a verdade para todas as comparações quando as cordas não são as mesmas, não apenas se o lado esquerdo é menos do que a direita lado - que é o que std :: sort quer; um predicado binário retornando true do lado esquerdo é menor do que o lado direito.

Isso 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 pode fazê-lo:

// 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 : As cordas não são terminada em nulo:

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

Provavelmente a maneira mais fácil é usado o velho função stdlib.h qsort. Isso deve funcionar:

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

Por favor note que este é padrão C e só funciona de confiança com texto em Inglês.

Se você tem uma lista de objetos String, em seguida, outras coisas são possíveis em C ++.

Se você estiver em Linux e escrever um gtk ou aplicação Qt, em seguida, gostaria de propor que você ter um olhar para essas bibliotecas de antemão.

Answer 6

Se os arquivos são grandes e não se encaixam na RAM, você pode usar bin / balde tipo de dividir os dados em arquivos menores e, finalmente, agregar as peças em um arquivo de resultado. Outras respostas mostrar-lhe como classificar cada arquivo balde individual.

Answer 7

A forma canônica para classificar uma matriz de seqüências de caracteres em C, e, portanto, uma forma disponível, mas não necessariamente recomendado fazê-lo em C ++, usa um nível de engano para 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

Algumas coisas vêm à mente:

1. Se os seus dados é muito grande para caber na memória, você pode querer apenas construir um índice na memória de deslocamentos de arquivo, em seguida, a memória de mapear o arquivo para acesso as cordas (depende do seu sistema operacional).
2. Em lugar vai exigir um muito de cópias de memória. Se você puder, use uma espécie shell. Então uma vez que você sabe a ordem final, é muito mais fácil para reordenar as cordas no local em tempo linear.
3. Se as cordas são todas do mesmo tamanho, você realmente quer uma espécie radix. Se você não estiver familiarizado com uma espécie Radix, aqui é a idéia básica: Comparação baseada em classificação (que é o que std::sort, qsort, e qualquer outro de propósito geral de classificação) sempre requer O (N log N) tempo. Radix ordenação compara um único dígito de cada vez (a partir de str[0] e terminando no str[K-1] por uma série K-lenth) e, em geral pode exigir só o tempo O (N) para executar.

Consulte o Internetfor uma descrição muito melhor detalhado de radix algoritmos de ordenação do que eu posso fornecer. Além de que eu disse, gostaria de evitar todas as outras soluções que utilizam instalações de classificação libarary padrão. Eles simplesmente não são projetados seu problema particular, infelizmente.

Answer 9

Você provavelmente vai querer olhar para arquivos de memória mapeada (ver http: //en.wikipedia. função org / wiki / Memória-mapped_file ), mmap () ( http: // en. wikipedia.org/wiki/Mmap ) em sistemas operacionais POSIX-queixa. Você essencialmente vai ter um ponteiro para a memória contígua que representa o conteúdo do arquivo.

O lado bom é que o OS vai cuidar de partes de carregamento do arquivo para a memória e descarregá-los novamente, se necessário.

Uma desvantagem é que você precisa para resolver a alguma forma de bloqueio de arquivos para corrupção evitar se mais de um processo é provável que o acesso ao arquivo.

Outra desvantagem é que isso não garante um bom desempenho - para fazer isso, você precisará de um algoritmo de ordenação que tenta evitar constantemente carga e descarga páginas (a menos que você tem memória suficiente para carregar o arquivo inteiro na memória ).

Espero que este deu-lhe algumas ideias!