vector & dequeue & list

1. vector

저장 원리 : 백터는 일반적인 배열처럼 연속된 메모리 공간을 찾아서 잡고 배열처럼 차근차근 인덱스로 저장한다.

이 말은 즉 배열처럼 operator[]로 접근이 가능하다는 소리이다. 

즉 백터는 동적으로 확장/가능이 가능한 dynamic array로 구현되어 있다.

 

강점 : 

1) 배열처럼 constant time 안에 인덱스 접근이 가능하다.

2)끝 부분에 삽입하는 연산은 reallocating이 발생하지 않는 한 constat time이다. reallocating 발생한다 하더라도 amortised constant time안에 수행가능하다.

3)일반적으로 vector는 list와 dequeue보다 random access time과 끝에서의 삽입 삭제가 빠르다. (하지만 상황이 어떠느냐에 따라서 달라질 수 있다.)

약점 :

컨터이너의 끝이 아닌 중간이나 처음의 삽입 삭제의 경우 메모리에 존재하는 연속된 데이터들을 옮겨줘야 하므로 다른 컨테이너에 비해 성능이 떨어진다.

언제 사용 ? access가 많이 발생하고 뒤에서의 삽입 삭제가 원활히 발생하는 경우에.

 

2. dequeue

기본적으로 dequeue는 vector of vectors라고 불리우는 컨테이너이다. chunk라 불리우는 vector의 pointer를 가지는 즉 다수의 chunk pointer를 array형식으로 가지는 pointer array map이다. 기본적으로 vector와 다른점은 vector같은 경우 크리가 다 찼을 경우 reallocating을 통해 새로운 메모리에 복사하는 과정을 거쳐야 하지만 dequeue는 새로운 chunk를 그냥 할당해주면 끝이다. map이 찼을 경우 메모리를 다시 할당해야 하는 경우가 있긴 하지만 amortised constant time안에 가능하다.

강점 : 

1)position index 접근이 가능하다.

2)시작과 끝 부분에 인덱스를 삽입/삭제하는 것이 빠르다

3)chunk만 할당하면 되므로 vector에 비해 확장비용이 저렴하다.

약점 :

1)위에 보는 것처럼 시작과 끝이 아닌 중간에 데이터의 삽입/삭제 같은 경우 성능이 현저히 떨어진다.

2)포인트 연산이 불가능하다.

*보통 queue나 stack같은 경우 dequeue가 기본 class이다.

 

3. list

doubly linked list로 구성되어 있다.

강점 : 

1)삽입/삭제의 경우 노드들을 순회하여 새로운 노드를 만들고 주소값만 link시켜주면 되기 때문에 search time+constant time으로 중간 삽입/삭제가 빠르다.

약점:

1)원소의 position index로 직접 접근이 불가능하다.
: 특정 원소에 접근하려면 처음이나 끝에서부터 선형 탐색을 하여야만 한다.

2)컨테이너 내 원소 순회는 forward / reverse 순회만 가능하며, 느리다. (선형 복잡도)

3)원소들간 상호 연결 정보를 위해 추가적인 메모리가 사용된다.

 

주의할 점 :

자료구조의 성능을 비교할 때는 원소의 크기, 지역성에 의한 캐시 미스를 잊지 말아야 합니다.
vector는 연속적으로 데이터를 저장하기 때문에 지역성이 높아 캐시 효율이 좋습니다.
그때문에 성능 테스트를 해보면 크기가 작은(원시 타입이나 간단한 구조체)에 대해서는 vector가 list에 비해
성능이 좋습니다.
반면에 list는 많은 상황에서 캐시 미스가 발생해 크기가 작은 원소에 대해서는 vector에 비해 느립니다.
그러나 원소의 크기가 커지게 되면 vector의 캐시 효율이 떨어지게 되므로 list가 상대적으로 성능이 좋아지게
됩니다.

 

출처 : https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl