[C++] 배열의 진화형, 벡터(std::vector)

• std::array의 크기는 컴파일 시간에 결정되는 상수여야 합니다. 따라서 프로그램 실행 중에는 변경할 수 없습니다.
• std::array의 크기가 고정되어 있어서 원소를 더 추가하거나 삭제할 수 없습니다.
• std::array의 메모리 할당 방법을 변경할 수 없습니다. 항사 스택 메모리를 사용합니다.

위와 같은 std::array의 단점을 피하고 동적,가변의 데이터를 처리하기 위해 std::vector가 등장합니다.

가변 크기 배열 이라고 생각하면 됩니다.

---

std::vector 초기화

// 크기가 0인 벡터 선언 
std::vector<int> vec;

// 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언 
std::vector<int> vec = {1, 2, 3, 4, 5};

// 크기가 10인 벡터 선언 
std::vector<int> vec(10);

// 크기가 10이고, 모든 원소가 5로 초기화된 벡터 선언 
std::vector<int> vec(10, 5);

---

push_back() 또는 insert()함수

벡터에 새로운 원소를 추가하려면 push_back() 또는 insert()함수를 사용합니다. 

 

push_back()함수는 벡터의 맨 마지막에 새로운 원소를 추가합니다.

 

insert()함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가합니다.

 

push_back()함수의 동작을 수도코드로 나타내면 다음과 같습니다.

push_back(val):
	if size capacity //새 원소를 추가할 공간이 있는 경우
		- 마지막 원소 다음에 val 저장 - 벡터 크기를 1만큼 증가
		- return;


if vector is already full //할당된 메모리 공간이 가득 차 있는 경우
	- 2*size 크기의 메모리를 새로 할당
	- 새로 할당한 메모리로 기존 원소 전부를 복사/이동
	- 데이터 포인터를 새로 할당한 메모리 주소로 지정
	- 마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가

맨 뒤에 원소를 삽입할 때, 뒤쪽에 남아있는 공간이 있다면 O(1)의 시간이 걸립니다.

 

그러나 공간이 충분하지 않으면 모든 원소를 복사/이동해야 하며, 이때는 O(n)의 시간이 걸립니다

 

 

insert() 함수의 경우, 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요합니다. 

필요한 경우 메모리를 새로 할당하는 작업도 수행됩니다. 

원소들을 이동하는 연산 때문에 insert() 함수는 O(n)의 시간이 걸립니다.

 

 

그리고 벡터는 일반 배열과 같은 방식의 접근방법이 허용됩니다.

[ ]기호를 활용할수 있다는 뜻입니다.

vector<int> vec;
vec.push_back(2);
vec.push_back(5);
cout<<vec[1]<<endl;

//결과:5 출력됨

---

find()함수

벡터에서 특정 값이 들어 있는지 찾고, 해당 값이 있는 인덱스를 알기 위해서 find()함수를 많이 사용합니다.

 

1. vector내에 해당 원소가 존재하는지 확인

find(v.begin(), v.end(), 찾을 대상)

리턴 값이 v.end()인 경우 => 해당 원소가 존재하지 않는 것

리턴 값이 v.end()가 아닌 경우 => 해당 원소 존재하는 것

 

2. vector내에서 해당 원소가 위치하는 인덱스 찾기

find(v.begin(), v.end(), 찾을 대상) - v.begin()

 

 

push_back()과 insert()함수와 find()함수를 사용하는 예제 코드는 다음과 같습니다.

std::vector<int> vec;				// 비어 있는 벡터 생성: {}
vec.push_back(1);	    			// 맨 뒤에 1 추가: {1}
vec.push_back(2);	        		// 맨 뒤에 2 추가: {1, 2}
vec.insert(vec.begin(), 0);			// 맨 앞에 0 추가: {0, 1, 2}
vec.insert(find(vec.begin(), vec.end(), 1), 4); // 1 앞에 4 추가: {0, 4, 1, 2}

 

---

emplac_back() 또는 emplace()함수

emplac_back() 또는 emplace()함수를 사용하면 효율적인 원소 추가가 가능합니다

 

push_back() 또는 insert() 함수의 단점 중 하나는 이들 함수가 추가할 원소를 먼 저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다는 점입니다. 

 

이러한 단 점은 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화할 수 있으며, 이러한 기능이 emplace_back() 또는 emplace() 함수에 구현되어 있습니다. 

 

그러므로 push_back() 또는 insert() 같은 일반적인 삽입 함수 대신 emplace_back() 또는 emplace() 함수를 사용하는 것이 성능향상에 도움이 됩니다.

이 경우 새 원소 위치에서 곧바로 객체가 생성되기 때문에 이들 함수인자에 생성된 객체를 전달하는 것이 아니라 생성자에 필요한 매개변수를 전달해야 합니다. 그러면 emplace_back() 또는 emplace() 함수가 전달된 생성자 인자를 적절하게 사용하여 객체를 생성하고 삽입합니다.

 

