Template class dealing with values and reference semantics

Question

I have been working on a priority queue using a binary heap and have developed a class for this as shown below.

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

Although I have this working I need to deal with the differences in comparing say a pointer / shared pointer say using dereference operator and values just using them as is. I am currently using SFINAE to do this based on if the class has operator *.

Is this the right way to achieve this?

Blair

Answer 1

The problem with using heuristics like this is that it's not always what the client of your code wants you to do, and you don't provide a way to change the behavior. Someday a client may want to use your class to store pointers and actually sort them with std::less<T> instead of dereferencing (BinaryHeap<void*,32> for example). Even with non-pointers, a client may simply want a differing ordering than that imposed by <.

When the Standard Library needs to perform comparison it usually uses std::less<T> by default but provides a way for the client to override that choice (e.g. std::priority_queue or std::sort). If I was writing your class, I would parameterize it by comparison operator defaulting to std::less<T> just like the Standard Library would. I would also provide a handy dereferencing comparator template to make it easy for clients using pointers to order by pointees.