[C++] vector : push_back() 의 시간복잡도는?

벡터의 프로퍼티들은 ptr, size, capacity 등이 스택에 존재한다.

str 은 메모리 주소, size 는 실제 들어가 있는 크기, capacity 는 쉽게 말해 추가될 걸 대비해 넉넉하게 잡아놓은 크기이다.

 

push_back() 의 시간복잡도는 O(1) 이다. 뒤에 넣기만 하면 된다.

push_front() 의 시간복잡도는 O(n) 이다. 모든 데이터를 한칸씩 뒤로 옮긴 다음 첫 공간에 넣어야 하기 때문이다.

pop 도 마찬가지.

 

capacity 는 벡터가 현재 정의된 사이즈 이후에 얼마나 더 정의될 수 있는지에 대한 정보이다.

push back 을 하고 싶은데 만약 바로 뒤에 다른 메모리가 잡혀 있으면 (fragmentation!!)

벡터 전체를 다른 공간에 옮겨야 하기 때문에 O(n) 이 된다. (전부 복사한 다음 기존 메모리를 해제)

 

벡터를 사용하는 이유는 퍼포먼스인데, 이것이 문제가 되면 굳이 사용하는 이유가 없는 것이다.

test_vec.reserve(n);

선언 할 때 처음에 사이즈가 0이더라도 capacity 를 정해준다. 대략적인 capacity 를 reserve 해주는 습관을 들이자

 

push_back() 은 대부분 O(1) 인데, 이렇게 프래그맨테이션이 걸릴 경우엔 O(n) 이 될 수 있다!

 

+ 동적 배열은 웬만해서 vector 를 쓰자!

new 같은 경우는 stl 보다 기능적으로도 떨어지고, 메모리 해제를 직접 해줘야 하기 때문에 메모리 누수의 가능성을 보장받지 않는다.

벡터는 스택에서 해제될 때, 프로퍼티에 존재하는 포인터를 따라가 같이 해제를 시켜준다!