[C++] vector 클래스 정리
🦥 vector?
Sequence containers representing arrays that can change in size
출처 : https://www.cplusplus.com/reference/vector/vector/
해석해보면 크기를 바꿀 수 있는 순차 컨테이너라는 뜻이다.
- fast random access ▶ 특정 위치의 원소에 빠르게 접근할 수 있다. O(1)
- allow denoting initial capacity ▶ 크기를 초기화(initialize) 할 수 있다.
- dynamically allocated array, automatically resize ▶ 가변적이다. 즉, 벡터에 원소가 삽입되고 삭제됨에 따라 자동으로 resize 한다. 또한, 연속된 메모리 기반의 컨테이너이다.
- inserting or removing the element at the end is efficient, but at other places, it is inefficient ▶ 벡터의 마지막에 원소를 삽입 또는 삭제하는 것은 효율적이다. 하지만 그 이외의 위치에서의 삽입과 삭제는 비효율적이다.
🦥 vector의 생성자와 초기화
▶ vector, vector 배열, 2차원 vector의 생성 방법 정리
vector 헤더 추가
#include <vector>
1) 비어있는 벡터 v 생성
vector<int> v1;
2) 0으로 초기화 된 4개의 원소를 가진 벡터 v를 생성
vector<int> v2(4);
3) 1, 2, 3을 원소로 하는 벡터 v 생성
vector<int> v3 = { 1, 2, 3 };
vector<int> v4{ 1, 2, 3 };
4) 벡터 배열 생성 : 벡터가 원소인 배열을 생성한다. 이때, 행은 가변이고 열은 고정이다. 즉, 벡터의 크기는 가변, 배열의 크기는 고정이다.
vector<int> v5[] = { {1, 2}, {3, 4} };
5) 2차원 벡터 생성 : 2차원 벡터의 행과 열은 모두 가변이다.
vector<vector<int>> v6;
6) n개의 벡터를 원소로 하는 2차원 벡터 생성 : n개의 vector
vector<vector<int>> v7(n, vector<int>(m, k));
7) 2차원 벡터의 원소를 직접 입력하여 초기화
vector<vector<int>> v8({
vector<int>({1, 2, 3}),
vector<int>({4, 5, 6, 7, 8}),
vector<int>({9, 10}),
vector<int>({11, 12, 13})
});
🦥 vector의 함수들
🌴 Iterator
Iterator를 활용하여 vector의 원소에 접근할 수 있다
v.begin(): 벡터의 첫번째 원소를 가리키는 iteratorv.end(): 벡터의 마지막 원소 다음을 가리키는 iterator (마지막 원소 아님!!)
/* 벡터의 모든 원소 출력 */
for (auto i = v.begin(); i != v.end(); i++) {
cout << *i << endl;
}
🌴 Fuction
vector 컨테이너의 멤버 함수들
1) 초기화
v.assign(5): 원소 5개 0으로 초기화v.assign(5,10): 원소 5개 10으로 초기화
2) 원소 접근
v.front(): 첫 번째 원소v.back(): 마지막 원소v.at(i): i번째 원소
3) 원소 삽입 / 삭제
v.push_back(5): 마지막 원소 뒤에 ‘5’ 삽입v.pop_back(): 마지막 원소 삭제v.insert(v.begin(), 3): 벡터의 처음에 (iterator가 가리키는 위치에) ‘3’ 추가
4) 벡터 크기 관련
v.size(): 실제 원소 수v.capacity(): 할당된 메모리 크기 (공간 수)v.reserve(10): 메모리 공간 크기를 10으로 변경. 늘어난 공간은 비어 있음v.resize(10): 메모리 공간 크기를 10으로 변경. 늘어난 공간을 0으로 초기화
5) 원소 삭제
v.clear(): 전체 원소 삭제v.erase(v.begin()): iterator가 가리키는 원소 삭제. size만 변함.
🦥 벡터 배열과 2차원 벡터의 차이
🌴 벡터 배열
벡터를 원소로 하는 배열이다. 이때, 벡터의 크기는 변할 수 있지만, 배열의 크기는 변할 수 없다. 즉, 벡터 배열은 행은 가변, 열은 고정이다
*아래는 이해를 돕기 위해 임의로 그린 그림이다.
vector<int>v[] = { {1, 2}, {3, 4} };
1행의 벡터에 원소를 추가하여 { {1, 2, 5}, {3, 4} } 를 만들 수는 있지만, 배열에 {5, 6, 7} 벡터를 하나 더 추가하여 { {1, 2}, {3, 4}, {5, 6, 7} } 를 만들 수는 없다.
🌴 2차원 벡터
벡터의 원소가 벡터인 구조이다. 행과 열이 모두 가변이다
*아래는 이해를 돕기 위해 임의로 그린 그림이다.
예를 들어, 아래와 같은 2차원 벡터를 만들었을 때,
vector<int>v[] = { {1, 2}, {3, 4} };
1행에 원소 5를 추가하여 { {1, 2, 5}, {3, 4} } 를 만들 수도 있고, 1열에 원소 5를 추가하여 { {1, 2}, {3, 4}, {5} } 를 만들 수도 있다.
🦥 2차원 벡터의 정렬
🌴 행 정렬
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
vector<vector<int>> v = { {3, 1}, {2, 1, 5}, {6} };
for (int i = 0; i < v.size(); i++) {
sort(v[i].begin(), v[i].end());
}
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v[i].size(); j++) {
cout << v[i][j] << " ";
}
cout << endl;
}
return 0;
}
[실행 결과]
1 3
1 2 5
6
🌴 열 정렬
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
vector<vector<int>> v = { {1, 3}, {1, 2, 5}, {6} };
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v[i].size(); j++) {
cout << v[i][j] << " ";
}
cout << endl;
}
return 0;
}
[실행 결과]
1 2 5
1 3
6
🦥 벡터의 size()와 capacity() 그리고 resize()와 reserve()
v.capacity(): 벡터가 할당된 공간의 크기v.size(): 벡터의 원소의 개수v.reserve(n)- 벡터의 크기를 n으로 할당.
- 공간만 할당하고 초기화 X.
- size는 증가하지 않고, capacity만 n으로
- 현재 공간 크기보다 더 작게는 할 수 없음.
v.resize(n)- 벡터의 크기를 n으로 할당.
- 늘어난 공간은 0으로 초기화.
- size와 capacity 모두 n으로
- 현재 공간 크기보다 더 작게할 수 있음.
🌴 resize와 reserve의 size와 capacity 변화
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
vector<int> v;
// 10개 원소 push
printf("------10 push-------\n");
for (int i = 0; i < 10; i++) {
v.push_back(i);
}
printf("size: %d cap: %d\n\n", v.size(), v.capacity());
// 20으로 resize
v.resize(20);
printf("-----resize 20 -----\n");
printf("size: %d cap: %d\n", v.size(), v.capacity());
for (auto i = v.begin(); i != v.end(); i++) {
cout << *i << " ";
}
// 30으로 reserve
v.reserve(30);
printf("\n\n-----reserve 30 -----\n");
printf("size: %d cap: %d\n", v.size(), v.capacity());
for (auto i = v.begin(); i != v.end(); i++) {
cout << *i << " ";
}
return 0;
}
[실행 결과]
------10 push-------
size: 10 cap: 13
-----resize 20 -----
size: 20 cap: 20
0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0
-> 늘어난 공간 0으로 초기화
-----reserve 30 -----
size: 20 cap: 30
0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0
-> reserve는 공간만 할당
🌴 현재 공간 크기보다 작은 크기로 resize, reserve
현재 공간 크기보다 작은 크기로 resize 했을 때에는 공간이 줄어들지만, reserve 했을 때는 그대로이다. reserve는 현재 공간 크기보다 더 작게할 수는 없기 때문!
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
vector<int> v;
// 20개 원소 push
printf("------20 push-------\n");
for (int i = 0; i < 20; i++) {
v.push_back(i);
}
printf("size: %d cap: %d\n", v.size(), v.capacity());
for (auto i = v.begin(); i != v.end(); i++) {
cout << *i << " ";
}
// 10으로 resize
printf("\n-----resize 10 -----\n");
v.resize(10);
printf("size: %d cap: %d\n", v.size(), v.capacity());
for (auto i = v.begin(); i != v.end(); i++) {
cout << *i << " ";
}
>
//5로 reserve
printf("\n-----reserve 5 -----\n");
v.reserve(5);
printf("size: %d cap: %d\n", v.size(), v.capacity());
for (auto i = v.begin(); i != v.end(); i++) {
cout << *i << " ";
}
return 0;
}
[실행 결과]
------20 push-------
size: 20 cap: 28
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
-----resize 10 -----
size: 10 cap: 28
0 1 2 3 4 5 6 7 8 9
-----reserve 5 -----
size: 10 cap: 28
0 1 2 3 4 5 6 7 8 9
🌴 벡터는 동적 배열이다.
동적 배열에서는 원소가 추가되면서 배열의 크기를 늘려줄 때 마다, 요소들을 담을 공간을 할당하고, 기존의 데이터를 복사하고, 기존의 공간을 제거하는 작업까지 해야한다. 이렇게 추가할 때마다 이런 일을 수행하게 되면 비용이 너무 많이 들어서, 동적 배열에서는 더 이상 추가할 공간이 없을 때 몇 배로 확장할 것인지 결정한다. 1씩 계속 늘어나는 것이 아니라 일정한 크기로 늘려놓고 추가하고, 다시 공간이 없으면 다시 일정 배율로 확장하고 추가하는 방식으로 동작한다. (growth rate)
벡터에서 원소를 추가할 때마다 size는 1씩 증가하지만, capacity는 1씩 증가하지 않고, 일정 범위마다 일정 배율로 늘어난다는 것이다.
아래 예제에서 확인해볼 수 있다.
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
vector<int> v;
printf("\n------push-------\n");
for (int i = 0; i < 30; i++) {
v.push_back(i);
printf("size: %d cap: %d\n", v.size(), v.capacity());
}
printf("\n------pop-------\n");
for (int i = 0; i < 30; i++) {
v.pop_back();
printf("size: %d cap: %d\n", v.size(), v.capacity());
}
}
[실행 결과]
Reference
Leave a comment