STL 컨테이너 - deque

deque

양쪽 끝에서 빠르게 삽입 및 삭제가 가능한 동적 배열 기반 컨테이너입니다. deque는 vector와 비슷하지만, 양쪽에서 삽입과 삭제가 효율적으로 이루어진다는 점에서 차이가 있습니다.

 

1. std::deque의 특징

• 양방향 삽입/삭제:
  • 양쪽 끝에서의 삽입/삭제가 O(1) 시간 복잡도를 가집니다.
• 동적 배열:
  • 메모리를 분할하여 관리하기 때문에, vector처럼 전체 메모리를 재할당하지 않아도 됩니다.
• 임의 접근(Random Access):
  • vector처럼 인덱스를 사용한 임의 접근이 O(1) 시간 복잡도로 가능합니다.
• 성능:
  • 중간 삽입/삭제는 느림 (O(n)).
• 다목적 컨테이너:
  • 큐, 덱, 스택 같은 구조를 쉽게 구현할 수 있습니다.

2. 헤더 파일

std::deque를 사용하려면 <deque> 헤더 파일을 포함해야 합니다.

3. 사용 예제

4. 주요 멤버 함수

삽입/삭제

함수명	설명
push_back(val)	끝에 요소 추가.
push_front(val)	앞에 요소 추가.
pop_back()	끝 요소 제거.
pop_front()	앞 요소 제거.
insert(it, val)	지정된 위치에 요소 삽입.
erase(it)	지정된 위치의 요소 제거.
clear()	모든 요소 제거.
resize(n, val)	크기를 n으로 조정. 필요하면 val로 초기화.
emplace(it, val)	지정된 위치에 직접 생성자 호출로 요소 추가.
emplace_back(val)	끝에 요소 생성 및 추가.
emplace_front(val)	앞에 요소 생성 및 추가.

접근 및 탐색

함수명	설명
front()	첫 번째 요소를 반환.
back()	마지막 요소를 반환.
at(index)	특정 인덱스의 요소를 반환 (경계 검사 포함).
operator[]	특정 인덱스의 요소를 반환 (경계 검사를 하지 않음).

리스트 관리

함수명	설명
size()	현재 요소의 개수를 반환.
empty()	리스트가 비어 있으면 true, 아니면 false 반환.
max_size()	저장할 수 있는 최대 요소 개수를 반환.
shrink_to_fit()	메모리 사용량을 줄임.