3.Priority Queue , LRU Queue , Map Lib 추가 및 TestCode 작성.

1. Priority queue  Test Code

2.Lru queue Test Code 

3.Map Test Code 

test code 작성.

test code 작성

 

 

map 변경점

일년전에 구현한 코드라 이론을 다시 보면서 틀린 부분을 찾느라 좀 시간이 소요됐다.

1.const char* 특수화 처리함.

value = const char* 특수화 클래스

이렇게 한 이유는 value를 const char* 로 넣었을 때 소멸자에서 데이터를 처리할때 delete 가 아닌 nullptr 처리하도록 하기 위해서 이다.

 

일반 포인터는 아래의 특수화로 들어가서 delete data를 수행한다.

value 일반 포인터 특수화

2.iterator에 접근해서 GetPtr 받아오지 않고 iterator 내부에서 처리하도록 데이터를 보호함.

기존 코드

기존 코드에서는 Node 데이터 자체를 얻기 위해서 GetCurPtr 함수를 호출했다.

그런데 이렇게 하면 Node Class 의 모든 데이터를 외부에서 제약없이 접근하는 것이 마음에 들지 않았다.

그래서 GetKey, GetValue 로 함수를 나누어서 Node를 반환하는 것이 아니라 값 자체를 반환하도록 하였다.

변경된 코드

3.중복 데이터 생길 시 해당 node 를 delete 처리해주도록 함.(node 추가는 원래 안됐고 node delete가 안되어서 leak 됐음.)

값이 같은 경우 delete

4.map 내부에서 node가 삭제될때 value*도 같이 delete 할지 말지 정할수있도록 함.(기본 delete X)

is_InnerDelete 변수를 추가.

내부에서 node 삭제시 node의 data도 delete 할수 있게 옵션을 줌.

node 만들때마다 innerdelete 정보도 같이 넣는다.

포인터 특수화된 node는 소멸할 때 innerDelete 옵션을 체크해서 삭제하거나 안한다.

main에서 사용할때 예시.

5.red black tree 내부적으로 잘못 구현된 부분들 고쳤다.
  연산 후 is_extern 을 안풀어줬다거나 색상을 교환해야하는데 일방적으로 주고 끝났다던가 하는 오류
  (delete case4 , case1)

delete case 4 : is_extern =false 안해준 코드 수정함.

 

delete case1: 형재노드의 부모의 컬러와 형제 노드의 컬러를 교환해야하는데 형제 노드 컬러를 변경하지 않았던 문제 수정

 

예전에 RBT 만들때 참고한 영상은 아래 영상이다.

https://youtu.be/6drLl777k-E?si=AZ58jvcD3QbC3RjC