[C++] STL - Vector

정말정말 중요한 내용이다.

STL은 Standard Template Libaray이다.

프로그래밍 할 때 필요한 자료구조/ 알고리즘들을 템플릿으로 제공하는 라이브러리이다.

STL에 대해 공부하기 전에 여러 용어에 대해 알아야한다.

컨테이너(container)

우리가 이전에 여러 데이터를 저장하는 방법으로 배열 방식이외의 방식은 없었다. 컨테이너는 데이터를 저장하는 객체 즉 자료구조 Data Structure인 것이다. 이 컨테이너중 하나인 Vector에 대해 다뤄보겠다.

Vector

벡터의 원리에 대해 정확히 알고 있어야한다.

1. vector의 동작 원리 (size/capacity)

2. 중간 삽입/삭제

3. 처음/끝 삽입/ 삭제

4. 임의 접근

 

vector를 알기 전 그전에 사용했던 배열에 대해 생각해보자. 배열의 장점만 지금까지 포스팅 했던 것 같은데 단점을 생각해보자.

예를 들어 MMO RPG에서 몬스터를 만든느데 배열의 사이즈가 10개인 몬스터형 배열을 만들었다고 해보자. 그런데 몬스터의 사이즈는 알 수 없다는게 문제다. 10 마리 일지 100마리 일지 심지어 유저 수에 따라 조절하기도 한다. 그렇다면 우린 동적 할당한 배열을 사용해야 하나 싶다. 물론 초기 생성할 때 유저수에 따라 동적 할당한 배열을 생성할 수 있겠지만 이 마저도 최대 사이즈를 넘길 수 없다 그 때 필요한 것이 vector이다.

 

Vector를 사용하기 위해서는 <vector>파일이 필요하다.

#include <iostream> 
#include <vector>

using namespace std;

int main()
{
	// 동적 배열
	vector<int> v;
	// 맨 뒤에 데이터를 넣기
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}

    return 0;
}

어떤 마법을 부렸길래 배열을 '유동적'으로 줄였다 늘렸다 할 수 있는 것일까?

vector의 원리 

매우 매우 중요한 개념이다. 배열은 생성할 때 크기가 정해진다. 유동적으로 사용하려면 어던 원리가 필요한 것인가.

2가지 주요 매커니즘이 있다.

 

1. 여유분을 두고 메모리를 할당한다.

예를들어 우리가 10개의 메모리를 요청했다면 20개의 메모리를 할당해준다. 이 특성만 놓고보면 그냥 배열이라 다를게 없다. 우리가 10개가 필요하니까 일단 여유롭게 20개로 선언하는 것과 별 차이가 없게된다. 하지만 2번째 특성으로 인해 달라진다.

 

2. 여유분까지 꽉 찼으면 메모리를 증설한다.

20개의 여유분이 가득차면 추가적으로 사이즈를 늘리게된다. 그런데 이게 가능한 일일까? 처음 만들어 질때, 사이즈가 정해질 텐데 어떻게 사이즈를 늘릴 수 있을까? 바로 다음과 같은 매커니즘이다.

int* arr = new int[20];   // 기존의 메모리

delete arr;                   // 메모리 삭제

arr = new int[200];      // 메모리 증설

즉, 기존의 배열을 삭제하고 메모리를 새로 할당해 그곳으로 옮기는 것이라 할 수 있다. 결론적으로 사이즈를 늘린다는게 실제로 늘리는게 아니라 새로 만드는 것이다.

 

질문이 있을 수 있다.

1. 처음 여유분은 얼만큼이 적당할까?

2. 증설을 얼만큼 해야할까?

3. 기존의 데이터를 어떻게 처리할까?

 

일단 vector의 원리를 제대로 이해하기 위해선 size와 capacity의 차이를 확실히 알고 있어야한다.

size vs capacity

결론부터 얘기하면 size는 실제 사용 데이터 개수이고, capacity는 여유분을 포함한 용량의 개수이다.

#include <iostream> 
#include <vector>

using namespace std;

int main()
{
	// 동적 배열
	vector<int> v;
	// 맨 뒤에 데이터를 넣기
	for (int i = 0; i < 1000; i++)
	{
		v.push_back(1);
		cout << v.size() << " " << v.capacity() << endl;
	}

    return 0;
}

결과 화면은 다음과 같다.

size는 실제 데이터의 양이기 때문에 1씩 늘어나는 반면 capacity는 묘한 흐름을 나타내는걸 볼 수 있다.

size는 1 2 3 4 5 6 7....

capacity는 1 2 3 6 9 13 19 28 42 63 ...

바로 capacity의 크기는 이전 크기의 1.5배를 하는걸 볼 수 있다.(이는 컴파일러에 따라 다르다.)

 

