deque, map

주의 : 해당 게시물에서 작성될 내용은 과제를 해결하기 위해 출처의 내용을 그대로 작성한 부분이 많으며 일절 광고나 수익 창출 목적으로 쓰인 것이 아님을 밝힙니다.

Deque
먼저 deque는 vector의 단점을 보완하기 위해 만들어졌습니다. vector처럼 배열 기반의 구조입니다.
Double Ended Queue의 준말로 기존의 큐와는 다르게 앞 뒤 어디로든 자료를 넣을 수 있고 어디로든 뺄 수 있는 자료구조 형태를 의미합니다.
vector에서는 새로운 원소가 추가될 때 메모리를 재할당하고 이전 원소를 복사하는 방식으로 인하여, 삽입시의 성능이 저하되는 단점이 있지만 deque는 이러한 단점을 보완하기 위해서 여러 개의 메모리 블록을 할당하고 하나의 블록처럼 여기는 기능을 제공합니다.
메모리가 부족할 때마다 일정한 크기의 새로운 메모리 블록을 할당함으로써 이전 원소들을 복사하지 않습니다. 또한 중간에 원소를 삽입하거나 삭제할 수 있습니다.
queue나 stack보다는 유연하고 Linked List보다는 조금 덜하다고 볼 수 있습니다. 선형으로 되어있는 배열보다는 원형으로 이루어져 있다고 생각하면 쉽습니다.

사용법 (vector와 90% 비슷합니다.)
먼저 <deque>헤더 파일을 추가합니다. using namespace std; 를 사용하면 편하게 사용할 수 있습니다.
선언은 deque<[Data Type]> [변수이름]을 합니다. (예시는 deque <string> dq;)

생성자와 연산자
deque dq는 비어있는 deque dq를 생성합니다.
deque dq(10)는 default(0)값으로 초기화된 10개의 원소를 가진 dq를 생성합니다.
deque dq(10, 4)는 4의 값으로 초기화 된 10개의 원소를 가진 dq를 생성합니다.
deque dq2(dq1)은 dq1을 복사한 dq2를 생성합니다.

멤버함수 (자주 사용하는 것들만 작성했습니다.)
dq.assign(4, 3)은 3의 값으로 4개의 원소를 할당합니다.
dq.front()는 첫번째 원소를 참조합니다.
dq.back()은 마지막 원소를 참조합니다.
dq.clear()는 모든 원소를 제거합니다.

dq.push_front(3)는 첫번째 원소 앞에 원소 3을 삽입합니다.
dq.pop_front()는 첫번째 원소를 제거합니다.
dq.push_back(5)은 마지막 원소 뒤에 원소 5를 삽입합니다.
dq.pop_back()은 마지막 원소를 제거합니다.

dq.begin()은 첫 번째 원소를 가리킵니다. (iterator와 사용합니다.)
dq.end()는 마지막 원소를 가리킵니다. (iterator와 사용합니다.)

---

Map
각 노드가 key와 value 쌍으로 이루어진 트리입니다. (중복이 허용되지 않습니다.)
first, second가 있는 pair 객체로 저장되는데 first-key와 second-value로 저장됩니다.

기본 형태는 map <key, value> map1입니다.

정렬
자료를 저장할 때 내부에서 자동으로 정렬합니다.
key를 기준으로 정렬하며 오름차순으로 정렬합니다.

사용방법
<map> 헤더파일을 추가합니다.
선언할 때는 map <key type, value type> 이름입니다.
map에서 데이터를 찾을 때는 iterator을 사용합니다. (찾지 못했을 경우에는 end를 반환합니다.)
중복을 허용하지 않기 때문에 insert 수행 시 key가 중복되면 insert가 수행되지 않습니다.

기본 메소드
begin()은 첫 번째 원소의 iterator를 반환합니다.
end()는 마지막 원소 다음의 iterator를 반환합니다.
clear()는 저장하고 있는 모든 원소를 삭제합니다.
insert()는 원소를 추가합니다.