[DS] C++ Deque 랜덤 액세스 O(1)?

일단 C++ 덱은 연속된 메모리 블록을 안 씀

1. 고정 크기의 배열 블록 여러개

2. 블록들을 가리키는 포인터 배열

블록 -> 블록 -> 블록 -> .. 이런 방식인데

포인터0 -> 블록0

포인터1 -> 블록1 이런식으로 가리킴

 

그리고 요소 접근 시 다음과 같은 연산

1. 인덱스를 블록 크기로 나눈 몫

2. 인덱스를 블록 크기로 나눈 나머지

이렇게 접근

 

그냥 inode 접근 스럽다