목록2024/09/27 (1)
개발하는 리프터 꽃게맨입니다.
게임을 위한 자료구조) 빠른 순회, 빠른 탐색, 빠른 삭제, 빠른 삽입 설계도
1. 오브젝트는 이중으로 관리 1) 빠른 삽입, 삭제, 탐색을 위한 해쉬 테이블 2) 빠른 순회를 위한 오브젝트 벡터, 빠른 삭제를 위해 특수한 형태의 벡터를 사용함 2. 해쉬 테이블 키 : 오브젝트의 ID (ID는 uint64 이며 유일하다.) 값 : std::pair (배열의 인덱스, 오브젝트의 unique_ptr) 3. 벡터 단순한 일자형 벡터 캐쉬 히트가 높아서 순회속도가 빠르다. 4. 탐색 해쉬 테이블을 통한 탐색 5. 삽입 해쉬 테이블을 통한 삽입 -> O(1) 배열에 추가적으로 삽입하고 배열의 인덱스를 해쉬 테이블에 업데이트 -> O(1) 이 때 push_back을 사용하면 안됨 벡터의 맨 뒤 인덱스를 얻어냄 해당 인덱스의 요소가 nullptr면 대입 해당 인덱스의 요소가 nullptr가 아..
자료구조/자료구조 설계
2024. 9. 27. 16:05