2
#include <functional>
#include <iostream>
#include <vector>

template <class value_type, class comparator_type>
class Heap {
    public:
    comparator_type comparator;
    explicit Heap(comparator_type some_comparator);
    std::vector<value_type> data;
    int Push(const value_type & value);
    void Delete(int index);
    const value_type & Root();
    void Pop();
    int Size();
    bool Empty();
    int Father(int index);
    int LeftSon(int index);
    int RightSon(int index);
    void SwapElements(int firstIndex, int secondIndex);
    int SiftUp(int index);
    void SiftDown(int index);
};

template <class value_type, class comparator_type>
Heap<value_type, comparator_type>::Heap(comparator_type some_comparator): comparator(some_comparator) {
}

template <class value_type, class comparator_type>    
int Heap<value_type, comparator_type>::Push(const value_type & value) {
    data.push_back(value);
    int index = data.size() - 1;
    return SiftUp(index);
}

template <class value_type, class comparator_type>    
void Heap<value_type, comparator_type>::Delete(int index) {
    const int last_index = data.size() - 1;
    if (index == last_index) {
        data.pop_back();
    } else {
        SwapElements(last_index, index);
        data.pop_back();
        if (index != 0 && comparator(data[Father(index)], data[index])) {
            SiftUp(index);
        } else {
            SiftDown(index);
        };
    };
}

template <class value_type, class comparator_type>
const value_type & Heap<value_type, comparator_type>::Root() {
    return data[0];
}

template <class value_type, class comparator_type>
void Heap<value_type, comparator_type>::Pop() {
    Delete(0);
}

template <class value_type, class comparator_type>
int Heap<value_type, comparator_type>::Size() {
    return data.size();
}

template <class value_type, class comparator_type>
bool Heap<value_type, comparator_type>::Empty() {
    return Size() == 0;
}

template <class value_type, class comparator_type>
int Heap<value_type, comparator_type>::Father(int index) {
    if (index == 0) {
        return -1;
    } else {
        return (index - 1) / 2;
    }
}

template <class value_type, class comparator_type>
int Heap<value_type, comparator_type>::LeftSon(int index) {
    int result = index * 2 + 1;
    if (result >= Size()) {
        return -1;
    } else {
        return result;
    };
}

template <class value_type, class comparator_type>
int Heap<value_type, comparator_type>::RightSon(int index) {
    int result = index * 2 + 2;
    if (result >= Size()) {
        return -1;
    } else {
        return result;
    };
}

template <class value_type, class comparator_type>
void Heap<value_type, comparator_type>::SwapElements(int firstIndex, int secondIndex) {
    std::swap(data[firstIndex], data[secondIndex]);
}

template <class value_type, class comparator_type>
int Heap<value_type, comparator_type>::SiftUp(int index) {
    if (index != 0 && comparator(data[Father(index)], data[index])) {
        SwapElements(index, Father(index));
        return SiftUp(Father(index));
    }
    return index;
}

template <class value_type, class comparator_type>
void Heap<value_type, comparator_type>::SiftDown(int index) {
    int new_place = index;
    int left_son_index = LeftSon(index);
    if (left_son_index != -1 && comparator(data[new_place], data[left_son_index])) {
        new_place = left_son_index;
    };
    int right_son_index = RightSon(index);
    if (right_son_index != -1 && comparator(data[new_place], data[right_son_index])) {
        new_place = right_son_index;
    };
    if (new_place != index) {
        SwapElements(index, new_place);
        SiftDown(new_place);
    };
}

struct IntCompare {
    bool operator() (int first, int second) const {
        return first < second;
    };
};

int main() {
    Heap<int, IntCompare> myHeap(IntCompare());
    myHeap.Push(1);
    return 0;
}

I'm trying to implement a binary heap with template parameters with value being stored and with a comparator being used. I'm getting errors of the form

request for member `Push' in `myHeap', which is of non-class type `Heap<int, IntCompare> ()(IntCompare (*)())' 

at the line

myHeap.Push(1);

The same thing happens with any other field of this class. What is my mistake and how can I fix it?

3
  • 1
    most-vexing parse strikes back, use Heap<int, IntCompare> myHeap((IntCompare())); instead, or Heap<int, IntCompare> myHeap(IntCompare{}); Commented Nov 6, 2014 at 10:20
  • @PiotrS. Oh, I see. How can I fix it? Commented Nov 6, 2014 at 10:24
  • see the two proposals Commented Nov 6, 2014 at 10:24

1 Answer 1

4

You're experiencing the most vexing parse problem in the line

Heap<int, IntCompare> myHeap(IntCompare());

change it to

IntCompare comp;
Heap<int, IntCompare> myHeap(comp);

or

Heap<int,IntCompare> myHeap(IntCompare{}/*Can't be confused with a function pointer*/);

or

Heap<int,IntCompare> myHeap((IntCompare())/* ditto */);
Sign up to request clarification or add additional context in comments.

1 Comment

Heap<int, IntCompare> myHeap((IntCompare()));

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.