[자료구조] 1. STL Vector

1. Vector 간단 요약

  Vector는 C++ 표준 라이브러리(Standard Template Library, STL)에 속한 컨테이너 중 하나로 가변 배열이다. Vector는 동적 할당을 활용하므로 Heap에 생성되며 메모리를 효율적으로 관리할 수 있다. 하지만 원소의 추가/삭제에 있어서는 효율적이지 않다(추가/삭제 시 다른 원소를 옮겨야하므로 O(n)).

 

2. Vector의 구조

- begin() : 가장 앞 원소가 있는 위치

- end() : 가장 마지막 원소 바로 뒤

- front() : 가장 앞 원소

- end() : 가장 뒤 원소

- size() : 원소의 개수

- capacity() : 할당된 크기

 

3. Vector 함수 정리

  1) 반복자(iterator) 관련

- begin() : 가장 앞 원소를 가리키는 iterator

- end() : 가장 마지막 원소의 바로 뒤를 가리키는 iterator

- rbegin() : 가장 뒤 원소를 가리키는 iterator, rend()와 함께 사용하며 뒤에서 앞으로 가는 반복문에서 사용

- rend() : 가장 앞 원소의 이전 자리를 가리키는 iterator, end()처럼 앞 원소가 아닌 그보다 앞자리를 가리킴

- cbegin() : begin()과 동일하나 수정이 불가능한(constant) iterator

- cend() : end()의 constant 버전

- crbegin() : rbegin()의 constant 버전

- crend() : rend()의 constant 버전

 

  2) 크기 관련

- size() : 원소의 개수

- max_size() : Vector가 저장할 수 있는 원소의 최대 개수

- capacity() : Vector 생성 시 실제로 할당된 공간의 크기

- resize(n) : 원소의 개수를 n으로 조정, 그러나 원래 사이즈보다 줄인 경우, 줄이기 전 추가한 원소는 실제 메모리 주소에 그대로 남아있음

- empty() : Vector의 원소가 없다면 true, 아니라면 false를 반환

- shrink_to_fit() : capacity 자체를 size에 맞게 줄이고 해당 capacity를 넘어는 원소를 모두 제거

- reserve(n) : capacity를 미리 n으로 예약

 

* Vector의 원소삽입 시간복잡도는 보통 O(1)이나, 원소를 capacity 이상으로 삽입하는 경우 Vector는 원소를 삽입할 수 있는 메모리를 확보하기 위해 메모리 재할당 후 원소를 복사하는 과정이 일어나 O(N)의 시간복잡도를 가진다. 하지만 자주 일어나지 않으므로 Vector의 원소 삽입 시간 복잡도를 amortized O(1)이라고 한다. 이런 일을 방지하기 위해서 reserve를 사용하여 capacity를 미리 Vector 활용에 넉넉할 정도로 확보해놓는 것이 효율적이다.

 

아래는 resize와 shrink_to_fit 예시이다.

#include <iostream>
#include <vector>

using namespcae std;

int main()
{
	vector<int> v1;
	v1.reserve(10);
    
	for(int i = 1; i <= 10; i++)
		v1.push_back(i);
        
	// v1 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	//      <------------size------------->
	//      <----------capacity----------->
	int vecSize = v1.size(); // 10
	int vecCapacity = v1.capacity(); // 10
    
	v1.reisze(5);
	// v1 : [1, 2, 3, 4, 5] 6, 7, 8, 9, 10
	//      <----size----->
	//      <----------capacity----------->
	vecSize = v1.size(); // 5
	vecCapacity = v1.capacity(); // 10
    
	v1.shrink_to_fit();
	// v1 : [1, 2, 3, 4, 5]
	//      <----size----->
	//      <---capacity-->
	vecSize = v1.size(); // 5
	vecCapacity = v1.capacity(); // 5
    
	return 0;
}

 

  3) 원소 접근 관련

- at(i) : 인덱스와 동일(v1.at(i) == v1[i])

- front() : 가장 앞 원소

- back() : 가장 마지막 원소

- data() : Vector 생성 시 할당된 메모리의 실제 주소를 반환

 

아래는 data 예시이다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v1 = { 1, 2, 3, 4, 5 };

	int* p = v1.data(); // 1이 저장된 메모리 주소를 반환, p에 저장

	cout << "v1 : [ ";
	for (int i = 0; i < v1.size(); i++)
		cout << *p++ << " "; // 주소 p 속의 값(*p)을 출력하고 포인터 옮기기(++)
	cout << "]";

	return 0;
}

 

 

v1 : [ 1 2 3 4 5 ]

 

  4) Vector 수정 관련

- assign() : 주어진 매개변수에 따라 Vector 원소를 수정

- push_back(n) : back()의 다음 위치에 원소 n 추가

- pop_back() : back() 위치의 원소 제거

- insert(pos, val) : pos 위치에 원소 val 삽입

- erase() : 원소 제거, erase(pos) > pos위치 원소 제거, erase(startPos, endPos) > startPos부터 endPos 원소 모두 제거

- clear() : Vector의 원소 모두 제거

- swap(vec) : 함수를 호출한 벡터와 vec의 원소를 바꿈

- emplace(iter, val) : iter 위치의 바로 앞에 원소 val 추가

- emplace_front(val) : 가장 앞 원소로 val 추가

- emplace_back(val) : 가장 마지막 원소로 val 추가, push_back과 emplace_back의 차이점 존재!

 

* assign은 크게 네 가지 사용법이 존재한다.

1) assign(size, value) : value라는 원소를 size만큼 Vector에 추가

2) assign(arr, arr + size) : arr라는 배열을 시작점부터 size만큼 Vector에 추가

3) assign(iterFirst, iterLast) : iterFirst부터 iterLast까지 Vector에 추가

4) assign(List) : List로 Vector를 초기화

 

* push_back VS emplace_back

1) push_back

  임시 객체를 std::move를 통한 복사 후 삽입하고, 인자를 통해 암시적 형변환이 가능하다면(ex. int a = 1이라고 선언한 뒤 push_back(a) 하는 과정을  push_back(1)로 생략할 수 있다) 인자로 삽입 가능하다. 이 경우 또한 마찬가지로 push_back 내부에서 위와 같은 과정을 거쳐 임시 객체를 생성한 뒤 복사하여 삽입한다.

2) emplace_back

  인자를 넘겨줌으로써 함수 내부에서 객체를 생성한뒤 해당 객체를 바로 삽입한다. 따라서 std:move 호출이 비싸다면 emplace_back이 push_back보다 좋다. 하지만 의도치 않은 암시적 형변환이 일어날 수 있고, 컴파일 시 에러가 잡히지 않았지만 런타임에 에러가 발생할 수 있는 등의 단점이 있다. C++17부터 emplace_back()을 이용하는 경우, 삽입된 요소에 대한 참조를 반환한다.