7.1 deque 데이터 추상(data abstraction)
deque은 `double-ended queue'의 약자이고, `덱(deck)'이라고 발음한다. 전통적으로, 이 용어는 콜렉션의 앞과 뒤 어느 곳에서나 삽입과 삭제가 가능한 데이터 구조들을 지칭하는데 사용되었는데, deque 컨테이너 클래스는 이것뿐만 아니라 더 많은 것을 할 수 있다. 실제로, deque 데이터 구조의 능력은 vector 클래스와 list 클래스가 제공하는 것들을 모두 포함한다.
- vector와 같이 deque은 인덱싱이 가능하다. 콜렉션 내에서의 위치를 키로 사용함으로써, 첨자로 값들을 접근할 수 있다. (물론 list 클래스에서는 제공하지 않는 기능이다.)
- list와 같이 deque의 앞과 뒤에 값을 효율적으로 추가할 수 있다. (vector 클래스에서는 vector의 맨뒤에서 값을 추가하는데 있어 효율적이다.)
- list와 vector 클래스에서와 같이, deque가 관리하는 시퀀스의 중간에서 값들을 삽입할 수 있다. 이러한 삽입 연산은 list에서도 효율적인 연산이지만, vector에서는 조금 더 비용이 드는 연산이다.
간단히 말해서, deque은 vector와 list를 필요로 하는 곳에서 모두 사용할 수 있다. vector와 list 대신에 deque를 사용하게 되면, 종종 프로그램의 성능이 더 나아진다. 어느 데이터 구조를 선택할지에 관해서는 4.2절을 참고하기 바란다.
7.1.1 Include 화일
deque 데이터 타입을 사용하는 프로그램은 모두 deque 헤더 화일을 사용해야 한다.
#include <deque>
7.2 deque 연산
deque는 vector와 같은 방식으로 선언하고, 클래스 내부에는 vector와 동일한 타입 정의를 가지고 있다.
begin()과 end() 멤버 함수는 양방향 반복자를 제공하는 리스트와는 달리, 임의접근 반복자를 리턴한다.
삽입(insert(), push_front(), push_back())은 deque의 원소를 가리키는 반복자나 레퍼런스들을 무효화시킬 수도 있다. 이는 vector 데이터 타입과 같이 list에서의 삽입보다 더 제한적이다.
deque내의 원소 타입에 소멸자가 정의되어 있다면, deque로부터 원소를 삭제할 때, 이 소멸자가 호출될 것이다.
deque 데이터 타입이 임의접근 반복자를 제공하기 때문에, vector에 적용되는 모든 generic 알고리듬은 deque에도 사용될 수 있다.
vector는 커다란 하나의 메모리 블럭에 원소들을 가지고 있는 반면, deque은 많은 수의 좀더 작은 블럭들을 사용한다. 메모리 블럭의 사이즈에 제한을 두고 있는 시스템에서 이는 매우 중요한 사항이며, 이러한 이유때문에 deque은 vector보다 더 많은 원소들을 포함할 수 있다.
값들을 삽입할 때는, 콜렉션내의 원소와 연결되어 있던 인덱스가 바뀌게 된다. 예를 들어, 3번 위치에 값을 삽입하면, 원래 3번 자리에 있던 값은 4번자리를 차지하게 되고, 4번 자리에 있던 값은 5번자리로 차례로 옮겨지게 된다.
7.3 예제 프로그램 - Radix Sort
The radix sort algorithm is a good illustration of how lists and deques can be combined with other containers. In the case of radix sort, a vector of deques is manipulated, much like a hash table.
Radix sorting is a technique for ordering a list of positive integer values. The values are successively ordered on digit positions, from right to left. This is accomplished by copying the values into "buckets," where the index for the bucket is given by the position of the digit being sorted. Once all digit positions have been examined, the list must be sorted.
The following table shows the sequences of values found in each bucket during the four steps involved in sorting the list 624 852 426 987 269 146 415 301 730 78 593. During pass 1 the ones place digits are ordered. During pass 2 the tens place digits are ordered, retaining the relative positions of values set by the earlier pass. On pass 3 the hundreds place digits are ordered, again retaining the previous relative ordering. After three passes the result is an ordered list.
| bucket | pass 1 | pass 2 | pass 3 |
| 0 | 730 | 301 | 78 |
| 1 | 301 | 415 | 146 |
| 2 | 852 | 624, 426 | 269 |
| 3 | 593 | 730 | 301 |
| 4 | 624 | 146 | 415, 426 |
| 5 | 415 | 852 | 593 |
| 6 | 426, 146 | 269 | 624 |
| 7 | 987 | 78 | 730 |
| 8 | 78 | 987 | 852 |
| 9 | 269 | 593 | 987 |
The radix sorting algorithm is simple. A while loop is used to cycle through the various passes. The value of the variable divisor indicates which digit is currently being examined. A boolean flag is used to determine when execution should halt. Each time the while loop is executed a vector of deques is declared. By placing the declaration of this structure inside the while loop, it is reinitialized to empty each step. Each time the loop is executed, the values in the list are copied into the appropriate bucket by executing the function copyIntoBuckets() on each value. Once distributed into the buckets, the values are gathered back into the list by means of an accumulation.
void radixSort(list<unsigned int> & values)
{
bool flag = true;
int divisor = 1;
while (flag) {
vector< deque<unsigned int> > buckets(10);
flag = false;
for_each(values.begin(), values.end(),
copyIntoBuckets(...));
accumulate(buckets.begin(), buckets.end(),
values.begin(), listCopy);
divisor *= 10;
}
}
The use of the function accumulate() here is slightly unusual. The "scalar" value being constructed is the list itself. The initial value for the accumulation is the iterator denoting the beginning of the list. Each bucket is processed by the following binary function:
list<unsigned int>::iterator
listCopy(list<unsigned int>::iterator c,
deque<unsigned int> & lst)
{
// copy list back into original list, returning end
return copy(lst.begin(), lst.end(), c);
}
The only difficulty remaining is defining the function copyIntoBuckets(). The problem here is that the function must take as its argument only the element being inserted, but it must also have access to the three values buckets, divisor and flag. In languages that permit functions to be defined within other functions the solution would be to define copyIntoBuckets() as a local function within the while loop. But C++ has no such facilities. Instead, we must create a class definition, which can be initialized with references to the appropriate values. The parenthesis operator for this class is then used as the function for the for_each() invocation in the radix sort program.
class copyIntoBuckets {
public:
copyIntoBuckets
(int d, vector< deque<unsigned int> > & b, bool & f)
: divisor(d), buckets(b), flag(f) {}
int divisor;
vector<deque<unsigned int> > & buckets;
bool & flag;
void operator () (unsigned int v)
{ int index = (v / divisor) % 10;
// flag is set to true if any bucket
// other than zeroth is used
if (index) flag = true;
buckets[index].push_back(v);
}
};