[C++] STL vector

vector

template < class T, class Alloc = allocator<T> > class vector; // generic template

• T : 요소의 type
• Alloc: 저장공간 할당 모델을 지정. 기본적으로는 allocator 클래스로 지정되어 있다. (가장 간단한 메모리 할당 모델이고, type에 영향을 받지 않는다)

설명

https://www.cplusplus.com/reference/vector/vector/

vector - C++ Reference

여기 있는 설명을 번역함.

 

벡터는 순차적 컨테이너로 사이즈가 변화할 수 있는 배열을 표현한다.

 

배열과 마찬가지로 벡터는 그 요소들을 저장하기 위해 순차적인 저장 공간을 사용한다. 그 말인 즉슨 offset을 이용해서 배열처럼 효율적이게 포인터로 요소들에 접근할 수 있다는 것이다. 하지만 배열들과 다르게, 벡터의 사이즈는 동적으로 변화할 수 있으며, 컨테이너에 의해 그 저장공간은 자동적으로 관리된다.

 

내부적으로 벡터들은 동적 할당 배열을 이용한다. 이 동적으로 할당된 배열은 요소의 수가 늘어날 경우 사이즈를 늘리기 위해 재할당되어야 할 수도 있다. 그 말인 즉슨 새로운 배열을 할당하고, 요소들을 그 새로운 배열로 옮겨야한다는 것이다. 이러한 작업은 수행 시간 측면에서 상대적으로 비싼 작업이며 그래서 벡터들은 새로운 요소가 컨테이너에 추가될 때마다 공간을 재할당하는 것은 아니다.

 

대신에 벡터 컨테이너들은 앞으로 사이즈가 늘어날 것을 대비해서 여분의 공간을 더 할당해둔다. 그렇게 하기 때문에 벡터가 실제로 담고있는 데이터의 크기보다 더 많은 공간을 차지할 수 있다. 라이브러리들은 메모리 사용과 할당에 있어서 사이즈의 균형을 이루기 위해 다양한 방법을 적용하고 있다. 하지만 어떤 케이스이든 재할당은 logarithmatically 자라는 사이즈로 지정되어야 각 요소가 벡터의 끝에 삽입될 때 amortized constant time complexity를 보장받을 수 있다. 

 

그렇기 때문에, 배열과 비교했을 때 벡터는 동적으로 그 사이즈를 조절하기 위해서 메모리를 효율적으로 관리하기 때문에 더 많은 메모리를 차지한다. 

 

다른 동적 컨테이너들 (deques, lists, forward_lists)와 비교했을 때, 벡터는 각 요소에 접근하기에 매우 효율적이며 상대적으로 컨테이너의 끝에 새로운 요소를 삽입하거나 삭제하는 데 효율적이다. 반대로 컨테이너의 끝이 아닌 곳에 삽입과 삭제가 일어나는 동작에 대해는 상대적으로 다른 컨테이너들보다 성능이 낮으며 iterator와 referecne들이 덜 일관적이다. 

 

흔히 사용되는 Member functions

• begin() : 맨 앞을 가리키는 iterator 반환
• end() : 맨 뒤를 가리키는 iterator 반환
• rbegin() : 리버스 iterator를 반환하기 위한 시작점 iterator반환
• rend() :리버스 iterator를 반환하기 위한 종점 iterator반환

 

• size() : 사이즈 반환
• max_size() : 최대 사이즈를 반환한다.
• resize() : 사이즈를 변경한다
• capacity() : 메모리에 할당된 사이즈를 반환한다.
• empty() : vector가 비었는지 확인
• reserve(): capacity(메모리에 실제 할당된 사이즈)를 변경하기 위해 요청
• shrink_to_fit() : 컨테이너의 capacity에 맞춰 나머지 요소들 날려버림

