제공되는 자료 구조를 직접 구현해보면 그 동작 방식을 더 잘 이해할 수 있다.
그래서 선형 자료구조를 각각 구현해보고자 한다. 이번 포스트에서는 동적 배열을 구현하는 과정에 대해 정리해보고자 한다.
동적 배열 (vector)
동적 배열 자체에 대한 설명은 다음 포스트를 참고하면 된다.
2024.02.07 - [c++/기초] - c++ 기초 - 벡터 (vector)
c++ 기초 - 벡터 (vector)
STL? Standard Template Library의 약자로 미리 구현된 자료구조와 알고리즘들을 템플릿으로 제공하는 라이브러리이다. STL은 크게 알고리즘, 컨테이너, 함수자, 반복자(iterator)로 구성되어 있다. 컨테이
dodongs-development-farm.tistory.com
vector 자체는 굉장히 다양한 기능이 있는데 그 중 대표적인 함수들을 구현해보고자 한다.
멤버 변수
private:
T* _data;
int _size;
int _capacity;
생성자와 소멸자
생성자에서는 멤버 변수를 초기화하는 값들을 넣어주고, 소멸자에서는 요소들의 메모리를 해제해준다.
public:
Vector() : _size(0), _capacity(0), _data(nullptr)
{
}
~Vector()
{
if (_data)
{
delete[] _data;
}
}
1) reserve
주어진 capacity만큼 메모리 공간을 잡은 후 기존의 데이터들을 복사해서 옮기는 작업을 진행한다. 즉, 주어진 capacity로 메모리를 증설하는 작업이다.
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; // 교체
}
2) resize
기존 vector 크기 < 매개변수 size인 경우 size만큼 capacity를 지정한다음 늘어난 공간에 기본 생성자로 채워준다.
기존 vector 크기 > 매개변수 size인 경우 size 만큼의 요소만 남기고 나머지는 없앤다. (이때 capacity는 따로 변하지 않는다.)
void resize(int size, T val = T())
{
T* newData = new T[size];
_size = _size > size ? size : _size; // 결국 더 작은 공간을 남기므로!
_capacity = size;
for (int i = 0; i < size; i++)
{
newData[i] = _data[i];
}
for (int i = _size; i < _capacity; i++) // (기존 벡터 크기 < 매개변수 size) => value의 기본 생성자로 나머지 채워준다.
{
newData[i] = val;
}
delete[] _data;
_data = newData; // 교체
_size = size;
}
3) push_back
push_back은 배열의 뒤에 요소를 집어넣는 작업이다. 여기서 크게 고려해야할 점은 size와 capacity의 비교이다. 만약 size가 capacity와 같다면 더 큰 capacity로 메모리를 잡고 옮긴 후 요소를 집어넣어야한다. 메모리를 더 잡아야하는 경우 앞서 구현한 reserve함수를 사용한다.
void push_back(const T& value)
{
if (_size == _capacity) // 메모리 증설 필요
{
int newCapacity = static_cast<int>(_capacity * 1.5);
if (_capacity == newCapacity)
{
newCapacity++;
}
reserve(newCapacity);
}
_data[_size] = value; // 데이터 뒤에 붙이기
_size++;
}
4) clear
capacity는 건들지 않고 size를 0으로 만들어주는 작업이다. 즉, 벡터에 있는 모든 요소들을 제거해준다. (size가 데이터 요소 개수이므로)
void clear()
{
if (_data)
{
delete[] _data;
_data = new T[_capacity];
}
_size = 0;
}
5) 그 외
T& operator[] (const int pos) { return _data[pos]; }
int size() { return _size; }
int capacity() { return _capacity; }
최종 코드
template<typename T>
class Vector
{
public:
Vector() : _size(0), _capacity(0), _data(nullptr)
{
}
~Vector()
{
if (_data)
{
delete[] _data;
}
}
void push_back(const T& value)
{
if (_size == _capacity) // 메모리 증설 필요
{
int newCapacity = static_cast<int>(_capacity * 1.5);
if (_capacity == newCapacity)
{
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 resize(int size, T val = T())
{
T* newData = new T[size];
_size = _size > size ? size : _size; // 결국 더 작은 공간을 남기므로!
_capacity = size;
for (int i = 0; i < size; i++)
{
newData[i] = _data[i];
}
for (int i = _size; i < _capacity; i++) // (기존 벡터 크기 < 매개변수 size) => value의 기본 생성자로 나머지 채워준다.
{
newData[i] = val;
}
delete[] _data;
_data = newData; // 교체
_size = size;
}
void clear()
{
if (_data)
{
delete[] _data;
_data = new T[_capacity];
}
_size = 0;
}
T& operator[] (const int pos) { return _data[pos]; }
int size() { return _size; }
int capacity() { return _capacity; }
private:
T* _data;
int _size;
int _capacity;
};
시간 복잡도
push_back: O(1)
중간 삽입, 삭제: O(N)
각 요소들을 하나씩 앞으로 당겨오거나 밀어내야하기 때문이다.
임의 접근: O(1)
시작 주소 기반으로 바로 원하는 위치의 주소를 계산할 수 있기 때문이다.