데이터 구조 LRUCache (Least Recently Used – 최근 최소 캐 시 사용)

제목 요구:
      데이터 구 조 를 설계 하여 LRU Cache 기능 (Least Recently Used – 최근 최소 캐 시 사용) 을 실현 합 니 다.다음 두 가지 동작 을 지원 합 니 다: get 과 put.『 8194 』 int get (int key) – key 가 존재 하면 key 에 대응 하 는 값 value (항상 0 이상) 를 되 돌려 줍 니 다.키 가 존재 하지 않 으 면 - 1 을 되 돌려 줍 니 다.      void put (int key, int value) – 키 가 존재 하지 않 으 면 value 를 삽입 합 니 다.키 가 존재 한다 면, 원래 존재 하 던 값 을 value 로 대체 합 니 다.용량 이 제한 되면 LRU Cache 는 새 요 소 를 삽입 하기 전에 최근 에 가장 적 게 사용 한 요 소 를 삭제 해 야 한다.      "사용" 의 정의 에 각별히 주의 하 십시오. 새로 삽입 하거나 키 를 가 져 오 는 것 은 한 번 사용 되 는 것 으로 간주 합 니 다.이미 존재 하 는 값 을 교체 하여 업데이트 합 니 다. 사용 되 지 않 습 니 다.『 8194 』 제한: O (1) 의 시간 복잡 도 에서 상기 2 가지 조작 을 완성 하 십시오.
입력 설명
      첫 줄 은 하나의 정수 n 을 읽 어 LRU Cache 의 용량 제한 을 나타 낸다.두 번 째 줄 부터 파일 끝까지 한 줄 마다 한 개의 조작 을 대표 합 니 다.      각 줄 의 첫 번 째 문자 가 p 이면 이 문자 뒤에 두 개의 정수 가 따라 put 작업 의 key 와 value 를 표시 합 니 다.      각 줄 의 첫 번 째 문자 가 g 이면 이 문자 뒤에 1 개의 정 수 를 따라 get 작업 의 key 를 표시 합 니 다.
출력 설명
      입력 중 get 작업 이 나타 나 는 순서에 따라 행 출력 get 작업 의 결 과 를 되 돌려 줍 니 다.
예시:
입력: 2 p 1 p 2 g 1 p 2 102 p 3 g 1 g 2 g 3 출력: 1 1 - 1 3
문제 풀이 방향:
      put (key, value) 는 O (1) 의 시간 내 에 완 성 됩 니 다. STD 의 한 용기: 양 끝 링크 list. list 가 [] 연산 자 를 다시 불 러 오지 않 았 기 때문에 O (1) 내 에서 찾기 위해 다른 용 기 를 사용 할 수 있 습 니 다: orderedmap。'사용' 요 소 를 사용 할 때마다 이 요 소 를 링크 의 첫 부분 으로 조정 합 니 다. 그러면 용량 을 초과 할 때 링크 끝의 요소 와 map 에 대응 하 는 값 을 직접 삭제 합 니 다.
리스트 소개:
      list 는 일종 의 서열 식 용기 다.      list 용기 가 완성 하 는 기능 은 실제 적 으로 양 방향 링크 와 매우 비슷 하 다. list 중의 데이터 요 소 는 링크 포인터 로 논리 적 의미 의 선형 표, 즉 list 도 링크 의 주요 장점 을 가진다. 즉, 링크 의 모든 위치 에서 요소 의 삽입, 삭제 작업 을 하 는 것 이 빠르다.      list 요소 노드 가 연속 적 인 메모리 에 요구 하지 않 기 때문에 list 에서 빠 른 랜 덤 액세스 가 지원 되 지 않 기 때문에 교체 기 에 대해 서 는 '+' 또는 '–' 작업 을 통 해 교체 기 를 후계 / 전구 노드 요소 로 이동 할 수 밖 에 없습니다.교체 기 를 + n 또는 n 으로 조작 할 수 없다 는 점 은 vector 등 과 다른 점 입 니 다.

