게임을 위한 자료구조) 빠른 순회, 빠른 탐색, 빠른 삭제, 빠른 삽입 설계도

1. 오브젝트는 이중으로 관리
1) 빠른 삽입, 삭제, 탐색을 위한 해쉬 테이블
2) 빠른 순회를 위한 오브젝트 벡터, 빠른 삭제를 위해 특수한 형태의 벡터를 사용함

2. 해쉬 테이블
키 : 오브젝트의 ID (ID는 uint64 이며 유일하다.)
값 : std::pair (배열의 인덱스, 오브젝트의 unique_ptr)

3. 벡터
단순한 일자형 벡터
캐쉬 히트가 높아서 순회속도가 빠르다.

4. 탐색
해쉬 테이블을 통한 탐색

5. 삽입
해쉬 테이블을 통한 삽입 -> O(1)
배열에 추가적으로 삽입하고 배열의 인덱스를 해쉬 테이블에 업데이트 -> O(1)
이 때 push_back을 사용하면 안됨

벡터의 맨 뒤 인덱스를 얻어냄
해당 인덱스의 요소가 nullptr면 대입
해당 인덱스의 요소가 nullptr가 아니면 push_back

6. 삭제
해쉬 테이블의 키를 확인하고 배열로 접근 -> O(1) + O(1)
삭제할 요소를 얻어냄. 이를 ItemA 라고 함
배열의 맨 뒤에 있으나 nullptr가 아닌 요소를 얻어냄. 이를 ItemB 라고 함
ItemA자리에는 ItemB를 대입하고
ItemB자리에는 nullptr를 대입함. (Swap하는 느낌) -> O(1)

ItemB에서 오브젝트의 ID를 얻어내서 해쉬 테이블의 ItemB 요소로 접근 -> O(1)
ItemB 요소의 배열 인덱스를 수정함 -> O(1)

최종적으로 ItemA를 해쉬 테이블에서 제거하면서 메모리 해제 -> O(1)

삭제가 빈번할 시 배열의 맨 뒤에 nullptr가 쌓이게됨
제거하지 않아도 상관없긴함 어차피 오브젝트가 많이 생성될 시 nullptr를 덮어쓰기 때문임

필요하다면 Garbage를 삭제할 수 있도록 CleanGarbage 함수를 제공

7. 순회
벡터의 처음부터 nullptr 가 나올 때까지 순회
이러면 딱 유효한 포인터만 빠르게 순회하게 됨

8. 추가
중요한 것은 해쉬 맵에 배열의 인덱스를 잘 매핑해야 한다는 것 (동기화 문제)
또, 배열에는 유효한 요소만 있는 것이 아니라 nullptr도 존재함
그래서 배열은 정확한 tail을 가리키고 있어야한다.

9. 성능 판가름 요소는 오로지 빠른 해쉬 테이블

10. (내 생각엔..) 유일한은 큰 메모리 복잡도
단, 오브젝트의 ID를 가지고 있어야만 위와같은 성능이 나옴
그렇기 때문에 오브젝트를 제거할 때 다른 객체에서 대신 지워주는게 아니라 자기가 자신을 직접 지워야함
만약, 특정 오브젝트를 찾고 싶다면 O(N)의 복잡도가 필요함