Array ( )

C++ vector 구현하기

2017-06-22 09:27:59 | 조회수 6005


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; }
};


C++ vector 구현하기 - 알고리즘닷컴
14 개의 글