[Algorithm] STL 데크(Deque)

데크 ( deque )

데크는 벡터와 유사하다.

동적 배열에 요소를 관리하며 임의 접근을 허용한다.

또한 벡터의 거의 동일한 인터페이스를 제공한다.

데크와 벡터의 차이는 테크는 동적 배열의 양 끝이 모두 열려있다.

즉, 앞 뒤 모두 삽입/삭제가 가능하다.

 

데크를 사용하기 위해서는 <deque>를 인클루드 해야한다.

또한 namespace std에 정의되어 있다.

 

데크의 기능 

1. 요소의 삽입/삭제는 동적 배열의 시작과 끝 부분 모두 빠르다.

2. 내부 구조는 요소에 접근할 때 하나 이상의 간접 방식을 취하기 때문에 대체로 요소 접근이나 반복자 이동이 약간 더 느리다.

3. 반복자는 특수한 자료형의 스마트포인터여야 한다.

4. 메모리 블록에 대한 크기 제한이 있는 시스템의 경우 데크가 벡터보다 더 많은 요소를 가질 수 있다.

용량이나 재할당 지점을 제어하는 연산을 제공하지 않는다. 내부 구조상 재할당 할 때 모든 요소를 복사할 필요가 없어 벡터보다 성능이 더 좋을 수 있다.

5. 메모리 블록들은 더 이상 사용되지 않는 경우 해제되기 때문에 데크의 메모리 크기는 줄어들 수 있다.

6. 중간에 요소를 삽입/삭제하는 경우 다른 요소들을 이동시켜야 하므로 상당히 느리다.

7. 반복자는 임의 접근 반복자이다.

 

데크 연산 

생성자와 소멸자

연산	설명
deque<elem> c	기본 생성자, 아무 요소도 갖지 않는 빈 데크를 생성한다
deque<elem> c(c2)	복사 생성자. 같은 자료형의 데크를 복사한 데크를 생성, 모든 요소를 복사한다
deque<elem> c = c2	복사 생성자. 같은 자료형의 데크를 복사한 데크를 생성, 모든 요소를 복사한다
deque<elem> c(rv)	이동 생성자. rv의 내용을 갖는 새로운 데크를 만든다 ( C++11 이후 지원 )
deque<elem> c = rv	이동 생성자. rv의 내용을 갖는 새로운 데크를 만든다 ( C++11 이후 지원 )
deque<elem> c(n)	기본 생성자로 초기화된 n개의 요소를 갖는 데크를 만든다
deque<elem> c(n, elem)	n개의 elem을 요소로 갖는 데크를 만든다
deque<elem> c(beg, end)	범위 [beg, end) 내의 요소를 갖는 데크를 만든다
deque<elem> c(initlist)	초기화자 목록 내의 요소로 초기화된 데크를 만든다 ( C++11 이후 지원 )
deque<elem> c = initlist	초기화자 목록 내의 요소로 초기화된 데크를 만든다
c.~deque()	모든 요소를 제거하고 메모리를 해제한다.

 

 

수정하지 않는 연산

