Ошибка компилятора с пользовательской функцией сравнения в качестве аргумента шаблона

Question

Я не могу заставить класс Heap принять Comparator в качестве второго аргумента шаблона.Компилятор продолжает пытаться создать экземпляр объекта Comparator.Зачем?Все, что я хочу, это сравнение между двумя предоставленными входами.Вот ошибка компилятора:

  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

Вот класс

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

Вот компаратор:

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

Вот основная функция

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

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 ++ обычно имеют перегруженный конструктор, который принимает явный экземпляр класса компаратора, изатем использует его для копирования-конструирования своего частного экземпляра компаратора.