C++ STL) deque란?

deque( double ended queue )

 

양쪽에서 끝나는 que(큐)를 줄여서 '데크'라고 불린다.

stack의 경우엔 최상단에서 삽입, 삭제가 일어나지만,

queue같은 경우는 한쪽에서 삽입, 반대쪽에서 삭제가 일어난다.

(한쪽 입구에서 삽입, 삭제 중 하의 기능만 가능)

 

 

deque 의 클래스는

선형 배열로 지정된 형식의 요소를 정렬하고 벡터와 같이

모든 요소에 대한 빠른 임의 액세스를 허용하고

컨테이너 뒷면에서 효율적인 삽입 및 삭제를 허용하는

시퀀스 컨테이너의 클래스 템플릿이다.

 

이러한 특성은 스택과 큐를 합친 기능으로 모든 입구에서 삽입 삭제가 가능하다.

 

구조

 

stack의 경우엔 LIFO(Last In First Out)

deck의 경우엔 FIFO(First In First Out)

 

deck의 장점

 

• deck는 vector와 다르게 양쪽 끝에서 삽입 삭제가 가능하다
• deck는 vector와 다르게 capacity 와 reserve 가 없다
• deck는 vector와 다르게 연속된 메모리에 존재하지 않는다. (포인터 연산으로 접근 불가하다)
• deck는 vector와 다르게 capacity가 꽉 차면 덩어리채로 메모리가 이동하지 않고

메모리 상에서 잘게 쪼개어서 보관하게 된다.

• deck 객체 자체에서 메모리에 쪼개져서 보관되는 덩어리들의 위치를 기억하고,

각각의 원소에 대해 접근할 수 있는 인터페이스를 제공해준다.

• deck는 어떤 경우라도 각각의 원소는 임의 접근 반복자를 통해 접근할 수 있다.
• deck는 vector에 비해 조금 더 복잡하게 구현되어 있지만

vcetor보다 메로리 공간을 효율적으로 쓸 수 있다. (재할당을 하지 않기 때문에 vector보다 빠름!)

• deck는 크기 할당이 자동으로 수행된다.
• 자원 접근이 쉽다.
• 원소를 어떤 방향으로든 참조해 나갈 수 있다(iterate)
• 데크 끝과 시작 부분에 효율적으로 원소를 추가할 수 있다.

 

코드 작성법

tamplate <class T, class Allocator = allocator<T> >
class deque;
deque <int> dp;

T : 보관하려는 원소의 타입

Allocator : 어떠한 방법으로 메모리에 할당할지에 관련한 할당 (allocator) 타입을 나타낸다.

기본적으로 T의 할당자 클래스 템플릿을 사용해 Heap에 할당!

생성자 : 데크를 생성

소멸자 : 데크를 소멸

operator!=      연산자의 좌변에 있는 deque 개체가 우변에 있는 deque 개체와 같지 않은지 테스트한다.

연산자<          연산자의 좌변에 있는 deque 개체가 우변에 있는 deque 개체보다 작은지 테스트한다.

operator<=     연산자의 좌변에 있는 deque 개체가 우변에 있는 deque 개체보다 작거나 같은지 테스트한다.

operator==     연산자의 좌변에 있는 deque 개체가 우변에 있는 deque 개체와 같은지 테스트한다.

연산자>          연산자의 좌변에 있는 deque 개체가 우변에 있는 deque 개체보다 큰지 테스트한다.

operator>=     연산자의 좌변에 있는 deque 개체가 우변에 있는 deque 개체보다 크거나 같은지 테스트한다.

 

멤버 함수들

 

 

교환

 

swap   두 deque의 요소를 교환한다.

 

반복자

 

begin()

rbegin()

ex) deque::iterator iter = dp.rbegin()

 

rend()

ex) deque::iterator iter = dp.rend()

 

할당 관련

 

size()

max_size()

resize()

empty() : 비었으면 true 반환

 

임의 접근

 

operator[]

at() : aperator[]보다 상대적으로 느리다. (유효범위를 점검하므로)

front()

back()

 

수정자 (Modifier)

 

assign : 데크에 원소를 집어넣는다.

ex) 3의 값으로 4개의 원소 할당

 

dp.assign(4, 3);

 

push_back() : 데크 끄텡 원소를 집어 넣는다.

push_front() : 데크 맨 앞에 원소를 집어 넣는다.

pop_back() : 마지막 원소 제거

pop_front() : 첫번쨰 원소를 제거

insert() : 데크 중간에 원소를 추가

ex) 3번째 위치에 4의 값 삽입

 

de insert(3, 4);

 

erase() : 원소 제거

swap() : 다른 데크와 바꿔치기

clear() : 원소를 모두 제거

 

할당자

 

get_allocator : 할당자 (allocator)를 얻는다.

 

멤버변수들

 

refrence : Allocator::reference

const_reference : Allocator::const_reference

iterator : 임의 접근 반복자(random access iterator)

const_iterator : 상수 임의 접근 반복자

size_type :데크 size를 나타내는 타입

difference_type : 데크 내의 두 원소 사이의 거리를 나타내는 타입

value_type : 원소 타입(T)

allocator_type : 할당자

pointer : 포인터

const_pointer : 상수 포인터
reverse_iterator : 역 반복자(끝에서 부터 참조해나간다)
reverse_iterator
const_reverse_iterator : 상수 역 반복자(reverse_iterator<const_iterator>)

 

#include <iostream>
#include <deque>

int main()
{
	std::deque<int> dq;
    for(int i = 0; i < 5; i++)
    	dq.push_back((i + 1) * 10);
    
    // 반복자 선언
    std::deque<int>::iterator iter;
    
    std::cout << "기본 deque 값 : ";
    for (iter = dq.begin(); iter != dq.end(); iter++)
    {
    	std::cout << *iter << " ";
   	}
std::cout << std::endl << std::endl;

	// test1. 앞뒤 삽입하기
	std::cout << "[Test1] push_front & end" << std::endl;
	dq.push_front(1);
	dq.push_front(2);
	dq.push_back(100);
	dq.push_back(200);
	
	std::cout << "[Test1] deque 값 : ";
	for (iter = dq.begin(); iter != dq.end(); iter++)
		std::cout << *iter << " ";
	std::cout << std::endl << std::endl;

	//[test2] : 역으로 출력
	std::cout << "[Test2] reverse_iterator" << std::endl;

	std::deque<int>::reverse_iterator rlter;

	for (rlter = dq.rbegin(); rlter != dq.rend(); rlter++)
		std::cout << *rlter << " ";
	std::cout << std::endl << std::endl;

	std::cout << "[Test3] insert(conlter ++ 두번, 2, INSERT)" << std::endl;
	std::deque<int>::const_iterator conlter = dq.begin();
	conlter += 2; // 두번째 자리에.
	dq.insert(conlter, 1, 333); // conlter반복자 333 원소 1개 삽입
	for (conlter =dq.begin(); conlter != dq.end(); conlter++)
	{
		std::cout << *conlter << " ";
	}
	std::cout << std::endl << std::endl;



	return 0;
}