[C++] vector container 정리 및 기본 사용법과 응용

[목차]

1. vector란?

2. vector의 장단점 

3. vector 사용 준비

4. vector 생성자

5. vector 멤버 함수

6. 2차원 vector

7. vector의 응용

 

 

그동안 PS를 하면서 vector가 반드시 필요한 문제를 접하지 못해서 그런지, 항상 그동안 익숙했던 배열을 이용해 왔다. 하지만 vector를 이용하면 훨씬 편리하다는 주변의 조언에 따라 이제라도 최대한 vector를 이용하려고 한다.

(사실 처음에 vector가 indexing이 안 되는 줄 알고 사용을 안 했는데,

배열과 똑같이 indexing이 되니 배열을 쓸 이유가 없는 것 같긴 하다....) 

 

---

1. vector란?

 

C++ STL에는 크게 두 개의 container가 있다. 배열처럼 원소들을 순서대로 보관하는 'Sequence Container'와 key값을 이용하여 대응하는 방식인 'Associative container'이다.  

 

vector는 둘 중 Sequence Container에 속하며, "자동으로 메모리가 할당되는 배열"이라고 이해하면 될 것이다. 

vector를 생성하면 heap 메모리에 동적으로 할당된다. 

또한 다른 container와 마찬가지로 template을 이용하기 때문에 데이터 타입은 자유롭게 이용할 수 있다. 

 

기본적으로 맨 뒤에서 원소의 삽입과 삭제가 가능하며, 중간에서도 가능하지만 크게 효율적이지 않다.

 

vector에 대한 일반적인 연산에 대한 복잡도는 다음과 같다.

 - 임의 접근 (Random Access) = O(1)

 - 벡터의 끝에 원소를 삽입하거나 삭제 = O(1)

 - 원소의 삽입과 삭제 = O(n)  (마지막 원소로부터의 거리에 비례)

 

 

2. vector의 장단점 (feat. 배열과의 차이)

 

<장점>

 

1. 배열과 달리 자동으로 메모리를 할당시켜주어 처음부터 원소의 개수를 지정해둘 필요가 없고, 원소의 삽입/삭제 시 효율적인 메모리 관리가 가능하다. 

2. vector의 중간의 원소를 삭제하거나, vector의 크기를 구하는 작업 등을 알아서 해주는 유용한 멤버 함수들이 많다. 

3. 배열 기반이므로 랜덤 접근(Random Access)이 가능하다. 

 

<단점>

 

1. 배열 기반의 container이므로 원소의 삽입, 삭제가 자주 수행되면 시간적인 측면에서 비효율적이다. 

 

 

3. vector 사용 준비

- vector container를 이용하기 위해서는 <vector> 헤더 파일을 추가해주어야 한다. 

- using namespace std; 를 추가하면 번거롭게 vector 앞에 std를 붙일 필요가 없다. 

- 기본적인 vector 선언 방식은 vector<[Data type]> [Name] 이다. 

 

 

4. vector 생성자

vector<[type]> v	[type]형의 빈 vector를 생성
vector<[type]> v(n)	0으로 초기화 된 n개의 원소를 가지는 [type]형의 vector를 생성
vector<[type]> v(n, m)	m으로 초기화 된 n개의 원소를 가지는 [type]형의 vector를 생성
vector<[type]> v2(v1)	v1을 복사하여 v2 vector를 생성
vector<vector<[type]>> v	[type]형의 2차원 vector 생성
vector<[type]> v = {a1, a2, a3, ... }	{a1, a2, a3, ...} 으로 초기화 된 [type]형의 vector 생성

 

예시)

#include<iostream>
#include<vector>

using namespace std;

int main(void) {
    vector<int> v1;            // 빈 vector
    vector<int> v2(5);       // {0, 0, 0, 0, 0}
    vector<int> v3(5, 1);      //{1, 1, 1, 1, 1}
    vector<int> v4(v3);       //v4 = v3
    vector<vector<int>> v5;  //2차원 벡터 
    vector<int> v6 = { 1, 2, 3, 4, 5 }; 
    
    cout << "v1 : ";
    for (int i = 0; i < v1.size(); i++) cout << v1[i] << ' '; 
    cout << "\nv2 : ";
    for (int i = 0; i < v2.size(); i++) cout << v2[i] << ' ';
    cout << "\nv3 : ";
    for (int i = 0; i < v3.size(); i++) cout << v3[i] << ' ';
    cout << "\nv4 : ";
    for (int i = 0; i < v4.size(); i++) cout << v4[i] << ' ';
    cout << "\nv6 : ";
    for (int i = 0; i < v6.size(); i++) cout << v6[i] << ' ';
}

 

결과)

 

 

5. vector 멤버 함수

 

