STL 06. 시퀀스 컨테이너 (Deque)

Deque 컨테이너는 Vector 컨테이너와 기능과 동작이 가장 비슷한 컨테이너이다.

vector의 단점을 보완하는 몇가지 특징을 가진다.

Deque 또한 시퀀스 컨테이너이고 배열기반 컨테이너이다.

 

Deque의 주요 인터페이스와 특징

템플릿 형식
template<typename T,  typename Allocator = allocator<T>> class deque	T는 deque 컨테이너 원소의 형식

<Deque의 템플릿 형식>

 

생성자
deque dq	dq는 빈 컨테이너
deque dq(n)	dq는 기본값(0)으로 초기화된 n개의 원소를 가진다.
deque dq(n, x)	dq는 x 값으로 초기화된 n개의 원소를 가진다.
deque dq(dq2)	dq는 dq2의 복사본이다. (복사 생성자를 호출한다.)
deque dq(b, e)	dq는 반복자 구간 [b, e)로 초기화된 원소를 갖는다.

멤버 함수
dq.assign(n, x)	dq에 x값으로 n개의 원소를 할당한다.
dq.assign(b, e)	dq는 반복자 구간 [b, e)로 할당한다.
dq.at(i)	dq의 i번째 원소를 참조한다. (const, 비 const 버전이 존재하며 범위 점검을 포함한다.)
dq.back()	dq의 마지막 원소를 참조한다. (const, 비 const 버전이 있음)
p = dq.begin()	p는 dq의 첫번째 원소를 가리키는 반복자(const, 비 const 버전이 있음)
dq.clear()	dq의 모든 원소를 제거한다.
dq.empty()	dq가 비었는지 조사한다.
p=dq.end()	p는 dq의 끝을 표시하는 반복자다(const, 비 const 버전이 있음)
q=dq.erase(p)	p가 가리키는 원소를 제거한다. q는 다음 원소를 가리킨다.
q=dq.erase(p,e)	반복자구간[b,e)의 모든 원소를 제거한다. q는 다음 원소를 가리킨다.
dq.front()	dq의 첫번째 원소를 참조한다.
q=dq.insert(p, x)	p가 가리키는 위치에 x값을 삽입한다. q는 삽입한 원소를 가리키는 반복자이다.
dq.insert(p, n, x)	p가 가리키는 위치에 n개의 x값을 삽입한다.
dq.insert(p, b, e)	p가 가리키는 위치에 반복자 구간 [b, e)원소를 삽입한다.
x = dq.max_size()	x는 dq가 담을 수 있는 최대 원소의 갯수이다. (메모리의 크기)
dq.pop_back()	dq의 마지막 원소를 제거한다.
dq.pop_front()	dq의 첫 원소를 제거한다.
dq.push_back(x)	dq의 끝에 x를 추가한다.
dq.push_front(x)	dq의 처음에 x를 추가한다.
p = dq.rbegin()	p는 dq의 역 순차열의 첫 원소로 가리키는 반복자다. (const, 비 const 버전이 있음)
p = dq.rend()	p는 dq의 역 순차열의 끝을 표시하는 반복자(const, 비 const 버전이 있음)
dq.rsize(n)	dq의 크기를 n으로 변경하고 확장 되는 공간의 값을 기본 값으로 초기화 한다.
dq.rsize(n , x)	dq의 크기를 n으로 변경하고 확장 되는 공간의 값을 x값으로 초기화 한다.
dq.size()	dq 원소의 개수이다.
dq.swap(dq2)	dq와 dq2를 swap 한다.

연산자
dq1 == dq2	dq1과 dq2의 모든 원소가 같은가? (bool)
dq1 != dq2	dq1과 dq2의 모든 원소 중 하나라도 다른 원소가 있는가? (bool)
dq1 < dq2	문자열 비교처럼 dq2가 dq1보다 큰가? (bool)
dq1 <= dq2	문자열 비교처럼 dq2가 dq1보다 크거나 같은가? (bool)
dq1 > dq2	문자열 비교처럼 dq1이 dq2보다 큰가? (bool)
dq1 >= dq2	문자열 비교처럼 dq1이 dq2보다 크거나 같은가? (bool)
dq[i]	dq의 i번째 원소를 참조한다.(const, 비 const 버전이 있으며 범위 점검이 없음)

