Есть ли лучшая альтернатива компаратору STL с состоянием?

Question

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

Один из вариантов, конечно, заключается в предоставлении пользовательского компаратора, который имеет состояние и выбирает между возрастающим и нисходящим при каждом вызове operator(), но я пытаюсь избежать снижения производительности из-за наличия этой ветви для каждого сравнения , Другая альтернатива, которую я вижу, - это дублирование всего алгоритма, один для сортировки по возрастанию, а другой для убывания.

Есть ли лучшая альтернатива этой проблеме?

РЕДАКТИРОВАТЬ : Поскольку некоторые люди, похоже, очень хотят помочь, не понимая проблемы здесь, я попытаюсь немного уточнить.

Я реализовал алгоритм внешней сортировки (внешняя сортировка слиянием). Алгоритм использует std::priority_queue на этапе объединения. Теперь сортировка может быть восходящей или нисходящей. Компаратор std::priority_queue должен отличаться для этих двух случаев. Вы можете себе представить, что простой алгоритм сортировки может быть легко параметризован для обработки восходящего / нисходящего типа:

// psuedocode...
if (ascending) {
    if (a > b) // do something
} else {
    if (a < b) // do something
}

Одна проблема с этим заключается в том, что флаг ascending должен проверяться на каждой итерации цикла сортировки. «jalf» предполагает, что компилятор может «встроить» эту ветку, но я не думаю, что видел, как это произошло, по крайней мере, с VC ++ (да, я смотрел на некоторую сборку).

Теперь, когда используется std::priority_queue, чтобы сохранить некоторые вещи в отсортированном порядке, фактический тип очереди отличается для восходящих и нисходящих сортировок (поскольку компаратор должен быть разным, и это параметр шаблона). Итак, варианты:

1. Дублировать алгоритм (функцию) для убывающего регистра.
2. Параметризовать алгоритм в порядке сортировки и использовать одну очередь для возрастания и другую для убывания.
3. Используйте функтор компаратора с одним фрагментом состояния (isAscending), чтобы operator()() мог выполнить правильное сравнение для возрастания и убывания.
4. Шаблонизируйте функцию и потребуйте, чтобы компаратор был передан в качестве аргумента шаблона.
5. Использовать указатель функции в качестве аргумента шаблона компаратора.

Обратите внимание, что я не переключаюсь между двумя различными режимами очереди во время алгоритма (как некоторые просили). Я устанавливаю очередь в качестве минимальной или максимальной очереди в начале алгоритма, и она остается таковой для этого конкретного вида.

Теперь сравните варианты выше.

Вариант 1 недоступен из-за нежелательного дублирования и обслуживания кода (хотя он, вероятно, даст лучший код).

Вариант 2 нежелателен из-за всех дополнительных проверок во время выполнения и ветвления, а также из-за ненужного создания очереди, которая не будет использоваться.

Вариант 3 более привлекателен, потому что ветвление инкапсулировано / изолировано в функторе компаратора, но все же требует проверки во время выполнения для каждого сравнения (это принципиально то, чего я хотел избежать).

Вариант 4 поднимает проблему на один уровень вверх и требует от вызывающего абонента знать и иметь доступ к функторам компаратора - что-то вроде грязного.

Вариант 5 выглядит довольно неплохо - он обеспечивает чистый код, позволяя функции компаратора различаться во время выполнения без изменения типа очереди. Логика принятия решения не должна быть доступна вызывающей стороне (как это было бы с вариантом 4).

Единственный минус, который я могу видеть с опцией 5, это то, что компилятор может не сможет встроить вызов через указатель функции - но в моем случае это было сделано, потому что вызываемая функция была определена локальнов том же переводчике.Если бы оно не было встроенным, я предполагаю, что вариант 3 был бы лучше, но в моем случае производительность была лучше с вариантом 5.

Кроме того, после того, как я понял, что вариант 5 возможен (я не сделал вво-первых), мне пришло в голову, что использование указателей на функции вместо функторов, вероятно, не так много, и я подозреваю, что люди иногда перепрыгивают через обручи, чтобы использовать функторы (как мне бы пришлось), когда указатель на функцию может сделать код намного чище(особенно, когда производительность не имеет значения).

Answer 1

Использовать шаблоны

template <typename Comparator>
void algo()
{
  std::priority_queue<int, std::vector<int>, Comparator> pqueue;
  ...
}

- редактировать
Я читаю ваши правки, но до сих пор не понимаю, что вас беспокоит. Вы говорите

Option 4 pushes the problem up one level and requires the
caller to know and have access to the comparator functors 
-- kind of messy.

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

void algo_ascending() {
  algo<Ascending_Comparator>();
}
void algo_descending() {
  algo<Descending_Comparator>();
}

Или даже

void algo(bool ascending) {
  if (ascending)
     algo<Ascending_Comparator>();
  else
     algo<Descending_Comparator>();
}

Answer 2

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

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

struct shared_state_t
{
 int number;
};

struct compare_t
{
 bool operator <(const record_t &left, const record_t &right) const { left < right; }
 tr1::shared_ptr<shared_state_t> shared;
};

void func()
{
 tr1::shared_ptr<shared_state_t> state(new shared_state_t());
 state->number = 42;
 compare_t comp;
 comp.shared = state;
 std::priority_queue<record_t, vector<record_t>, compare_t> queue(comp);
 // do something with queue
 state->number = 999;
 // compare object of queue is aware of the new state
}

Answer 3

std::priority_queue принимает объект компаратора в своем конструкторе. Возьмите объект как параметр функции и передайте его конструктору. Каждый вызов создаст другой контейнер в зависимости от параметра. Так что ветка только на момент постройки.

template<class C>
void the_algorithm(const C& compare)
{
    std::priority_queue<Type> q(compare);
    // ...
}

bool this_before_that(const Type& op1, const Type& op2);

// ...
{
    the_algorithm(this_before_that);
    the_algorithm(ThatBeforeThis_Functor());
}

Здесь количество ветвлений просто в порядке вызовов алгоритма.