Блог

Я не могу заставить класс Heap принять компаратор в качестве второго аргумента шаблона. Компилятор продолжает пытаться создать экземпляр объекта 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 Tamp;) [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_typeamp;, __gnu_cxx::__alloc_traits<std::allocator<long unsigned int> >::value_typeamp;)’
         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 amp;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 amp;o1, const T amp;amp;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);
}
  

Здесь вы вызываете свой компаратор:

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

Cmp это ваш класс компаратора. Это параметр шаблона, который вы указываете в качестве вашего Comparator экземпляра шаблона.

Теперь отложим на время тему шаблонов. Для всех практических целей Cmp здесь есть класс. Представьте, что это обычный класс:

 class Cmp {

 // ...
};
  

Теперь спросите себя, что бы выражало:

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

значит, тогда?

Это, конечно, означает: создайте временный экземпляр Cmp класса и передайте два параметра в Cmp конструктор.

Теперь вы должны быть в состоянии понять вашу проблему. В вашем классе comparator нет конструктора, который принимает два параметра. Это то, что говорит вам ваш компилятор.

Вместо этого в вашем классе comparator используется перегруженный () оператор.

В вашем случае использования нет смысла создавать временный объект. Ваше очевидное намерение здесь — смоделировать ваш Heap шаблон и использовать его аналогично тому, как контейнеры стандартной библиотеки C используют классы компаратора.

На самом деле контейнеры стандартной библиотеки C , грубо говоря, объявляют член класса, который является экземпляром класса comparator, а затем вызывают () перегрузку оператора члена класса.

Это свободно переводится в ваш Heap шаблон, объявляющий частный член класса:

 private:
    Cmp cmp;
  

И затем вызывающий () перегрузку оператора этого члена класса.

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

Также обратите внимание, что стандартные библиотечные контейнеры C обычно имеют перегруженный конструктор, который принимает явный экземпляр класса comparator, а затем использует его для копирования-конструирования своего частного экземпляра comparator.