I have implemented some thing very similar. Implementing the iterators is the most challenging. I used boost::iterator_facade to implement the iterators. Using boost::iterator_facade you can easy adapt any cached on disk data structures to have a STL container interface.