CODEWITHSUNDEEP
c++compiler-errors
cppprogrammer
cppprogrammer

Reputation: 135

Compiler error with custom comparator function as template argument

I can't get the Heap class to accept the Comparator as the second template argument. The compiler keeps trying to instantiate a Comparator object. Why? All I want is a comparision between the 2 provided inputs. Here's the compiler error:

  In file included from main.cpp:1:0:
Heap.hpp: In instantiation of ‘void Heap<T, Cmp>::bubbleUp(size_t) [with T = long unsigned int; Cmp = Comparator<long unsigned int>; size_t = long unsigned int]’:
Heap.hpp:29:35:   required from ‘void Heap<T, Cmp>::insert(const T&) [with T = long unsigned int; Cmp = Comparator<long unsigned int>]’
main.cpp:7:15:   required from here
Heap.hpp:119:9: error: no matching function for call to ‘Comparator<long unsigned int>::Comparator(__gnu_cxx::__alloc_traits<std::allocator<long unsigned int> >::value_type&, __gnu_cxx::__alloc_traits<std::allocator<long unsigned int> >::value_type&)’
         if (Cmp(fArray[idx], fArray[getParent(idx)]))
         ^
Heap.hpp:119:9: note: candidates are:
Heap.hpp:128:7: note: constexpr Comparator<long unsigned int>::Comparator()
 class Comparator

Here's the class

#pragma once
#include <vector>
#include <functional>
#include <assert.h>
#include "boost/optional.hpp"

template <typename T, typename Cmp>
class Heap
{

  public:
    Heap()
        : fArray()
    {
    }
    ~Heap() {}
    void insert(const T &toInsert)
    {
        fArray.push_back(toInsert);
        bubbleUp(fArray.size() - 1);
    }


  private:
    std::vector<T> fArray;
    size_t getParent(size_t i) const
    {
        assert(i / 2 < fArray.size());
        return i / 2;
    } 


    void bubbleUp(size_t idx)
    {
        if (idx == 0)
        {
            return;
            // return early if root
        }
        // If heap property violated, swap and recurse upwards
        if (Cmp(fArray[idx], fArray[getParent(idx)])
        {
            std::iter_swap(fArray.begin() + idx, fArray.begin() + getParent(idx));
            bubbleUp(getParent(idx));
        }
    }
};

Here's the comparator:

template <typename T>
class Comparator
{
  public:
    bool operator()(const T &o1, const T &&o2)
    {
        return o1 < o2;
    }
};

Here's the main function

int main(){
    Heap< size_t,Comparator<size_t> >  h;
    h.insert(4);
    h.insert(5);
    h.insert(6);
    h.insert(3);
}

Upvotes: 1

Views: 201

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118310

You're invoking your comparator here:

if (Cmp(fArray[idx], fArray[getParent(idx)])

Cmp is your comparator class. This is the template parameter, which you specify as your Comparator template instance.

Now, set aside the topic of templates, for the moment. For all practical purposes, Cmp is a class here. Pretend it's an ordinary, plain class:

class Cmp {

 // ...
};

Now, ask yourself, what would expression:

Cmp(fArray[idx], fArray[getParent(idx)])

mean, then?

It means, of course: construct a temporary instance of the Cmp class, and pass two parameters to Cmp's constructor.

Now, you should be able to understand your problem. Your comparator class does not have a constructor that takes two parameters. That's what your compiler is telling you.

Your comparator class has an overloaded () operator, instead.

It makes no sense to construct a temporary object, in your use case. Your obvious intent here is to model your Heap template and use it in a similar way to how the standard C++ library's containers use comparator classes.

What the standard C++ library's containers actually do, loosely speaking, is that they declare a class member that's an instance of the comparator class, and then invoke the class member's () operator overload.

This loosely translates into your Heap template declaring a private class member:

private:
    Cmp cmp;

And then invoking this class member's () operator overload.

if (cmp(fArray[idx], fArray[getParent(idx)])

Also, note that standard C++ library containers typically have an overloaded constructor that takes an explicit instance of the comparator class, and then uses it to copy-construct their private comparator instance.

Upvotes: 2

Related Questions