vector container에는 vector를 다루는 유용한 멤버 함수가 많다.

vector<int> v; 라고 선언되었다고 가정하고, 하나씩 살펴보자.

 

v.assign(n, m)	m으로 n개의 원소 할당
v.at(index)	index번째 원소를 반환한다. 유효한 index인지 체크하기 때문에 안전하다.
v[index]	index번째 원소를 반환한다. 배열과 같은 방식이며 유효성을 체크하지 않는다.
v.front()	첫 번째 원소를 반환한다.
v.back()	마지막 원소를 반환한다.
v.clear()	모든 원소를 제거한다. 메모리는 그대로 남아있게 된다. (size는 줄어들고 capacity는 유지)
v.begin()	첫 번째 원소를 가리키는 반복자(iterator)를 반환한다.
v.end()	마지막 원소 다음을 가리키는 반복자(iterator)를 반환한다.
v.push_back(m)	마지막 원소 뒤에 원소 m을 삽입한다.
v.pop_back()	마지막 원소를 제거한다.

 

예시)

#include<iostream>
#include<vector>

using namespace std;
void print_(vector<int> v) {
    for (int i = 0; i < v.size(); i++)cout << v[i] << ' ';
    cout << '\n';
}

int main(void) {
    vector<int> v = { 1, 2, 3, 4, 5 };
   print_(v);  //{1, 2, 3, 4, 5}
    v.assign(2, 5);
   print_(v);  //{5, 5}
    v.push_back(3);
    v.push_back(4);
   print_(v);  //{5, 5, 3, 4}
    cout << v.at(0) << ' ' << v.at(2) << '\n';  // 5 3
    cout << v[1] << ' ' << v[3] << '\n';  // 5 4
    cout << v.front() << ' ' << v.back() << " \n"; // 5 4
    v.pop_back();
   print_(v);  // {5, 5, 3}
    v.clear();
   print_(v);  // {  }
}

 

 

결과)

 

v.rbegin()	거꾸로 시작해서 첫 번째 원소를 가리키는 반복자(iterator)를 반환한다.
v.rend()	거꾸로 시작해서 마지막 원소를 가리키는 반복자(iterator)를 반환한다.
v.reserve(n)	n개의 원소를 저장할 공간을 예약한다.
v.resize(n)	크기를 n개로 변경한다. 커진 경우에는 빈 곳을 0으로 초기화한다.
v.resize(n, m)	크기를 n개로 변경한다. 커진 경우에는 빈 곳을 m으로 초기화한다.
v.size()	원소의 개수를 반환한다.
v.capacity()	할당된 공간의 크기를 반환한다. (size()와 다름)
v2.swap(v1)	v1과 v2를 swap한다.
v.insert(iter, m)	iter가 가리키는 위치에 m의 값을 삽입한다. 그리고 해당 위치를 가리키는 반복자(iterator)를 반환
v.insert(iter, k, m)	iter가 가리키는 위치부터 k개의 m 값을 삽입한다. 다음 원소들은 뒤로 밀린다.
v.erase(iter)	iter 반복자가 가리키는 원소를 제거한다. capacity는 그대로 유지된다.
v.erase(start, end)	start 반복자부터 end 반복자까지 원소를 제거한다.
v.empty()	vector가 비어있으면 true를 반환한다.
v.max_size()	v가 담을 수 있는 최대 원소의 개수(메모리 크기) 반환
v.shrink_to_fit()	capacity의 크기를 vector의 실제 크기에 맞춤

 

예시)

#include<iostream>
#include<vector>

using namespace std;

int main(void) {
    vector<int> v = { 1, 2, 3, 4, 5 };
    vector<int> ::iterator iter;

    cout << "vector = ";
    for (iter = v.begin(); iter != v.end(); iter++)    cout << *iter << ' ';  //iterator 이용
    cout << "\n\n";

    cout << "reverse vector = ";
    vector<int> ::reverse_iterator riter;
    for (riter = v.rbegin(); riter != v.rend(); riter++) cout << *riter << ' '; //reverse iterator 이용
    cout << "\n\n";
    
    cout << "vector size = " << v.size() << '\n';
    cout << "vector capacity = " << v.capacity() << "\n\n";

    v.resize(6);        
    cout << "vector resize(6) = ";
    for (int i = 0; i < v.size(); i++)     cout << v[i] << ' '; 
    cout << "\n\n";
    
    v.resize(8, 3);    
    cout << "vector resize(8, 3) = ";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    cout << "\n\n";

    v.resize(5);        
    cout << "vector resize(5) = ";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    cout << "\n\n";

    v.insert(v.begin() + 3, 10);
    cout << "vector insert(v.begin() + 3, 10) = ";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    cout << "\n\n";

    v.insert(v.begin() + 1, 4, 9);
    cout << "vector insert(v.begin() + 1, 4, 9) = ";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    cout << "\n\n";

    v.erase(v.begin() + 3);
    cout << "vector erase(v.begin() + 3) = ";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    cout << "\n\n";

    v.erase(v.begin() + 2, v.begin() + 5);
    cout << "vector erase(v.begin() + 2, v.begin() + 5) = ";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
    cout << "\n\n";

    if (v.empty()) cout << "vector is empty!";
    else cout << "vector is not empty!";
}

 

 

