[C++] vector

STL (Standard Template Library)
프로그래밍할 때 필요한 자료구조/알고리즘들을 템플릿으로 제공하는 라이브러리

 

vector : 동적 배열

 

알아볼 내용

- vector의 동작 원리 (size/capacity)
- 중간 삽입/삭제
- 처음/끝 삽입/삭제
- 임의 접근

 

기본적인 내부 동작

- 여유분을 두고 메모리를 할당한다

- 여유분까지 꽉 찼으면, 메모리를 증설한다

=> 기존에 쓰던 영역을 버리고 더 큰 영역을 할당받아서 쓴다

 

Q1) 여유분은 얼마만큼이 적당할까?

Q2) 증설을 얼마만큼 해야할까?

Q3) 기존의 데이터를 어떻게 처리할까?

 

실제 데이터가 있는 크기를 size, 여유분까지 해당하는 크기를 capacity라 칭한다.

capacity는 컴파일러에 따라 다른데, visual studio기준 1.5배씩 증가한다

데이터가 몇 개 정도 더 필요할지 예측할 수 없으니 미래 1.5배 정도 늘리는 것.

1개씩 늘린다면 push_back() 실행마다 기존 데이터를 이사 시켜야하는데, 1.5 ~ 2배씩 늘린다면 일정 capacity에 도달하면 이사 횟수가 점차 줄어들어 안정적이게 된다.

 

Q) 기존에 쓰던 메모리 공간에 동적할당을 추가로 받아 이어 붙으면 되지 않을까?

A) 그곳이 비어있다는 보장이없다. 이미 사용 중이라면 불가능 함. 그래서 증가된 capacity를 가진 새로운 공간을 받아 이사시키는 것

 

capacity는 늘어날 순 있지만, 내부적으로 다시 줄어들진 않는다.

=> 프로그래머가 capacity를 0으로 만들려면?

vector().swap(v);

임시적인 빈 vector를 만들어 기존 v와 swap한다.

 

메모리 블록에 연속하게 저장된다는 것은 장점이자 단점이 된다.

[ 장점 ]

- 모든 원소들이 하나의 메모리 블록에 "연속하게" 저장된다.

임의 접근이 가능하고, 연속 할당으로 인한 cache hit 덕분에 많지 않은 size일 경우 전체 순회가 빠르다.

[ 단점 ]

- 모든 데이터가 연속적으로 있을거라고 보장되어 있어야 하기 때문에 중간 삽입/삭제 연산 수행마다 밀거나 당겨줘야 한다

당길 때는 기존 메모리 공간에서 당기기만 함, 밀 때는 새로운 공간을 받아서 이사함

중간 삽입/삭제 : O(N)

처음 삽입/삭제 : O(N) (v[0]에 해당하는 중간 삽입/삭제와 동일함)

끝 삽입/삭제 : O(1)

 

처음 삽입/삭제는 비효율적이므로 vector 내부에서 push_front(), pop_front()을 지원하지 않는 이유를 추측할 수 있다.

Q) 끝 삽입은 항상 O(1)일까?

A) push_back() 실행시, size와 capacity가 동일할 경우 증설 작업이 필요해 내부에서 reserve()가 호출되므로 O(N) 추가 됨.

=> vector가 갖는 최대 크기를 프로그래머가 안다면, reserve() 통해 미리 크기를 할당받아둘 수 있다.

 

구현 연습

template<typename T>
class Vector
{
public:
    Vector() {}
    
    ~Vector()
    {
        if (_data)
            delete[] _data;
    }
 
    void push_back(const T& value)
    {
        if (_size == _capacity)
        {
            int newCapacity = static_cast<int>(_capacity * 1.5f);
            if (newCapacity == _capacity)
                newCapacity++;
 
            reserve(newCapacity);
        }
 
        _data[_size] = value;
 
        _size++;
    }
 
    void reserve(int capacity)
    {
        if (capacity <= _capacity) return;
 
        _capacity = capacity;
 
        T* newData = new T[_capacity];
 
        for (int i = 0; i < _size; i++)
            newData[i] = _data[i];
 
        if (_data)
            delete[] _data;
 
        _data = newData;
    }
 
    void clear()
    {
        if (_data)
        {
            delete[] _data;
            _data = new T[_capacity];
        }
 
        _size = 0;
    }
 
    T& operator[](const int idx) { return _data[idx]; }
 
    int size() const { return _size; }
    int capacity() const { return _capacity; }
 
private:
    T* _data = nullptr;
    int _size = 0;
    int _capacity = 0;
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    Vector<int> v;
 
    for (int i = 0; i < 100; i++)
    {
        v.push_back(i);
 
        cout << "v.size() : " << v.size() << " | " << "v.capacity() : " << v.capacity() << "\n";
    }
 
    v.clear();
 
    cout << "-- v.clear() --" << "\n";
    cout << "v.size() : " << v.size() << " | " << "v.capacity() : " << v.capacity() << "\n";
 
    return 0;
}

 

 

 

 

[ Reference : Rookiss의 C++ Part 3 자료구조 ]