Содержание подстановки очереди приоритетов С++

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

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. В рамках функциональности моего класса мне нужно сделать следующее:

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

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

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

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

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

Ответ 1

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

Ответ 2

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

Фактически, 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> может забрасывать (стандарт С++ не гарантирует отсутствие отказа здесь!), Третья строка функции op() могла бы оставить объект Foo в недопустимом состоянии. Здесь реализация сильно исключающая исключение и, скорее всего, такая же эффективная:

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

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

Ответ 3

Я думаю, вы могли бы использовать простой 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_;
};

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

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

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

То же, что и выше. second = std::move(thid). Компаратор получает reset и будет вести себя как куча минут.

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

После перемещения третий будет находиться в состоянии, но undefined. Вы не можете полагаться на имеющуюся память, поэтому вам придется привести ее в правильное и определенное состояние. Вы можете использовать third.clear(); third.resize( n ).