연산	설명
c.empty()	컨테이너가 비었는지 알려주는 함수
c.size()	현재 요소의 수를 반환
c.max_size()	최대 저장 가능한 요소의 수를 반환
c.shrink_to_fit()	요소의 수에 맞도록 용량을 줄이라고 요청 ( C++11 이후 지원 )
c1 == c2	c1과 c2가 같은지 반환, 모든 요소가 같아야 한다
c1 != c2	c1과 c2가 다른지 반환
c1 < c2	c1이 c2보다 작은지 반환
c1 > c2	c1이 c2보다 큰지 반환
c1 <= c2	c1이 c2보다 작거나 같은지 반환
c1 >= c2	c1이 c2보다 크거나 같은지 반환
c[idx]	idx번째 있는 요소 반환 ( 범위 검사를 하지 않음 )
c.at(idx)	idx번째 있는 요소 반환 ( 범위를 넘어넌 경우 범위 오류 예외를 던짐 )
c.front()	첫 번째 요소 반환 ( 첫 번째 요소가 존재하는지 검사 안함 )
c.back()	마지막 요소 반환 ( 마지막 요소가 존재하는지 검사 안함 )
c.begin()	첫 번째 요소에 대한 임의 접근 반복자 반환
c.end()	마지막 요소 다음 위치에 대한 임의 접근 반복자 반환
c.cbegin()	첫 번째 요소에 대한 임의 접근 상수 반복자 반환 ( C++11 이후 지원 )
c.cend()	마지막 요소 다음 위치에 대한 임의 접근 반복자 반환 ( C++11 이후 지원 )
c.rbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 반복자 반환
c.rend()	역방향 반복에서의 마지막 요소 다음 위치에 대한 역방향 반복자 반환
c.crbegin()	역방향 반복에서의 첫 번째 요소에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )
c.crend()	역방향 반복에서의 마지막 요소 다음 위치에 대한 역방향 상수 반복자 반환 ( C++11 이후 지원 )

 

 

삽입/제거 연산

연산	설명
c = c2	c2의 모든 요소를 c에 할당
c = rv	rv의 모든 요소를 c에 이동 할당 ( C++11 이후 지원 )
c = initlist	초기화자 목록 내 모든 요소를 할당 ( C++11 이후 지원 )
c.assign(n, elem)	n개의 elem의 복사본을 요소로 할당
c.assign(beg,end)	범위 [beg,end) 내 요소를 할당
c.assign(initlist)	초기화자 목록 내 모든 요소를 c에 할당
c1.swap(c2)	c1과 c2의 데이터를 교환
swap(c1,c2)	c1과 c2의 데이터를 교환
c.push_back(elem)	elem의 복사본을 c의 끝에 덧붙임
c.pop_back()	마지막 요소 삭제 ( 반환하지 않음 )
c.push_front(elem)	elem의 복사본을 c의 앞에 덧붙임
c.pop_front()	첫 번째 요소 삭제 ( 반환하지 않음 )
c.insert(pos,elem)	반복자 위치 pos 앞에 elem의 복사본을 삽입 후 새 요소의 위치 반환
c.insert(pos,n,elem)	반복자 위치 pos 앞에 elem의 복사본을 n개 삽입 후 새 요소 중 첫 번째 요소의 위치 반환
c.insert(pos,beg,end)	반복자 위치 pos 앞에 [beg. end) 내 모든 요소의 복사본 삽입 후 새 요소 중 첫 번째 요소의 위치 반환
c.inset(pos,initlist)	반복자 위치 pos 앞에 초기화자 목록 내 모든 요소의 복사본 삽입 후 새 요소 중 첫 번째 요소의 위치를 반환
c.emplace(pos,args....)	반복자 위치 pos 앞에 인자 args로 초기화된 요소의 복사본을 삽입 후 새 요소의 위치 반환 ( C++11 이후 지원 )
c.emplace_back(args...)	인자 args로 초기화된 요소의 복사본을 끝에 삽입, 반환값 없음 ( C++11 이후 지원 )
c.emplace_front(args...)	인자 args로 초기화된 요소의 복사본을 앞에 삽입, 반환값 없음 ( C++11 이후 지원 )
c.erase(pos)	반복자 위치 pos에 있는 요소 삭제 후 다음 요소의 위치 반환
c.erase(beg,end)	범위 [beg,end)내 모든 요소 삭제 후 다음 요소의 위치 반환
c.resize(num)	요소의 수를 num개로 바꿈, 만약 size가 커질 경우 자료형에 맞는 기본 생성자로 초기화
c.resize(num,elem)	요소의 수를 num개로 바꿈, 만약 size가 커질 경우 elem의 복사본으로 초기화
c.clear()	모든 요소를 제거, 컨테이너를 비움