[C++ STL] 덱 (Deque)
·
Programming/C++
개요벡터와 비슷하지만 양방향으로 원소를 삽입 / 제거할 수 있는 컨테이너시간 복잡도임의 위치 원소 접근: O(1)맨 앞/뒤에 원소 추가 및 제거: O(1)중간에 원소 삽입 및 제거: O(n)벡터보다 빠르게 동작함주요 기능 및 특징벡터보다 빠른 이유 (덱의 구조)덱은 벡터와 다르게 원소들이 실제로 메모리 상에서 연속적으로 존재하지 않는다. 이 때문에 원소들이 어디에 저장되어 있는 지에 대한 정보를 보관하기 위해 추가적인 메모리를 더 필요로 한다. (즉, 덱은 속도를 위해 메모리를 희생함)덱의 원소들은 일정 크기로 잘려서 각각의 블록에 저장된다. 그리고 그 블록들의 시작 주소를 가리키는 포인터들의 벡터가 존재한다. 크기를 늘리는 경우에서도 차이를 보이는데, 벡터의 경우 벡터가 가득 찬 상태에서 새로운 원소..