[STL] DEQUE

[STL] DEQUE

STL좀써보자 2008/02/12 17:39

블로그 > 껀
http://blog.naver.com/bravedog/100005052459

■ deque의 능력

● 원소들을 컨테이너의 앞과 끝에 삽입및삭제하는 과정이 빠르다 (vector는 끝의 경우만 빠르다)

이 동작들은 “아모타이즈드” 상수 시간에 이루어진다

● deque의 내부 자료구조는 원소를 액세스하기 위해서 하나 이상의 간접성(indirection)을

이용하기 때문에, 원소의 액세스 시간과 반복자의 이동 시간이 약간 더 느리다

(분리된 메모리 블록을 이용하기 때문에)

● 반복자는 반드시 기존의 포인터 타입이 안라 스마트 포인터여야 한다.

왜냐하면, 다른 메모리 블록으로 이동을 할 수 있어야 하기 때문이다

● 만약 시스템에서 메모리 블록에 대한 사이즈의 제한값이 존재한다면, deque는 vector에 비해서

더 많은 원소를 가질 수 있다.왜냐하면,deque는 하나 이상의 메모리 블록을 사용하기 때문이다.

그러므로 max_size()는 vector에 비해서 더 큰 값을 반환할 것이다.

● deque는 용량과 재할당 같은 제어조건을 사용자에게 주지 않는다. 특별히 deque에서는 원소의

삽입과 삭제가 이루어지는 순간, 원소를 참조하고 있던 모든 포인터와 레퍼런스, 반복자들을

무효화시킨다(맨 앞부분과 맨 뒷부분에 삽입 및 제거를 하는 경우에는 예외이다).

그러나 deque의 재할당은 vector보다 효율적으로 이루어진다. 왜냐하면,

deque의 내부 자료구조의 특성상 deque는 재할당시에 모든 원소들을 복사할 필요가 없다.

● 메모리 블록은 더 이상 사용되지 않을 경우 해제된다. 그러므로 eque의 메모리 사이즈는

줄어들 수 있다(그러나 언제, 어떻게 이루어지는 지는 구현에 따라 다르다).

다음 사항은 vector와 동일하게 적용된다

● 컨테이너의 중간에 원소를 삽입 및 제거하는 동작은 시간을 필요로 한다. 왜냐하면, 삽입되거나

삭제된 원소 이후의원소들이 모두 이동하거나 공간이 부족할경우 새로운공간을 만들기때문이다.

● 반복자는 랜덤 액세스를 지원한다.

요약하자면, 다음과 같은 상황에서는 deque를 선호하는 것이 좋다.

● 컨테이너의 앞쪽과끝쪽으로 삽입과삭제가 이루어지는경우(이것은 queue 구조를위한경우이다)

● 컨테이너의 원소드을 참조하지 않는 경우

● 컨테이너가 더 이상 사용되지 않을 경우 메모리가 해제되기를 원할 경우

(표준에서는 언제 해제되는지에 대한 명시가 없다)

vector의 인터페이스와 deque의 인터페이스는 거의 유사하다. 따라서 vector의 사용법을 안다면 deque를 사용하는 것에는 별다른 어려움이 없다.

■ deque의 생성자와 소멸자
동작	효과
deque<Elem> c	원소 원이 빈 deque를 생성한다
deque<Elem> c1(c2)	같은 타입의 다른 deque를 복사하여 생성한다(모든 원소들은 복사된다)
deque<Elem> c(n)	디폴트 생성자에 의해서 생성되는 n개의 원소와 함깨 deque를 생성한다
deque<Elem> c(n,elem)	elem 원소의 n개의 복사본으로 deque를 초기화하여 생성한다
deque<Elem> c(begn,elem)	[beg,end) 범위의 원소로 deque를 초기화하여 생성한다
c.~deque<Elem>()	모든 원소들을 파괴하고 메모리를 해제한다

