Top Mud Sites Forum - View Single Post

Rhuarc · 03-05-2005, 06:26 PM

priority_queue is typically an adapted vector, and is little more than a sorted vector, but yes, you could easily implement your own heap based priority_queue in just a few lines of code. However, the lack of iterators is the sole reason that priority_queue exists at all. They were removed for a reason.

I'm curious though, which do you think would be more expensive; iterating through a few thousand list elements every few seconds? or sorting a few thousand list elements several times, every few seconds? (every insert into the priority queue is going to cause the queue to be resorted (or resized, if the element is inserted into the proper location to keep the list sorted)).

I still maintain that a (standard) priority_queue is not an efficient data structure for this. While yes, it's true that lookups will be faster, inserts and deletes will be much slower, and in an event system, you are going to have alot of inserts and deletes.

You could certainly roll your own, but personally, I would wait and see if the performance merits it. (follow the 80/20 rule).

03-05-2005, 06:26 PM	#7
Rhuarc Member Join Date: Jul 2003 Posts: 50	priority_queue is typically an adapted vector, and is little more than a sorted vector, but yes, you could easily implement your own heap based priority_queue in just a few lines of code. However, the lack of iterators is the sole reason that priority_queue exists at all. They were removed for a reason. I'm curious though, which do you think would be more expensive; iterating through a few thousand list elements every few seconds? or sorting a few thousand list elements several times, every few seconds? (every insert into the priority queue is going to cause the queue to be resorted (or resized, if the element is inserted into the proper location to keep the list sorted)). I still maintain that a (standard) priority_queue is not an efficient data structure for this. While yes, it's true that lookups will be faster, inserts and deletes will be much slower, and in an event system, you are going to have alot of inserts and deletes. You could certainly roll your own, but personally, I would wait and see if the performance merits it. (follow the 80/20 rule).