BrowserUk,
My module Tie::Hash::Sorted does most of what you are asking for, albeit some stuff is "under the covers". You are welcome to abuse it in any way you want for your purposes or you can send me a feature request and I will do it when I have a chance.