Método de ordenamento: Qual usar? std::sort ou for aninhado? [RESOLVIDO]

paulo1205
(usa Ubuntu)

Enviado em 10/02/2016 - 13:55h

Seria interessante saber um pouco mais sobre a forma desses vetores de linhas. É um std::vector<std::vector<int>>, std::vector<std::array<int, 5>> ou um int(*)[5], ou alguma outra coisa?

De todo modo, ordenar as colunas de cada linha com std::sort() deveria funcionar com as alternativas que eu perguntei sem que você precise criar código.

#include <algorithm>

#include <array>

#include <vector>



using namespace std;



void f(){

  const size_t rows=5000, cols=5;

  vector<vector<int>> vv_mat(rows, vector<int>(cols));

  vector<array<int, cols>> va_mat(rows);

  array<array<int, cols>, rows> aa_mat;

  int native_aa_mat[rows][cols];

  int (*pa_mat)[cols]=new int[rows][cols];

  int **pp_mat=new int *[rows];

    for(size_t r=0; r<rows; r++) pp_mat[r]=new int[cols];



  /* ... */



  // Ordena a milésima linha de cada um dos tipos de matriz declarados acima

  sort(vv_mat[999].begin(), vv_mat[999].end());

  sort(va_mat[999].begin(), va_mat[999].end());

  sort(aa_mat[999].begin(), aa_mat[999].end());

  sort(native_aa_mat[999], native_aa_mat[999]+cols);

    // também conhecido como “sort(&native_aa_mat[999][0], &native_aa_mat[999][cols])”, ou ainda

    // “sort(native_aa_mat[999], native_aa_mat[999]+(sizeof *native_aa_mat/sizeof **native_aa_mat))”.

  sort(pa_mat[999], pa_mat[999]+cols);

  sort(pp_mat[999], pp_mat[999]+cols);



  /* ... */



  // Antes do fim da função, não se pode esquecer de desalocar quem precisa de desalocação.

  for(size_t r=0; i<rows; r++)

    delete[] pp_mat[r];

  delete[] pp_mat;

  delete[] pa_mat;

} 

Se, contudo, o problema for ordenar as linhas da matriz, então você não poderá usar std::sort() diretamente sobre todos os tipos de dados acima, pois arrays nativos só podem ser destino da operação de atribuição no momento em que são declarados. Isso implica que std::sort() não pode ser usada para ordenar as linhas native_aa_mat e pa_mat. Já para as demais, você pode usar lambdas, funções ou objetos-função (functors), junto com a versão de std::sort() que recebe três argumentos.

// Comparador a primeira coluna, versão função.

// (Fiz como template para poder aplicar a qualquer dos tipos

// de matriz cujas linhas possam ser ordenadas.)

template <class linetype> bool cmp_1_col(const linetype &l1, const linetype &l2){

  return l1[0]<l2[0];

}



// Comparador da primeira coluna, versão functor.

struct cmp_1_col_t {

  template <class linetype> bool operator()(const linetype &l1, const linetype &l2){

    return l1[0]<l2[0];

  }

};



