[boost] Fastest Data-structure maybe from STL or Boost ..!!

All, I wish to record 1000 real time data which need to be in sorted order. I used STL MAP which sorts using KEYS and than sorted the value using STL VECTOR, the complete scenario give me almost 6ms of time analysis. The TARGET is to achieve almost 1.5 - 2.0 ms. Also, once this data structure is completely filled I want to delete the first data and replace it with the new data. Can I have the fastest data structure (STL or BOOST) techniques for the same. ~ Thanks!!