C++, STL-1 Array와 VECTOR와 LIST

STL Standard Template Library 

C++ 표준 템플릿 라이브러리를 의미한다. 

알고리즘, 컨테이너, 함수, 반복자 라는 네가지 구성 요소를 제공한다.

시퀀스 컨테이너 : vector, deque, list,

연관(Associative) 컨테이너 : map, multimap, hast_set, hash_map, hash_multiset, hash_multimap

컨테이너 어댑터(adaptors) : queue, priority_queue, stack 

Array 

스택에 연속된 공간이 할당된다. (STACK)

컴파일 타임에 메모리가 할당되므로 Fixed Size

Vector

Vector는 메모리 할당을 연속적으로 하고, List는 따로따로 할당을 한다.

힙에 연속된 공간이 할당된다. (HEAP)

Runtime에 메모리가 할당 되므로 flexible size 

dynamic array like C Array.

시간복잡도 

- Random Access - Constant O(1)

백터에 아무공간이나 접근하는 것은 O(1)의 시간 복잡도를 가진다.

- Insertion or removal of elements at the end - amortized constant O(1)

마지막 공간에 삽입하거나 제거하면 O(1)의 시간 복잡도를 가진다.

- Insertion or removal of elements - linear in the distance to the end of the vector O(n)

마지막 공간이 아닌 다른 공간에 삽입이나 삭제가 일어나면 삽입이나 삭제가 일어난 곳 부터 끝까지 O(n)의 시간복잡도를 가진다.

- find 의 경우 O(n) 하지만 연속적인 메모리 공간을 사용하므로 list보다 find를 수행하는 능력이 빠르다. 그러므로 99%는 vector를 사용하고 list는 잘 사용하지 않는다고 한다. 

size 는 실제크기

capacity는 실제 확보한 메모리 

 

List

forward_list의 경우 singly linked list(단방향리스트)이다.

더블링크드 리스트(양방향리스트)이다. 비연속적으로 메모리를 할당한다. 

시간복잡도 

- 어느공간에서 삽입과 삭제가 일어나든 O(1)의 시간복잡도를 가진다. (주소를 가르키는 방향만 바꿔주면 되기 때문이다.)

- 백터와는 다르게 O(1)의 랜덤 액세스는 불가능하다. 랜덤 엑세스는 O(n)이다.

- find의 경우 O(n)

 

시간복잡도 표	find	random access	I/O	I/O (end)
Array	O(n)	O(1)	인덱스를 안다면 O(1) 인덱스를 모른다면 O(n)	O(1)
Vector	O(n)	O(1)	O(n)	O(1)
List	O(n)	O(1)	O(1)	O(1)