C++ [STL] vector 구현

1. 정의

구현하고자 하는 자료형 vector를 아래와 같이 정의해보자.

A : 값을 저장하는 일차원 배열이다. 배열의 index는 0부터 시작하며, 배열의 최대 크기는 max_size이다. 따라서 A[0]부터 A[max_size-1]까지 총 max_size개의 값을 저장할 수 있다.
size : 현재 배열 A에 저장되어 있는 값의 개수를 나타낸다. 따라서 A[0]부터 A[size-1]까지 값이 저장되어 있다.
max_size : 배열 A가 최대로 저장할 수 있는 값의 개수를 나타낸다.

vector에 값을 추가하다보니, size가 max_size보다 더 커지는 경우를 살펴보자.

다섯번째 값을 추가하고 싶지만, A의 크기가 충분하지 않은 상태이다. 이와 같을 때에는 아래의 과정을 따른다.
1) 기존의 A 배열 크기 max_size의 2배 크기인 새로운 배열 A'을 생성한다.
2) A에 있던 값들을 A'의 같은 index에 순서대로 옮기고, 추가하지 못했던 값도 추가한다.

3) A에 대한 메모리를 해제하고, A'을 A로 취급한다.

2. 구현

3. 복잡도

1) 공간복잡도 : N개의 원소를 vector에 삽입하기 위해서 2N보다 작은 크기의 일차원 배열 A가 필요하다.
2) 시간복잡도 : N개의 원소를 vector에 삽입하기 위해 필요한 연산량을 계산해보자. 전체 연산은 값 복사를 위한 연산과 값 추가를 위한 연산으로 이루어져 있으므로 다음과 같다.