c++ - マップの値であるアイテムを消去する方法

Question

私はこのような地図を持っています:

std::map<unsigned,(string,timestamp)> themap.

しかし、マップ内の最も高い 1000 のタイムスタンプのみを保持することによって、マップのサイズを管理する必要があります。これを処理する最も効率的な方法は何ですか？

どうにかして上記の地図のコピーを

std::map<timestamp,(string,unsigned)> - erase elements not in top 1000, then massage this map back into original?

それとも他の方法ですか？

これが私のコードです。

/* map of callid (a number) to a carid (a hex string) and a timestamp (just using unsigned here)
   The map will grow through time and potentially grow to some massive amount which would use up all 
   computer memory.  So max sixe of map can be kept to 1000 (safe to do so).  Want to remove items 
   based on timestamp
*/
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>


typedef unsigned callid;
typedef unsigned timestamp;
typedef std::string carid;
typedef std::pair<carid,timestamp> caridtime;
typedef std::map<callid,caridtime> callid2caridmap;

int main() {

   //map of callid -> (carid,timestamp)
   callid2caridmap cmap;

   //test data below
   const std::string startstring("4559023584c8");
   std::vector<carid> caridvec;
   caridvec.reserve(1000);
   for(int i = 1; i < 2001; ++i) {
      char buff[20] = {0};
      sprintf(buff, "%04u", i);
      std::string s(startstring);
      s += buff;
      caridvec.push_back(s);
   }
   //generate some made up callids
   std::vector<callid> tsvec;
   for(int i = 9999; i < 12000; ++i) {
      tsvec.push_back(i);
   }

   //populate map
   for(unsigned i = 0; i < 2000; ++i)
      cmap[tsvec[i]] = std::make_pair(caridvec[i], i+1);

   //expiry handling
   static const int MAXNUMBER = 1000;

   // what I want to do is retain top 1000 with highest timestamps and remove all other entries.  
   // But of course map is ordered by the key
   // what is best approach.  std::transform??
   // just iterate each one.  But then I don't know what my criteria for erasing is until I have
   // found the largest 1000 items
   // std::for_each(cmap.begin(), cmap.end(), cleaner);

   //nth_element seems appropriate.  Do I reverse the map and have key as timestamp, use nth_element 
   //to work out what part to erase, then un-reverse the map as before with 1000 elements
   //std::nth_element(coll.begin(), coll.begin()+MAXNUMBER, coll.end()); 
   //erase from coll.begin()+MAXNUMBER to coll.end()

   return 0;
}

アップデート：

これが私が遊んでいる解決策です。

// as map is populated also fill queue with timestamp
std::deque<timestamp> tsq;
for(unsigned i = 0; i < 2000; ++i) {
   cmap[tsvec[i]] = std::make_pair(caridvec[i], i+1);
   tsq.push_back(tsvec[i]);
}
std::cout << "initial cmap size = " << cmap.size() << std::endl;


// expire old entries
static const int MAXNUMBER = 1000;
while(tsq.size() > MAXNUMBER) {
   callid2caridmap::iterator it = cmap.find(tsq.front());
   if(it != cmap.end())
      cmap.erase(it);

   tsq.pop_front();
}

std::cout << "cmap size now = " << cmap.size() << std::endl;

しかし、可能な代替案にはまだ興味があります。