Vector vs List 차이와 캐시적중률

Vector

• 연속적으로 메모리를 할당
• reserve개념으로 메모리영역 선할당 정책(1.5배 ~ 2배의 메모리공간 할당)을 통해 요소를 추가할 때마다 new가 일어나지 않음
• 캐시 적중률이 높아서 속도가 빠르다
• 포인터++ 연산으로 요소에 접근할 수 있어서 랜덤 엑세스가 가능하다
• capacity가 꽉 차면 전체 메모리 재할당이 일어난다

 

 

List

• 비연속적으로 메모리 할당
• 요소를 추가할 때마다 new 일어난다
• 노드 기반의 구조로 앞과 뒤의 요소를 가리키는 오버헤드가 필요하다
• Vector의 임의접근이 불가함, Iterator를 통해 순차적으로 접근해서 요소를 찾아야 한다
• 캐시 적중률이 낮다

 

캐시 적중률

CPU의 연산에 필요할 때마다 메모리에서 데이터를 가져옴

근데 Main memory or RAM은 CPU보다 느려서 보다 빠른 메모리 필요함

 

그것이 캐시메모리

CPU는 주로 쓰는 데이터 메모리에서 계속 가져오는 것이 아니라

캐시 메모리에 저장해둠

 

다음에 데이터를 가져올 때 CPU의 접근 순서는

캐시 메모리 > 메모리 > 보조기억장치

 

필요한 데이터가 캐시에 있으면 적중, 없으면 실패로

캐시 적중률을 높이면 속도가 빠름