Re-sort Priority Queue?

[S G H]

I've got a priority queue of items who, from time to time, returns a different comparison result.
Any way to re-sort a priority queue who is storing them?

Example:

#include <cstdlib>
struct Random {
    bool operator<(const Random&) const { return !(rand()&1); }
};

[LB]

Ignoring that horrifying comparison operator, I think it's better to use a container that doesn't care about the order of its elements unless you manually sort it. Otherwise you're violating the container's requirements, which I think might be undefined behavior (I'm not sure though).

[S G H]

It was purely as an example.
I'm going to give a try using a std::vector and std::make_heap/... as, from what I understood, that's what the priority_queue is using.

[Duthomhas]

[edit]
DON'T DO THIS!
The comparison functor of a priority queue must be stateless.

So OP is out of luck if he wants to apply a different comparison to the container. Just wrap your data in a new priority queue.
[/edit]

Off the top of my head:

template <typename T>
struct MyPriorityCompare
  {
  enum { MODE_X, MODE_Y, MODE_Z } mode;
  MyPriorityCompare(): mode( MODE_X ) { }
  bool operator () ( const T& lhs, const T& rhs )
    {
    switch (mode)
      {
      case MODE_X: return lhs.x < rhs.x;
      case MODE_Y: return lhs.y < rhs.y;
      case MODE_Z: return lhs.z < rhs.z;
      }
    throw error? return default?
    }
  };

MyPriorityCompare <3DPoint> mpc;
std::priority_queue <3DPoint, std::deque <3DPoint> , MyPriorityCompare <3DPoint> > priority_points;

mpc.mode = mpc.MODE_Y;
// I'm not sure ATM how to force priority queue to reorder. Call std::make_heap() on the contents? 

Just a thought.

[S G H]

Solved using lists and sorting elements on insertion, manually re-sorted when required.

[LB]

Please tell me you didn't use std::list ;)

[S G H]

Thanks @ Duoas for the edit (The edit was more useful than the post itself :> )
@LB: I don't think std::list has any kind of big downsides in my situation, besides for the amount of new calls.

_{Does std::list store the end pointer? Or does it travel all the way through every time?}

[LB]

@EssGeEich: nevermind, I misunderstood your post. std::list is good for inserting often.

[JLBorges]

> std::list is good for inserting often.

Not the best for priority-based insertion.
push_back() followed by std::push_heap() on std::vector<> would be faster.

And std::make_heap() on a vector (when the priorities change) would be faster than std::list<>::sort()

[LB]

Ah, I guess vector wins in more cases than I thought :)

[S G H]

Alright, making a comparison test.
Pathfinding (100x100 map) Test:

Container                      | Time
std::list                      | 164ms
Reserved std::vector/make_heap | 290ms
std::vector/make_heap          | 321ms
std::priority_queue            | 355ms

Either I did something wrong, or I've been able to use a std::list in an optimal way.

Reserving more memory doesn't do the trick either, time goes down to around 290ms.

@JLBorges: Making you notice a little detail anyways: Guess you noticed it.