填空题

关联容器map设计

Question

关联容器map保存<key, value>数据，能通过key快速存储或查找记录。请设计一个map，能够满足以下要求：

1. map的容量size是一个固定值N，即map最多保存N个<key, value>记录；

2. map insert一个<key, value>前，首先判断这个key是否已经在map中存在：

   1) 如果存在：记这个已存在的记录为<key, old_value>，若old_value<value，则把old_value更新为value；否则，不做更新。

   2) 如果不存在：

       若size<N，则执行map的insert，保存这个<key, value>，且size+=1；

       若size==N，先淘汰掉一个更新时间最早的记录，再执行map的insert，保存这个<key, value>，size保持为N不变。

说明：记录的更新时间默认为其被insert进map的时间，之后的某一时刻T，如果这个记录的value被更新，那么，该记录的更新时间就变为T。

输入描述： 第一行是map的最大size N（N<=200000），之后每一行都为"Key Value"，其中Key为一个字符串（长度<16），Value为无符号整数(unsigned int)，Key和Value之间用空格分隔。输入样例： 2 10_123_50_A0 1566918054 10_123_50_A1 1566918054 10_123_50_A1 1566918055 10_123_50_A3 1566918055 10_123_50_A4 1566918056 输出描述： 输出为map insert的过程中被淘汰掉的记录（不输出value被更新的记录），每行为"Key Value", 和输入文件的"Key Value"格式相同。输出样例 10_123_50_A0 1566918054 10_123_50_A1 1566918055