Содержимое очереди подкачки приоритетов C ++

17

Я пишу класс, который имеет три очереди приоритета как частные члены.

class Foo {
...
...

private:
  // I am fine with using pointers instead if it helps.
  std::priority_queue<int> first;   // min heap.
  std::priority_queue<int> second;  // max heap.
  std::priority_queue<int> third;  // min heap.
};

Теперь мне нужно, чтобы first и third начинались с min heaps и second как max heap . В рамках функциональности моего класса мне нужно сделать следующее:

  1. Переместите second в first . В идеале это достигается за счет наименьшего количества копий. Основной вектор должен просто перемещаться. Дополнительно first теперь должно вести себя как max heap .
  2. Переместите third в second . Это означает, что second теперь должно вести себя как min heap .
  3. Так как содержимое third перемещено в second , оно должно быть пустым. Я хотел бы либо выделить новый базовый вектор, либо повторно использовать first's базового вектора (он больше не нужен. Кроме того, третье должно теперь быть max heap .

Мне нужно выполнить этот цикл (max - & gt; min и min - & gt; max) неизвестное количество раз.

Я изо всех сил стараюсь сделать это с помощью std::priority_queue , поскольку Comparator является аргументом шаблона, что означает, что я не могу его изменить во время выполнения. Это мешает мне превратить min heap в max heap .

Итак, мои вопросы:

  1. Есть ли способ, которым я мог бы сгибать std::priority_queue , чтобы сделать мои ставки, не делая это чрезвычайно уродливым?
  2. Если нет, то я могу, возможно, переструктурировать мой класс, чтобы сделать то же самое, но все равно использовать std::priority_queue ?
  3. В противном случае я мог бы повторно использовать большую часть логики heapify в библиотеке std для достижения этого?
задан Rajiv 19.05.2014 в 08:10
источник
  • Интересный и хорошо написанный вопрос, +1, нам нужно больше этого. –  Matteo Italia 19.05.2014 в 08:13
  • Пойдем, так что нет времени для полного ответа, но: Как вы видите, максимальные и минимальные PQ - это разные типы, поэтому вам нужно объявить их как таковые и не может просто переназначить. Возможно, на самом деле есть две макс и две мини-кучи. Сохраните флаг состояния, чтобы узнать, что у вас есть в данный момент. Вам нужно представить общий интерфейс для всех PQ, поэтому вам нужно написать адаптер вокруг каждого из них. –  Keith 19.05.2014 в 08:49

3 ответа

8
  

Есть ли способ, которым я мог бы сгибать std :: priority_queue, чтобы сделать мой   предлагая цену, не делая ее чрезвычайно уродливой?

Вы можете написать оболочку, которая скрывает предикат и использует наследование за кулисами. Однако это кажется излишним.

  

Если нет, то я могу, возможно, переструктурировать мой класс, чтобы сделать то же самое   но все же используйте std :: priority_queue?

Вы можете обернуть доступ к очередям в функциях. Затем используйте переменную bool или integer, чтобы проверить, к какой очереди нужно обращаться.

  

В противном случае я мог бы повторно использовать большую часть логики heapify в std   библиотеки для достижения этого?

Это звучит как лучший вариант, основанный на том, что вы объяснили. Храните каждый priority_queue в std::vector и используйте функции std::make_heap , std::push_heap и std::pop_heap для управления структурой кучи. Если вы сохраняете все очереди приоритетов в std::array<std::vector<int>, 3> , вы можете использовать std::rotate для выполнения описанной вами логики. Кроме того, вам нужно будет сохранить логическую переменную, указывающую, какой предикат использовать для операций кучи.

    
ответ дан D Drmmr 19.05.2014 в 08:49
  • Именно то, что я искал. На самом деле я уже использовал функции make_heap, push_heap и pop_heap. Специальный +1 для предложения std :: array + std :: rotate. Это еще больше уменьшает код котловой плиты! –  Rajiv 19.05.2014 в 08:52
3

Компаратор с состоянием

