std::vector로 배우는 레벨업 #1
선행학습: std::vector의 size와 capacity에 대해서 제대로 알고있자
std::vector의 push_back과 reserve를 한번 직접 구현해보자..
언뜻 생각해보면 template에 대해서 조금만 알고 있으면 다음과 같이 쉽게 구현 할 수 있을 거라는 생각이 들 것이다.
template<class T>
class MyVector
{
public:
MyVector()
: _data(nullptr)
, _size(0)
, _capacity(0)
{
}
~MyVector()
{
delete[] _data;
}
size_t size() const noexcept { return _size; }
size_t capacity() const noexcept { return _capacity; }
T& operator[](size_t idx)
{
return _data[idx];
}
void reserve(size_t newCapacity)
{
if (_capacity < newCapacity)
{
// 더 큰 공간을 할당 하고
T* newData = new T[newCapacity];
// 기존의 _data를 복사한다.
for (size_t i = 0; i < _size; ++i)
{
newData[i] = _data[i];
}
// 기존의 _data는 메모리 해제
delete[] _data;
_data = newData;
_capacity = newCapacity;
}
}
void push_back(const T& value)
{
if (_capacity <= _size)
{
reserve(calculate_growth(_capacity + 1));
}
_data[_size++] = value; // 복사 및 사이즈 증가
}
private:
size_t calculate_growth(const size_t new_size) const
{
if (_capacity > std::numeric_limits<size_t>::max() - _capacity / 2)
{
return (new_size); // geometric growth would overflow
}
const size_t geometric = _capacity + _capacity / 2;
if (geometric < new_size)
{
return (new_size); // geometric growth would be insufficient
}
return (geometric); // geometric growth is sufficient
}
private:
T* _data;
size_t _size;
size_t _capacity;
};
한번 다음의 테스트 코드로 std::vector과 MyVector의 출력결과가 어떻게 다른지 확인해 보면….
Foo temp;
std::cout << "1-1. std::vector<Foo> :" << std::endl;
std::vector<Foo> stdVec;
std::cout << "1-2. std::vector<Foo>::reserve(2) :" << std::endl;
stdVec.reserve(2);
std::cout << "1-3. std::vector<Foo>::push_back(temp) :" << std::endl;
stdVec.push_back(temp);
std::cout << "2-1. MyVector<Foo> :" << std::endl;
MyVector<Foo> myVec;
std::cout << "2-2. MyVector<Foo>::reserve(2) :" << std::endl;
myVec.reserve(2);
std::cout << "2-3. MyVector<Foo>::push_back(temp) :" << std::endl;
myVec.push_back(temp);
Foo()
1-1. std::vector<Foo> :
1-2. std::vector<Foo>::reserve(2) :
1-3. std::vector<Foo>::push_back(temp) :
Foo(const Foo&) #c++ 버젼에 따라 Foo& operator=(const Foo&) 일 수도 있음
2-1. MyVector<Foo> :
2-2. MyVector<Foo>::reserve(2) :
Foo()
Foo()
2-3. MyVector<Foo>::push_back(temp) :
Foo& operator=(const Foo&)
push_back을 했을때 복사생성자가 호출되느냐 대입연산자가 호출되느냐는 c++ 버젼에 따라 차이가 있을 수 있으니, 동일하다고 치고,
stl버젼은 reserve를 했을때 생성자가 호출되지 않지만, MyVector는 생성자가 2번 호출되는 차이점을 볼 수 있다.
이 차이가 의미하는 것은 무엇일까?
눈치가 빠른분들은 이미 감을 잡으셨을 것이다.
그렇다. vector에서 reserve함수를 통하여 capacity의 크기를 늘린다는 것은 메모리공간만 할당하는 것이지, 실제 객체가 생성되는 것은 아니다.
혹시, 아직 c++에서 객체 생성의 의미를 정확히 모르고 있었다면, 이제는 정확히 이해 했을 것이다.
(잘 모르겠으면 ‘c++에서 malloc과 new의 차이점‘을 읽어보자)
그럼 한번 요구사항에 맞게 코드를 고쳐보자
~MyVector()
{
::operator delete(_data);
}
void reserve(size_t newCapacity)
{
if (_capacity < newCapacity)
{
// 더 큰 공간을 할당 하고
const size_t bytes = sizeof(T) * newCapacity;
T* newData = static_cast<T*>(::operator new(bytes));
// 기존의 _data를 복사한다.
for (size_t i = 0; i < _size; ++i)
{
newData[i] = _data[i];
}
// 기존의 _data는 메모리 해제
::operator delete(_data);
_data = newData;
_capacity = newCapacity;
}
}
이제 std::vector와 동일한 결과가 나옴을 확인 할 수 있을 것이다.