그래서 위의 첫번째 질문인 1. 처음 여유분은 얼만큼이 적당할까?에 대한 답은 이전 크기의 1.5배 이다.

그런데 그러면 capacity도 그냥 size랑 맞추면 되는거 아닌가 싶다. 하지만 3번째 질문인 데이터와 이는 연관되어 있다. 새로운 메모리를 만들때 즉, 이사를 갈때 이삿짐(데이터)를 전부 들고 이동해야한다. 그렇다는건 capacity가 늘어날 때마다 이사를 해야하는데 이삿짐을 옮기는 비용이 계속 발생하기 때문이다.

 

그렇다면 초반에는 복사가 되게 많이 일어나게될 것임을 예측할 수 있다. 우리가 초반 데이터의 양을 알고 있다면 capacity의 값을 조절할 수 있다.

#include <iostream> 
#include <vector>

using namespace std;

int main()
{
	// 동적 배열
	vector<int> v;
	// 맨 뒤에 데이터를 넣기
	v.reserve(1000);	// 여유분 1000개 늘리기
	v.resize(1000);		// size를 1000개로 지정하면 여유분도 1000개로 자동으로 늘어남
	for (int i = 0; i < 1000; i++)
	{
		v.push_back(1);		// 다만 이렇게 하면 1000개에서 1씩 늘어나서 size가 2000이 됨.
		cout << v.size() << " " << v.capacity() << endl;
	}

    return 0;
}

그렇다면 벡터를 전부 다 사용한 후에 clear를 하게 되면 어떻게 될까?

#include <iostream> 
#include <vector>

using namespace std;

int main()
{
	// 동적 배열
	vector<int> v;
	// 맨 뒤에 데이터를 넣기
	v.reserve(1000);	// 여유분 1000개 늘리기
	
	for (int i = 0; i < 1000; i++)
	{
		v.push_back(1);		
		cout << v.size() << " " << v.capacity() << endl;
	}
	v.clear();
	cout << v.size() << " " << v.capacity() << endl;

    return 0;
}

그렇다면 size는 0이지만 capacity는 줄어들지 않게 된다. c++에서는 이미 1000을 사용했다면 나중에도 사용할 여지가 있는것으로 보아 capacity가 한번 늘어나면 줄어들지 않는다. 하지만 내가 진짜 다 줄였으면 좋겠다고 생각하면 

다음과 같은 코드로 가능하다.

vector<int>().swap(v);

이렇게 임시 벡터를 만들고 그걸 v랑 바꾸면 가능하다. 실무에서는 잘 쓰지 않는다.

 

중간 삽입 삭제

이걸 알기 위해서는 반복자 라는 개념을 알고 있어야한다. 포인터와 유사한 개념으로 컨테이너의 원소를 가리키고, 다음 이전 원소로 이동이 가능한 것이라고 알고 있으면 된다.

#include <iostream> 
#include <vector>

using namespace std;

int main()
{

	vector<int> v(10);
	
	vector<int>::iterator it;
	int* ptr;

	it = v.begin();
	ptr = &v[0];

	cout << *it << endl;
	cout << *ptr << endl;
    return 0;
}

iterator는 결국엔 그냥 클래스 중 하나이고 연산자 오버로딩을 통해 포인터 처럼 사용이 가능한 것이다.

#include <iostream> 
#include <vector>

using namespace std;

int main()
{
	vector<int> v(10);
	
	vector<int>::iterator it;
	for ( it = v.begin(); it != v.end(); ++it)
	{
		cout << *it << endl;
	}
    return 0;
}

 그래서 중간 삽입 삭제가 왜 중요할까? vector는 동적 배열이고 동적으로 커지는 배열을 의미한다. 즉 결국은 배열이다.

원소가 하나의 메모리 블록에 연속하게 저장된다는 것이다.

예를 들어

[0][1][2][3][4][ ][ ] 라는 백터가 있다고 해보자.

중간 2 앞에 5를 삽입하고자 하면 메모리를 늘리는 것이 아닌 나머지 데이터를 뒤로 미뤄야한다.

[0][1][5][2][3][4][][]

즉, 데이터가 1000개가 있었다면 복사가 998번 일어나게 될테니 매우 비효율적이다.

또 삭제는 하나의 데이터를 삭제한 후 벡터는 연속적으로 저장되어 있기 때문에 앞으로 전부 복사해서 당겨야한다.

역시 매우 비효율적이다.

또한 맨 앞부분에 데이터를 삽입하는 것 역시 매우 비효율적이다.

하지만 맨 뒤에 삽입하는것은 효율적이라는 걸 추론할 수 있다.

 

데이터에 임의접근을 하기 위해서는 맨 앞주소에서 더해서 접근하면 되기때문에 매우 쉽게 가능하다.