정의
- C++ STL에는 크게 두 개의 container가 있다.
배열처럼 원소들을 순서대로 보관하는 'Sequence Container', key값을 이용하여 대응하는 방식인 'Associative Container'이다. - vector는 Sequence Container로 어떤 자료형도 넣을 수 있고 자동으로 메모리가 할당되는 동적 배열이다.
- Vector는 맨 뒤에서 원소의 삽입, 삭제가 가능하며 중간에서도 가능하다.
시간 복잡도
- 임의 접근에 O(1)의 복잡도를 갖는다.
- 벡터 끝에서의 원소 삽입, 삭제에 O(1)의 복잡도를 갖는다.
- 중간에서의 원소 접근, 삽입, 삭제는 마지막 원소로부터의 거리에 비례하여 O(n)의 복잡도를 갖는다.
특징
- vector는 자동으로 메모리를 할당시켜주므로 처음에 원소의 개수를 지정할 필요가 없어 원소를 삽입, 삭제 시 메모리를 효율적으로 관리할 수 있다.
- 어떤 요소에도 임의 접근이 가능!
하다. - 원소의 삽입, 삭제가 빈번하면 시간적인 측면에서 비효율적이다.
- push_back() 함수는 값을 넣는 과정에서 복사 생성자를 호출한다. 또한, 삽입 시 모든 값들을 새로운 메모리에 복사한 후 해당 자리에 값을 넣는다.
따라서 복사생성자로 인한 오버헤드가 커지게 되며 성능 저하를 야기한다.
iterator
- begin(): 벡터 시작 주소 값 반환
- end(): 벡터 마지막 + 1 주소 값 반환
- rbegin(): 벡터의 끝 지점을 시작점으로 반환
- rend(): 벡터의 (시작점 + 1) 지점을 끝 부분으로 반환
size()와 capacity()
- size(): 원소의 개수 반환
- capacity(): 할당된 메모리 크기 반환
- 벡터 크기가 capacity 크기를 초과하면 reallocate(재할당) 발생.
재할당이 발생하면 모든 값들을 새로운 메모리 공간에 복사한 후 기존 벡터 파괴.
새로운 메모리 공간은 기존 capacity 크기의 1/2만큼 늘린 크기이다. 즉, capacity 크기는 1.5배가 된다.
복사 과정에서 복사생성자가 발생하여 프로그램의 성능이 저하된다.
-> 재할당이 자주 일어나는 것을 방지하기 위해 reserve() 함수 사용
** 재할당 시 이전에 소유하고 있던 iterator는 무효화된다.
reserve()
- reserve(): capacity 크기 설정,
벡터를 충분히 만들어 불필요한 생성 과정 제거 - 원소의 개수를 미리 알고 있다면 reserve()를 통해 capacity 메모리를 미리 할당하면 효율적.
- reserve()의 크기가 과도하게 크면 벡터가 불필요하게 늘어나 메모리 낭비가 심할 수 있다.
-> 메모리 낭비 해결을 위해 shrink to fit() 함수 사용
shrink to fit()
- shrink to fit(): capacity()의 크기를 조정
- shrink to fit()을 호출하여 추가로 할당된 메모리를 반환, 실제 벡터의 크기만큼 메모리를 할당하도록 한다.
ex) 할당된 메모리: 100, 실제 사용량: 20일 때
shrink to fit()을 호출하면 할당된 메모리가 20으로 변경되고 80이 시스템에 반환된다. - reserve() 사용으로 발생한 빈 공간을 제거
참고 사이트
https://rebro.kr/37
https://hwan-shell.tistory.com/119
https://coding-factory.tistory.com/596
https://jungwoong.tistory.com/28
