[STL] vector

벡터(vector)는 가변 배열을 만들 때 사용하는 STL의 컨테이너 라이브러리이다. 자동으로 메모리가 할당되는 배열이라고 생각하면 된다.

 

[벡터의 특징]

1. 가변적인 크기

크기가 선언 시에 고정되는 배열과는 달리, vector는 크기가 동적으로 변한다. 따라서 저장할 데이터의 개수를 미리 알 수 없다면 vector을 사용하는 것이 좋다.

 

2. 중간에 데이터를 삽입/삭제할 수 없다.

벡터는 배열처럼 데이터를 순차적으로 저장하기 때문에 중간에 데이터를 삭제하거나 삽입하는 것이 번거롭다. 따라서 벡터는 가장 뒤에 있는 데이터를 삭제 및 삽입하는 경우에 사용하는 것이 좋다.

 

3. 저장할 데이터 개수가 많은 경우 검색이 용이하지 않다.

데이터를 순차적으로 저장하기 때문에 많은 데이터를 저장할 경우 검색 속도가 빠르지 않다. 검색을 자주한다면 벡터보다는 map, set, hash_map을 사용하는 것이 더 좋다.

 

4. 데이터 랜덤 접근 가능

배열과 같은 특성을 가지므로 랜덤 접근이 가능하다. 특정 데이터가 저장된 위치를 아는 경우, 랜덤 접근을 사용하는 것이 좋다.

 

 

[vector 사용 방법]

1. <vector> 헤더파일을 include한다.

2. vector 선언: vector<data type> [변수명]

#include<iostream>
using namespace std;
#include<vector>
vector<int> vec;

 

 

[vector의 멤버 함수]

vector<int> vec;

 

1. vec.push_back(1);

- 마지막에 원소 1을 추가

+) vec.emplace_back(1)로 대체해서 사용 가능 (emplace_back이 push_back보다 효율적인 경우가 많음)

 

2. vec.pop_back();

- 마지막 원소를 삭제

 

3. vec.size();

- 원소의 개수를 반환

 

자주 사용되는 vector 멤버 함수

vector 기본 멤버 함수

 

[vector 사용 예제]

 

#include<iostream>
using namespace std;
#include<vector>
 
int n = 1000;
int arr[1000]; //heap
vector<int> vec;
 
int main()
{
    //int arr2[1000]; //stack
    for (int i = 0; i <= n; ++i)
    {
        arr[i] = i; //overflow 발생
        vec.push_back(i * 2); // Time complexity = amortized O(1)
   }
 
    n = 0;
 
    for (int i = 0, end = vec.size(); i < end; ++i) cout << vec[i] << endl;
    return 0;
}
 

 

위 코드를 보면, 일반적인 int형 배열인 arr과 int형 vector 변수 vec을 선언해주었다. 

arr 배열을 전역변수로 설정해준 이유는 아래 접은 글에서 확인하자.

---

배열을 전역변수로 선언하면 heap 영역에 할당되고, main 함수 내에서 지역변수로 배열을 선언하면 stack 영역에 할당된다. 따라서 크기가 큰 배열을 선언할 것이라면 동적 할당을 하거나 전역변수로 선언해주는 것이 좋다. 또한 전역변수로 선언하면 굳이 초기화를 따로 해주지 않아도 처음부터 0으로 초기화되므로 전역변수로 선언해주는 것이 여러모로 편하다.

---

 

for (int i = 0; i <= n; ++i)
{
    arr[i] = i; //overflow 발생
    vec.push_back(i * 2); // Time complexity = amortized O(1)
}

for문의 arr 배열에 0부터 2000까지 삽입하면 overflow가 발생하여 프로그램이 실행되지 않는다.

반면 vector의 경우, vec.push_back(i*2) 함수를 사용하여 값을 삽입하는데, n의 크기가 1000보다 커져도 overflow가 발생하지 않고 정상적으로 프로그램이 실행된다. 이때의 시간 복잡도는 amortized O(1), 즉 평균 O(1)이다. 그 이유는, vector에서 배열이 꽉 찼을 경우, 원래 배열보다 2배 큰 배열을 생성하여, 원래 배열에 있던 데이터를 새로 생성한 배열에 복사하기 때문이다. 

 

예를 들어, N = 50000일 때, 

1에서 N - 1까지 배열에 삽입할 경우의 시간복잡도는 O(1)이다.

이 상태에서 N을 배열에 삽입하면, 이때까지도 시간복잡도는 O(1)이다.

하지만 이 다음 N + 1을 삽입할 경우, 크기가 2*N(100,000)인 배열을 새로 생성한 뒤 원래 배열에 있던 N개의 데이터를 새로운 배열에 복사하므로, 시간복잡도는 O(N)이 된다. 그리고 N은 2*50000, 즉 100000으로 갱신된다.

따라서 1부터 N + 1(=50001)까지 삽입했을 때의 평균적인 시간복잡도는 O(1)이 된다. 

이후 50002부터 100000까지 삽입했을 경우 시간복잡도는 O(1)이다.

 

첫 번째 for문이 끝나면 vec.size() 함수에 end를 걸어준 후 vec 벡터의 전체 원소를 출력한다.

for (int i = 0, end = vec.size(); i < end; ++i) cout << vec[i] << endl;

 

[참고 자료]

http://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS7393457320

https://blockdmask.tistory.com/70