■ deque의 수정하지 않는 동작들
동작	효과
c.size()	실제 원소의 개수를 반환한다
c.empty()	컨테이너가 비어있는지를 판단한다 (size()==0와 동일하나 더 빠르다).
c.max_size()	컨테이너가 가질 수 있는 최대 원소의 개수를 반환한다.
c1 == c2	c1과 c2가 같은지 판단한다
c1 != c2	c1과 c2가 다른지 판단한다 ( !(c1==c2)와 동일하다 ).
c1 < c2	c1이 c2보다 작은지를 판단한다
c1 > c2	c1이 c2보다 큰지를 판단한다( c2<c1과 동일하다 ).
c1 <= c2	c1이 c2보다 작거나 같은지를 판단한다 ( !(c2<c1)와 동일하다 ).
c1 >= c2	c1이 c2보다 크거나 같은지를 판단한다 ( !(c1<c2)와 동일하다 ).
c.at(idx)	인덱스가 idx인 원소를 반환한다 (만약 idx가 범위를 벗어났다면 범위 에러 예외를 발생시킨다)
c[idx]	인덱스가 idx인 원소를 반환한다(에러 검사를 하지 않는다)
c.front()	첫 번째 원소를 반환한다(원소가 있는지 검사하지 않는다)
c.back()	마지막 원소를 반환한다(원소가 있는지 검사하지 않는다)
c.begin()	첫 번째 원소를 가리키는 랜덤 액세스 반복자를 반환한다
c.end()	맨 마지막 원소 뒤를 가리키는 랜덤 액세스 반복자를 반환한다
c.rbegin()	역방향에서 첫 번째 원소의 역방향 반복자를 반환한다
c.rend()	역방향에서 마지막 원소 뒤를 가리키는 역방향 반복자를 반환한다

■ deque의 수정하는 동작들
동작	효과
c1 = c2	c2의 모든 원소들을 c1에 할당한다
c.assign(n, elem)	elem 원소의 n개의 복사본을 할당한다
c.assign(beg, end)	[beg,end) 범위의 원소를 할당한다
c1.swap(c2)	c1과 c2의 데이터를 교체한다.
swap(c1,c2)	동일하다(전역 함수).
c.insert(pos,elem)	반복자 pos위치에 elem의 복사본을 삽입한다 그리고 새로운 원소의 위치를 반환한다
c.insert(pos,n,elem)	elem의 n개의 복사본을 반복자 pos 위치에 삽입한다. 반환값은 없다.
c.insert(pos,beg,end)	[beg,end) 범위의 모든 원소들을 복사하여 반복자 pos 위치에 삽입한다. 반환값은 없다.
c.push_back(elem)	끝부분에 elem의 복사본을 추가한다.
c.pop_back()	마지막 원소를 제거한다(제거된 원소를 반환하지 않는다.)
c.push_front(elem)	앞부분에 elem의 복사본을 추가한다
c.pop_front()	첫 번째 원소를 재거한다(제거된 원소를 반환하지 않는다).
c.erase(pos)	반복자 pos 워치의 원소를 제거한다. 그리고 다음 원소의 위치를 반환한다.
c.erase(beg,end)	[beg,end)범위의 모든 원소들을 제거한다. 그리고 다음 원소의 위치를 반환
c.resize(num)	원소의 개수를 num개로 변경한다 (만약 size()가 증가된다면, 새로운 원소들은 그들의 디폴트 생성자에 의해서 생성된다.)
c.resize(num,elem)	원소의 개수를 num개로 변경한다 (만약 size()가 증가된다면, 새로운 원소는 elem의 복사본이다).
c.clear()	모든 원소들을 제거한다(빈 컨테이너로 만든다).

deque의 동작은 다음과 같은 경우에만 vector와 다르다

1. deque는 용량에 관한 함수들을 제공하지 않는다(capacity()와 reserve()).

2. deque는 앞부분과 끝부분에 직접적으로 원소를 추가, 삭제할 수 있는 함수를 제공한다

( push_front()와 pop_front() ).

다른 동작들은 vector와 동일하지다 다음과 같은 상황하에 대해서는 주의해야만 한다

1. at()을 제외한 모든 멤버 함수는 인덱스나 반복자가 유효하지 검사하지 않는다

2. 원소의 삽입 및 제거는 재할당을 유발한다. 그러므로 모든 삽입 및 제거 동작은 모든 포인터와

레퍼런스, deque의 다른 원소를 참조한는 반복자를 무효화시킨다. 그러나 맨앞부분과 뒷부분의

경우는 이에 해당하지 않는다. 이 경우에는 레퍼런스와 포인터는 유효하다.

그러나 반복자는 여전히 유효하지 않다.