[STL] Deque 생성, 삽입, 삭제 등 사용법

 

 

 

---

1. deque

 

deque, 디큐 혹은 덱이라고 부른다.

 

deque 또한 vector와 마찬가지로 배열 기반 컨테이너로서 vector의 있는 멤버 함수들과 거의 유사하다.

 

 

vector와 다른점을 말하면 바로 보이는 것으로는 push_front(), pop_front()가 있다. 

 

해당 멤버 함수들을 사용하여서 vector에서는 뒤에서만 push, pop 하였다면 deque는 앞과, 뒤 2방향에서 원소를 삽입하거나 삭제할 수 있다.

(사실 insert, erase 멤버 함수를 사용하면 vector도 삽입, 삭제 가능함. 단, 비효율적)

 

 

그래서 스택+큐의 구조라 볼수 있다하지만 이는 엄밀히 말하자면 아니며, 쉽게 기억하기 위하여 스택+큐 구조다라고 생각만 하면 될 것이다.

 

 

또한, 눈에 보이지는 않지만 vector와 다른점을 말하자면 vector가 메모리 블록에 연속하여 저장되었다면

 

deque는 여러 메모리 블록에 나뉘어 저장된다.

 

 

 

 

예를 들어 아래와 같이 4개의 원소가 들어 있는 deque이 있다.

 

이럴 경우 push_front(99)를 하여 앞에 원소를 추가해준다고한다면

 

 이처럼 하나의 메모리 블록이 아니라 나누어 저장하므로 앞쪽의 메모리 블록을 두고 저장할 수 있는 것이다.

 

vector의 경우 하나의 메모리 블록을 사용하므로 insert를 사용하여 맨 앞에 삽입을 시도할 경우 모든 원소를 밀어내야하는 비효율적인 동작을 수행해야 한다.

 

 

물론 deque 또한 insert를 사용하여 중간에 삽입하고자 하는 경우 밀어내야 하지만 앞뒤로 더 효율적인 곳을 선택하여 밀어낼 수 있으므로 vector보다 더욱 효율적이다.

 

따라서 deque는 vector보다 좀 더 효율적으로 동작한다.

 

 

 

 

---

2. 코드

환경 : Visual Studio 2019

#include <iostream>
#include <deque>
using namespace std;

int main() {

	/* 생성자 */
	deque<int> dq;
	//deque<int> dq(5); // size = 5만큼 int의 기본값 0으로 초기화
	//deque<int> dq(5, 2); // size = 5 만큼 2로 초기화
	
    // 삽입, 삭제
	dq.push_back(3);	// 3
	dq.push_front(5);	// 5 3
	dq.push_front(2);	// 2 5 3
	dq.push_back(1);	// 2 5 3 1
	dq.pop_front();		// 5 3 1
	for (int i : dq) {
		cout << i << " ";
	}
	cout << "\n";

	cout << "길이 : " << dq.size() << "\n";
	cout << "맨앞 : " << dq.front() << " 맨뒤 : " << dq.back() << "\n";

	// 새로 초기화
	dq.assign(3, 4);	// size = 3 만큼 4로 초기화
	for (int i = 0; i < dq.size(); i++) {
		cout << dq[i] << " ";
	}
	cout << "\n";

	return 0;
}

결과

 

 

---

3. 참 조

 

deque - C++ Reference