list와 vector 비교 차이를 비교한 글들은 굉장히 많다.

Cpp STL을 기반으로 보통 쓰여진 글들이지만.

자료구조 더블링크드리스트와 동적 배열(실 언어들의 구현체)의 비교로 봐야한다.

많은 글들에서 메모리할당 해제 비용과 캐시 언급이 없어 아쉬워서 정리

벡터

• index 접근 가능
• 삽입시
  • 끝에 추가, 삭제만 하는 경우 일반적으로 O(1)
  • 중간 삽입, 삭제 : O(n)
  • 삽입시에 가끔 : 메모리 할당 비용 + 복사 발생 O(n)

리스트

• index 접근 불가
• 대부분 작업 O(1) (삽입 삭제)

많은 글들에서 이 정도 복잡도에 관해서 비교만 나와있는 상황.

사실 이 둘을 비교하기에는 복잡도보다는 메모리 할당, 해제 캐시 메모리 관점에서 접근하는것이 더 올바르다고 생각한다.

메모리 할당 해제 및 캐시의 관점에서

1. 구현상 노드 구조로 되어있는 리스트는 추가 삭제시에 힙 메모리 할당 해제가 발생한다

heap 메모리 관리는 간헐적으로 system call이 발생하고 굉장히 비용이 비싸다.

복잡도를 떠나 그냥 동작이 느리다.

리스트는 삽입 삭제는 벡터 끝 삽입, 삭제과는 비교도 안되게 비용이 비싸다.

자료구조 해제 비용도 원소별로 해제되기에 상대적으로 크다.

1. 힙 메모리 할당 해제, 노드 구조에 따른 원소당 메모리 오버헤드 발생 및 메모리 파편화 발생

이는 캐시라인 효율을 떨어뜨리고 메모리 점프 비용이 발생하며, 이는 원소 접근 비용 및 순회 비용이 상대적으로 크다.

그래서 성능을 굉장히 중시하는 곳에서는 대부분 벡터로 처리함.

벡터에 대한 몇가지 최적화 방법

1. 정렬이 필요할 때. 정렬을 맞춘답시고 중간삭제를 남발하는것보다 그냥 뒤에다 때려박고 정렬 한번하는게 나을 수 있다.
2. 메모리 재할당 및 복사 비용에 대한 해결.

메모리를 미리 크게 할당한다 (reserve), 여기서 메모리 할당 해제 비용 자체를 없애기 위해 캐싱을 사용할 수도있다.

1. 중간 삭제 비용 swap and pop_back (정렬이 깨지기에 사용은 제한적)

2. 여러 Queue 구조에서의 경쟁 문제

벡터를 두개 돌려쓰는 더블 버퍼링 기법 응용 가능

여기서 더 나아가면

메모리 응집성(효율) 및 메모리 jump 로 인해 해시 테이블보다 벡터가 낫다고 할 정도 (제한적인 케이스에 해당)