[STL] vector

vector

배열 기반의 컨테이너

배열 기반이기 떄문에 인덱스 접근이 가능하다. (탐색의 용이)

원소 삽입/삭제 시에는 앞에서부터 할 수 없으며, 맨 뒤에서만 가능하다.

-> 중간 삽입 및 삭제 시에는 삽입 위치의 확보, 삭제 위치의 활용을 위해

-> 해당 원소 이후 포인터의 이동이 발생한다. (선형 시간 O(n))

-> 단 맨 끝에서 삽입 및 삭제는 포인터 이동이 필요 없다.(상수 시간 O(1))

-> 배열 기반이기 떄문에 메모리 개수를 넘어서는 삽입의 시도가 있을 경우

-> 배열의 재할당 및 기존 원소들의 복사가 발생한다.

-> vector의 원소를 삭제하여 원소가 존재하던 메모리 공간은 남아 있는다.

-> 결론적으로 vector는 삽입 삭제가 불리하다고 할 수 있다.

 

 

 

 

vector의 사용법

-> vector를 사용하기 위해서는 #include <vector>를 추가해야한다.

 

 

vector의 선언

-> 저장하고 관리할 데이터의 자료형을 <>안에 명시한다.

 

원소 삽입

-> push

-> vector는 뒤에서만 삽입이 가능하다.

 

 

 

원소 삭제

-> pop

-> vector는 뒤에서만 삭제가 가능하다.

 

 

 

size()

-> 원소의 개수를 반환하는 함수

 

 

clear()

-> 모든 원소를 삭제하는 함수

-> 단, vector에 저장하는 원소가 동적할당된 주소일 경우

-> clear를 호출하기 전에 사용자가 직접 동적할당을 해제해주고 호출해야 한다.

 

 

 

empty()

-> 원소가 비어있는지 아닌지 검사하는 함수

-> 비어 있을 경우 true, 비어있지 않을 경우 false

 

capacity()

-> 메모리 할당 개수를 반환하는 함수

-> 원소를 5개 삽입하였으나 capacity는 6이 나온다

-> 그 이유는 vector의 재할당 떄문이다

 

vector의 메모리 정책

메모리 크기를 넘어서는 삽입의 시도가 있을경우 재할당 및 복사가 발생한다.

이 떄, 재할당은 (기존 메모리 개수 >> 1) 만큼 추가로 증가하게 된다

단, 나눈 몫이 0일 경우 최소 1만큼 추가로 재할당이 발생한다.