<Deque의 인터페이스>

 

멤버 형식
allocator_type	메모리 관리자 형식
const_iterator	cosnt 반복자 형식
const_pointer	const value_type* 포인터 형식
const_reference	const value_type& 형식
const_reverse_iterator	const 역반복자 형식
difference_type	두 반복자 차이의 형식
iterator	반복자 형식
pointer	value_type* (포인터) 형식
reference	value_type& (레퍼런스) 형식
reverse_iterator	역 반복자 형식
size_type	첨자(index)나 원소의 개수 등의 형식
value_type	원소의 형식

<Deque의 템플릿 멤버 형식>

#include <iostream>
#include <deque>
#include <vector>

using namespace std;
int main(void) {
	deque<int> dq;

	for (deque<int>::size_type i = 0; i < 10; ++i)
		dq.push_back((i + 1) * 10);

	for (deque<int>::size_type i = 0; i < dq.size(); ++i)
		cout << dq[i] << ' ';
	cout << endl;

	//vector와의 차이점은 메모리할당 정책이다. 원소가 추가될때 메모리가 부족하면 새로운 메모리 블록을 할당해서 원소를 추가한다.

	vector<int> v(4, 100); // 100으로 초기화 한 size 4의 컨테이너 v
	deque<int> dq1(4, 100); // 100으로 초기화 한 4개의 원소를 갖는 컨테이너 dq

	v.push_back(200); // v에 200 insert
	dq1.push_back(200); // dq1에 200 insert

	for (vector<int>::size_type i = 0; i < v.size(); i++) // v는 메모리 블록을 재할당-> 이전 원소 복사 -> 새로운 원소 추가
		cout << v[i] << " ";
	cout << endl;

	for (deque<int>::size_type i = 0; i < dq1.size(); i++) // dq는 새로운 메모리 블록을 할당하고 새 원소 추가
		cout << dq1[i] << " ";
	cout << endl << endl;
	dq1.push_front(300); // dq1의 맨 앞에 300을 삽입 // 앞쪽에 원소를 추가하므로 앞쪽으로 메모리 블록을 할당하며 추가한다.
	dq1.push_back(1000); // dq1의 맨 뒤에 1000 삽입
	for (deque<int>::size_type i = 0; i < dq1.size(); i++)
		cout << dq1[i] << " ";
	cout << endl << endl;

	deque<int> dq2;
	dq2.push_back(10);
	dq2.push_back(22);
	dq2.push_back(33);
	dq2.push_back(40);
	dq2.push_back(50);

	deque<int>::iterator iter;
	for (iter = dq2.begin(); iter != dq2.end(); iter++)
		cout << *iter << " ";
	cout << endl;

	iter = dq2.begin() + 2; // 반복자에 + 2 : begin + 2 = 33
	cout << *iter << endl;

	iter += 2; // 반복자에 +2  : 33 -> 40 -> 50
	cout << *iter << endl;
	
	iter -= 3; // 반복자에 -3 : 50 -> 40-> 33 -> 22 !
	cout << *iter << endl << endl;

	deque<int> dq3;
	for (int i = 0; i < 10; i++) {
		dq3.push_back((i + 1) * 10);
	}
	deque<int>::iterator iter1;
	deque<int>::iterator iter2;

	for (iter1 = dq3.begin(); iter1 != dq3.end(); ++iter1)
		cout << *iter1 << " ";
	cout << endl;

	iter1 = dq3.begin() + 2; // 시작 + 2에 반복자를 가리킴
	iter2 = dq3.insert(iter1, 500); // 삽입된 원소를 가리키는 반복자
	cout << *iter2 << endl;

	for (iter1 = dq3.begin(); iter1 != dq3.end(); ++iter1)
		cout << *iter1 << " ";
	cout << endl << endl;




	return 0;
}