模板類處理價值和參考語義

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來做這個的基礎上，如果類有運營商*。

這是實現這一目標的正確方法嗎？

布萊爾

Answer 1

的使用啓發式像這樣的問題是，它並不總是你的代碼的客戶希望你做了，你不提供一種方法來改變行爲。有一天，一個客戶可能想使用你的類來存儲指針，實際上他們std::less<T>，而不是取消引用（BinaryHeap<void*,32>例如）排序。即使使用非指針，客戶也可能只需要一個不同於<所規定的順序。

當標準庫需要執行比較時，默認情況下它通常使用std::less<T>，但爲客戶端提供了一種覆蓋該選項的方法（例如std::priority_queue或std::sort）。如果我正在寫你的班級，我將通過比較運算符來參數化它，就像標準庫一樣，默認爲std::less<T>。我還會提供一個方便的解引用比較模板，以便使用指針的客戶端可以很容易地通過pointees進行排序。