STL#3 Deque

STL중에서도 시퀀스 컨테이너(Sequence Container) - 데이터가 삽입 순서대로 나열되는 형태. 벡터, 리스트 , 데크,- 의 마지막 자료구조인 데크.

 

vector는 동적배열이고

[            ]

list는 이중 연결 리스트,

[ ] <-> [ ] <-> [ ] <-> [ ]

deque 는 double-ended queue로 

[            ]

[            ]

 

잘 쓰이지 않으나 가끔 서버에서 버퍼 컨테이너를 사용하는데 쓰이기도 하나 주로 벡터나 리스트를 사용한다.

기본적으로 어떤 차이가 있는지와 차이만 알아보고 끝낼 것이다.

 

벡터처럼 데이터를 배열형태로 가지고 있는데 배열과 다르게 데이터가 꽉 찼을 때 더 큰 영역을 할당해서 이전하는게 아니라 기존데이터를 두고 독립된 영역에 새로 배열을 만들어 둘을 연결한다는 차이를 가지고 있다. 그래서 벡터와 리스트의 중간의 성질을 가지고 있다.

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

int main()
{
    deque<int> _dq; 
    // capacity의 개념이 없고 필요할 때마다 배열을 새로 만드는 개념이다.
    // push_back과 push_front가 둘 다 있다.
    _dq.push_back(1);
    _dq.push_frint(2);
    
    // random access(임의 접근)도 가능하다.
    cout<<_dq[0]<<endl;  // 2
    
    // vector와 마찬가지로 배열 기반으로 동작한다.
    // 다만 메모리 할당 정책이 다르다.
    vector<int> v(3,1); // size가 3, 1로 모두 초기화.
    deque<int> dq(3,1);
    
    v.push_back(2);
    v.push_back(2); 
    
    dq.push_back(2);
    dq.push_back(2);
    dq.push_front(3);
    dq.push_front(3); 
    
    // 위 과정을 디버깅모드에서 중단점 찍고 메모리 창에서 v, dq의 시작점(v[0], dq[0]) 보면
    // v는 계속 기존주소의 값들이 날라가고 새로 v[0]에서 만드는 반면
    [1, 1, 1, 2, 2]
    
    // dq는 dq[0]은 계속 그 주소에 같은 값인걸 알 수 있다.
    // 다만 push_back까지만 하고 dq[4]를 보면 dq[0]과 관련없는 주소에 저장되어 있었다.
    // 그리고 push_front를 하고 다시 dq[0]을 하면 기존 주소와 또 다른 위치에 저장되어 있다.
    [     3, 3] <-> [1, 1, 1, 2] <-> [2     ]
    
    return 0;
}

 

 

 1.deque의 동작 원리

 

2. 중간삽입/삭제

중간의 삽입 삭제는 주어진 배열 내에서 삽입할 경우 오래 걸린다.

dq[4] = 5; 할경우 다른 원소들의 이동이 일어나서 

[     3, 3] <-> [1, 1, 5, 1] <-> [2, 2    ]

이동이 오래걸린다.  뒤의 원소들이 많았으면 새로운 배열을 만들어 복사도 해야한다.

그래서 벡터와 같이 중간 삽입/삭제는 오래걸린다.

데크에서 중간원소를 삽입/삭제하게 될 경우 하나의 배열 크기를 유지하기 위해 앞 뒤 빈 배열중 비용이 적은쪽으로 밀어야한다. 위의 경우도 오른쪽 배열에 하나의 원소밖에 없었으므로 오른쪽으로 이동했다.

중간에 배열을 삽입하면 더 빠르게 동작했을테지만...

 

3. 처음/끝 삽입/삭제

push_front, push_back.둘 다 빠르다.

 

유동적으로 배열에 접근 가능하니깐

 

4. 임의 접근

어떻게 임의 접근이 동작하는가?

#include <deque>

deaue<int>::iterator iter; 

를 만들어 iterator를 타고 들어가 

 

 using iterator                  = _Deque_iterator<_Scary_val>;
 using const_iterator            = _Deque_const_iterator<_Scary_val>;
// deque 페이지의 위 부분이 나온다 
// deque 파일에서 _Deque_const_iterator를 F12로 한 번 더 타고 간다음에
// 조금 더 내려보면 아래와 같은 부분이 나온다.


    _NODISCARD reference operator*() const noexcept {
        const auto _Mycont = static_cast<const _Mydeque*>(this->_Getcont());
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(_Mycont, "cannot dereference value-initialized deque iterator");
        _STL_VERIFY(_Mycont->_Myoff <= this->_Myoff && this->_Myoff < _Mycont->_Myoff + _Mycont->_Mysize,
            "cannot deference out of range deque iterator");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        _Size_type _Block = _Mycont->_Getblock(_Myoff);
        _Size_type _Off   = _Myoff % _Block_size;
        return _Mycont->_Map[_Block][_Off];
    }
    
    // _Myoff가 몇번째 데이터를 이용해 어떤 블록에 들어있는지를 찾아오고
    // 고정값인 _Block_size를 이용해 그 블록에서 몇번째 오프셋인지 나머지 연산으로 구한다.

즉 블록마다 같은 크기로 가지고 있어서 몇번째 블록인지, 몇번 오프셋인지의 정보를 이용한다.

리스트처럼 앞 뒤 정보를 가지고 있는게 아니라 몇동 몇호처럼 테이블 정보를 _Map이 가지고 있었기에 가능하다.

데이터 블록 내에서 첫번째 블록의 처음부분과 마지막 블록의 마지막 부분 말고는 빈 공간이 있으면 안된다.

 

deque의 특징.

-앞과 뒤에 데이터를 삽입/삭제하는것은 빠르지만 나머지 삽입/삭제는 느리다.(벡터와 유사)

- 벡터는 앞에다가 데이터를 넣는게 느리나 데크는 양방향으로 빠르게 가능하다.