[STL] deque 정리 및 예제

[STL] deque 정리 및 예제

deque 컨테이너는 vector 컨테이너와 기능과 동작이 비슷한 컨테이너로 vector의 단점을 보완하는 몇가지 특징을 갖는다.

deque도 vector 컨테이너와 같이 시퀀스 컨테이너이며 배열 기반 컨테이너이다.

[기타/C++ STL] - [STL] vector 벡터 정리 및 예제

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

생성자
deque dq	dq는 빈 컨테이너이다.
deque dq(n)	dq는 기본값으로 초기화된 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번째 원소를 참조한다.
dq.back()	dq의 마지막 원소를 참조한다.
p=dq.begin()	p는 dq의 첫 원소를 가리키는 반복자다
dq.clear()	dq의 모든 원소를 제거한다.
dq.empty()	dq가 비었는지 조사한다.
p=dq.end()	p는 dq의 끝을 표식하는 반복자다
q=dq.erase(p)	p가 가리키는 원소를 제거한다. q는 다음 원소를 가리킨다.
q=dq.erase(b,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()	dq의 끝에 x를 추가한다.
dq.push_front()	dq의 앞쪽에 x를 추가한다.
p=dq.rbegin()	p는 dq의 역 순차열의 첫 원소를 가리키는 반복자이다.
p=dq.rend()	p는 dq의 역 순차의 끝을 표식하는 반복자
dq.resize(n)	dq의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화한다.
dq.resize(n,x)	dq의 크기를 n으로 변경하고 확장되는 공간의 값을 x 값으로 초기화한다.
dq.size()	dq 원소의 개수다
dq.swap(dq2)	dq와 dq2를 swap 한다.

연산자
dq1 == dq2	dq1과 dq2의 모든 원소가 같은가? (bool)
dq1!=dq2	dq1과 dq2의 모든 원소 중 하나라도 다른 원소가 있는가?
dq1 < dq2	문자열 비교처럼 dq2가 dq1보다 큰가?
dq1 > dq2	문자열 비교처럼 dq1이 dq2보다 큰가?
dq[i]	dq의 i번째 원소를 참조한다.

멤버 형식
allocator_type	메모리 관리자 형식
const_iterator	const 반복자 형식
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 는 vector의 메모리 할당 단점을 해결하기 위해 여러 개의 메모리 블록을 할당하고 사용자에게는 하나의 블록처럼 보이게 하는 정책을 사용한다.

vector는 새로운 원소를 삽입할 때 할당된 메모리가 부족하면 이전 메모리 블록을 삭제하고 새로운 메모리 블록을 재할당하며 이전 원소를 모두 복사하지만, deque는 새로운 단위의 메모리 블록을 할당하고 원소를 삽입한다.

또한, 새로운 원소를 순차열 중간에 삽입 , 제거 하더라도 원소의 개수가 작은 쪽 으로 밀어낸다.

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

#include <iostream> #include <deque> using namespace std; int main(){     deque<int> dq;     dq.push_back(10);     dq.push_back(20);     dq.push_back(30);     dq.push_back(40);      dq.push_back(50);     for (deque<int>::size_type i = 0; i < dq.size(); ++i){         cout << dq[i] << ' ';     }     cout << endl;     dq.push_front(100);     dq.push_front(200);    // 앞에 추가한다.     for (deque<int>::size_type i = 0; i < dq.size(); ++i){         cout << dq[i] << ' ';     }     cout << endl;     deque<int>::iterator iter;     deque<int>::iterator iter2;     for (iter = dq.begin(); iter != dq.end(); ++iter){         cout << *iter << ' ';     }     cout << endl;     iter = dq.begin() + 2;            // dq의 3번째 원소에 접근     iter2 = dq.insert(iter, 500);    // 3번째 원소 자리에 500을 삽입한다.     cout << *iter2 << endl;     for (iter = dq.begin(); iter != dq.end(); ++iter){         cout << *iter << ' ';     }     return 0; }

결과 : 10 20 30 40 50 200 100 10 20 30 40 50 200 100 10 20 30 40 50 500 200 100 500 10 20 30 40 50

deque는 시퀀스 컨테이너이며 배열 기반 컨테이너이다. 그래서 vector와 유사한 특징을 가지며 임의 접근 반복자(Random Access Iterator)를 지원한다. vector와 다른 점은 원소가 메모리 블록에 연속하게 저장되지만 하나의 메모리 블록이 아닌 여러 메모리 블록에 나뉘어 저장된다는 것이다.

출처: https://hyeonstorage.tistory.com/325?category=614599 [개발이 하고 싶어요]