This is really in reply to Re^8: Re-orderable keyed access structure?, but I'm breaking the thread structure here to go back one step and ask what it really is that you need to achieve. Maybe, if you state your actual problem, someone can propose a different way of looking at it that would indicate a data structure more directly suited to your ultimate goals.
Re^2: Re-orderable keyed access structure? f.ex makes me wonder whether the actual order is at all important, or whether you simply require it as a corollary of your way of looking at your problem. That description looks vaguely like you might want a heap instead of a list.
But I don't know, so I could be completely wrong on this, and therefor I'm asking for what it really is you're trying to solve.
Makeshifts last the longest.