[자료구조 C/C++] #2 Vector

✏️ Vector란?

C++에는 두 가지 유형의 container가 있는데, 그 중 Vector는 Sequence Container범주에 속합니다.
동적으로 메모리 할당이 가능하며 자동적으로 heap영역에 메모리가 생성되며 C에서 넘어오신 분들은 malloc이나 calloc을 생각하시면 될 것 같습니다. 배열 크기를 선언하고 사용하는 것보다 더 편리하며 오버플로우나 segmentation fault가 발생할 가능성이 줄어듭니다.

 

✏️ Vector의 시간 복잡도

임의 접근 시 => O(1)
벡터의 끝에 원소를 삽입하거나 삭제 시=> O(1)
원소의 삽입과 삭제 시 =>O(n)  

 

✏️ Vector 사용법

// 우선 vector헤더파일을 불러와야 합니다 
#include<vector>

// vector<Data Type>변수명
vector<int>v
// 크기가 정해져있지 않아 자유롭게 크기 변경이 가능

vector<int>v(5)
// 크기가 정해져 있어서 크기 변경이 불가능합니다.

// 2차원은 vector<vector<int>>v 으로 하면 됩니다.

 

✏️ Vector 멤버 함수

멤버 함수	설명
v.assign(n, m)	m으로 n개의 원소 할당합니다.
v.at(index)	index번째 원소를 반환합니다. 유효한 index인지 먼저 검사를 하기 때문에 안전성은 보장되지만 시간적인 측면에서 좋지 않습니다.
v[index]	index번째 원소를 반환한다. 일반적인 배열 접근 방식과 동일합니다.
v.front()	첫 번째 원소를 반환합니다. 이때 원소는 삭제되지 않습니다.
v.back()	마지막 원소를 반환한다. 이때 원소는 삭제되지 않습니다.
v.clear()	vector안의 모든 원소를 제거합니다. 다만 처음에 할당된 메모리는 유지됩니다(size는 줄어들지만 capacity는 줄어들지 않습니다).
v.begin()	첫 번째 원소를 가리키는 iterator를 반환합니다.
v.end()	마지막 원소 다음을 가리키는 iterator를 반환합니다.
v.push_back(m)	vector 마지막 원소 뒤에 원소 m을 삽입합니다.
v.pop_back()	vector의 마지막 원소를 제거합니다.
v.rbegin()	거꾸로 시작해서 첫 번째 원소를 가리키는 iterator를 반환합니다.
v.rend()	거꾸로 시작해서 마지막 원소를 가리키는 iterator를 반환합니다.
v.reserve(n)	n개의 원소를 저장할 공간을 예약합니다.
v.resize(n)	vector의 크기를 n개로 변경합니다. 만약 크기가 커진 경우에는 빈 공간을 0으로 채워줍니다.
v.resize(n, m)	vector의 크기를 n개로 변경합니다. 만약 크기가 커진 경우에는 빈 공간을 m으로 채워줍니다.
v.size()	원소의 갯수를 반환합니다.
v.capacity()	할당된 공간의 크기를 반환합니다. 공간의 크기를 반환하는 것이지 원소의 갯수를 반환하는 것이 아니기 때문에 size()함수와 다릅니다.
v2.swap(v1)	v1과 v2를 swap합니다.
v.insert(it, m)	it가 가리키는 위치에 m의 값을 삽입 후, 해당 위치를 가리키는 반복자(iterator)를 반환해줍니다.
v.insert(it, k, m)	it가 가리키는 위치부터 k개의 m 값을 삽입합니다. 이때 다음 원소들은 자동적으로 뒤로 밀립니다.
v.erase(it)	it반복자가 가리키는 원소를 제거한다. size는 줄어들지만 capacity는 그대로 유지됩니다.
v.erase(start, end)	start 반복자부터 end 반복자까지 원소를 제거합니다.
v.empty()	vector가 비어있으면 true를 비어있지 않으면 false를 return합니다.
v.max_size()	v가 담을 수 있는 최대 원소의 개수를 반환합니다.

✏️ 기타

멤버 함수	설명
v.sort(v.begin(),v.end())	vector를 정렬해줍니다.
v.unique(v.begin(),v.end())	중복되는 원소들이 있을 때 유용한 함수입니다. vector를 정렬한 후 중복되는 원소들을 뒤로 보내줍니다. 그리고 나서 반복자는 중복이 시작되는 지점을 반환해줍니다. 이후 중복 원소들은 erase함수를 통해 삭제해주시면 됩니다. 다만 이 두 함수들은 <Algorithm>이라는 헤더파일안에 있으니 주의하셔야 합니다.
vector<pair<int,int>>v	pair와도 함께 사용할 수 있습니다. 원소 접근 시에는 v.front().first,v.front().second와 같이 접근합니다.