std::map 的删除和插入效率


 
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include "datetime.h"
 
using namespace std;
 
//由两个整数合成一个64位的整数。
class CTimeId
{
 public:
  uint64_t  merge(int time,int uniqueid)
  {
   uint64_t newid = 0ll;
   const int SIZE = sizeof(int);
   char * p = (char *)&newid;   
   memcpy(p,&uniqueid,SIZE);
   //printf("%llu\n",t);
   
   memcpy(p + SIZE,&time,SIZE);
   //printf("%llu\n",t); 
   
   return newid;
  }
  
  int gettime(uint64_t &u64)
  {
   const int SIZE = sizeof(int);
   
   char * p = (char *)&u64;
   
   int time = 0;
   memcpy(&time,p + SIZE,SIZE);
   //printf("time=%d\n",time);
   return time;
   
  }
  
  void split(uint64_t &u64,int &time,int &uniqueid)
  {
   const int SIZE = sizeof(int);
   
   char * p = (char *)&u64;
   memcpy(&uniqueid,p,SIZE);
   //printf("uniqueid=%d\n",uniqueid);
   
   memcpy(&time,p + SIZE,SIZE);   
   //printf("time=%d\n",time);    
  }
};
 
 
int main()
{ 
 std::map<uint64_t,int> m;
 const int MAX = 1000000; 
 std::vector<uint64_t> del;
 std::vector<uint64_t> insert;
 //随机构造一堆数据
 for(int i = 0;i < MAX;++i)
 {
  CTimeId timeid;
  int now = ::time(0);
  if(i % 5)
  {
   now += i * 90;
  }
  if(i % 29)
  {
   now += i * 100;
  }
  
  if(i % 8)
  {
   now += i * 30;
  }
  
  if(i % 39)
  {
   now += i * 5;
  }
  
  uint64_t key = timeid.merge(now,i);
  
  if(i % 50 == 0)
  {
   del.push_back(key);      
   insert.push_back(key + i * 40);
  }
  
  m[key] = now;
 }
 
 std::map<uint64_t,int>::iterator it;
 int now = 0;
 for(it = m.begin();it != m.end();++it)
 {
  if(it->second < now)
  {
   std::cout<<"error"<<endl;
  }
  else
  {
   now = it->second;
  }
 }
 
 //统计删除和插入的效率
 CDateTime dtstart;
 std::cout<<del.size()<<","<<m.size()<<","<<dtstart.LongDateTime()<<endl;
 for(size_t i = 0,k = insert.size() - 1;i < del.size();++i,--k)
 {
  m.erase(del[i]);
  m.insert(make_pair(insert[i],0));
 }
 CDateTime dtend;
 std::cout<<del.size()<<","<<m.size()<<","<<dtend.LongDateTime()<<","<<dtend.SubMilliSecond(dtstart)<<endl; 
}
 
 
/*
g++ -I../include aa.cpp datetime.cpp -lrt -o aa;./aa    
20000,1000000,2013-01-24 15:18:34
20000,1000000,2013-01-24 15:18:34,73
 
g++ -I../include aa.cpp datetime.cpp -lrt -O2 -o aa;./aa
20000,1000000,2013-01-24 15:18:09
20000,1000000,2013-01-24 15:18:09,23
 
比较一下,对100W个元素的map,成功进行了2w次插入,2w次删除,使用编译器
O2优化,时间23毫秒,完全不优化,73毫秒。
*/

补充：软件开发 , C++ ,