STL로 제공되는 vector의 핵심 기능을 간단하게 구현해 본다.(push(), size() 정도?)
push의 경우 배열이 꽉 찰 경우 그 크기를 2배로 늘리며 배열을 복사하며, 아닐 경우에는 그대로 넣는다.
이렇게 할 경우 복사하는 순간의 시간 복잡도가 $O(N)$ 이 되지만, 삽입할 때의 복잡도가 $O(1)$ 이므로
amortized O(1) 이라고 본다.
resize 등은 만들지 않았지만 같은 원리로 구현할 수 있다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
template<class T>
class vector
{
public:
T *data;
int capacity, sz;
vector(int initSize = 64)
{
data = new T[initSize];
capacity = initSize;
sz = 0;
for (int i = 0; i < initSize; i++) data[i] = 0;
}
T &operator[](int i){ return data[i]; }
void push_back(T value)
{
if (full())
{
T *temp = new T[capacity];
for (int i = 0; i < sz; i++)
temp[i] = data[i];
delete[]data;
capacity *= 2;
data = new T[capacity];
for (int i = 0; i < sz; i++) data[i] = temp[i];
delete[]temp;
}
data[sz++] = value;
}
int size(){ return sz; }
bool empty() { return !sz; }
bool full(){ return capacity == sz; }
};