I had it as a vector for that reason.  But since I had to insert more often, I figured the perf tradeoff was closer and the code was much clearer using a list.

It's already much faster than before with the priority outside the object, but if it shows up we can probably try to fine tune it here.  I've read STL lists are far from ideal perf wise.

-[Unknown]