안녕하세요 A.N.S.I 부원 주진형입니다.
오늘은 먼저 포스트 된 vector 자료구조에 대해서 조금 더 심화된 내용을 공부해볼까 합니다.
Vector
vector는 가변적으로 크기가 변하는 연속된 데이터를 가질 수 있는 자료구조입니다.
가변적
vector는 각 vector instance에 대해서 push 나 여러 함수들을 통해서 크기가 가변적으로 변합니다.
예를 들어
#include<iostream>
#include<vector>
using namespace std;
int main(){
vector<int> v;
cout << v.size() << endl;
v.push_back(1);
cout << v.size() << endl;
v.push_back(2);
cout << v.size() << endl;
return 0;
}
위 코드의 결과를 보면 v 라는 vector instance 의 크기는 0, 1, 2로 하나씩 늘어나게 됩니다.
어떻게 이런 일이 가능한 걸까요?
내부 구현
vector는 size만 가지고 있는 것이 아닙니다. capacity. 즉 최대로 담을 수 있는 용량이 정해져 있죠.
size vs capacity
간단히 말하면 size는 이 vector instance가 가지고 있는 element 들의 개수를 말하는 것이고,
capacity는 이 vector instance가 가질 수 있는 element 의 최대 개수를 말하는 것입니다.
size가 capacity 보다 커질 때
그렇다면 size가 최대 용량인 capacity 보다 커질 때는 무슨 일이 일어날까요?
실제 구현되어 있는 코드를 봅시다.
public:
template <class... _Valty>
decltype(auto) emplace_back(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
if (_Mylast != _My_data._Myend) {
return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
}
_Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
#if _HAS_CXX17
return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
(void) _Result;
#endif // _HAS_CXX17
}
void push_back(const _Ty& _Val) { // insert element at end, provide strong guarantee
emplace_back(_Val);
}
이 코드는 visual studio 2019 에 vector class 의 구현체입니다.
하나씩 따라가도록 해보죠.
void push_back(const _Ty& _Val) { // insert element at end, provide strong guarantee
emplace_back(_Val);
}
push_back 이 불리는 부분입니다.
emplace_back() 이라는 함수를 불러오는군요.
public:
template <class... _Valty>
decltype(auto) emplace_back(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
if (_Mylast != _My_data._Myend) {
return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
}
_Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
#if _HAS_CXX17
return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
(void) _Result;
#endif // _HAS_CXX17
}
emplace_back 의 구현체입니다.
읽기 힘들겠지만 하나하나 보도록 하죠.
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
먼저 이 부분 입니다. 먼저 _My_data 에 vector 안에 배열 포인터를 들고 오는 것 같습니다.
그리고 _Mylast 에 _My_data 의 마지막 값의 포인터를 넣어줍니다.
if (_Mylast != _My_data._Myend) {
return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
}
이 부분은 위에서 선언한 _Mylast 와 _My_data 의 end 값을 비교하는 부분입니다.
비교하고 같지 않으면 capacity 중에서 사용하지 않은 부분에 emplace back을 하는 함수를 불러옵니다.
_Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
#if _HAS_CXX17
return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
(void) _Result;
#endif // _HAS_CXX17
위의 if 문에서 걸리지 않았다면, 즉 _Mylast 와 _My_data 가 같을 때의 행동입니다.
reallocate 하고 emplace를 하는 함수를 불러옵니다.
그리고 그 결과값을 return 해줍니다.
요약
- vector가 가진 배열의 마지막 값의 포인터와, vector 가 가질 수 있는 배열의 마지막의 포인터를 비교.
- 다르면 원래 가진 배열에 emplace.
- 같으면 reallocate 후 emplace.
이렇게 요약을 할 수 있을 겁니다.
reallocate
위에서 볼 수 있듯이 size 가 capacity 보다 커지게 되면 reallocate를 해주고, emplace를 한다고 되어있습니다.
그러면 reallocate로 뭘 하는 걸까요?
바로 capacity 가 두 배인 새로운 배열을 만드는 것입니다.
그리고 만들어진 새로운 배열에 원래 있던 값들을 복사 합니다.
시간 복잡도
?? 그러면 push 는 O(1) 이 아니네요?
최악의 경우에는 O(n) 이 걸릴 수 있지만 capacity 가 n 일 때 n 번넣을 때 총 n 번 넣고, n 번 복사를 하기 때문에 평균적으로 상수시간에 끝난다고 봐도 무방합니다.
문제점
하지만 위에서 말한건 평균일 때 O(1) 이 된다는 말이고,
만약 size 와 capacity 가 10,000,000인 vector 가 있다고 생각해봅시다.
이 vector 에다가 push_back을 하면 어떤 일이 일어날까요?
- 10,000,000인 메모리 공간을 해제한다.
- 20,000,000인 메모리 공간을 할당한다.
- 10,000,000개의 element를 복사한다.
이런 일이 일어나게 되면 굉장히 많은 시간이 소요되게 됩니다.
마법따윈 없다
vector는 일반 배열에 비해서 굉장히 편하게, 쉽게 쓸 수 있다는 장점을 가지고 사용할 수 있습니다.
하지만 위에서 말한 것 처럼 문제점들도 있으니, 속도가 굉장히 중요한 프로그램을 사용해야할 때가 온다면 유의해서 사용해주시면 좋을 거 같습니다.
모든 프로그래밍에서 힘든 작업이 굉장히 편하고 쉽게 되어있다면, 그 뒷단이 그 힘든 작업을 다 해주고 있다는 사실을 기억하고 프로그래밍을 하시면 더 좋은 프로그래머가 될 수 있을 거라고 믿습니다.
감사합니다.