선행학습: std::vector의 size와 capacity에 대해서 제대로 알고있자
std::vector의 push_back과 reserve를 한번 직접 구현해보자..
언뜻 생각해보면 template에 대해서 조금만 알고 있으면 다음과 같이 쉽게 구현 할 수 있을 거라는 생각이 들 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
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의 출력결과가 어떻게 다른지 확인해 보면….
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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); |
1 2 3 4 5 6 7 8 9 10 11 |
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의 차이점‘을 읽어보자)
그럼 한번 요구사항에 맞게 코드를 고쳐보자
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
~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와 동일한 결과가 나옴을 확인 할 수 있을 것이다.
code
more code
~~~~