그러나, 자주 쓰이는 함수 같지는 않고, MS측에서 호환성이 떨어진다는??식의 답변을 해서 개인적으로만 사용하는게 좋을 것 같습니다.

---

원소 제거를 위해 pop_back()과 erase()함수

pop_back() 함수는 벡터에서 맨 마지막 원소를 제거하며, 그 결과 벡터 크기는 1만큼 줄어듭니다.

 

erase() 함수는 두 가지형태로오버로딩되어있습니다.

한 가지 형태는 반복자 하나를 인자로 받아 해당 위치 원소를 제거하고, 다른 형태는 범위의 시작과 끝을 나타내는 반복자를 받아 시작부터 끝 바로 앞 원소 까지 제거합니다. 즉, 시작 위치 원소는 제거되지만 끝 위치 원소는 제거되지 않습니다

 

C++표준에서는 이들 함수 동작 시 벡터의 용량이 감소할 필요가 없지만, 컴파일러마다 달라질 수 있다고 합니다.

(저장된 원소의 갯수는 줄지만 실제 해당 벡터가 차지하는 용량을 의미)

 

pop_back()은 맨 뒤만 건드리기때문에 빠르고, 시간복잡도는 O(1)입니다.

 

그러나 erase()는 특정 위치 원소를 삭제한 후, 뒤쪽의 원소들을 모두 앞으로 이동해야 하기 때문에 O(n)의 시간이 소요됩니다.

std::vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8,9};

// 맨 마지막 원소 하나를 제거합니다: {0, 1, 2, 3, 4, 5, 6, 7, 8} 
vec.pop_back();

//맨처음원소를제거합니다: {1,2,3,4,5,6,7,8} 
vec.erase(vec.begin());

// 1번째 원소부터 4번째 앞 원소까지 제거합니다: {1, 5, 6, 7, 8} 
vec.erase(vec.begin() + 1, vec.begin() + 4);

 

---

유용한 std::vector 멤버 함수

• clear() : 모든 원소를 제거하여 완전히 비어 있는 벡터로 만들음
• shrink_to_fit() : 여분의 메모리 공간을 해제하는 용도로 사용됨. 이 함수를 호출하면 벡터의 용량이 벡터 크기와 같게 설정됨. 벡터 크기가 더 이상 변경되지 않을 때 사용하면 유용
• reserve(capacity) : 벡터에서 사용할 용량을 지정함. 매개변수로 지정한 값이 현재 용량보다 크면 메모리를 매개변수만큼 재할당함. 매개변수 값이 현재 용량보다 같거나 작으면 아무런 동작을 하지 않음. 이 함수는 벡터의 크기를 변경하지 않음.
• resize(count) :  count만큼 배열의 원소 갯수를 조정함. reserve와 비슷해 보이지만, resize는 v.size()>count 일 경우 원소의 갯수를 줄이고 v.size<count일 경우 value가 없으면 value_type의 기본 생성자를 호출해 size가 count가 될때까지 늘립니다. 

 

reserve()와 resize()의 차이는 아래 코드로 확인 가능합니다. (코드 출처: 깐깐한 조부장 블로그)

vector<int> v1, v2;
v1.reserve(10000);
v2.resize(10000);

cout << "v1.size(): " << v1.size() << '\n';
cout << "v1.capacity(): " << v1.capacity() << '\n';

cout << "v2.size(): " << v2.size() << '\n';
cout << "v2.capacity(): " << v2.capacity() << '\n';

결과:
v1.size() : 0
v1.capacity() : 10000
v2.size() : 10000
v2.capacity() : 10000

 

---

벡터 복사 std::copy

vector<int> v1={1,2,3};
vector<int> v2(v1.size()); //반드시 복사할 벡터크기 이상이어야함

std::copy(v1.begin(),v1.end(),v2.begin());
// v2속 원소는 1,2,3으로 v1과 같게됨

---

벡터 이어붙이기 insert()함수

vector<int> v1 { 1,2,3 };
vector<int> v2 { 4,5,6 };

// 1 2 3 4 5 6
vector<int>::iterator it = v1.insert(v1.end(), v2.begin(), v2.end());
cout<<*it; //4출력됨

insert()함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가합니다.

 

 

return값은 추가를 시작 한 곳의 위치를 나타내는 반복자입니다.

즉 위 예시같이 cout<<*it를하면 4가 출력됩니다.

 

vec.insert(vec.begin(), 0);			// 맨 앞에 0 추가: {0, 1, 2}

이런식으로 특정 값을 앞에도 붙일 수 있습니다.

---

std::vector는 템플릿 매개변수에서 데이터 타입 다음에 할당자(allocator)를 전달할 수 있습니다.
사용자 정의 할당자를 사용하려면 정해진 인터페이스를 따라야합니다.
벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는 allocate(),deallocate(),construct(),destroy()등의 함수를 제공해야함.