vector |
장점 |
가변 길이 Sequence에 대한 임의 접근이 가능하며, 시퀸스 끝부분에서 신속한 삽입, 삭제가 가능하다. 검색 속도가 가장 빠르다. |
단점 |
시퀀스의 맨 끝이 아닌 임의의 다른 위치에서의 삽입삭제는 느리다.(선형시간) | |
deque |
장점 |
시퀀스 양쪽 끝의 삽입, 삭제가 벡터보다 빠르다. |
단점 |
시퀀스의 접근시간은 vector보다 느리고, 중간에서의 삽입삭제는 list보다 느리다. | |
list |
장점 |
시퀀스 중간에서의 삽입, 삭제가 가장 빠르다. |
단점 |
시퀀스 접근 시간이 가장 느리고, 임의 접근이 불가능하다. |
검색 속도 : vector > deque > list
삽입 삭제 : list > deque > vector
- 순서 없이 요소를 저장할 때 사용한다. vector, list, deque의 3가지 종류가 있다.
시퀀스 컨테이너에 속하는 3가지 컨테이너들간에 기능에 차이는 거의 없다. 주로 서능에 차이가 난다.
검색은 vector가 가장 빠르지만 삽입, 삭제는 list가 가장 빠르다.
세가지 컨테이너 중에서 모든 연산에 대해 수행 성능이 최고인 컨테이너는 없다. 그래서 자신이 만드는 프로그램
에 가장 적합한 컨테이너를 선택하는 것이 중요하다.
또한, 이들 컨테이너들은 거의 동일한 인터페이스로 만들어져 있기 때문에 프로그램을 수정하지 않고도 컨테이너를 변경해 가면서 가장 좋은 성능을 내는 컨테이너를 찾아 낼 수 있다.
인터페이스에 차이가 있다면, 그것은 해당하는 컨테이너를 사용하는 것을 다시 한번 고려해 보라고 의도적으로 그렇게 설계한 것이다.( 예로, vector에는 push_front, pop_front가 없다. )
실제로는 캐시 때문에 vector가 제일 빠르다 . 왜냐하면 list는 연속된 메모리가 아니기 때문에 캐시에 올라올때 모든 메모리가 올라오지 못한다. 하지만 vector는 연속된 메모리로써 메모리에 위치하게 된다. 그러므로 왠만하면 vector를 사용하여 메모리를 잡자.
Tag | C++