오늘은 c++ STL 컨테이너에서 시퀸스 컨테이너인 vector에 대해 정리하겠다.

vector란?

vector 컨테이너는 자동으로 메모리가 할당하는 배열이다.

객체 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경한다. 이 컨테이너의 헤더 파일은 이다.

벡터 컨테이너는 아래와 같이 선언한다.

#include<vector>
vector<템플릿 인수> 객체 이름(셍성자인수);

템플릿 인수는 벡터 컨테이너에 저장될 요소의 타입을 전달하고, 생성자 인수로는 벡터 컨테이너의 초기 크기를 전달하며, 생략하면 요소를 가지지 않는 빈 벡터를 생성한다.

중간에 값을 삽입하거나 삭제할 수 있지만, 배열 기반이기 때문에 삽입 삭제가 빈번하게 일어난다면 비효율적이다.

예제

vector<int> result(n); //초기 크기가 정해진 벡터
vector <bool> isVisted; //초기 크기가 정해지지 않은 벡터

vector의 초기화

출처 : https://hwan-shell.tistory.com/119

예제)

vector<int> v;        //int형 백터 생성

vector<int>v(4);    //int형 백터 생성 후 크기를 4로 할당(모든 백터요소 0으로 초기화)

vector<int>v = { 1, 2, 3};        //int형 백터 생성 후 1, 2, 3 으로 초기화

vector<int>v[] = {{ 1, 2}, {3, 4}};        //int형 백터 배열 생성(행은 가변이지만 열은 고정)

vector<vector<int>> v;        //2차원 백터 생성(행과 열 모두 가변)

vector<int> v = { 1, 2, 3, 4, 5};        //백터 범위를 5로 지정하고 정수 10으로 초기화
v.assign(5, 10);    //output : 10 10 10 10 10

vector<vector<int>> graph(n, vector<int>(n)); 	//v라는 벡터는 n개의 원소를 가지고 있는데,
//각 원소를 int 자료형을 담은 vector로 초기화하라는 뜻이다. 
//내부의 벡터는 n개의 원소를 담고 있으며 0이라는 값으로 초기화된다.

또한 구조체로도 선언이 가능하다.

struct meeting
{
  int first;
  int second;
};


int main(){
  int n;
  cin >> n;

  vector<meeting> arr(n); //이렇게 하면 vector에 구조체 형식으로 변수가 들어간다.
  for(int i = 0; i<n; i++){
      cin >> arr[i].first >> arr[i].second;
  }

}

이런식으로 구조체 형식으로 vector를 선언할 수 있다.

vector의 Iterators

출처 : https://hwan-shell.tistory.com/119

이외에도 여러 함수가 있다.

vector의 멤버 함수

• v.at(idx)
  : idx번째 원소를 참조한다. v[idx]보다 속도는 느리지만, 범위를 점검하므로 안전하다.
• v.front(), back()
  : 첫번째 원소/ 마지막 원소를 참조한다.
• v.clear()
  : 모든 원소를 제거한다. 다만 원소만 제거하고 메모리는 남아있다. size만 줄어 들고, capacity는 그대로 남아있다는 것이 특징이다.
• v.push_back(m)
  : 마지막 원소 뒤에 원소 m을 삽입한다.
• v.pop_back()
  : 마지막 원소를 제거한다.
• v.begin()
  : 첫번째 원소를 가리킨다. (iterator와 사용)
• v.end()
  : 마지막의 "다음"을 가리킨다. (iterator와 사용)
• v.rbegin()
  : reverse begin을 가리킨다. 거꾸로 해서 첫번째 원소를 가리킨다. (iterator와 사용)
• v.rend()
  : reverse end 을 가리킨다. 거꾸로 해서 마지막의 다음을 가리킨다.
• v.resize(n)
  : 크기가 n으로 변경한다. 더 커졌을 경우 default값인 0으로 초기화한다.
• v.resize(n,3)
  : 크기가 n으로 변경한다. 더 커졌을 경우 인자의 값을 3으로 초기화 한다.
• v.size()
  : 원소의 갯수를 리턴한다.
• v.capacity()
  : 할당한 공간의 크기를 리턴한다. 공간 할당의 기준은 점점 커지면서 capacity를 할당하게 된다.
• v2.swap(v1)
  : v1과 v2의 원소와 capacity 바꿔준다. (모든 걸 스왑한다.)
  v1의 capacity를 없앨때 (할당한 메모리를 프로그램이 끝나기 전에 없애고 싶을때) 사용하기도 한다.
  v2를 capacity가 0인 임시 객체로 만들어서 스왑을 해준다.
  vector().swap(v1);
• v.insert(2,3,4)
  : 2번째 위치에 3개의 4값을 삽입한다. (뒤의 값은 뒤로 밀린다.)
• v.insert(2,3)
  :2번째 위치에 3의 값을 삽입한다. 삽입한 곳의 iterator를 반환한다.
• v.erase(iter)
  : iter가 가리키는 원소를 제거한다. size만 줄어들고 capacity(할당된 메모리)는 그대로 남는다. erase는 파라미터 하나를 받을 때와 두 개를 받을 때 다르다.
