Question is very simple: is there analogue of std::priority_queue in UE4?
Hi,
There isn’t a direct analogue to std::priority_queue, but you can use heap functions on TArray instead, with an inverted predicate:
struct MyType
{
explicit MyType(int32 InPriority);
int32 Priority;
};
struct MyTypePredicate
{
bool operator()(const MyType& A, const MyType& B) const
{
// Inverted compared to std::priority_queue - higher priorities float to the top
return A.Priority > B.Priority;
}
};
TArray<MyType> Queue;
Queue.HeapPush(MyType(10), MyTypePredicate());
Queue.HeapPush(MyType(5), MyTypePredicate());
Queue.HeapPush(MyType(20), MyTypePredicate());
Queue.HeapPush(MyType(15), MyTypePredicate());
MyType Next;
Queue.HeapPop(Next, MyTypePredicate());
check(Next.Priority == 20);
Hope this helps,
Steve
4 Likes
Thank you!
thanks for this
Nice solution!! but i have one question is this thread safe for a scenario of one consumer and many producers?
I’m afraid not. You’ll need to protect access to the array by a mutex.
Steve
For people finding this now, there’s (in my opinion) a better way to do it via overriding the < operator and wrapping a TArray up a bit.
Keep in mind: A lower number means higher priority
CODE
template <typename InElementType>
struct TPriorityQueueNode {
InElementType Element;
float Priority;
TPriorityQueueNode()
{
}
TPriorityQueueNode(InElementType InElement, float InPriority)
{
Element = InElement;
Priority = InPriority;
}
bool operator<(const TPriorityQueueNode<InElementType> Other) const
{
return Priority < Other.Priority;
}
};
template <typename InElementType>
class TPriorityQueue {
public:
TPriorityQueue()
{
Array.Heapify();
}
public:
// Always check if IsEmpty() before Pop-ing!
InElementType Pop()
{
TPriorityQueueNode<InElementType> Node;
Array.HeapPop(Node);
return Node.Element;
}
TPriorityQueueNode<InElementType> PopNode()
{
TPriorityQueueNode<InElementType> Node;
Array.HeapPop(Node);
return Node;
}
void Push(InElementType Element, float Priority)
{
Array.HeapPush(TPriorityQueueNode<InElementType>(Element, Priority));
}
bool IsEmpty() const
{
return Array.Num() == 0;
}
private:
TArray<TPriorityQueueNode<InElementType>> Array;
};
USAGE
// -- Construction
TPriorityQueue<UTile*> Frontier;
// -- Adding elements: (element, priority)
Frontier.Push(TargetTile, 0.0f);
Frontier.Push(Grid->At(10, 16), 8.0f);
Frontier.Push(StartTile, 1000.0f);
// -- Iteration
while (!Frontier.IsEmpty()) {
UTile* Current = Frontier.Pop(); // Removes it from the top of the heap
Current->DoMagic();
}
4 Likes