Fonction de tri d'insertion avec commutateur de commande

Question

J'ai essayé d'écrire une fonction de tri d'insertion qui permutera entre croissant et décroissant en fonction du signe de son argument (order). Cela fonctionne, mais cela ne semble pas correct car l'opérateur conditionnel que j'ai utilisé comme commutateur ajoutera une surcharge à chaque itération de la boucle interne. Donc, je voudrais demander votre avis sur la façon dont je pourrais écrire une meilleure version de ma fonction.

void Array::sort(int order) //Array is a struct that contains a vector of pointers named vect, as well as this function. 
{ 
    if (order==0) return; 
    bool ascending = (order>0); 
    int i,j; 
    Data* buffer; //Data is a struct containing some variables, including the key that has to be sorted. 
    for (i=1; i<_size; i++) 
    { 
    buffer = vect[i]; //A vector of pointers to Data objects declared in the Array struct. 
    j=i-1; 
    while (j>=0 && (ascending?(vect[j]->key > buffer->key):(vect[j]->key < buffer->key))) 
    { 
     vect[j+1] = vect[j]; 
     j--; 
    } 
    vect[++j] = buffer; 
    } 
} 

Answer 1

Vous voulez essentiellement écrire deux fonctions, dont chacune connaît son ordre de tri statiquement (c'est-à-dire, au moment de la compilation), et choisir lequel appeler dynamiquement.

Le plus simple changement est la suivante:

// original code, templated 
template <bool Ascending> 
void Array::sort() { 
    int i,j; 
    Data* buffer; 
    for (i=1; i<_size; i++) { 
    buffer = vect[i]; 
    j=i-1; 
    while (j>=0 && (Ascending?(vect[j]->key > buffer->key):(vect[j]->key < buffer->key))) 
    { 
     vect[j+1] = vect[j]; 
     j--; 
    } 
    vect[++j] = buffer; 
    } 
} 

// original prototype 
void Array::sort(int order) { 
    if (order > 0) 
    sort<true>(); 
    else if (order < 0) 
    sort<false>; 
} 

Notez que bien qu'il y ait encore une déclaration ternaire dans la boucle intérieure, il peut facilement être optimisé loin puisque Ascending est constant (juste une constante différente dans chaque instanciation) .

Une manière plus propre est de supprimer entièrement l'instruction ternaire, et de passer à la place une sorte de fonction de comparaison dans le modèle de fonction interne. Nous pourrions passer un pointeur de fonction, ou un lambda - j'utilise les objets de fonction intégrés puisqu'ils font déjà ce que nous voulons.

// Comparitor is some type you can call to compare two arguments 
template <typename Comparitor> 
void Array::sort(Comparitor comp) { 
    int i,j; 
    Data* buffer; 
    for (i=1; i<_size; i++) { 
    buffer = vect[i]; 
    j=i-1; 
    while (j>=0 && comp(vect[j]->key, buffer->key)) { 
     vect[j+1] = vect[j]; 
     j--; 
    } 
    vect[++j] = buffer; 
    } 
} 

// std::greater and less come from <functional> 
void Array::sort(int order) { 
    typedef decltype(vect[0]->key) KeyType; // or use the real type directly 
    if (order > 0) 
    sort(std::greater<KeyType>()); 
    else if (order < 0) 
    sort(std::less<KeyType>()); 
} 

Answer 2

Une option consiste à utiliser un modèle, et redéfinir votre fonction

template<class T> void Array::sort(T op) 
{ 
    ... 
    while (j>=0 && op(vect[j]->key,buffer->key)) 
    ... 
} 

vous pouvez appeler votre genre avec l'objet de tri approprié

struct LessThan : public std::binary_function<int, int, bool> { 
    bool operator() (int x, int y) const { return x < y; } 
}; 
struct GreaterThan : public std::binary_function<int, int, bool> { 
    bool operator() (int x, int y) const { return x > y; } 
}; 

Array::sort(LessThan()); 

Answer 3

Si vous voulez vraiment la performance , vous pourriez écrire deux fonctions, au lieu d'une. Mais conduit à la duplication. C'est là que C++ brille avec les templates.