Sequence Container (vector, list, deque)

Container : 임의 타입의 객체를 보관
Iterator : 보관된 원소에 접근할 수 있는 반복자

복잡도 O(1) >  O(log n)  > O(n)  >  O(n log n) 순으로 빠르다.

Vector
임의의 위치에 있는 원소에 접근 시 O(1)
: 배열처럼 [ ] 이용, at( ) 함수를 이용

맨 뒤 원소의 추가시 amortized O(1)
맨 뒤 원소의 제거시 O(1)

임의의 위치에 원소의 추가, 제거 시 O(n)
: 원소들을 한 칸씩 이동시키는 복사가 필요함.

 list와 가장 큰 차이
: 임의의 원소를 접근할 수 있다
: 메모리 관점에서 연속된 공간을 차지

개별 원소에 대한 접근 속도와 컨터이너 끝에서의 삽입, 제거 속도는 가장 빠름

Deque
vector와 가장 큰 차이
: 연속된 메모리에 올라가 있지 않음.
: 첫 부분의 삽입, 제거의 효율이 더 높음.
: 동적확장/ 축소 방식
: 저장원소가 많고 메모리 할당량이 큰 경우 확장비용 절감

list와 가장 큰 차이
: 시작과 끝 위치가 아닌 곳에서의 삽입 제거 시 list에 비해 속도가 현저히 떨어짐

List
양방향 연결구조
: 어느 위치에서나 삽입, 제거가 빠름
: 컨테이너 자체에서는 시작 원소와 마지막 원소의 위치만을 기억하므로
: 임의의 위치에 있는 원소 접근을 위해서는 링크를 따라가야함
: sort, merge, splice 멤버 함수 제공

임의의 위치에 있는 원소에 접근 시 O(n)
임의의 위치에 원소 추가, 제거 시 O(1)

index 접근 불가능
상호 연결 정보를 위해 추가적인 메모리가 사용됨