8. vector: 가변 길이 배열 컨테이너

template<
    class Ty,
    class Allocator = std::allocator<Ty>
> class vector;

   vector는 가변 길이를 갖는 배열 컨테이너이다. <vector>헤데어서 정의된다. array와 유사하게 일반적인 배열과 똑같은 방법으로 사용할 수 있지만, 동적으로 크기를 늘릴 수 있다는 것이 차이점이다. 많은 상황에서 길이가 일정한 데이터 보다는 정해지지 않은 경우를 다루기 때문에 보통 배열을 대체하는 방법으로 array 대신 vector를 많이 사용한다. 메모리적인 요소를 제외하고는 기존 배열 및 array와 거의 비슷한 방법을 통해 사용할 수 있다.

   vector는 주로 필요할 때마다 새로운 원소를 삽입하거나, 삭제한다. 이 때, 메모리가 부족해지면 추가 공간의 재할당 및 기존 공간의 해제가 일어난다. 재할당 과정에서 추가적인 재할당 횟수를 줄이기 위해 사용되고 있는 메모리양과 할당된 메모리 총 양이 다를 수 있다. 여기서 보관된 원소의 개수를 크기(size)라고 하고, 할당되어 저장할 수 있는 최대 원소의 개수를 용량(capacity)라고 한다.

   vector를 사용할 때에는 3가지에 주의해야 한다.

1. 삽입과 삭제는 마지막 위치에서만 빠르다. (1.사용-수정 참고)
2. 삽입 시 재할당에는 큰 오버헤드가 있을 수 있다. (2. 재할당에 대하여 참고)
   

1. 사용

#include<iostream>
#include<vector>

using namespace std;

void print_vector(vector<int> arr) {
	for (auto& v : arr) {
		cout << v << ' ';
	}
	cout << endl;
}

int main() {
	vector<int> arr;

	arr.push_back(1);			// 1
	arr.push_back(2);			// 1 2


	cout << arr[1] << endl;		// 2

	arr.erase(arr.begin());		// arr[0]을 삭제 
	print_vector(arr);			// 2 55 4 5

	return 0;
}

생성

   다양한 방법을 통해서 초기화 하거나, 공간을 미리 할당해 놓을 수 있다. vector를 생성할 때, Allocator를 입력할 수 있는데, 기본 allocator가 있기 때문에 생략해도 무방하다. 기본 allocator는 내부적으로 new 연산을 사용해서 메모리를 할당한다. vector는 7개의 생성자가 존재하고, 각각의 생성자는 allocator를 추가로 받거나, 관련된 오버로드가 있는 등 총 14개가 있다고 볼 수 있다.

1. 기본 생성자
2. size를 전달하는 생성자
3. initializer_list를 전달하는 생성자
4. 시작과 끝의 이터레이터를 전달하는 생성자
5. 복사 생성자
6. 이동 생성자

// 1.	기본 생성자
//		아무것도 할당되지 않은 상태로 초기화.
vector<int> arr1;		

// 2.	size를 전달 받는 생성자.
//		size만큼의 크기의 배열을 생성하고, 모든 원소는 0으로 초기화.
vector<int> arr2(5);	// 0 0 0 0 0

// 2-2.	size와 초기화 값 v을 받는 생성자
//		size 크기의 배열을 동적 할당하고, 모든 원소를 v로 초기화.
vector<int> arr2_2(5, 1);	// 1 1 1 1 1

// 3.	initializer_list
vector<int> arr3 = { 1,2,3,4,5 };
vector<int> arr3_2{ 1,2,3,4,5 };
vector<int> arr3_3({ 1,2,3,4,5} );

// 4.	iterator
vector<int> arr4(arr3.begin(), arr3.end());				// 1 2 3 4 5;
vector<int> arr4_2(arr3.begin() + 1, arr3.end() - 1);	// 2 3 4

// 5.	copy
vector<int> arr5(arr4);		// 1 2 3 4 5

// 6. move
vector<int> arr6(move(arr5)); // 1 2 3 4 5

