Chapter06-02 시퀀스 컨테이너 : deque

• deque의 개념
  - double - ended queue, 즉 양단 큐의 약어로 양쪽 끝에서 빠르게 삽입과 삭제가 가능한 자료구조 입니다. 
  
  - 벡터와 마찬가지로 시퀀스 컨테이너이며 배열 기반 컨테이너입니다.
  
  - 벡터 컨테이너와 기능과 동작이 가장 비슷한 컨테이너로 벡터의 단점을 보완하는 몇 가지 특징이 있습니다.
  
  - 벡터(vector)보다 유연하고 리스트(list)보다 빠르게 작동하므로 덱은 두 자료구조의 중간 지점에 있다고 볼 수 있습니다.
  
  - 그 외 덱에 관한 자세한 설명은 아래 링크를 참고하는 것이 좋습니다.

https://cplusplus.com/reference/deque/deque/

https://cplusplus.com/reference/deque/deque/

• vector와 deque의 차이
  - 벡터와 덱의 가장 큰 차이는 메모리 블록 할당 정책 입니다.
  
  - 벡터의 장점이자 단점인 하나의 메모리 블록 할당 정책은 배열처럼 정수 연산만으로 원소에 접근해 빠르게 읽고쓰기할 수 있습니다. 그러나 메모리 블록이 하나 밖에 없기 때문에 새로운 원소가 추가되면 한 개의 통으로 된 메모리를 전체 재할당 하고 이전 원소 값을 새로 할당된 메모리에 복사 해야하기 때문에 성능이 저하될 수 있습니다.
  
  - 덱은 이러한 단점을 해결하기 위해 내부적으로는 여러 개의 메모리 블록을 할당하고 사용자에게는 마치 하나의 블록처럼 보이는 정책을 사용합니다. 그렇기 때문에 원소의 추가 시 메모리가 부족할 때마다 일정 크기의 새로운 메모리 블록을 할당하여 이전 메모리를 제거하거나 이전 원소를 복사하는 등의 연산을 수행하지 않아 성능 저하 문제가 발생하지 않습니다.
  
  
  
  
  
• deque에서의 메모리 할당
  - 앞서 덱의 메모리 할당 방식은 하나가 아닌 여러 개의 메모리를 할당하는 것이라고 배웠습니다. 그렇다면 새로운 원소를 삽입하면 덱의 내부에서는 어떤 일이 벌어질까요?
  
  - 벡터의 경우 할당된 메모리가 부족하면 전체 메모리를 재할당 및 복사한다고 했습니다. 그러나 덱의 경우 아예 새로운 메모리 블록을 부족한 메모리 만큼 재할당하고 그 새롭게 할당된 메모리에 원소를 삽입해줍니다.
  
  - 구체적으로, 덱은 map이라는 포인터 배열을 기반으로 여러 개의 고정 크기 블록(chunk)을 관리합니다.
  - 각 블록은 n개의 원소를 담을 수 있으며, 이 블록들을 배열로 연결해 마치 연속된 공간처럼 보이게 합니다.
  - 원소 접근 시에는 index = overall_position / block_size, offset = overall_position % block_size 같은 수식을 사용해 빠르게 접근합니다.
  
  - 예를 들어, 벡터에서 insert 함수로 특정 인덱스에 데이터를 삽입하는 방식과 비교해봅시다. 벡터에서는 insert시 아예 메모리를 다시 재할당해야 했습니다. 그러나 덱은 새로운 원소를 순차열 중간에 insert하거나 erase하더라도 원소의 개수가 작은 쪽(앞쪽 또는 뒤로)을 자동으로 비교해서 해당 방향으로 데이터를 밀어내고 새 원소를 채워줍니다. 이렇게 자동으로 결정된 방향을 기준으로 데이터를 정리해주기 때문에 insert시 덱은 벡터보다 더욱 효율적으로 작동합니다.
  
  - 또한, 하나가 아닌 여러 메모리 블록을 사용하기 때문에 특정 인덱스를 이용해 insert로 값을 추가하거나 데이터의 끝에만 원소를 추가하는 push_back만을 지원하던 벡터와 다르게 덱에서는 원소를 앞쪽과 뒤쪽에 모두 추가할 수 있습니다.
  
  
  
  
  
