서론

C++을 사용할 때 거의 필수적으로 사용하는 STL(standard template library)에서 제공해주는 vector class의 method의 시간복잡도를 기억하기 쉽게 이해를 토대로 정리해보자.

필자는 알고리즘을 풀 때 주로 사용한다.


Vector

기본적으로 vector는 자동으로 동적할당 해주는 배열이라고 생각하면 된다.

그러므로 stack이 아닌 heap 메모리를 사용하게 되며, 여러 가지 기능을 제공하는 만큼 단순 배열보다는 속도가 좀 떨어진다.

내부적으로도 ‘배열’의 구조로 데이터를 저장한다. (연속적인 메모리)

또한 vector클래스가 스택에서 해제될 때 자동으로 해당되어 있는 메모리를 전부 해제해줘서 메모리 누수를 고민할 필요가 없다.


시간 복잡도

기본적으로 흔히 사용하는 method에 대해서 알아보자

random access : O(1)

v[4], v.at(4) : 과 같이 임의의 원소에 접근하는 것은 배열과 마찬가지로 시작 주소에서 offset 만큼 연산하여 접근하기에 O(1)이라고 볼 수 있다.

임의의 위치에 원소 추가 및 제거 : O(n)

v.inset(v.begin() + 1, 100);

v.erase(v.begin() + 1);

배열과 마찬가지로 특정 인덱스에 원소를 추가하거나 제거 시 연속적인 메모리를 가져야하기 때문에 그 뒤에 데이터 전부를 한칸씩 옮겨주는 작업이 필요하다. 그래서 O(n) 만큼의 시간복잡도를 가진다.