C++을 사용할 때 거의 필수적으로 사용하는 STL(standard template library)에서 제공해주는 vector class의 method의 시간복잡도를 기억하기 쉽게 이해를 토대로 정리해보자.
필자는 알고리즘을 풀 때 주로 사용한다.
기본적으로 vector는 자동으로 동적할당 해주는 배열이라고 생각하면 된다.
그러므로 stack이 아닌 heap 메모리를 사용하게 되며, 여러 가지 기능을 제공하는 만큼 단순 배열보다는 속도가 좀 떨어진다.
내부적으로도 ‘배열’의 구조로 데이터를 저장한다. (연속적인 메모리)
또한 vector클래스가 스택에서 해제될 때 자동으로 해당되어 있는 메모리를 전부 해제해줘서 메모리 누수를 고민할 필요가 없다.
기본적으로 흔히 사용하는 method에 대해서 알아보자
random access : O(1)
임의의 위치에 원소 추가 및 제거 : O(n)