결과)

 

6. 2차원 vector

 

2차원 배열처럼 vector를 2차원으로 생성할 수 있다. 

vector<vector<int>> v;
vector<vector<int>> v(N, vector<int>(K));
vector<vector<int>> v(N, vector<int>(K, val));

 

첫 번째 줄은 빈 vector를 생성하는 것이다.

두 번째 줄은 N행 K열 vector를 생성하는 것이다.

기존의 vector 생성자를 생각해보면, vector<int>(K)를 N개 가지는 vector라고 생각할 수 있다.

3번째 줄은 vector를 val 값으로 모두 초기화하는 것이다. 

 

 

7. vector의 응용

(이 부분은 PS를 하면서 학습하는 대로 계속해서 추가할 예정이다)

 

1) vector내의 중복된 원소 제거

 

중복된 원소를 제거하고 싶을 때, 배열을 이용한다면 상상만 해도 매우 번거로울 것이다. 

하지만 vector와 unique라는 함수를 이용한다면 매우 간단해진다. 

(물론, 집합을 나타내는 set을 이용하면 중복되는 원소는 자동으로 사라진다)

 

좌표 압축 기법에서 자주 이용되니 알아두면 유용할 것 같다.

 

우선, unique라는 함수를 이용하기 위해서는 <algorithm> 헤더를 추가해주어야 한다.

cpp reference에 나와 있는 unique 함수 코드를 살펴보자

 

template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last)
{
    if (first == last) return last;
    ForwardIterator result = first;
    while (++first != last) {
        if (!(*result == *first)) *(++result) = *first;
    }
    return ++result;
}

 

일단, first와 last는 구하고자 하는 범위의 양 끝이 된다. vector를 이용한다면 주로 first는 v.begin(), 

last는 v.end()가 될 것이다. 

핵심적인 부분은 result 변수(현재 위치)이다. 해당 변수를 통해서 중복되지 않은 원소들만 담기게 된다. 

 

5번째 줄) result에 first를 담아둔다. 

 

6번째 줄) first를 한칸 이동시킨 후, last와 같다면 원소가 1개 있는 경우이다.

따라서 이 땐 result를 한 칸 이동 시킨 후 반환해준다. 이는 결국 last와 같다. 

만약 ++first와 last가 다르다면 안쪽 루프를 돌게 된다. 

 

7번째 줄) 현재 result가 가리키는 값과 first가 가리키는 값이 같은지 체크하고, 같다면 아무 것도 수행하지 않고 루프를 다시 돌게 된다. 만약 다르다면 result 다음 위치에 first가 가리키는 원소를 담는다. 

 

9번째 줄) 지금까지 담긴 원소의 다음 위치를 반환한다. (중복을 제외한 벡터를 v2라고 하면 v2.end() = result라고 생각하면 된다.)

 

unique함수가 위와 같이 앞에서부터 순서대로 작동하기 때문에 vector내에서 중복을 제거하기 위해서는 기본적으로 정렬을 해두어야 한다. 

 

따라서 정렬을 한 후, unique함수를 수행하고 나면 중복되지 않은 원소들만 담은 vector의 끝 iterator가 반환된다. 

이를 이용하여 erase함수를 통해서 뒷부분은 제거해준다. 

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
    vector<int> v = { 1, 3, 2, 1, 8, 3, 5, 2, 6, 5, 8 };
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
}

 

 

또 다른 방법으로는 resize 함수를 이용하는 것이다. 

erase함수를 이용하는 것과 큰 차이는 없으므로 자유롭게 사용하면 될 것 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
    vector<int> v = { 1, 3, 2, 1, 8, 3, 5, 2, 6, 5, 8 };
    sort(v.begin(), v.end());
    vector<int>::iterator it;
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
}

 

 

2) pair 이용하여 순서쌍 원소 받기

 

pair를 이용하여 순서쌍을 원소로 하는 vector를 생성할 수 있다.

vector에 어떤 두 값을 push하기 위해서는 미리 두 값을 이용하여 하나의 순서쌍을 생성한 뒤에, push해주어야 한다.

아래 예시를 수행하면 "12 3" 이 출력된다.

vector<pair<int, int>> v;
v.push_back(make_pair(12, 3));
cout << v[0].first << ' ' << v[0].second;