STL - deque

 

deque

 

데크는 list와 vector의 중간 정도라고 생각하면 된다. 

vector처럼 배열 형식을 가지고 있지만 저장 공간이 꽉 찼을 때 독립적인 저장 공간을 하나 더 만든다.

vector의 경우 새로운 메모리 공간을 이전보다 크게 잡고 이전에 데이터를 복사해와서 연속적으로 데이터를

저장하지만 데크는 메모리 공간을 독립적으로 여러 개 만드는 형식이다. 그래서 vector의 특성과 list의 특성이

섞여 있다고 생각하면 된다.

 

ex) vector  

[ 1 1 1 ] // 최대 공간이 3개인 배열에서 데이터를 추가한다면 이 데이터는 복사 후 사라짐

[  1 1 1 2    ] // 이런 식으로 다른 메모리 공간으로 이동해 기존보다 1.5배 정도 크게 공간을 잡아줌

 

ex) deque

[ 1 1 1 ] // 마찬가지로 3개의 공간을 가지고 있는 상태에서 push_back 사용 시

[ 2       ] // 기존 메모리 공간을 유지하고 새로운 메모리 공간에 데이터를 잡아준다.

// push_front 함수를 사용해도 push_back과 동일하게 새로운 메모리 공간을 가져온다.

 

 

deque의 경우 중간 삽입/삭제는 느리게 동작하지만

처음, 끝 삽입/삭제는 빠르게 동작한다.

 

처음, 끝은 위에서 설명했던대로 새롭게 메모리 공간을 할당해서 데이터를 추가하거나 삭제하면 끝이지만

중간 삽입/삭제의 경우 vector처럼 다른 데이터들을 당겨오거나 밀어내거나 해야 하는 상황이 발생하기 때문에

비효율적이다.

 

그리고 마지막은 임의접근이다.

deque의 경우 임의 접근은 빠르다.

각 할당된 데이터 공간을 다르게 기억해두고 특정 데이터에 접근할 때 기억해두었던 데이터 공간을 호출해서

임의 접근을 하기 때문에 빠르게 동작할 수 있다.