array index

배열 인덱스 접근은 주소 계산 한 번으로 끝난다

원소가 같은 크기로 연속 배치되어 있으면 i번째 칸의 주소를 즉시 계산할 수 있다.

base index

연속 주소 슬롯

base+0a[0]
base+4a[1]
base+8a[2]
base+12a[3]
base+16a[4]
base+20a[5]

주소 계산식

base + index 3 × stride 4B = base + 12B
특징 효과 주의점
연속 배치 순차 접근이 캐시에 잘 맞는다. 중간 삽입은 뒤 원소 이동이 필요하다.
고정 stride 인덱스 접근이 O(1)이다. 원소 크기가 고정되어야 계산이 단순하다.
재할당 capacity를 늘리면 뒤에 더 넣을 수 있다. 재할당 순간 참조와 iterator가 깨질 수 있다.