[STL] vector #1

STL (Standard Template Library)

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

 

컨테이너(Container) : 데이터를 저장하는 객체 (자료구조 Data Structure)

 

vector (동적 배열)

• vector의 동작 원리 (size/capacity)
• 중간 삽입/삭제
• 처음/끝, 삽입/삭제
• 임의 접근

 

배열

const int MAX_SIZE = 10
int arr[MAX_SIZE] = { };

for (int i = 0; i < MAX_SIZE; ++i)
	arr[i] = i;

근데 여기서 추가로 데이터를 가지고 싶다면?

몬스터를 추가시키고 싶다면?

그러면 애초에 배열의 크기 10으로 잡아서 사용못하는 문제가 있을 것이다.

추가적으로 배열을 늘리는 것이 불가능하다.

결론은 유동적이지 않다.

그렇다고 애초에 메모리를 크게 만들었을 때, 만약 데이터가 한 개 밖에 안들어오면 메모리 낭비가 심한 문제도 있을 것이다.

 

동적 배열

usnig namespace std;
#include <vector>

int main()
{
	vector<int> y;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

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

매우 매우 중요한 개념 → 어떤 마법을 부렸길래 배열을 ‘유동적으로’ 사용한 것인가?

1. (여유분을 두고) 메모리를 할당한다
2. 여유분까지 꽉 찼으면, 메모리를 증설한다.

int *arr = new int[100];
// 부족하네?
delete arr;
arr = new int[1000];

대충 이런식.

 

의문점

1. 여유분은 얼만큼이 적당할까?
2. 증설을 얼만큼 해야할까?
3. 기존의 데이터를 어떻게 처리할까? [ex) 기존에 있던 메모리를 새로운 메모리에 복사? or 기존에 이어서 메모리 저장?]

size (실제 사용 데이터 개수)

// 1 2 3 4 5 6 7 ….

capacity (여유분을 포함한 용량 개수)

// 1 2 3 4 6 9 13 19 28 42 63 …. (대략 1.5배)

for (int i = 0; i < 1000; ++i)
{
	v.push_back(100);
	cout << v.size() << " " << v.capacity() << endl;
}

size [ 1 2 3 4 5 ]

capacity [ 1 2 3 4 5 ]

capacity를 1씩 증가시킨다고 하면, 증설하자마자 매번 기존의 데이터를 복사하는 비용이 들 것이다.

여유있게 1.5배 ~ 2배를 증설시켜 복사 비용 횟수가 그렇게 많이 들지 않을 거라는 점에서 여유있게 만들어 놓는 것이다.

 

근데도 데이터가 늘어날 때 마다 capacity가 늘어나고, 그로 인해 복사하는 비용이 아쉽기도 하는 생각이 든다.

그럴 때 capacity의 크기를 미리 세팅해줄 수 도 있다.

v.reserve(1000);

 

사이즈도 조절할 수 있다.

capacity를 미리 세팅안해줬다면 그만큼 capacity도 자동으로 알아서 조절된다. (똑같이 설정됨)

v.resize(1000);

 

claer를 하면 size는 초기화되지만, capacity자체는 내부적으로 줄지 않는다.

그럼에도 capacity를 없애고 싶다하면 임시 vector를 통해 복사하면 된다.

vector <int>() swap(v);

 

생성자 자체에서 size(1000)를 지정해주고, 특정값(-1)로 초기화 하는 명시적인 방법도 있다.

또한 다른 벡터로 복사도 가능하다.

vector<int> v(1000, -1);

vector<int> v2 = v;