Класс шаблона, относящийся к значениям и ссылочной семантике

Question

Я работал над очередью приоритетов, используя двоичную кучу, и разработал для этого класс, как показано ниже.

#include <iostream> 
#include <type_traits> 

template<class T, int N> 
class BinaryHeap{ 

    template<class T1> 
    class has_less_than_operator 
    { 
    private: 
     class no{}; 
     template<class X> 
     static auto has(X&& t) -> decltype (t.operator < (t)); 

     static no has(...); 
    public: 
     enum { 
      value = !std::is_same< 
      decltype(has(std::declval<T1>())), 
      no>::value 
     }; 
    }; 

    static_assert(std::is_copy_assignable<T>::value && 
        std::is_copy_constructible<T>::value, 
        "Must be copy assignable and constructable"); 
public: 
    BinaryHeap() : used_(0){ 

    } 

    BinaryHeap(BinaryHeap const& other) = default; 

    BinaryHeap& operator = (BinaryHeap const& other) = default; 

    inline T& max(){ 
     return elements_[FIRST]; 
    } 

    inline T const & max() const{ 
     return elements_[FIRST]; 
    } 

    void insert(T const& item){ 
     elements_[++used_] = item; 
     swim(used_); 
    } 

    inline bool full() const{ 
     return used_ == N; 
    } 

    void deleteMax(){ 
     std::swap(elements_[used_],elements_[FIRST]); 
     sink(FIRST); 
     elements_[used_--] = T(); 
    } 

private: 

    template<class T1> 
    class has_dereference_operator 
    { 
    private: 
     class no{}; 
     template<class X> 
     static auto has(X&& t) -> decltype (t.operator *()); 

     static no has(...); 
    public: 
     enum { 
      value = !std::is_same< 
      decltype(has(std::declval<T1>())), 
      no>::value 
     }; 
    }; 



    inline bool parent_less(int position,std::integral_constant<int,0> i){ 
     return elements_[ position/2] < elements_[position]; 
    } 

    inline bool parent_less(int position,std::integral_constant<int,1> i){ 
     return *(elements_[ position/2]) < *(elements_[position]); 
    } 

    void swim(int position){ 
     while(position > 1 && parent_less(position,std::integral_constant<int, has_dereference_operator<T>::value>())) 
     { 
      std::swap(elements_[ position/2], elements_[position]); 
      position /= 2; 
     } 
    } 

    inline int which_less(int p1, int p2, std::integral_constant<int,0> i){ 
     return (elements_[ p1] < elements_[p2]) ? p1 : p2; 
    } 

    inline int which_less(int p1, int p2, std::integral_constant<int,1> i){ 
     return (*(elements_[ p1]) < *(elements_[p2])) ? p1 : p2; 
    } 

    inline int which_greater(int p1, int p2, std::integral_constant<int,0> i){ 
     return (elements_[ p1] < elements_[p2]) ? p2 : p1; 
    } 

    inline int which_greater(int p1, int p2, std::integral_constant<int,1> i){ 
     return (*(elements_[ p1]) < *(elements_[p2])) ? p2 : p1; 
    } 

    void sink(int position){ 
     while(position * 2 <= used_){ 
      int first = position * 2; 
      if(first > used_) break; 

      int greater_child = which_greater(first, first + 1, std::integral_constant<int, has_dereference_operator<T>::value>()); 
      int lesser = which_less(greater_child, position, std::integral_constant<int, has_dereference_operator<T>::value>()); 
      if(lesser == greater_child) 
       break; 

      std::swap(elements_[greater_child], elements_[position]); 
      position = greater_child; 
     } 
    } 

    inline int current_position() const{ 
     return used_ + 1; 
    } 

    static const int MAX = N + 1; 
    static const int FIRST = 1; 
    static const int LAST = N; 
    T elements_[MAX]; 
    int used_; 
}; 

int main(int argc, const char * argv[]) 
{ 

    BinaryHeap<int, 10> b; 

    b.insert(1); 
    b.insert(20); 
    b.insert(21); 
    b.insert(3); 
    b.insert(2); 

    std::cout << "Max: " << b.max() << std::endl; 

    b.deleteMax(); 

    std::cout << "Max: " << b.max() << std::endl; 

    return 0; 
} 

Хотя я эта работа, мне нужно, чтобы иметь дело с различиями в сравнении скажет, указатель/общий указатель говорит с помощью оператора разыменования и ценностей просто использовать их как есть. В настоящее время я использую SFINAE для этого, основываясь на том, имеет ли класс оператор *.

Это правильный путь для достижения этой цели?

Blair

Answer 1

Проблема с использованием эвристики, как это то, что это не всегда то, что клиент вашего кода хочет от вас, и вы не предоставите способ изменить поведение. Когда-нибудь клиент может захотеть использовать ваш класс для хранения указателей и фактически сортировать их с помощью std::less<T> вместо разыменования (например, BinaryHeap<void*,32>). Даже без указателей клиент может просто хотеть отличаться от заказа, отличного от <.

Когда стандартная библиотека должна выполнять сравнение, она обычно использует std::less<T> по умолчанию, но дает возможность клиенту переопределить этот выбор (например, или std::sort). Если бы я писал ваш класс, я бы его параметрировал бы оператором сравнения по умолчанию, равным std::less<T>, как и стандартная библиотека. Я бы также предоставил удобный шаблон сравнения разыменования, чтобы упростить клиентам использование указателей для заказа по указателям.