题目

    浏览器有一个cache，可以存放M(M <= 5000) 个url地址（url为长度小于30的字符串）。现在进行N(N <= 20000)次访问，每一个访问，如果访问的url在cache中存在，则输出Cache，如果不在cache中存在，输出Internet，且从cache中删除一个最近最少访问的url，然后将该新访问的url添加到cache中。

分析

    LRU cache类似的题目，维持一个unordered_map记录< url, iterator in cache list>，以及一个 list< string> 用作cache（因为list相比较vector，deque，queue等容器，它从中间删除一个元素的时间复杂度为O(1)). 

    如果url在< url, iterator in list>中存在，则将url在list中的节点提前到list的头部，并更新 < url, iterator in list>；     如果url在容器中不存在，（1）如果unordered_map< url, iterator in list>的大小为M，则需要删除list中尾部的url，同时将 unordered_map< url, iterator in list>中对应的项一块删除。（2）如果unordered_map< url, iterator in list>的大小小于M，则直接加入list头部，并设置unordered_map< url, iterator in list>

实现

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;list
            
              cache;unordered_map
             
              ::iterator> str_it_map;int main(){ int n, m; char url[50]; scanf("%d %d", &n, &m); getchar(); for (int i = 0; i < n; i++){ scanf("%s", url); if (str_it_map.find(url) == str_it_map.end()){ if (str_it_map.size() == m){ str_it_map.erase(*(--cache.end())); cache.erase(--cache.end()); } cache.push_front(url); str_it_map[url] = cache.begin(); printf("Internet\n"); } else{ cache.erase(str_it_map[url]); cache.push_front(url); str_it_map[url] = cache.begin(); printf("Cache\n"); } } return 0;}