• deque의 단점
  - 여기까지 보면 덱은 완벽한 자료구조처럼 보이지만, 단점 역시 존재합니다.
  
  
  • 중간 삽입이나 삭제는 여전히 많은 원소 이동이 필요하므로 리스트에 비해 비효율적입니다.
    
    덱은 벡터와 같은 시퀀스 기반 컨테이너이고 '데이터를 밀어내고 새 원소를 채워준다'라는 점에서 새로운 원소를 자주 추가해야 하는 상황에서 사용하기에는 상당히 비효율적입니다. 그럼에도 데이터를 뒤쪽 또는 앞쪽으로 양방향으로 밀어낼 수 있다는 점에서 아예 처음부터 다시 메모리를 재할당해야하는 벡터보다는 효율적이라고 할 수 있습니다.
    
    
  • 캐시 친화성(cache locality)이 vector보다 떨어집니다.
    
    여러 블록이 흩어져 있기 때문에 메모리 접근 시 캐시 미스가 발생할 가능성이 높습니다.
    
    
    
  • 일부 구현체(STL 벤더)에 따라 deque의 성능이나 block size가 다를 수 있습니다.
    
    덱의 내부 블록 구조는 STL 표준에서 명확히 정의되어 있지 않기 때문에, 사용하는 컴파일러나 라이브러리에 따라 블록 크기나 성능이 다를 수 있습니다. 예를 들어 libstdc++, libc++, MSVC STL 등 구현체에 따라 메모리 블록 할당 방식이나 초기 블록 수가 달라집니다. 따라서 고성능이 중요한 상황에서는 구현체의 특성까지 고려해야 할 수 있습니다.
  
  
  
• deque를 쓰면 효율적인 상황 예시
  
  1. 앞뒤 양쪽 끝에서 자주 삽입하거나 삭제할 때
  • 벡터는 뒤쪽에서만 빠른 삽입/삭제를 보장하고, 앞쪽 삽입은 전체 요소를 이동시켜야 해서 비효율적입니다.
  • 반면 덱은 앞쪽과 뒤쪽 모두 O(1)에 가까운 시간 복잡도로 처리합니다.
  * 예시
  • 0-1 BFS
    - 가중치가 0 또는 1일 때 push_front()와 push_back()을 통해 Dijkstra보다 더 빠른 구현이 가능
    
    
  • 최솟값/최댓값 슬라이딩 윈도우
    - monotonic deque (단조 큐)로 O(N) 시간 복잡도로 최댓값 유지 가능
    
    
  • LRU 캐시 구현
    - deque + unordered_map 조합으로 순서를 유지하며 캐시 갱신 가능
    
    
  2. 랜덤 접근이 필요한데 리스트보다 빠르고 싶을 때
  • 덱은 중간 접근도 가능합니다. 리스트는 중간 접근에 O(N) 시간이 들지만, 덱은 O(1) 시간에 인덱싱이 가능합니다.
  • 내부적으로는 여러 개의 고정 크기 배열을 관리하는 포인터 배열 구조이므로, 벡터만큼은 아니지만 꽤 빠른 랜덤 접근이 가능합니다.
  
  3. 컨테이너의 크기가 자주 변할 때
  • 벡터는 한 번 용량이 꽉 차면 전체를 새로 할당하고 복사하는 비용이 듭니다.
  • 반면 덱은 필요한 만큼의 블록만 추가해서 전체 복사를 줄일 수 있습니다.
  
  
  
  
• 벡터, 덱, 리스트의 연산 종류별 성능 비교
  
  

  연산 종류	vector	deque	list
  push_back	O(1)	O(1)	O(1)
  push_front	O(N)	O(1)	O(1)
  insert middle	O(N)	O(N)	O(1)
  random access	O(1)	O(1)	O(N)
  캐시 효율	높음	중간	낮음