[C++] 표준 자료구조(컨테이너) vector, list, deque(queue)

평상시에 자주 사용하지만 필요한 로직에 따라서 구분하여 사용했다.

stack 구조가 필요한 경우 vector

queue 구조가 필요한 경우 queue 또는 deque

list 구조가 필요한 경우 list

삽입, 삭제, 읽기만 사용시에는 문제가 없을 수 있지만

큰 데이터의 정렬, 중간에 삽입, 복사 등의 작업을 수행하는 경우 어떤 컨테이너가 성능이 좋은지

궁금하여 관련한 내용을 찾아 보았다.

Vector

dynamic array과 같은 동작으로 하는 컨테이너로 동적 사이즈의 배열을 사용하고자 할때 사용

또한 삽입/삭제 메서드로 push_back(), pop_back()으로 stack 구조(FILO)를 연상시켜 stack 구조가 필요할때 주로 사용

특징으로는 새로운 요소들이 삽입될 때 사이즈를 확장하기 위해 전체 데이터가 이동하는 경우가 있음

장점
1. 접근성 - 다른 컨테이너(list, deque..)에 비해 매우 효과적으로 요소에 접근, 포인터와 [] 연산자로 접근
2. 끝에 있는 요소의 삽입/삭제가 효율적이며 성능이 좋음
3. 어떠한 순서로도 요소들 순회가가능 (random access iterator)

단점
1. 끝 위치 외 위치에 요소를 삽입/삭제 시 성능 안좋음
2. 사이즈 확장시 reallocation 비용이 큼(매번 reallocation되는 것은 아님) reserve 메서드로 사전에 충분한 공간을 확보할 수 있음

 

Deque (Double ended queue)

일반적으로 Queue 구조(FIFO)에서 양끝쪽에서 모두 삽입 삭제가 가능하도록 구현되어 있는 컨테이너

(std::queue는 구현부를 보면 std:deque를 이용하여 구현함 -> 기능을 제한함으로써 구현?)

장점
1.  []연산자를 활용하여 요소에 접근이 가능
2. 컨텐이너의 끝 뿐만 아니라 앞에서도 삽입/제거 성능이 좋음
3. 어떠한 순서로도 요소들 순회가 가능 (random access iterator)
2. 사이즈 확장시에 reallocation 비용이 거의 없음

단점
1. 양 끝이 아닌 곳에서 삽입/제거 수행시 성능이 낮음(list 보다)

 

List

doubly linked list로 구현

장점
1. 일반적으로 다른 컨테이너 보다 삽입/제거/이동 연산이 빠름

단점
1. []연산자로 접근할 수 없음
2. Fast random access 지원이 안됨

 

https://www.experts-exchange.com/articles/2812/Which-STL-Container.html

Which STL Container? | Experts Exchange

위 링크를 참조하여 그래서 언제! 어떤 컨테이너를 사용할 것인가를 정리

 

vector

1. 미리 데이터의 양을 가늠할 수 있을 때 → vector

2. 원소에 어떤 순서로도 접근할 수 있어야할 때 → vector

3. 데이터를 한번에 추가해야하고 존재하는 데이터에 추가되어야할 때 → vector

3. 원소를 끝이 아닌 곳에서 자주 삽입/삭제 해야할 때 → vector X

4. 얼마나 많은 데이터가 삽입될지 알지 못할 때 → vector X

deque

1. 양 끝으로 데이터를 추가/삭제해야할 때 → deque

2. 원소를 어떤 순서로도 임의 접근할 수 있어야할 때 → deque

3. 원소를 끝이 아닌 곳에서 자주 삽입/삭제 해야할 때 → deque X

4. C Style array와 호환이 필요할 때 → deque X, vector O

list

1. 저장해야하는 데이터의 양을 예상하지 못할 때 → list

2. 원소를 양끝이 아닌 곳에 자주 삽입/삭제 해야할 때 → list

3. 작은 데이터를 많이 저장해야할 때 → list X

4. 상수시간에 원소에 임의 접근이 필요할 때 → list X

 

정리하면

list를 써야할 때를 제외하면 용도에 맞게 vector와 deque를 사용

삽입/삭제 연산

- 양 끝단에서 삽입/삭제 → deque

- 한 끝단에서 삽입/삭제 → vector

- 중간에서 빈번하게 삽입/삭제 → list

- 삽입하는 데이터의 양을 예측할 수 없을 때 → deque, list

접근

- 인덱스를 통한 접근 또는 임의 위치 접근이 필요할 때 → vector, deque

 

https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

C++ benchmark – std::vector VS std::list VS std::deque

위 링크는 실제 Benchmarking 결과 

Fill - push_back()연산을 이용하여 데이터를 추가한 경우 속도

8 byts 원소를 반복적으로 삽입한 결과

4096 byts 원소를 반복적으로 삽입한 결과

 

16 byts 원소를 반복적으로 삽입한 결과

vector_ 는 vector_pre로 reserve 메서드로 미리 양을 예약해 놓은 vector를 의미
결과적으로 push_back() 메서드 속도는 vector_pre가 가장 빨랐으며 deque와 vector는 유사
list는 성능이 안좋았음

 

Linear search - find()연산을 이용하여 데이터를 찾는 경우

 

Linear search 결과 또한 list가 성능이 안좋았으며 deque와 vector는 성능이 비슷했음

 

Random Insert (+Linear Search)

 : 임의 위치에 Insert하기 위해서는 위치를 찾아가야 하므로 Linear Search 성능이 포함됨

 

일부 결과에서 list가 deque와 vector보다 성능이 낮게 나오지만 이는 Linear search로 인한 것임
원소의 용량이 큰 경우 list > deque > vector 순서로 성능이 좋음

 

Random remove (+Linear Search)

일부 작은 데이터 8bytes원소 제거시 list가 성능이 낮게 나오지만 대체로 list의 성능이 좋으며
list > deque > vector 순서로 성능이 좋음

 

Sort  정렬

작은 용량 8bytes 원소에서는 search 문제로 list가 성능이 안좋았음
큰 용량 1024bytes 원소에서는 list가 다른 두 컨테이너보다 성능이 좋았음

 

최종 정리