[ STL ] 표준 시퀀스 컨테이너(vector, deque, list)

컨테이너는 같은 타입을 저장, 관리할 목적으로 만들어진 클래스입니다. 컨테이너는 2가지로 나뉩니다.

-표준 시퀀스 컨테이너

-표준 연관 컨테이너 

시퀀스 컨테이너는 vector, deque, list 3가지가 있습니다. ->vector deque는 배열기반, list는 노드기반 컨테이너

연관 컨테이너는 set, multiset, map, multimap 4가지가 있습니다. -> 전부다 노드기반 컨테이너

[ 시퀀스 컨테이너 ]

시퀀스 컨테이너는 차례차례 원소를 추가하고 제거하는 push_back()과 pop_back()을 가지며 첫 원소와 마지막 원소를 참조하는 front()와 back()을 가집니다. 또한, 지정한 위치에 원소를 삽입할 수 있는 insert()를 가집니다.

> vector

- vector는 앞쪽이 막혀 있는 형태로, 앞쪽에는 원소를 추가/제거할 수 없으며, 뒤쪽에만 추가/제거가 가능합니다.(다른 시퀀스 컨테이너list, deque는 앞쪽에 원소를 추가/ 제거 할 수 있는 push_front, pop_front()를 가집니다. 

- capacity()는 vector만이 가지는 멤버함수입니다.  vector는 배열기반 컨테이너이면서, 원소를 컨테이너에 계속 추가할 수 있는 컨테이너입니다. 배열기반이므로 연속한 메모리를 1번에 할당하지만, 계속 원소가 추가되면 메모리를 재할당 해야하는데 vector는 메모리를 새로 재할당하고 원소를 전부 복사합니다. 그러므로 리 메모리를 할당할 수 있는 메모리 예약함수 reserve() 함수로 넉넉한 메모리를 확보하여 재할당하는일이 없도록 해야합니다. 

- vector는 메모리 재할당시 메모리의 크기capacity를 (이전capacity + (이전capacity/2)) 만큼 할당합니다. 어떤 컴파일러는 2배로 확장하는 컴파일러도 있습니다. 

장점 : 개별원소들을 position Index로 접근이 가능하다. (O(1)) 상수복잡도 

원소를 컨테이너의 끝에 삽입/제거하는것이 빠르다(상수-아모타이즈드 복잡도)

어떠한 순서로도 원소들을 순회할 수 있다. (로그복잡도)

일반적으로 vector는 다른 deque, list에 비해 개별원소에 대한 접근속도와 컨테이너의 끝에서 삽입/제거하는 속도가 가장 빠르다. 

(상황별로 다를 수 있음) 

단점: 컨테이너의 끝 위치가 아닌곳에 삽입/제거 수행시 성능이 매우 떨어짐

 

>deque 

- deque도 시퀀스컨테이너이며 배열기반 컨테이너이기 때문에 vector와 크게 다른점은 없다.

다른점은 메모리 블록 할당 정책이다.  vector의 장점이자 단점인 하나의 메모리블록 할당 정책은 배열처럼 정수 연산만으로 원소에 접근하고 빠르게 값을 읽고 쓸 수 있다. 하지만 새로운 원소가 추가 될 때 메모리 재할당과 원소복사로 인해 성능이 저하된다.

- deque는 여러 개의 메모리 블록을 할당하고, 사용자에게는 하나의 블록처럼 보이게 하는 정책을 사용한다. 

원소 추가시 메모리가 부족하다면 일정한 크기의 새로운 메모리블록을 할당하여 이전 메모리를 제거하거나 이전 원소를 복사하는 연산을 수행하지 않는다.

이러한 방식의 장점은 저장원소가 많고 메모리할당량이 큰 경우 vector에 비해 확장비용이 절감된다. (전체가 재할당되기 보다, 늘어나야 할 크기만큼 chunk가 하나 더 할당되면 그만이므로) 

단점은 컨테이너 처음부터 끝까지 연속 메모리 공간이 아니므로, vector에서가능했던 원소들간 포인터 연산이 불가능하다.

- deque는 앞쪽에 원소를 추가/ 제거 할 수 있는 push_front, pop_front()를 가집니다. 

- 원소삽입시 앞과 뒤 원소중 적은 원소를 가진 쪽으로 밀려나게 된다. 

장점 : 개별원소들을 position Index로 접근이 가능하다. (O(1)) 상수복잡도 

원소를 컨테이너의 끝 뿐 아니라 앞에서도 삽입/ 제거하는것이 빠르다. 

어떠한 순서로도 원소들을 순회할 수 있다. (로그복잡도)

단점: 컨테이너의 끝 위치가 아닌곳에 삽입/제거 수행시 성능이 매우 떨어짐 

 

>list

- vector와 deque와는 다르게 노드기반 컨테이너이기 때문에 원소가 노드단위로 저장되며 이중연결 리스트로 구성된다.

[ ]연산자와 at()연산자가 없으며 임의접근 반복자가 아닌 양방향 반복자를 제공한다. 그래서 원소를 탐색하려면 ++, --연산을 사용해야 한다.

앞/뒤로 원소를 추가할 수 있다. push_front, push_back, 시퀀스컨테이너이므로 front()와 back()함수로 가장 첫 원소와 뒤 원소를 반환하는 함수를 제공한다.

- list의 가장 큰 특징 중 하나는 순차열 중간에 원소를 삽입/삭제 하여도 상수시간복잡도의 수행성능을 보인다는 점이다.

배열기반 컨테이너(vector/deque)처럼 원소를 밀어내지 않고 노드를 서로 연결하기만 하면 되기 때문이다.

- 또한, 삽입/제거동작은 반복자를 무효화 시키지 않는다. 반복자가 가리키는 원소 자체가 제거되지 않는 한 반복자가 가리키는 원소는 그대로 존재한다.

- 하지만 배열기반 컨테이너의 반복자는 원소의 삽입과 제거 동작이 발생하면 메모리가 재할당되거나 원소가 이동할 수 있으므로 반복자가 무효화된다. 

- 순차열 중간에 삽입/제거가 빈번하게 발생하며, 원소의 상대적인 순서가 중요하다면 list컨테이너를 사용하면 된다.

다른 list와 결합할 때에도 좋은 컨테이너이다. 노드의 연결연산(상수시간)만으로 두 리스트를 하나의 리스트로 결합할 수 있다.

장점 : 컨테이너의 어느 위치에서도 삽입/제거가 빠르다(상수복잡도)

원소들의 컨테이너 내 순서이동이 빠르다(상수복잡도)

vector와 deque와 다르게 list의 가장 큰 강점은 컨테이너 내 어느위치에서도 원소의 삽입 제거가 빠르다는 것이다. 

단점: position index로 직접 접근이 불가하다.(선형탐색으로 접근해야함. 선형복잡도)

원소들간 상호 연결정보를 위해 추가적인 메모리가 사용된다. (원소수가 적을수록 상대비율은 올라감)