stl vector / list / queue 속도 비교

링크 : https://blog.naver.com/omg92/60148996317

stl vector, list, queue 속도 비교

 

문득 vector와 queue의 속도 차이가 궁금해져서 관련 자료를 찾아봤다.

 

벡터는 런타임에 크기가 변경될 수 있는 배열과 같은 자료구조이다. 따라서 배열과 유사하게 사용할 수 있다.

 

인덱스 구조를 사용하기 때문에 임의 접근이 가능하고 탐색이 빠르다는 장점이 있다.

 

하지만 인덱스 구조를 유지하기 위해서 임의의 위치에 있는 원소의 삽입 및 삭제가 어렵다는 단점이 있다 !

 

100,000칸 짜리 배열에서 맨 앞 칸을 빼고 나머지 99,999칸을 앞으로 당기는 것과 비슷한 원리.

 

속도 차이는 위 링크에서 확인할 수 있다.

 

따라서 삽입/삭제가 자주 일어나는 환경에서는 벡터 대신에 리스트를 사용하는 것이 좋다.

 

기회가 된다면 3가지 자료구조를 전부 뜯어봐야겠다.