void f(){

  const size_t rows=5000, cols=5;

  vector<vector<int>> vv_mat(rows, vector<int>(cols));

  vector<array<int, cols>> va_mat(rows);

  array<array<int, cols>, rows> aa_mat;

  int **pp_mat=new int *[rows];

    for(size_t i=0; i<rows; i++) pp_mat[i]=new int[cols];



  using vv_line_t=decltype(vv_mat)::value_type;

  using va_line_t=decltype(va_mat)::value_type;

  using aa_line_t=decltype(aa_mat)::value_type;

  using pp_line_t=decltype(*pp_mat);



  /* ... */



  /*

    Ordena linhas da matriz usando a função que compara apenas

    valores na 1ª coluna.



    Note que é preciso ser explícito com relação ao tipo dos argumentos

    (tipo de cada linha) porque estamos passando um ponteiro de

    função; se fosse uma chamada direta (por exemplo:

    “cmp_1_col(vv_mat[0], vv_mat[1])”), o compilador conseguiria

    identificar o tipo dos argumentos e instanciar a função correta.

  */

  sort(vv_mat.begin(), vv_mat.end(), cmp_1_col<vv_line_t>);

  sort(va_mat.begin(), va_mat.end(), cmp_1_col<va_line_t>);

  sort(aa_mat.begin(), aa_mat.end(), cmp_1_col<aa_line_t>);

  sort(pp_mat, pp_mat+rows, cmp_1_col<pp_line_t>);



  /*

    Mesma coisa, mas usando functors.



    Note que, agora, não é preciso dizer o tipo de cada linha pois,

    como não há ponteiros envolvidos, o compilador consegue

    saber os tipos dos argumentos.  Por outro lado, note que

    estamos criando objetos temporários distintos em cada chamada.

    Se fosse um objeto mais complexo, isso envolveria uma chamada

    de construtor no início e uma de destrutor para cada operação.

    Além disso, mesmo que você tivesse duas matrizes do mesmo tipo,

    ainda teria objetos distintos, e o compilador teria de ser bem

    esperto também para não instanciar duas vezes a função que

    faz a comparação para o mesmo tipo de argumento.

  */

  sort(vv_mat.begin(), vv_mat.end(), cmp_1_col_t());

  sort(va_mat.begin(), va_mat.end(), cmp_1_col_t());

  sort(aa_mat.begin(), aa_mat.end(), cmp_1_col_t());

  sort(pp_mat, pp_mat+rows, cmp_1_col_t());



  /*

    Functors novamente, mas com um objeto só.



    Note que, apesar de ser um só objeto, a função de comparação

    será instanciada de modo diferenciado para cada tipo de matriz.

    Por outro lado, podemos ter certeza de que não haverá mais de

    uma instância da função de comparação para o mesmo tipo de

    linhas comparadas.  Além disso, todas as operações de ordenação

    são feitas com apenas uma chamada ao construtor e uma ao

    destrutor deste único objeto.

  */

  cmp_1_col first_col_comparator;

  sort(vv_mat.begin(), vv_mat.end(), first_col_comparator);

  sort(va_mat.begin(), va_mat.end(), first_col_comparator);

  sort(aa_mat.begin(), aa_mat.end(), first_col_comparator);

  sort(pp_mat, pp_mat+rows, first_col_comparator);



  /*

    Finalmente, a versão usando lambdas.



    Pessoalmente, só gosto de lambdas quando as funções são

    bem curtas.  É o caso aqui.  Por outro lado, eles acabam

    deixando a coisa meio poluída visualmente, na minha opinião,

    e eu acabei quebrando as linhas para que eu mesmo tivesse

    clareza do que estava fazendo.



    Note que não existe mágica.  O compilador converte lambdas em

    functors anônimos, que têm uma função operator()() com os

    mesmos argumentos que você tiver usado para o lambda.



    Note ainda que lambdas não permitem o uso de templates.

  */

  sort(

    vv_mat.begin(), vv_mat.end(),

    [](const vv_line_t &a, const vv_line_t &b){ return a[0]<b[0]; }

  );

  sort(

    va_mat.begin(), va_mat.end(),

    [](const va_line_t &a, const va_line_t &b){ return a[0]<b[0]; }

  );

  sort(

    aa_mat.begin(), aa_mat.end(),

    [](const aa_line_t &a, const aa_line_t &b){ return a[0]<b[0]; }

  );

  sort(

    pp_mat, pp_mat+rows,

    [](const pp_line_t &a, const pp_line_t &b){ return a[0]<b[0]; }

  );



  /*

    Lambdas ainda.



    Como lambdas criam functors anônimos, é possível associá-los

    a objetos específicos, que poderiam ser reaproveitados para

    ordenar objetos do mesmo tipo.

  */

  auto vv_1st_col_lamb_cmp=

    [](const vv_line_t &a, const vv_line_t &b){ return a[0]<b[0]; }

  ;

  stable_sort(vv_mat.begin(), vv_mat.end(), vv_1st_col_lamb_cmp);



  /* ... */

}