Compiler error with custom comparator function as template argument

Question

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

Sam Varshavchik · Accepted Answer · 2019-03-05 02:54:53Z

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.

Collectives™ on Stack Overflow

Compiler error with custom comparator function as template argument

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related