На самом деле, STL предоставляет возможности для вашего конкретного случая: вы можете передать компаратор к конструктору приоритетная очередь . Основная идея заключается в том, чтобы дать компаратору некоторое внутреннее состояние, которое определяет, следует ли применять операцию меньше или больше, чем . Тип компаратора выглядит следующим образом:

struct LessOrGreater
{
    explicit LessOrGreater( bool isLess ) : isLess{isLess} {}

    bool operator()( int lhs, int rhs ) const
    {
        return isLess == (lhs<rhs);
    }

    bool isLess;
};

Фактический тип очереди приоритетов -

using MinOrMaxQueue =
    std::priority_queue<int,std::vector<int>,LessOrGreater>;

Реализация класса

Теперь ваш класс может быть реализован с точки зрения этой особой очереди приоритетов.

class Foo {
public:
    Foo()
        : first { LessOrGreater{ false } } // initialize as min heap
        , second{ LessOrGreater{ true  } } // initialize as max heap
        , third { LessOrGreater{ false } } // initialize as min heap
    {}

    void op(); // The operation you explained

private:
    MinOrMaxQueue first; 
    MinOrMaxQueue second;
    MinOrMaxQueue third; 
};

Теперь описанная операция может быть реализована следующим образом:

void Foo::op()
{
    first  = std::move(second);
    second = std::move(third);
    third  = MinOrMaxQueue{ LessOrGreater{ true } }; // might throw!
}

Сделать безопасным исключение

Однако этот код не является безопасным для исключений. Поскольку конструктор по умолчанию std::vector<int> может выбрасывать (стандарт C ++ не гарантирует, что здесь нет!), Третья строка функции op() могла бы бросить объект Foo в недопустимое состояние. Вот реализация, которая сильно исключающая исключение и, скорее всего, такая же эффективная:

void Foo::op()
{
    MinOrMaxQueue tmp{ LessOrGreater{ true } };
    first .swap( second );
    second.swap( third );
    third .swap( tmp );
}

Первая строка - единственная строка, которая может быть выбрана, но она не изменяет объект Foo . Так что бросание не может ничего повредить. Остальные три строки никогда не бросаются, и, следовательно, функция сильно исключает.

    
ответ дан Ralph Tandetzky 19.05.2014 в 14:03
1

Я думаю, вы могли бы использовать простой std :: vector в качестве хранилища данных, а затем иметь адаптер для указания свойства кучи. Внутренний адаптер поддерживает std :: vector для хранения данных и хранения текущего компаратора. Позвольте мне посмотреть, работает ли это с тремя вашими требованиями:

class Heap
{
    Heap& opertor=(Heap&& h)
    {
        swap(*this, h);
        return *this;
    }

    void setComparator( std::function<bool (int, int)> c)
    {
        comparator = std::move(c);
    }

    void insert(int x)
    {
        // use std::push_heap to insert x with current comparator.
    }

    void swap(Heap& h)
    {
        swap(comparator, h.comparator);
        swap(data, h.data);
    }
private:
    std::function<bool (int,int)> comparator;
    std::vector<int> data_;
};
  
  1. Переместить второй в первый. В идеале это достигается за счет наименьшего количества копий. Основной вектор должен просто перемещаться.   Кроме того, сначала следует вести себя как максимальная куча.
  2.   

Это можно сделать, вызвав first = std::move(second) . Теперь данные перемещаются, и компаратор будет установлен на один со второго, делая вначале максимальную кучу в будущем.

  
  1. Двигайтесь от третьего до второго. Это означает, что секунда должна теперь вести себя как куча минут.
  2.   

То же, что и выше. %код%. Компаратор получает сброс, и он будет вести себя как минимальная куча.

  
  1. Поскольку содержимое третьего было перенесено на второе, оно должно быть пустым. Я хотел бы & gt; либо выделять новый базовый вектор, либо повторно использовать базовый вектор (он больше не нуждается в & gt;). Кроме того, третье должно быть максимальной кучей.
  2.   

После перемещения третий будет находиться в действительном, но неопределенном состоянии. Вы не можете полагаться на имеющуюся память, поэтому вам придется привести ее в правильное и определенное состояние. Вы можете использовать second = std::move(thid) .

    
ответ дан Jens 19.05.2014 в 09:01