begin() #             iterator
rbegin() #  list       
end()  #  list       iterator
push_back() #     list   
push_front() # list       
empty()  #  list    
resize() #  resize(n) list        n   ，         ，                T()     list  。    resize(n,val)，            T(val)        ，      
clear() #  list      
front() #  list          
back() #  list            
pop_back() #         
pop_front() #         
swap() #      ,list1,swap(list2) swap(list1,list2)     list1 list2   
splice() #      
/**
  list            ，      list，       
dest_list.splice(iterator position,list& source_list) # source_list        dest_list position   
dest_list.splice(iterator position,list& source_list, iterator it)# source_list it         dest_list position   
dest_list.splice(iterator position,list& source_list, iterator first,iterator last)# source_list first last      dest_list position  

##  
#include
#include 
using namespace std;
int main()
{
	listlist1,list2;
	for(int i=1;i<=4;i++) {
		list1.push_back(i);
		list2.push_back(i+10);
	}
	// list1 1 2 3 4
	// list2 11 12 13 14
	list::iterator it=list1.begin();
	it++;
	list1.splice(it,list2);//1 11 12 13 14 2 3 4
	if(list2.empty()) cout<::iterator it=list1.begin();it!=list1.end();++it) cout<::iterator it=list2.begin();it!=list2.end();++it) cout< > list3;
	for(i=1;i<=3;i++)
		list3.push_back(make_pair(i,i+3));
	list >::iterator iter=list3.begin();
	cout<first<second<

unordered_지도 소개
1. 맵 과 의 차이
『 8194 』 맵 의 내부 실현 은 빨 간 검 은 나무 (빨 간 검 은 나 무 는 엄격 한 균형 이 진 검색 트 리) 이기 때문에 이 용 기 는 자동 으로 정렬 하 는 기능 을 가지 고 맵 내부 의 모든 요 소 는 질서 가 있 습 니 다.맵 에 대한 모든 작업 은 빨간색 과 검은색 트 리 를 기반 으로 하기 때문에 많은 작업 은 O (logn) 의 시간 내 에 완성 할 수 있 고 맵 은 요소 순서 에 대한 요구 가 있 는 장소 에 적 용 됩 니 다.      단점: 붉 은 검 은 나무의 노드 는 노드 지침 과 데이터 영역 을 저장 해 야 하기 때문에 붉 은 검 은 나무의 공간 비용 이 비교적 크다.   unorder_map 의 내부 실현 은 해시 표 이 고 열 린 링크 주소 지정 법 으로 충돌 문 제 를 해결 하기 때문에 요소 의 검색 속 도 는 O (1) 에 달 할 수 있 고 검색 작업 이 비교적 높 은 장소 에 적용 된다.단점: 해시 표 의 시간 복잡 도가 비교적 높다.
2. 사용

find(key) #  key       ，       end()  ，  map    key。
count(key) #  key map      ，   0  key  map 
iterator erase(const_iterator pos ) #  map pos    
iterator erase(const_iterator first, const_iterator last );#  map first last    
size_type erase(const key_type& key )#    key    。
begin() 　　#              
end() 　　   #               
cbegin()　   #               （const_iterator） 
cend() 　　 #                
insert()  　　#     
/**
unordered_map         ，      ，           。
unordered_map::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair) 
it->first;               //   (*it).first   (the key value)
it->second;              //  (*it).second  (the mapped value) 
**/

구현 코드:

#include 
#include 
#include 
#include 
#include 
using namespace std;
class LRUCache{
private:
	int cap;
	list> L;
	unordered_map>::iterator> m;
public:
	LRUCache(int capacity){
		cap=capacity;
	}
	int get(int key){
		auto it=m.find(key);
		if(it == m.end()) return -1;
		L.splice(L.begin(),L,it->second);
		return it->second->second;
	}
	void put(int key,int value){
		auto it=m.find(key);
		if(it != m.end()) {
            it->second->second=value;
        }else{
            L.push_front(make_pair(key,value));
            m[key]=L.begin();
        }
		if(m.size() > cap){
			int k=L.rbegin()->first;
			L.pop_back();
			m.erase(k);
		}
	}
};
int main(){
    int n;
    cin>>n;
    LRUCache L(n);
    string cmd;
    char commond;
    while(getline(cin,cmd)){
        istringstream iss(cmd);
        iss>>commond;
        if(commond=='p'){
            int key,val;
            iss>>key>>val;
            L.put(key,val);
        }else if(commond=='g'){
            int key;
            iss>>key;
            int val=L.get(key);
            cout<

주의 하 다.
『 8194 』 는 줄 별로 입력 을 읽 고 각 줄 의 입력 은 getline (cin, cmd) 을 통 해 cmd 에 읽 은 다음 istringstream iss (cmd) 를 통 해 문자열 입력 흐름 을 구성 한 다음 에 문자, 정 수 를 해석 합 니 다.