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

标签： c++compiler-errors

Answer 1

你在这里调用你的比较器：

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

Cmp是你的比较类。这是模板参数，您将其指定为Comparator模板实例。

现在，暂时搁置模板的话题。出于所有实际目的，Cmp这里是一个类。假设它是一个普通的、普通的类：

class Cmp {

 // ...
};

现在，问问自己，会表达什么：

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

那是什么意思？

当然，这意味着：构造一个Cmp类的临时实例，并将两个参数传递给Cmp的构造函数。

现在，您应该能够理解您的问题了。您的比较器类没有带有两个参数的构造函数。这就是你的编译器告诉你的。

相反，您的比较器类有一个重载的()运算符。

在您的用例中，构造一个临时对象是没有意义的。您在这里的明显意图是对Heap模板进行建模并以与标准 C++ 库的容器使用比较器类的方式类似的方式使用它。

标准 C++ 库的容器实际上所做的是，松散地说，它们声明一个作为比较器类实例的类成员，然后调用该类成员的()运算符重载。

这松散地转换为您的Heap模板声明一个私有类成员：

private:
    Cmp cmp;

然后调用这个类成员的()运算符重载。

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

另请注意，标准 C++ 库容器通常具有一个重载的构造函数，该构造函数采用比较器类的显式实例，然后使用它来复制构造它们的私有比较器实例。