[STL]벡터(vector)의 메모리 재할당에 대해

#include <iostream>

#include <vector>

//벡터 출력 함수

void Print(std::vector<int>& myvector)

{

std::vector<int>::iterator it;

std::cout << "myvector contains:";

for (it = myvector.begin(); it < myvector.end(); it++)

{

std::cout << ' ' << *it;

}

std::cout << '\n';

}

void main()

{

std::vector<int> myvector(3, 100); // size : 3, capacity : 3 , 맨처음 메모리 할당

std::vector<int>::iterator it;

Print(myvector);    //myvector contains: 100 100 100

it = myvector.begin();

it = myvector.insert(it, 200); // size : 4, capacity : 4 , 새로운 메모리 공간에 전부 재 할당

Print(myvector);    //myvector contains: 200 100 100 100

it = myvector.insert(it, 1, 300); // size : 5, capacity : 6 , 새로운 메모리 공간에 전부 재 할당

Print(myvector);    //myvector contains: 300 200 100 100 100

it = myvector.insert(it, 1, 302); // size : 6, capacity : 6

Print(myvector);    //myvector contains: 302 300 200 100 100 100

it = myvector.insert(it, 1, 303); // size : 7, capacity : 9 , 새로운 메모리 공간에 전부 재 할당

Print(myvector);    //myvector contains: 303 302 300 200 100 100 100

it = myvector.insert(it, 1, 304); // size : 8, capacity : 9 

Print(myvector);    //myvector contains: 304 303 302 300 200 100 100 100

it = myvector.insert(it, 1, 305); // size : 9, capacity : 9 

Print(myvector);    //myvector contains: 305 304 303 302 300 200 100 100 100

it = myvector.insert(it, 1, 306); // size : 10, capacity : 13 , 새로운 메모리 공간에 전부 재 할당

Print(myvector);    //myvector contains: 306 305 304 303 302 300 200 100 100 100

it = myvector.begin(); //이터레이터 변수 다시 시작지점으로 초기화

std::vector<int> anothervector(2, 400); // 다른 벡터

myvector.insert(it + 2, anothervector.begin(), anothervector.end()); // size : 12, capacity : 13

Print(myvector);    //myvector contains: 306 305 400 400 304 303 302 300 200 100 100 100

int myarray[] = { 501, 502, 503 }; // size : 15, capacity : 19 , 새로운 메모리 공간에 전부 재 할당

myvector.insert(myvector.begin(), myarray, myarray + 3);

Print(myvector);    //myvector contains: 501 502 503 306 305 400 400 304 303 302 300 200 100 100 100

myvector.pop_back(); // size : 14, capacity : 19 , 동일한 메모리 공간, 뒤에 것만 삭제, 반환값 없음

Print(myvector);    //myvector contains: 501 502 503 306 305 400 400 304 303 302 300 200 100 100

myvector.reserve(5); // size : 14, capacity : 19 , 이전 capacity보다 같거나 작으면 동작하지 않음

Print(myvector);    //myvector contains: 501 502 503 306 305 400 400 304 303 302 300 200 100 100

myvector.reserve(20); // size : 14, capacity : 20 , 새로운 메모리 공간 전부 재 할당

Print(myvector);    //myvector contains: 501 502 503 306 305 400 400 304 303 302 300 200 100 100

myvector.resize(5); // size : 5, capacity : 20 , 동일한 메모리 공간, 사이즈 외에 것은 삭제

Print(myvector);    //myvector contains: 501 502 503 306 305

myvector.shrink_to_fit(); // size : 5, capacity : 5 , 새로운 메모리 공간 전부 재 할당, 벡터 용량(capacity)을 크기(size)에 맞춤. c++11에 추가

Print(myvector);    //myvector contains: 501 502 503 306 305

getchar();

}

c++ 에서 class나 데이터를 한 군데 모아 사용하는데에 

가장 잘 사용했던 것이 vector였는데

이전 까지는 내부 메모리를 무시하고 사용했었다. 

그래서 단편화 현상 유발이나 

여러 다른 문제들을 야기 할 수 있다는 것을 간과했다.

하지만 위와같이 테스트해본 결과 메모리 처리가 

다른 STL들과는 다른 점이 있어서

정리를 해두려고 한다.

벡터는 size와 capacity가 별도로 있다.

capacity는 벡터에 허용된 용량을 나타내고

size는 그 용량 내에 차지하고 있는 크기를 나타낸다.

테스트 결과 벡터에서는 capacity가 바뀌는 상황이 되면

메모리 재할당이 이루어 지는 것을 발견 할 수 있었다.

벡터 내에서는 data들이 일렬로 배열처럼 들어 있는데

일렬로 원하는 용량이 들어 갈 수 있는 공간을 찾아서

메모리와 data들이 재 할당 되는 것이다. 

기존의 공간은 이제 비게 되고 다른 곳에서 사용가능해진다.

현재공간에서 size 외에 남은 용량은 다른 곳에서 사용하지 못한다.

용량을 함수로 늘리거나 줄이는거 외에

insert나 push_back으로 추가 삽입이 이루어 질때 

capacity를 넘기게 되면 자동으로 메모리 재할당이 이루어 진다.

하지만 1씩 증가되는 것이 아니라 현재 capacity의 1.5배로 늘어나는 것을 확인했다.

capacity 변화 순서 : 3 -> 4(4.5지만 소수 버림) -> 6 -> 9 -> 13(13.5지만 소수 버림) -> 19(19.5지만 소수 버림)

벡터는 리스트보다 데이터 검색이 빠르다.

하지만 추가 삭제가 빈번하여

메모리 재할당이 자주 일어나면 성능이 낮아질 수 밖에 없다.

그만큼 단편화도 자주 일어날 가능성이 크다.

벡터(vector)의 좋은 사용법은 

추가 삭제가 자주 일어나지 않아야 하고

미리 reserve로 최대 용량을 잡아주거나

resize로 원하는 만큼만 생성해 그 안에서 컨트롤 하는 것이다.

최대 용량은 단편화를 낮추기 위해 2의 배수가 좋을 것 같다고 생각한다.