• v.empty()
  : vector가 비었으면 리턴 true. 비어있다의 기준은 size가 0이라는 것이지, capacity와는 상관이 없다.

size와 capacity와의 관계

size()와 capacity()는 차이가 있다. size()는 원소의 갯수를 리턴하지만, capacity()는 할당된 공간의 크기를 리턴한다. 공간 할당의 기준은 점점 커지면서 capacity를 할당하게 된다.

dev c++ 기준으로 string 클래스로 vector를 만들 때,

원소 갯수 1 => capacity 1
원소 갯수 2 => capacity 2
원소 갯수 3 => capacity 4
원소 갯수 4 => capacity 4
원소 갯수 5 => capacity 8
원소 갯수 6 => capacity 8
원소 갯수 7 => capacity 8
원소 갯수 8 => capacity 8
원소 갯수 9 => capacity 16

기존 메모리의 *2로 증가한다.
이런식으로 메모리 할당을 하는 이유는 push_back이 일어날 때마다 동적할당을 하면, 비효율적이므로 미리 정해둔 만큼 동적할당를 한번에 하는 것이다.

원소 개수가 증가하면서, 메모리를 증가해서 따로 할당하게 되면 기존 위치에 메모리를 할당하는 것이 아닌, 새롭게 메모리를 할당해서 원소들을 전부 복사하는 형태이다.

기존에는 복사에 대한 비용이 많이 들었다. 하지만 std::move라는 것이 도입되면서 복사하지 않고 이동하게 되어 메모리 증가에 따른 비용이 많이 들지 않게 되었다.

다시 정리하자면 size는 할당된 메모리 안에 요소가 들어있는 것의 갯수이고, capacity는 할당된 메모리의 갯수이다.

Vector의 삭제 - remove() 함수 VS erase() 함수

헤더

remove() 함수는 algorithm 헤더를 선언해줘야한다. 그에 반해 erase 함수는 vector의 함수들 중 하나이기 때문에, vector 헤더만 선언해줘도 괜찮다.

기본 형태

• remove 함수의 기본 형태

remove(first, last, 삭제하려는 값); // 범위는 [first,last)

remove 함수는 특정 범위를 탐색하여 그 범위에 있는 특정값을 삭제할 수 있다.

• erase 함수의 기본 형태

// vector의 이름이 v라고 가정

// 1
v.erase(first, last); // 범위는 [first,last)

// 2
v.erase(삭제하려는 값의 위치);

erase 함수는 특정 범위에 속하는 모든 값들을 삭제하거나 (해당 범위에서의 특정 값은 삭제 불가능), 특정 값의 위치를 보내면 해당 값을 삭제할 수 있다.

두 함수의 공통점
둘다 first와 lasr에 포함되는 범위가 [first, last)이다. last는 범위에 포함되지 않는다.

그리고 두 함수 모두 맨끝 범위에 위치한 값은 삭제할 수 없다. 1 2 3이 있을 경우 범위가 1~3일때 3은 삭제할 수 없다는 의미이다.

두 함수의 차이점

• remove 함수는 아예 특정 값을 인자로 보내어 해당 값을 삭제할 수 있고, 이 때 특정 범위를 탐색하여 삭제하려는 값을 찾아내어 삭제할 수 있다.
• 반면 erase 함수의 경우 특정 값을 삭제하려면 해당 값의 위치를 인자로 보내야 삭제할 수 있고, 범위 내에서 특정 값을 찾아내는 것은 불가능하다. 범위가 주어지면 그 범위의 모든 값들을 삭제하는 것만 가능하다.

두 함수의 반환값

• remove 함수의 반환값
  remove 함수는 주어진 범위( [first, last) - last는 미포함 ) 중에서 삭제되지 않은 가장 마지막 값의 새로운 위치에서 바로 뒤에 있는 위치의 iterator를 반환해준다.

  예를 들어 1 2 3 2 2 4 라는 vector의 전체 범위 중에서 2를 remove하면 1 3 4 ... 가 되는데, 1 3 4 ... 에서 즉, 범위 내에서 삭제되지 않은 마지막 값인 4의 바로 뒤 위치 iterator를 반환해준다는 것이다.

• erase 함수의 반환값
  erase 함수는 범위와 상관없이 마지막으로 지워진 값의 위치에서 바로 뒤에 있던 값의 새로운 위치의 iterator를 반환해준다.

  예를 들어 1 2 3 4 5 6 7 이라는 vector의 범위를 2 3 4라고 하고 erase하면 2 3 4가 모두 지워지고 1 5 6 7 ... 이 된다(실제로는 아니다. 이에 대한 내용은 뒤에 나오는 각 함수의 특징에 대한 설명에 나와있다). 이 때 기존의 vector에서 가장 마지막에 지워진 4 바로 뒤에 있던 값이 5이므로, 1 5 6 7 ... 에 있는 새로운 5의 위치 iterator를 반환해준다는 것이다.