Is there a better alternative to an STL comparator with state?

Question

I have a fairly large, sophisticated algorithm that uses a std::priority_queue. In some cases, I want the queue to be a min-queue, and in others, a max-queue. So I have to provide a comparator type that does one or the other. Since the comparator is a template parameter, it is fundamentally part of the type of the std::priority_queue. So everywhere the queue is referenced, the code must know the type.

One option, of course, is to provide a custom comparator that has state, and selects between ascending and descending on each invocation of operator(), but I'm trying to avoid the performance overhead of having this branch for every comparison. The other alternative that I can see is to duplicate the entire algorithm, one for sorting ascending, and the other for descending.

Is there a better alternative to this problem?

Answer 1

Use templates

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

Answer 2

If you want to use a comparator which has state then you can not change that state because the comparator is copied by the queue. In order to change the state of your comparator after your queue was constructed you can use shared state.

However the state should not be used to alter the result of comparisons after elements are added to the queue. This would probably cause weird behavior of the queue.

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 takes a comparator object in its constructor. Take the object as a function parameter and pass it to the constructor. Each call will create a different container depending on the parameter. So the branch is only at the time of construction.

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());
}

The branching count here is merely in the order of calls to the algorithm.