[C++::STL] 1. vector

1. vector 

vector는 sequence container에 속해있는 컨테이너다. vector는 가변길이 배열이라고 볼 수 있다. 

따라서, vector를 정의할 때는 따로 size할당을 해주지 않아도 된다. (물론, 해줄 수도 있다.) 

vector를 정의할 때는, vector <type> name; 으로 정의하면 된다. 

이때, type에는 int , double, char, pair <int, int>, tuple <int, int, int>등이 들어갈 수 있다. template을 이용하였기 때문에, 이러한 모든 타입이 허용된다. 

 

2. vector의 특징

1. vector는 임의의 위치에 있는 원소에 O(1)으로 접근할 수 있다.

예를 들어, v [ i ]라고 하면, i번째 원소를 찾아준다.

 

2. vector는 맨 뒤에 새로운 원소를 추가하거나 지우는 과정을 O(1)에 수행할 수 있다. ( vector는 10개의 원소가 들어있을 때, 20개를 저장할 공간을 미리 할당한다고 한다. 하지만, 이 공간이 다 채워진다면, 새로운 큰 공간을 다시 할당하고, 기존의 원소들을 복사한다고 한다. 이경우 O(n)이라는 시간복잡도가 된다. 그러나, 이러한 case는 매우 드물다고 한다. )

 

3. vector는 임의의 위치에 원소를 추가하거나 제거하는 것은 O(n)이다. 그 이유는 원소를 뺀 만큼 남아있는 원소들을 이동시켜줘야 하기 때문이다. 

 

3. vector의 반복자

vector의 반복자를 얻기 위해서는 vector_name.begin() , vector_name.end() 함수를 사용하면 된다고 한다. 이때, vector_name.end()는 vector의 마지막원소 다음 포인트를 가리킨다. 따라서, 사용에 주의를 요한다.  

#include <bits/stdc++.h>
using namespace std;

vector<int> v;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5); 

	for (vector<int>::iterator itr = v.begin(); itr != v.end(); itr++) {
		cout << *itr << '\n';
	}
}

이때, itr은 int형 벡터를 가리키니, itr++를 할 때마다, 4byte씩 증가함을 예측할 수 있다. 따라서, 메모리를 읽을 때, 4byte씩 읽게 된다. 또한, itr은 포인터와 유사하므로, *itr을 이용해 값에 접근하게 된다. 

 

4. 반복자를 사용해 함수 이용 

v.insert ( v.begin() + k, val); --> v [k] 앞에 val을 추가

 

v.erase(v.begin() + k); --> v [k]를 제거 ( return 값은 제거된 값 다음을 포인팅 하고 있는 반복자다. 만약에 원소가 마지막이었다면, end()를 반환한다. 범위를 지정해 제거해 주는 경우, [start, end)였다면, end()를 반환한다.) ex) v.erase(v.begin(), v.begin() + 2)라면 v [0]와 v [1]까지 제거된 후, v [2]를 포인팅 하고 있는 iterator를 반환한다. 

 

vector <type>::const_iterator citr = v.cbegin() + k; 이렇게 설정하면, *citr 값을 변경하지 못한다. 

 

vector <type>::reverse_iterator riter = v.rbegin();  

--> 사용방법 : for (; riter!= v.rend(); riter++) cout << *riter << '\n';

 

vector <type>::const_reverse_iterator criter = v.crbegin(); 

 

 v.push_back(val)  --> val을 마지막원소 뒤에 추가

 

v.pop_back() --> 마지막원소 버림. 

 

 

 

 

5. 내가 문제를 풀 때 많이 쓰는 케이스

전역변수로 vector를 선언한 다음, main에서 처리를 했다. 

 

case 1.

#include <bits/stdc++.h>
using namespace std;

vector<int> v;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 

	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] << '\n';
	}
}

 

case 2.

#include <bits/stdc++.h>
using namespace std;

vector<int> v;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5); 

	for (int& s : v) {
		cout << s << '\n';
	}
}

범위 기반 for 문을 이용하는 경우다. 이때, 값을 복사하기 싫고, 그냥 reference만 받고 싶다면 위와 같이 &를 붙여주면 된다. 

타입을 설정하기 귀찮은 경우, type자리에 auto를 적으면 된다. 

#include <bits/stdc++.h>
using namespace std;

vector<int> v;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5); 

	for (auto s : v) {
		cout << s << '\n';
	}
}

 

 

6. 구조체를 배운기념으로  

#include <bits/stdc++.h>
using namespace std;

typedef struct family {
	string name; 
	int age; 
} Family;
vector<Family> v;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	v.push_back({ "rudgh99",26 }); 
	cout << v[0].name << '\n';
	
}

 

reference : https://modoocode.com/223

씹어먹는 C++ - <10 - 1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)>