덱(deque) 은 시퀀스 컨테이너(Sequence Container) 중 하나로 순서를 유지하는 선형 자료구조이다.
deque 은 vector 의 단점을 보완하기 위해 만들어진 컨테이너이며 vector 와 마찬가지로 배열 기반의
구조를 가지고 있다.
vector 는 메모리 공간이 가득차면 새로운 메모리 블럭을 만들고 원본 데이터를 복사한 다음 원본 메모리
블럭을 할당해제 시킨다.
deque 는 메모리 공간이 가득차도 vector 와 달리 새로운 메모리 블럭을 하나 더 만들고 여러 개의 메모리
블럭을 하나의 블럭처럼 여긴다.
데이터들이 메모리상에 붙어있지만 메모리 블럭들은 떨어져 있기 때문에 캐시 적중률(Cache Hit Rate) 이
vector 보다는 낮다.
deque 는 위와 같은 구조를 가지고 있기에 vector 와 달리 push_front(), pop_front() 가 존재하며
중간에서 원소를 삽입/삭제 하는 경우에도 vector 에 비해 조금 더 효율적이다.
deque 에 대한 일반적인 연산의 복잡도는 다음과 같다.
O(1)O(1)O(N)<aside> 💡
장점
</aside>
vector 보다 비용이 적게 든다.<aside> 💡
단점
</aside>
deque 의 원소에 안전하게 접근할 수 있다.vector 보다 중간 삽입/삭제가 좋지만 list 보다는 좋지 못하다.vector 보다 성능이 좋지 못하다.deque 헤더파일#include <deque>
deque 의 선언std::deque<Type> DequeName;
deque 생성자 (편의상 int)| std::deque<int> dq; | 비어있는 덱 dq를 생성 |
|---|---|
| std::deque<int> dq(n); | 기본값(0)으로 초기화된 n 개의 원소를 갖는 덱 dq를 생성 |
| std::deque<int> dq(n, m); | m으로 초기화된 n 개의 원소를 갖는 덱 dq를 생성 |
| std::deque<int> dq2(dq1); | 덱 dq1을 복사하여 덱 dq2를 생성 |
std::deque<int> dq;
| dq.push_front(n) | 덱 맨 앞에 원소 n 삽입 |
|---|---|
| dq.push_back(n) | 덱 맨 뒤에 원소 n 삽입 |
| dq.insert(iter, m) | iter가 가리키는 위치에 m을 삽입한 후 해당 위치를 가리키는 iterator를 반환 |
| dq.insert(iter, n, m) | iter가 가리키는 위치에 n 개의 원소 m을 삽입한 후 해당 위치를 가리키는 iterator를 |
| 반환. 삽입 시 앞뒤 원소의 개수를 판단해 적은 쪽으로 밀어서 삽입 | |
| dq.pop_front() | 첫 번째 원소를 제거 |
| dq.pop_back() | 마지막 원소를 제거 |
| dq.erase(iter) | iter가 가리키는 위치의 원소를 삭제한 후 앞뒤의 원소 개수를 판단해 적은 쪽의 원소를 |
당겨서 채움. 삭제한 곳의 iterator를 반환함. |
|
| dq.clear() | 모든 원소를 제거 |
| dq.assign(n, m) | m의 값으로 초기화된 n 개의 원소를 할당 |
| dq.front() | 첫 번째 원소의 참조를 반환 |
| dq.back() | 마지막 원소의 참조를 반환 |
| dq.at(index) | index 번째 원소를 반환. (유효 index 인지 체크하기 때문에 안전하나 dq[index]보다 |
| 느림) | |
| dq[index] | index 번째 원소를 반환. (유효 index 인지 체크하지 않아 dq.at(index)보다 빠름) |
| dq.begin() | 첫 번째 원소를 가리키는 iterator를 반환 |
| dq.end() | 마지막 원소의 다음을 가리키는 iterator를 반환 |
| dq.rbegin() | 마지막 원소를 가리키는 reverse_iterator를 반환 |
| dq.rend() | 첫 번째 원소의 앞을 가리키는 reverse_iterator를 반환 |
| dq.size() | 원소의 개수를 반환 |
| dq.resize(n) | size를 n 으로 변경. 만약 size가 커진 경우 빈 곳을 0(기본값)으로 초기화, |
| 작아진 경우 뒤에서부터 원소 삭제 | |
| dq.resize(n, m) | size를 n 으로 변경. 만약 size가 커진 경우 빈 곳을 m으로 초기화, |
| 작아진 경우 뒤에서부터 원소 삭제 | |
| dq.empty() | 덱 dq가 비었으면 (size == 0) true를 반환 |
| dq2.swap(dq1) | dq2 덱과 dq1 덱을 서로 바꿈 |
deque에는 capacity가 없다.
deque 의 원소 삽입/삭제 과정을 간략화 하면 다음과 같이 진행된다.
deque의 맨 앞, 뒤에서 원소 삽입/삭제 시에는 원본 원소들을 복사하는 과정이 없기 때문에 빠르게 동작한다.
deque의 중간 위치에서 원소 삽입/삭제 시에는 원본 원소들을 복사하는 과정이 필요하기 때문에
비효율적이다.
#include <iostream>
#include <deque>
int main()
{
std::deque<int> dq;
std::deque<int>::iterator it;
// [1][2][3][4][5] deque 생성
for (int i = 1; i <= 5; i++)
dq.push_back(i);
std::cout << "원본 deque" << std::endl;
for (it = dq.begin(); it != dq.end(); ++it)
std::cout << (*it) << " ";
// 원본 deque 복사
std::deque<int> dq1 = dq;
std::deque<int> dq2 = dq;
std::cout << "\\n\\ndq[1]에 0삽입" << std::endl;
dq1.insert(dq1.begin() + 1, 0);
for (it = dq1.begin(); it != dq1.end(); ++it)
std::cout << (*it) << " ";
std::cout << "\\n\\ndq[1] 원소 삭제" << std::endl;
dq2.erase(dq2.begin() + 1);
for (it = dq2.begin(); it != dq2.end(); ++it)
std::cout << (*it) << " ";
return 0;
}
원본 deque
1 2 3 4 5
dq[1]에 0삽입
1 0 2 3 4 5
dq[1] 원소 삭제
1 3 4 5
deque는 vector처럼 임의 접근(Random Access)이 가능하다.
#include <iostream>
#include <deque>
int main()
{
std::deque<int> dq;
std::deque<int>::iterator it;
// [1][2][3][4][5] deque 생성
for (int i = 1; i <= 5; i++)
dq.push_back(i);
std::cout << "원본 deque" << std::endl;
for (it = dq.begin(); it != dq.end(); ++it)
std::cout << (*it) << " ";
// 3번째 원소 dq[2] 임의 접근
dq[2] = 0;
// 3번째 원소 출력
std::cout << "\\n\\n3번째 원소 dq[2] = " << dq[2] << std::endl;
std::cout << "\\n임의 접근 후 deque" << std::endl;
for (it = dq.begin(); it != dq.end(); ++it)
std::cout << (*it) << " ";
return 0;
}
원본 deque
1 2 3 4 5
3번째 원소 dq[2] = 0
임의 접근 후 deque
1 2 0 4 5