std::vector의 크기가 변경 될 때
서론
#include <vector>, c++ 이 기본으로 제공하는 벡터 라이브러리다.
우리가 벡터를 선언하면 스택이라는 공간에 벡터가 생성된다. 그렇다고 벡터 안의 값들도 스택에 생성되는 것은 아니다. 이것들은 힙이라는 공간에 생성된다. 벡터는 동적어레이 이기 때문이다. 또한, 벡터의 사이즈를 변경하면 벡터자체의 주솟값은 변경되지 않지만, 벡터의 가장 첫 번째 값의 주솟값은 변한다. 이것들은 무엇이고 왜 그럴까?
개요
스택과 힙이란?
스택(Stack)이라는 공간은 정적 메모리(static memory)할당에 사용되는 공간이다. 정적인 메모리, 즉, 컴파일 시간에 크기가 결정되어서 런타임에서의 크기변경이 되지 않는 메모리라는 말이다. 이 스택이라는 공간에서 함수의 호출과 로컬 변수가 LIFO(Last In First Out) 구조로 저장이 된다. 또한 함수가 종료되거나 로컬 변수가 선언된 프레임을 벗어나게 되면 자동으로 메모리가 해제된다. 따라서, 접근이 쉽고 빠르다. 하지만 크기가 제한적이라서 무제한 호출 등이 일어나면 그 유명한 스택오버플로우(Stack Overflow)가 나타날 수 있다.
힙(Heap)이라는 공간은 동적 메모리(dynamic memory)할당에 사용되는 공간이다. 동적이라는 말을 보면 알 수 있듯이, 컴파일타임이 아니라 런타임에 크기가 결정된다. 이 공간은 스택에 비해 복잡할 수 있지만 크기가 매우 크기 때문에 잘 사용만 한다면 우리에게 큰 이점을 가져다줄 수 있다. 이때 '잘 사용' 한다는 것은 대표적으로 메모리 누수를 일으키지 않는 것으로도 볼 수 있다. 메모리 누수란 개발자가 힙 공간에 메모리를 할당시켜 놓고 명시적으로 해제를 하지 않아서 발생하는 현상이다. 스택과 다르게 힙에 할당된 메모리는 사용이 끝난 후 자동으로 해제되지 않기 때문에 힙 공간에 메모리를 할당하였다면 반드시 메모리를 해제하는 것에 신경을 써야 한다.
위의 내용들을 더 자세히 설명하려면 프로세스와 스레드, 메모리(heap, stack, data, code), 컴파일타임, 런타임등을 설명해야 한다. 이 내용은 다른 글에서 설명하겠다.
본론
그래서 우리가 std::vector <int> vec;이라고 선언을 하면 이 vec이라는 것은 stack 공간에 만들어진다. 생각해 보면 우리는 std::vector를 만들어서 잘 써왔었지만 delete vec;처럼 직접 메모리 해제를 해준 적은 없을 것이다. 서론에서 언급했던 stack이라는 공간에 할당된 메모리들은 자동으로 메모리 해제가 되기 때문에 우리가 직접 해제해 줄 필요가 없기 때문이다. 그러면 vector는 정적어레이(static array)인가?
답을 말하자면 아니다. vector라는 메타데이터를 가진 벡터 그 자체는 스택공간에 할당이 되지만 벡터가 갖는 실제 값들은 힙에 할당되기 때문이다.
std::vector vec; 이런 식으로 벡터를 생성하면 size가 0, capacity가 0이다. 이때 size는 벡터가 보유하고 있는 실제 요소의 개수이다. capacity는 내부적으로 할당된 메모리의 크기를 나타낸다. 즉, size와 capacity는 항상 같지는 않다는 말이다. <vector> 라이브러리가 제공하는 함수에서도 이를 알 수 있는데 resize()와 reserve()라는 함수이다.
resize()로 벡터의 크기를 줄이면 요소의 개수는 줄어들 수 있지만 할당된 메모리의 크기는 줄어들지 않는다.
resize()로 벡터의 크기를 늘리면 요소의 개수는 default로 0이 되며 요소의 수가 늘어나고 할당이 필요하다면 메모리 재할당도 수행한다.
reserve()로 할당된 메모리를 축소시킬 수 없다.
reserve()로 크기를 늘리면 size는 커지지 않고 메모리 공간만 할당이 된다.
우리가 push_back()을 여러 번 하였을 때 vector의 메모리 공간이 어떻게 변화하는지 살펴보자 아래 코드는 vec를 생성 후 7번 동안 push_back()을 한 상태이다.
Vector Address는 스택공간에 저장된 vector의 메타데이터이다.
따라서 사이즈가 변경되어도 주솟값이 같다(0000004280 CFF7 D8).
다음으로, Address of first elements는 capacity가 변경될 때마다 바뀐다.
capacity가 1에서 2로 변경될때 000001C684567410-> 000001C684574110
capacity가 2에서 3으로 변경될때 000001C684574110-> 000001C684573E90
capacity가 3에서 4로 변경될때 000001C684573E90->000001C684573850
capacity가 4에서 6으로 변경될때 000001C684573850->000001C684570450
capacity가 6에서 9로 변경될때 000001C684570450->000001C6845704B0
위 내용처럼 변경되었다.
다음으로 size는 1씩 늘어나는데 반해 capacity는 뭔가 이상하게 늘어난다. 100번 동안 push_back()해보면 capacity는 1,2,3,4,6,9,13,19,28,42,63,94,141의 크기로 변화한다.
규칙을 찾았는가?
그렇다 만약 Size가 Capacity와 같아서 capacity를 늘릴 때 capacity는 1씩 증가하는 것이 아니라 현재크기의 1.5배만큼 증가한다.
왜 그럴까?
사실 필자는 벡터의 크기가 증가할 때 2배씩 커진다고 배웠었다. 이에 의문이 생겨 찾아본 결과 반드시 2배도 아니고 반드시 1.5배도 아니다. 이는 컴파일러의 버전마다 다르게 보이는데 예를 들어 GCC 6.3.0에서 실험을 했을 때는 capacity가 2배씩 늘어났고 Visual Studio의 C++ 17 버전 컴파일러 환경에서는 1.5배씩 증가했다. 이를 좀 더 정확히 알아보기 위해서 직접 <vector> library에 push_back이 되는 곳을 찾아가 보았다.
c++의 기본 library <vector>에 쓰인 코드이다. _Geometric = _Oldcapacity + _Oldcapacity / 2; 이렇게 되어있다.
이제 왜 capacity가 1.5배씩 늘어나는지 해결되었다 휴~!
아직 하나 남았다. 벡터의 가장 첫 요소의 메모리 주소는 왜 자꾸 바뀌는 것일까?
자칫 잘못 생각하면 기존의 벡터의 뒷부분에 필요한 메모리만큼 덧붙여서 증가시키면 벡터 첫 번째 요소의 주솟값은 안 변하지 않을까?라고 생각할 수 있다.
하지만 틀렸다. capacity가 변경될 때에는 새로운 capacity에 맞는 메모리공간을 다시 만든 후에 기존의 벡터를 그대로 복사해서 붙이고 기존의 공간은 destroy 하는 코드가 구현되어 있다. 즉 메모리의 주솟값이 변경될 수밖에 없는 것이다. 이후 이 벡터가 선언된 프레임을 나가게 되면 자동을 메모리 해제가 일어난다.
결론
vector의 크기가 커질 때 벡터 자체(메타데이터)의 주소값은 변하지 않는다.
capacity가 늘어날 때 새로운 메모리공간을 할당 후 복사하기 때문에 벡터요소의 첫 번째 값(data() 함수로 접근가능)의 주솟값은 변화한다.
capacity는 2배 or 1.5씩 늘어난다.
마무리
위에서 잠깐 언급된 프로세스와 스레드, 메모리(heap, stack, data, code), 컴파일타임, 런타임에 대한 개념은 다른 글에서 설명하겠다.
위의 내용을 바탕으로 개발자 면접 간
1. 프로세스와 스레드의 차이는 무엇인가요?(이제 heap과 stack을 곁들여서)
2. 스택은 무엇이고 힙은 무엇인가요?
3. 정적어레이와 동적어레이의 차이점은 무엇인가요?
4. 배열과 리스트의 차이점은 무엇인가요?
등에 대한 질문을 생각해 볼 수 있겠다. 스스로에게 질문을 해보고 답해보자.
헷갈리는 부분은 보완하기! 찡긋 O.<
틀린 부분이나 보완해줬으면 하는 내용이 있으면 댓글로 알려주세요! 추가 설명이 필요하신 부분도 댓글로 알려주세요.
어떠한 피드백도 환영입니다. 긴 글 읽어주셔서 감사합니다.