std::deque(덱)

std::deque(덱)

• push_front, pop_front, push_back, pop_back동작이 O(1) 시간 복잡도로 동작
• 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작
• 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작, 실제로는 최대 n/2

→ 양방향으로 빠르게 확장할 수 있다, 모든 원소에 임의 접근 제공

덱은 벡터와 리스트에서 제공되는 함수를 조합한 것 이상의 기능을 제공한다.

#include <iostream>
#include <deque>

using namespace std;

int main() {
	deque<int> deq = { 1,2,3,4,5 };
	deq.push_front(0); //맨 앞 원소 추가 {0,1,2,3,4,5}
	deq.push_back(6); //맨 뒤 원소 추가 {0,1,2,3,4,5,6}

	deq.insert(deq.begin()+2, 10); //맨 앞에서 두칸 뒤에(deq[2]위치에) 10 추가 {0,1,10,2,3,4,5,6}
	deq.pop_back(); //맨 뒤 원소 삭제 {0,1,10,2,3,4,5}
	deq.pop_front(); //맨 앞 원소 삭제 {1,10,2,3,4,5}

	deq.erase(deq.begin() + 1); //{1, 2, 3, 4, 5}
	deq.erase(deq.begin() + 3, deq.end()); //{1, 2, 3}


}

 

* 스택의 구현을 위해 덱을 기본 컨테이너로 사용한다.