1.4 std::vector

std::array의 단점

1. array의 size 변경 불가능 -> 원소의 삽입, 삭제 불가능

2. 항상 stack 메모리 사용

 

std::vector

가변 크기 배열

 

선언 및 초기화

//크기가 0인 벡터 선언 
std::vector<int> v0;
//크기가 3인 벡터의 원소 값 지정
std::vector<int> v1 = {1,2,3};
//모든 원소가 0으로 초기화 된, 크기가 3인 벡터 선언
std::vector<int> v2(3);
//크기가 3이고, 모든 원소가 1로 초기화된 벡터 선언
std::vector<int> v3(3, 1);

 

원소 추가

push_back(): 벡터의 맨 마지막에 새로운 원소 추가

//의사코드(pseudocode)
push_back(val):
	if size < capacity
    	마지막 원소 다음에 val 저장
        size++;
        return;
	if vector is already full
    	2*size 크기의 메모리 새로 할당
        새로 할당한 메모리로 기존 원소 전부를 복사/이동
        데이터 포인터를 새로 할당한 메모리 주소로 지정
        마지막 원소 다음에 val 저장
        size++;

첫번째 경우 시간복잡도 O(1)

두번째 경우 시간복잡도 O(n). 그러나 빈도수 낮음

push_back()의 평균 시간 복잡도 O(1)

 

 

insert(삽입할 위치를 나타내는 반복자, val): 시간 복잡도 O(n)

 

push_back()과 insert()의 단점:

추가할 원소를 먼저 임시로 생성한 후,  벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다.

-> 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화 가능

-> emplace_back() 혹은 emplace() 사용! : 새 원소 위치에서 곧바로 객체가 생성되기 때문에 인자에 생성된 객체를 전달하는 것이 아니라 생성자에 필요한 매개변수를 전달해야 한다.

 

 

원소 제거

pop_back() : 벡터에서 맨 마지막 원소를 제거. 벡터 크기 1 감소

시간 복잡도 O(1)

erase(): 

1. 인자가 iterator 하나일때, 해당 위치 원소 제거

2. 인자가 iterator 두개 일때, 시작부터 끝 바로 앞 원소까지 제거

O(n)

 

기타 함수

clear(): 모든 원소를 제거. 빈 벡터로 만들어준다.

reserve(capacity): 벡터에서 사용할 용량 지정. 매개변수가 현재 용량보다 클 때만 메모리를 매개변수 크기만큼 재할당한다.

shrink_to_fit(): 여분의 메모리 공간 해제. 벡터의 용량 = 벡터 크기