C++ vector 구현하기


작성일 : 2017-06-22 09:27:59
조회수 : 3424


본문

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 구현하기 - 알고리즘닷컴
알고리즘 문서에서는 다양한 알고리즘 개념들을 포스팅 하는 곳입니다.