Deque1 [C++] deque, stack, queue, priority_queue deque deque는 vector와 list의 중간 정도의 컨테이너로, 여러 개의 메모리 블록을 할당하여 하나처럼 사용합니다. 1. vector처럼 capacity를 늘이는 과정에서 전체 copy가 일어나지 않습니다. (chunk 단위로 메모리 블록을 새로 할당 후 연결함) 2. 인덱스 접근은 가능하나, 연속적인 메모리가 아니기 때문에 포인터 연산은 불가합니다. 3. vector와 같이 처음, 끝이 아닌 중간에 삽입, 삭제하는 경우 요소를 밀어내면서 오버 헤드가 발생합니다 - O(N) stack과 queue LIFO의 stack과 FIFO의 queue는 위의 deque로 구현되어 있다. (STL 기준) 1. 두 컨테이너 모두 접근, 삽입, 삭제의 시간 복잡도가 O(1)로 아주 우수합니다. (front .. 2021. 12. 2. 이전 1 다음
