On Friday, 30 November 2012 04:40:03 UTC+2, Jeremy Murphy wrote:
To my surprise and horror, when I used std::priority_queue in place of std::set, the time and space performance is abysmally bad. So bad that I can't imagine why.
...
struct Node {
Node(std::vector<unsigned int> S, std::shared_ptr<Node> P) : state(S), parent(P) {}
std::vector<unsigned int> state;
std::shared_ptr<Node> parent;
};
and the queue is then defined:
typedef std::shared_ptr<Node> Element;
typedef std::priority_queue<Element, vector<Element>, Comp> PriorityQueue;
I can't really say what is going on ... perhaps make bit smaller example that demos
the problem.
My experience is directly opposite: priority_queue washes the floors with sets,
intrusive_sets, maps, sorted lists etc in context where you always pop the best
and alternate pops and pushes rather rapidly. Also the vector on what priority_queue
adapts is way more memory efficient than std::set.
So ... it feels that you have defect somewhere but can't show where, sorry.
One note ... I tend to remove usage of shared_ptr in performance critical algorithms.
It is heavy and performs way worse than some index, iterator, unique_ptr or raw pointer.