STL :: 컨테이너(deque)

STL :: 컨테이너(deque)

출처 : http://blog.daum.net/coolprogramming/77

deque 컨테이너는 '시퀀스 컨테이너'이며 '연속 메모리 기반 컨테이너'입니다.

연속 메모리 기반 컨테이너의 특징이 필요하고 요소의 추가, 삭제가 앞쪽과 뒤쪽에서 빈번하게 발생한다면 deque를 사용하는 것이 좋습니다.

 

deque의 주요 개념을 그림으로 표현하면

 

그림에서 보는 것처럼 deque는 앞과 뒤에 데이터 요소들이 추가될 수 있는 형태입니다. 또 데이터 요소를 저장하는 여러 개의 메모리 단위를 갖습니다.

그래서 요소의 추가, 삭제가 앞쪽과 뒤쪽에서 빈번하게 발생하더라도 vector나 string 처럼 메모리를 재할당하고 컨테이너의 모든 요소를 복사할 필요 없이 새로운 메모리 단위를 할당하여 새 요소만 추가하면 됩니다. 또 컨테이너의 중간 요소가 삽입(insert), 삭제(erase) 되더라도 요소들을 뒤쪽이나 앞쪽으로 모두 밀어낼 수 있으므로 vector나 string 보다 더 좋은 성능을 갖습니다. 위 그림을 이해한다면 그리 어렵지 않게 알 수 있을 것입니다.

 

1, deque의 특징과 주요 함수

 앞, 뒤로 추가, 삭제될 수 있으므로 push_front(), push_back(), pop_front(), pop_back()함수 등을 가지고 있으며 연속 메모리 기반 컨테이너이므로 []연산자 함수를 제공합니다.

 

데이터 추가와 출력

#include<iostream>
#include<deque>
using namespace std;
voidmain( )
{
    deque<int> dq;

    for(int i = 0 ; i < 10 ; i++)
        dq.push_back( (i+1)*10 );

    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;
}


1. 10 20 30 40 50 60 70 80 90 100

 데이터를 추가하더라도 일정한 메모리 단위가 생성되며 요소들이 추가됩니다.

위 예제의 그림입니다. 새로운 메모리 단위만 생성할 뿐 vector처럼 메모리 재할당 및 모든 요소 복사가 발생하지 않습니다.

 

 

 

앞쪽에 데이터 요소를 추가하더라도 효율적으로 메모리를 생성합니다.

#include<iostream>
#include<deque>
using namespace std;

voidmain( )
{
    deque<int> dq;

    for(int i = 0 ; i < 10 ; i++)
        dq.push_back( (i+1)*10 );

    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;

    dq.push_front(100);
    dq.push_front(200);
    dq.push_front(300);
    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;
}


1. 10 20 30 40 50 60 70 80 90 100
   300 200 100 10 20 30 40 50 60 70 80 90 100

 push_front()로 앞쪽에 데이터 요소를 추가하면 새로운 메모리 단위를 생성하고 데이터를 추가합니다.

위 예제의 그림입니다.

 

 

 

또 컨테이너 요소 중간에 삽입(insert), 삭제(erase) 하더라도 데이터 요소의 개수가 작은 쪽(앞쪽, 뒤쪽)을 밀어냅니다. vector 처럼 메모리가 부족하면 재할당하고 모든 요소를 복사할 필요없이 새로운 메모리 단위만 할당하면 됩니다.

간단한 insert() 예제입니다.

#include<iostream>
#include<deque>
using namespace std;

voidmain( )
{
    deque<int> dq;

    for(int i = 0 ; i < 10 ; i++)
        dq.push_back( (i+1)*10 );

    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;


    deque<int>::iterator iter = dq.begin()+1;

    iter = dq.insert( iter , 500);


    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;
    cout << *iter << endl;
}




1. 10 20 30 40 50 60 70 80 90 100
   10 500 20 30 40 50 60 70 80 90 100
   500

 중간에 데이터 요소를 삽입하면 삽입할 위치를 기준으로 앞쪽 요소의 개수가 작으므로 앞쪽으로 밀어냅니다. 삽입은 항상 반복자가 가리키는 위치 앞에 삽입됩니다. erase도 비슷하게 동작합니다.

위 예제의 그림입니다.

 

 

 

 

 2, deque의 반복자

deque는 '연속 메모리 기반 컨테이너'이므로 임의 접근 반복자를 제공합니다.

 

반복자 예제

#include<iostream>
#include<deque>
using namespace std;

voidmain( )
{
    deque<int> dq;

    for(int i = 0 ; i < 10 ; i++)
        dq.push_back( (i+1)*10 );

    deque<int>::iterator iter;
    for( iter = dq.begin(); iter != dq.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;

    iter = dq.begin() + 3;
    cout << *iter << endl;
    iter -= 3;
    cout << *iter << endl;
}


1. 10 20 30 40 50 60 70 80 90 100
   40
   10

 deque도  vector, string처럼 '임의 접근 반복자'를 제공합니다.