별도로 assign이라는 메서드를 지원하는데, 이미 할당이 이루어진 컨테이너에 대해서 생성자와 비슷한 연산을 하고자 할 때 사용할 수 있다.

vector<int> arr;

vector<int> arr1;

이터레이터

vector의 이터레이터는 이터레이터의 모든 연산을 지원한다.

접근

   기존 배열 및 array컨테이너와 완전히 같은 연산을 제공한다. [] 연산자나 .at() 메서드로 원하는 인덱스의 요소의 레퍼런스를 얻을 수 있다. front()와 back()을 통해서 첫 번째 요소와 사용 중인 마지막 요소를 얻을 수 있다. 할당 범위를 넘어서거나, 아직 초기화되지 않은 size보다 큰 원소를 엑세스 할 수는 없다.

	arr[0] = 100;	// 1 -> 100
	arr.at(4) = 0;	// 5 -> 0
	arr.front();	// == arr[0]
	arr.back();		// == arr[size-1]

용량

   크기를 확인하기 위해서 size() 메서드를, 용량을 확인하기 위해서는 capacity()메서드를 사용한다. reverse()로 추가적인 공간을 예약 할당 할 수 있고, shrink_to_fit()을 이용해서 할당되었지만 사용되지 않는 공간을 반납할 수 있다. empty()로 할당된 공간이 없는지 확인할 수 있다.

								// size()	capacity

vector<int> arr2(10);			// 10		10
arr2.push_back(1);				// 11		15

arr2.reserve(100);				// 11		100

arr2.shrink_to_fit();			// 11		11

arr2.clear();					// 0		0
arr2.reserve(10);				// 0		10
cout << arr2.empty();	// true

수정

   원하는 위치에 새로운 요소를 추가하거나, 삭제할 수 있다. 단, 모든 연산이 빠르지는 않는다. 원소를 맨 끝에서 추가하거나 삭제하는 연산은 O(1)이다. 그러나, 처음이나 중간 인덱스에서 똑같은 연산을 수행하고자 할 때에는 기존 요소들을 한칸씩 이동시켜야 하기 때문에 O(n)의 복잡도를 갖는다.

   삽입은 insert(), emplace(), emplace_back(), push_back() 등의 메서드를 이용한다. _back은 컨테이너 맨 끝에서 빠른 삽입을 하겠다는 의미이다. 삭제는 erase()와 pop_back()을 이용한다. 삽입과 삭제할 요소의 선택은 이터레이터를 통해 전달한다.

vector<int> arr{ 1,2,3 };

// 끝에서의 삽입과 삭제
arr.push_back(4);		// 1 2 3 4
arr.push_back(5);		// 1 2 3 4 5
arr.pop_back();			// 1 2 3 4


// insert를 사용한 삽입
arr.insert(arr.begin(), 99);				// 99 1 2 3 4

// insert는 list-initializer를 이용할 수 있다.
arr.insert(arr.begin()+1, {98,97});	// 99 98 97 1 2 3 4

// erase를 이용한 삭제.
arr.erase(arr.begin());		// 98 97 1 2 3 4
arr.erase(arr.begin());		// 97 1 2 3 4
arr.erase(arr.begin());		// 1 2 3 4

// emplace를 이용한 삽입
arr.emplace(arr.begin(), 0);	// 0 1 2 3 4
arr.emplace_back(37);	// 0 1 2 3 4 37

resize()는 현재 size보다 작게 설정하면 해당 인덱스 전까지 모든 요소들이 삭제된다. 또, size보다 큰 값으로 설정하면 해당하는 크기만큼 요소들을 일정한 값으로 채운다. clear()를 이용하면 현재 할당된 데이터를 삭제할 수 있다.

arr.resize(1);			// 0
arr.resize(5, 1);		// 0 1 1 1 1
arr.clear();			// x

2. 재할당에 대해서

