Comment activer la comparaison relationnelle de pointeurs dans une erreur?

Question

Nous avons été mordue à plusieurs reprises ci-dessous:

#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std; 

void print(int* pn) { cout << *pn << " "; } 

int main() { 
    int* n1 = new int(1); 
    int* n2 = new int(2); 
    int* n3 = new int(3); 

    vector<int*> v; 
    v.push_back(n1); 
    v.push_back(n2); 
    v.push_back(n3); 

    sort(v.begin(), v.end()); // Here be dragons! 

    for_each(v.begin(), v.end(), print); 
    cout << endl; 
    delete n1; delete n2; delete n3; 
} 

Le problème est que std :: sort compare les pointeurs entiers non entiers, ce qui est pas ce que le programmeur prévu. Pire, la sortie peut apparaître correcte et déterministe (considérez l'ordre des adresses renvoyées par new ou allouées sur la pile). Le problème racine est que le tri appelle éventuellement l'opérateur < pour T, ce qui est rarement une bonne idée lorsque T est un type de pointeur.

Est-il possible d'empêcher cela ou au moins d'obtenir un avertissement du compilateur? Par exemple, existe-t-il un moyen de créer une version personnalisée de std :: sort que requiert une fonction de comparaison lorsque T est un pointeur?

Answer 1

Pour pointeurs en général, vous pouvez le faire:

#include <ctime> 
    #include <vector> 
    #include <cstdlib> 
    #include <algorithm> 
    #include <functional> 
    #include <type_traits> 

    namespace util { 
     struct sort_pointers { 
      bool operator() (int *a, int *b) { 
       return *a < *b; 
      } 
     }; 

     template <typename T, bool is_pointer = !std::tr1::is_pointer<T>::value> 
     struct sort_helper { 
      typedef std::less<T> wont_compare_pointers; 
     }; 

     template <typename T> 
     struct sort_helper<T,false> { 
     }; 

     template <typename Iterator> 
     void sort(Iterator start, Iterator end) 
     { 
      std::sort(start, 
         end, 
         sort_helper 
         < 
          typename Iterator::value_type 
         >::wont_compare_pointers()); 
     } 

     template <typename Iterator, class Func> 
     void sort(Iterator start, Iterator end, Func f) { 
      std::sort(start, end, f); 
     } 
    } 

    int main() { 
     std::vector<int> v1; 
     std::vector<int*> v2; 
     srand(time(0)); 

     for(int i = 0; i < 10; ++i) { 
      v1.push_back(rand()); 
     } 

     util::sort(v1.begin(), v1.end()); 

     for(int i = 0; i < 10; ++i) { 
      v2.push_back(&v1[i]); 
     } 

     /* util::sort(v2.begin(), v2.end()); */ //fails. 
     util::sort(v2.begin(), v2.end(), util::sort_pointers()); 

     return 0; 
    } 

std::tr1::is_pointer était juste ce qu'il a été appelé dans Visual Studio 2008, mais je pense que Boost a un aussi, et les nouvelles compiles pourrait fournir comme std::is_pointer. Je suis sûr que quelqu'un serait en mesure d'écrire une solution plus jolie, mais cela semble fonctionner.

Mais je dois dire, je suis d'accord avec la roue dentée, il n'y a aucune raison pour cela, le programmeur devrait être en mesure de voir si cela va être un problème et agir en conséquence.

Addition:

Vous pouvez généraliser un peu plus je pense, pour sélectionner automatiquement un foncteur qui déréférencer les pointeurs et comparer les valeurs:

namespace util { 
    template <typename T> 
    struct sort_pointers { 
     bool operator() (T a, T b) { 
      return *a < *b; 
     } 
    }; 

    template <typename T, bool is_pointer = !std::tr1::is_pointer<T>::value> 
    struct sort_helper { 
     typedef std::less<T> compare; 
    }; 

    template <typename T> 
    struct sort_helper<T,false> { 
     typedef sort_pointers<T> compare; 
    }; 

    template <typename Iterator> 
    void sort(Iterator start, Iterator end) 
    { 
     std::sort(start, 
        end, 
        sort_helper 
        < 
         typename Iterator::value_type 
        >::compare()); 
    } 
} 

De cette façon, vous ne devez pas Pensez à si vous lui fournissez des pointeurs à comparer ou non, il sera automatiquement triés.

Answer 2

IMO, les programmeurs doivent savoir que std::sort suppose que le conteneur stocke des valeurs. Si vous avez besoin d'un comportement différent pour la comparaison, vous fournissez une fonction de comparaison. Par exemple. (Non testé):

template<typename T> 
inline bool deref_compare(T* t1, T* t2) { return *t1 < *t2; } 

//... 

std::sort(v.begin(), v.end(), deref_compare<int>); 

Modifier

FWIW, Jacob's answer se rapproche le plus de l'accomplissement directement ce que vous voulez. Il pourrait y avoir des façons de généraliser davantage.

Answer 3

Je n'ai pas une bonne réponse pour les pointeurs en général, mais vous pouvez restreindre les comparaisons si vous utilisez un pointeur intelligent de n'importe quel type - par exemple boost :: shared_ptr.

#include <boost/shared_ptr.hpp> 
using namespace std; 

template<class T> 
bool operator<(boost::shared_ptr<T> a, boost::shared_ptr<T> b) 
{ 
    return boost::shared_ptr<T>::dont_compare_pointers; 
} 

int main() { 
    boost::shared_ptr<int> A; 
    boost::shared_ptr<int> B; 
    bool i = A < B; 
} 

Sortie:

In function 'bool operator<(boost::shared_ptr<T>, boost::shared_ptr<T>) [with T = int]': 
t.cpp:15: instantiated from here 
Line 8: error: 'dont_compare_pointers' is not a member of 'boost::shared_ptr<int>' 
compilation terminated due to -Wfatal-errors. 

vous pouvez donc utiliser des pointeurs intelligents, ou créer votre propre wrapper pointeur intelligent. C'est très lourd pour ce que vous voulez, donc si vous créez un wrapper pour détecter cette situation, je vous recommande de ne l'utiliser qu'en mode debug. Donc, créez une macro (ugh, je sais) et utilisez-la pour déclarer des pointeurs.

#ifdef DEBUG 
    #define pointer(x) pointer_wrapper<X> 
#else 
    #define pointer(x) x* 
#endif 

Cela nécessite encore vos programmeurs pour l'utiliser, bien sûr!