C ++ priority_queue с пользовательским компаратором и удалением любого элемента - PullRequest
0 голосов
/ 03 октября 2019

Я работаю над решением с минимальной кучей, которое помимо пользовательского компаратора требует поддержки удаления любого элемента. Полностью настраиваемая куча Impl является одним из способов. Но я хотел положиться на C ++ STL для желаемых операций.
Документация C ++ и ответ StackOverflow здесь указали на то, что я должен использовать собственный класс и перегружать пользовательский метод remove. Я также перегружал пользовательский компаратор в том же классе.

template<typename T>
class custom_priority_queue_MinHeap : public std::priority_queue<T, std::vector<T>>
{
  public:
  bool remove(const T& value) 
  {
    auto it = std::find(this->c.begin(), this->c.end(), value);
    if (it != this->c.end())
    {
        this->c.erase(it);
        std::make_heap(this->c.begin(), this->c.end(), this->comp);
        return true;
    }

    return false;
  }

  bool operator()(const pair<int, int> &a, const pair<int, int> &b)
  {
    cout << "Custom comparator called" << endl;  <----------- Never called
    return a.second > b.second;
  }
};

Расход пользовательской кучи выглядит примерно так:

custom_priority_queue_MinHeap<pair<int, int>> minHeap;
minHeap.push({0, 10});
minHeap.push({1, 5});
minHeap.push({2, 15});

while(!minHeap.empty())
{
    pair<int, int> p = minHeap.top();
    minHeap.pop();
    cout << p.first << " " << p.second << endl;
}

При запуске на Ideone , minHeap push не работает должным образом. Он мигает ниже выхода:

2 15
1 5
0 10    

Правильный вывод должен быть:

1 5
0 10  
2 15      

Перегрузка компаратора () никогда не вызывается, что кажется виновником. Элементы выталкиваются в том порядке, в котором они были вставлены. Интересно, что функция remove работает нормально.

Вопрос (ы):
Можно ли полностью полагаться на C ++ priority_queue STL для достижения желаемых операций, то есть пользовательский компаратор с поддержкой удаления любого элемента? Если да, есть ли что-то, чего мне не хватает в вышеупомянутой реализации?

1 Ответ

1 голос
/ 03 октября 2019

Спасибо PaulMcKenzie за то, что указал мне правильное направление! Проблема заключалась в том, что priority_queue в STL является классом с тремя параметрами. В моем импле отсутствовал третий параметр класса сравнения.
Ниже изменения работали нормально. Ideone ссылка

class Comp
{
public:
    bool operator()(const pair<int, int> &a, const pair<int, int> &b)
    {
        cout << "Custom comparator called" << endl;
        return a.second > b.second;
    }
};

template<typename T>
class custom_priority_queue_MinHeap : public std::priority_queue<T, std::vector<T>, Comp>
{
    ...
};
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...