자료구조 #시퀀스컨테이너 #deque
디큐 아니고 덱임.
덱은 원소를 추가/제거하는 시간 복잡도가 O(1)이며 벡터와 마찬가지로 임의 접근이 가능한 컨테이너다. (다만 임의의 원소를 추가/제거하는 것은 O(n)임)
그럼에도 벡터보다 더 빠르게 구동한다. 그러나 원소들이 실제 메모리상에 연속적으로 존재하는 것은 아니기 때문에 원소들이 어디에 저장되어 있는지에 대한 추가적인 메모리가 필요함.
그래서 벡터랑 비교했을 때 8배 가까이 되는 메모리 용량을 요구하게 됨. 즉, 속도를 위해 메모리를 희생하는 컨테이너.
덱은 원소들이 일정하게 잘려서 메모리에 블록 형태(일정한 크기를 지니는 배열)로 흩어져 있다. 또한 각각의 블록들이 어디에 있는지 그 주소를 저장하는 벡터를 지니고 있다. (할당 시 앞쪽과 뒤에 빈 메모릴를 남겨두고 있음.)
⇒ 이러한 형태 덕에 임의의 원소를 임의의 자리에 추가할 때
- 아무 메모리 공간에 해당 원소를 저장하고
- 주소를 저장하는 벡터에서만 그 위치에 저장하면 된다. 즉, 그 이후의 모든 원소를 복사해야하는 벡터보다는 빠르게 저장할 수 밖에.