Jak zmienić relacyjne porównanie wskaźników w błąd?

Question

Byliśmy pogryzieni przez następujący błąd wiele razy:

#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; 
} 

Problem polega na tym, że std :: sort porównuje wskaźniki liczby całkowitej liczby całkowite, które nie jest tym, co programista przeznaczeniem. Co gorsza, dane wyjściowe mogą być poprawne i deterministyczne (należy rozważyć kolejność adresów zwróconych przez nowe lub przydzielonych na stosie). Głównym problemem jest to, że sortowanie ostatecznie wywołuje operatora < dla T, co rzadko jest dobrym pomysłem, gdy T jest typem wskaźnika.

Czy istnieje sposób, aby temu zapobiec, a przynajmniej uzyskać ostrzeżenie kompilatora? Na przykład, czy istnieje sposób utworzenia niestandardowej wersji std :: sort, która wymaga funkcji porównania, gdy T jest wskaźnikiem?

Answer 1

Dla wskaźników w ogóle można to zrobić:

#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 właśnie co to było nazywane w Visual Studio 2008, ale myślę, że zbyt doładowania ma jeden, a nowsze kompiluje może dostarczyć go jako std::is_pointer. Jestem pewien, że ktoś mógłby napisać ładniejsze rozwiązanie, ale wygląda na to, że działa.

Ale muszę powiedzieć, zgadzam się z cogwheel, nie ma ku temu powodu, programista powinien być w stanie sprawdzić, czy to będzie problem i działać zgodnie z nim.

Dodatek:

Można uogólnić go nieco więcej myślę, aby automatycznie wybrać funktor, który dereference tych wskaźników i porównanie wartości:

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()); 
    } 
} 

W ten sposób nie trzeba Zastanów się, czy dostarczasz wskaźniki do porównania, czy nie, ale zostaną one automatycznie uporządkowane.

Answer 2

IMO, programiści powinni wiedzieć, że std::sort przyjmuje wartości przechowujące pojemnik. Jeśli potrzebujesz innego zachowania dla porównania, to zapewnisz funkcję porównywania. Na przykład. (Niesprawdzone):

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

//... 

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

Edit

FWIW, Jacob's answer przychodzi najbliżej bezpośrednio realizacji, co chcesz. Być może istnieją sposoby dalszego uogólnienia tego.

Answer 3

Nie mam dobrej odpowiedzi dla wskaźników w ogóle, ale możesz ograniczyć porównania, jeśli używasz inteligentnego wskaźnika dowolnego rodzaju - np. 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; 
} 

wyjściowa:

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. 

Więc można używać inteligentnych wskaźników, lub stworzyć swój własny wskaźnik inteligentne opakowania. Jest to bardzo duże, ale to, co chcesz, więc jeśli utworzysz opakowanie, aby wykryć tę sytuację, zalecam używanie go tylko w trybie debugowania. Stwórz więc makro (wiem, wiem) i używaj go do zadeklarowania wskaźników.

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

Oczywiście nadal wymaga to od was programistów!