“腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。”

#include <algorithm>
#include <ctime>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
void timestamp()
{
  time_t t = time(0);
  cout << ctime(&t) << endl;
}
// 模拟时钟
class PseudoTimer
{
  int m_us;
public:
  PseudoTimer() : m_us(0) {}
  int getMicroseconds() { return m_us += (rand() % 100); } // 登录平均间隔：1000000 / 20000 = 50微秒
};
/*
  hash表，表中保存最近一次登录时间
  但这个表可能会增长（有用户长时间不登录），需要定时清除其中的旧记录
  QQ号已经到10位了，8字节长整数保存
*/
class HotUserMonitor
{
  typedef long long   QQ_t;
  struct UserStatus
  {
    int   last_login_time;
    bool  is_hot;
    UserStatus(int t, bool h) : last_login_time(t), is_hot(h) {}
  };
  map<QQ_t, UserStatus>   m_cache;
  static int const US_IN_5_MINUTES = 1000000 * 60 * 5;
public:
  void login(QQ_t qq, int now)
  {
    map<QQ_t, UserStatus>::iterator p = m_cache.find(qq);
    if(p == m_cache.end()){ // qq号不在缓存中：保存时间、冷用户
      m_cache.insert(make_pair(qq, UserStatus(now, false)));
    }
    else{ // 命中
      p->second.last_login_time = now; // 更新最后登录时间
      p->second.is_hot = ( (now - p->second.last_login_time) <= US_IN_5_MINUTES); // 超时：冷却
    }
  }
  void scan_and_clean(int now)
  {
    int host_user_count = 0;
    for(map<QQ_t, UserStatus>::iterator p = m_cache.begin(); p != m_cache.end(); ){
      if( (now - p->second.last_login_time) <= US_IN_5_MINUTES){
        if(p->second.is_hot){
          ++host_user_count;
          //cout << p->first << ' ' << p->second.first << ' ' << p->second.second << '/n'; // 热用户太多
        }
        ++p;
      }
      else{ // overtime
        m_cache.erase(p++);
      }
    }
    cout << "hot user count: " << host_user_count << endl;
  }
};
int main()
{
  srand(time(0));
  PseudoTimer pt;
  HotUserMonitor hsm;
  int const LOGIN_COUNT_IN_5_MINUTES = 20000 * 60 * 5;
timestamp();
  for( int i = 0; i < LOGIN_COUNT_IN_5_MINUTES; ++i){ // 模拟6000000次登录事件（20000 * 5 * 60）
    hsm.login(rand() * rand(), pt.getMicroseconds());
  }
timestamp();
  hsm.scan_and_clean(pt.getMicroseconds());
timestamp();
  return 0;
}