오버헤드

   push_back()과 같은 메서드로 vector에 새로운 원소를 삽입할 때, size 보다 capacity가 커서 확보된 공간이 있다면 O(1)의 빠른 속도로 새로운 요소가 삽입된다.

   그러나, size==capacity 일 때, 즉 더 이상 남은 공간이 없다면 재할당을 통해서 공간을 확보해야 한다. 총 3개의 과정을 통해서 처리되는데, 기존 공간에 있던 요소들을 새로 할당한 공간에 복사하는데, O(n)이 걸린다.

1. 새로운 공간을 확보한다.

   

2. 기존 데이터를 새 메모리에 복사한다.

   

   

할당되는 크기

   메모리를 추가적으로 확보할 때마다 다시 복사를 해야한다면, 굉장히 비효율적일 것이다. 따라서, 추가적인 메모리 할당 횟수를 줄이는 것이 연산의 성능을 끌어올릴 수 있다. 가장 간단한 방법은 새로 할당할 때, 그 용량을 넉넉하게 잡아 새로운 할당 횟수를 줄이는 것이다. 넉넉한 용량에 대한 C++에서 정해진 기준은 없다. 일반적으로는 기존 크기의 2배로 새로 할당하는 경우가 많고, msvc++에서는 기존 크기의 1.5배의 크기로 재할당을 받는 것으로 보인다.

#include<iostream>
#include<vector>

using namespace std;

int main() {
	const int SIZE = 100;
	vector<int> v;

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

1, 1
2, 2
4, 4
5, 6
6, 6
7, 9	-> 6개의 복사 발생
8, 9
9, 9
10, 13	-> 9개의 복사
11, 13
12, 13
13, 13
14, 19
...
20, 28	-> 19개의 복사
...
29, 42	-> 28개의 복사
...
43, 63	-> 42개의 복사
...
64, 94	-> 63개의 복사
...
95, 141 -> 94개의 복사
...

얼마나 느려질까?

   우선, 이론적으로 접근해보자. 위 코드를 예로 생각했을 때, 할당/해제에 시간 소요가 없다고 가정하고, 각 한번의 삽입과 복사는 1이라는 같은 시간이 걸린다고 가정한다. 그랬을 때, 이미 100 이상의 메모리가 할당되어 있었다면 단, 100의 시간으로 삽인 연산을 마칠 수 있다. 그런데, 마지막 재할당만 복사된다고 가정해도 이미 195로 최소 2배의 추가적인 연산이 필요해진다. (복잡도를 표현해보고 싶었지만 잘 되지 않았다.)

   이를 실제로 실험하는 코드를 작성하고 release 모드에서 돌려본 결과 요소의 크기가 클 수록 속도 차이가 컸으며, 최소 2배의 차이가 있었다.

// vector<int>
void int1(const int N) {
    vector<int> v;
    for (int i = 0; i < N; i++) {
        auto d = v.data();
        v.push_back(i);
    }
}

void int2(const int N) {
    vector<int> v;
    v.reserve(N);
    for (int i = 0; i < N; i++) {
        v.push_back(i);
    }
}

// vector<tuple<int,int,int>>
// tuple은 3개의 정수를 담고 있는 구조체라고 생각하자.
void tuple1(const int N) {
    vector<tuple<int, int, int>> v;
    for (int i = 0; i < N; i++) {
        v.push_back({ i,i,i });
    }
}

void tuple2(const int N) {
    vector<tuple<int, int, int>> v;
    v.reserve(N);
    for (int i = 0; i < N; i++) {
        v.push_back({ i,i,i });
    }
}

int main() {
    constexpr int N = 1'000'000;
    constexpr int ITER = 100;
    double total = 0;

    for (int i = 0; i < ITER; i++) {
        auto start = chrono::high_resolution_clock::now();
        // 여기에서 함수를 실행하자.
	// int1(N);
        auto end = chrono::high_resolution_clock::now();
        std::chrono::duration<double> duration = end - start;
        cout << duration.count() << endl;
        total += duration.count();
    }
    cout << endl;
    cout << (total / ITER) << endl;
	return 0;
}

각각 따로 실행
int1	0.00442967
int2	0.00211421

tuple1	0.0143804
tuple2	0.00471348