• operator[] : 배열처럼 접근 방식
• at() : 일종의 인덱스에 있는 요소 반환 (범위 확인 함)
• front() : 맨 앞 요소 반환
• back() : 맨 뒤에 요소 반환
• data() : 포인터를 반환함 (예시: https://www.cplusplus.com/reference/vector/vector/data/ 참고)

 

• assign() : 벡터에 특정 값으로 특정 개수 채울 수 있음
• push_back(): 맨 뒤에 요소 추가
• pop_back() : 맨 뒤에 요소 삭제
• insert() : 새 요소 추가
• erase() : 요소 삭제
• swap() : 두 컨테이너의 요소 뒤바꿈 (https://www.cplusplus.com/reference/vector/vector/swap/)
• clear(): 벡터를 비워버림. size도 0으로 바뀜.
• emplace() : 특정 위치에 새로운 요소 추가 가능
• emplace_back(): 뒤에다가 새로운 요소 추가

* push_back, insert()는 이미 존재하는 객체를 컨테이너에 복사하거나 옮기는데 반해, emplace는 현재 마지막 요소의 뒤에다가 새로운 요소를 construct해서 더해준다. (capacity가 넘어갈 경우 자동으로 저장공간이 할당된다.) 

 

사용 예시 및 분석

1) assign, resize, shrink_to_fit

#include <vector>
#include <iostream>

using namespace std;

void printVector(vector<int> v){
	for(vector<int>::iterator it = v.begin(); it<v.end(); it++){
		cout << *it << " ";
	}
	cout << endl;
}

int main(void){
	
	vector<int> v;
	vector<int> v2;

	cout << "---------- ASSIGN-----------" << endl;
	cout << "is vector empty? " << v.empty() << endl;
	v.assign(10, 100);
	printVector(v);
	cout << "vector size: " << v.size() << endl;
	cout << "is vector empty? " << v.empty() << endl;
	cout << "capacity: " << v.capacity() << endl;

	cout << "\n---------- RESIZE ----------" << endl;
	v.resize(7);	
	printVector(v);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;

	
	cout << "\n---------- SHRINK TO FIT ----------" << endl;
	v.shrink_to_fit();
	printVector(v);
	cout << "vector size: " << v.size() << endl;
	cout << "capacity: " << v.capacity() << endl;

resize()를 했을때는 capacity가 변하지 않았지만, shrink_to_fit을 하고나면 capacity가 변경되는 걸 확인할 수 있다. 

 

2. push_back

	cout << "\n---------- PUSH BACK ----------" << endl;
	v.push_back(80);
	v.push_back(90);
	printVector(v);	
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;

size는 2만 늘었지만 자동으로 capactiy가 14로 늘었다. 

 

capactiy를 넘어서는 push_back을 해주면 어떻게 될까?

	cout << endl;
	cout << "push back one" << endl;;
	v.push_back(50000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;
	cout << "push back one" << endl;;
	v.push_back(50000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;
	cout << "push back one" << endl;;
	v.push_back(50000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;
	cout << "push back one" << endl;;
	v.push_back(50000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;
	cout << "push back one" << endl;;
	v.push_back(50000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;
	cout << "push back one" << endl;;
	v.push_back(50000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;

capacity를 넘어선 순간, 28 로 자동 여유롭게 메모리 할당이 된 것을 확인할 수 있다. 

 

3. emplace

emplace는 어떨까?

	cout << "\n---------- EMPLACE ----------" << endl;
	v.emplace(v.begin()+4, 40000);
	printVector(v);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;
	cout << "emplace one" << endl;
	v.emplace(v.begin()+4, 40000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;
	cout << "emplace one more" << endl;
	v.emplace(v.begin()+4, 40000);
	cout << "emplace one more" << endl;
	v.emplace(v.begin()+4, 40000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;
	cout << "emplace one more" << endl;
	v.emplace(v.begin()+4, 40000);
	cout << "emplace one more" << endl;
	v.emplace(v.begin()+4, 40000);
	cout << "vector size: " << v.size() << endl;	
	cout << "capacity: " << v.capacity() << endl;

역시 capacity 14를 넘어가는 순간 28로 자동으로 늘어난다.

 

4. max_size, capacity, front, back

	cout << "\n---------- SIZES ----------" << endl;
	cout << "max size: " << v.max_size() << endl;
	cout << "capacity: " << v.capacity() << endl;

	cout << "\n---------- FRONT, BACK ----------" << endl;
	cout << v.front() << endl;
	cout << v.back() << endl;
	cout << "vector size: " << v.size() << endl;
	

5. pop_back, erase

	
	cout << "\n---------- POP BACK ----------" << endl;
	v.pop_back();
	cout << "vector size: " << v.size() << endl;
	
	cout << "\n---------- ERASE ----------" << endl;
	v.erase(v.begin()+1); 
	cout << "vector size: " << v.size() << endl;

erase는 특정 위치 값을 지울 수 있다는 점 외에, 둘다 size가 자동 변경되는 것을 확인할 수 있다.

 

6. data. swap

	cout << "\n---------- DATA ----------" << endl;
	printVector(v);
	int* ptr= v.data();
	ptr = ptr + 2;
	*ptr = 1000;
	printVector(v);
	
	cout << "---------- SWAP ----------" << endl;
	v2.push_back(1);
	v.swap(v2);
	printVector(v);
	printVector(v2);

data를 통해 특정 위치에 포인터로 접근해서 값을 변경할 수 있는 것을 확인했다. 

swap은 두 벡터의 값들을 뒤바꾼다. 

v2에는 1만 담겨있었고, v에는 값이 꽤 많았는데, 

v에 이제 1만 담겨있고, v2에 v의 값들이 저장되어 있는 것을 확인할 수 있다.