std::deque

 

 

C++ Standard Library 의 deque

 

 

deque

 

deque란?

덱(deque)은 양방향 큐(double-ended queue)의 약자이다.

벡터는 가변 길이 배열이고, push_front() 또는 pop_front() 같은 함수는 비용이 많이든다.

std::deque를 사용하면 이러한 단점을 극복할 수 있다.

 

 

덱의 구조

 

C++ 표준은 어떤 기능의 동작만을 정의할 뿐이며,
어떻게 구현해야 하는지는 정의하지 않는다.

deque는 list 혹은 vector보다 구현이 약간 복잡한데,

deque는 다른 컨테이너만큼 단순하지는 않기 때문에

실제 구현은 좀 더 다른 형태일 수 있고,

많은 최적화 기법이 적용되었을 수 있다.

그러나 기본 개념은 같다. 즉, 이러한 컨테이너를 구현하려면 연속된 메모리 청크가 필요하다.
먼저 덱의 필요조건을 살펴본 후, 실제 구현 방법에 대해 알아보자.

 

++ Puls ++

 

메모리 청크는 
동적으로 메모리를 할당할 때 사용되는 일정한 크기의 메모리 블록을 의미한다.
이때 청크는 요소들 간 포인터를 사용하지 않는다.
각 청크는 배열 형태로 데이터를 저장하는 포인터와 청크의 크기,
다음 청크를 가리키는 포인터를 갖고 있다.
여기서 포인터를 사용하지 않는다는 것은
메모리 청크는 일반적인 포인터를 사용하지 않고, 
인덱스 또는 오프셋을 사용하여 요소들을 참조한다는 의미다.

 

쉽게 얘기해서 

배열 같은 자료나 동적 메모리 할당하는 자료를 사용할 때는 메모리 청크를 사용하고,

리스트와 같이 연결된 자료를 사용할 때는 노드를 사용하면 된다.

 

++

 

C++ 표준에서는 덱의 동작에 있어서 다음 조건을 만족해야한다고 규정한다.

 

1) n/2의 시간 복잡도를 가지는 원리

 

• push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 한다.
• 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 한다.
• 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며,
  실제로는 최대 n/2 단계로 동작한다.
  여기서 n은 덱의 크기이다.

 

이 조건들을 살펴보면 덱은 양방향으로 매우 빠르게 확장할 수 있어야 하며,
모든 원소에 임의의 접근을 제공해야 한다.

 

 

그러므로 자료 구조가 벡터와 비슷하지만,
앞쪽과 뒷쪽 모두 확장할 수 있다는 점에서 다르다.

 

원소 삽입과 삭제 시 n/2 단계를 허용한다는 점에서
이 연산이 모든 원소를 이동시키는 동작을 수행한다는 점을 예상할 수 있으며,

이러한 원소 이동을 벡터에서 구현하려면 삽입 또는 삭제의 연산이 필요하다.

 

하지만 덱은 어느 방향으로든 빠르게 확장해나가는 것이
덱의 자료구조의 근간이 되는 요건이다.

원소 삽입시,
벡터와 같이 나머지 원소를 항상 오른쪽으로 이동해야만 한다는 의미가 아니라는 뜻이다.

 

원소 삽입 위치에서 가장 가까운 끝쪽 오른쪽이라면 오른쪽 왼쪽이라면 왼쪽이 될 수 있으며,
해당 방향으로 나머지 원소를 이동해도 된다.

 

이러한 특정 위치에서 가장 가까운 끝은

컨테이너 내부의 삽입 위치에서 n/2 이상 떨어져 있을 수 없기 때문에

최대 n/2 단계의 시간 복잡도를 가진다.

 

 

2) deque의 메모리 관리법

 

덱의 맨 앞에 새로운 원소를 추가할 경우,

만약 첫 번째 메모리 청크에 여유 공간이 없다면, 새로운 청크를 할당하고,

이 메모리 청크 주소를 맨 첫 번째 메모리 청크 주소로 설정한다.

이 작업을 수행하려면 청크 주소를 저장하는 메모리 공간은 새로 할당해야 하지만,

실제 원소 데이터는 전혀 이동시키지 않아도 된다.

 

메모리 재할당을 최소화하려면 첫 번쨰 청크부터 원소를 추가하지 않고

중간 위치의 청크부터 원소를 저장할 수 있다.

이러한 방식을 사용하면 일정 횟수위 push_front() 함수에 대해 메모리 재할당을 피할 수 있다.

 

 

1) 과 2) 로 deque를 이해했으니 

deque를 사용해보자.

 

출저 - 

https://learn.microsoft.com/ko-kr/cpp/standard-library/deque-class?view=msvc-170

deque 클래스

// deque_assign.cpp
// compile with: /EHsc
#include <deque>
#include <iostream>
#include <initializer_list>

int main()
{
    using namespace std;
    deque <int> c1, c2;
    deque <int>::const_iterator cIter;

    c1.push_back(10);
    c1.push_back(20);
    c1.push_back(30);
    c2.push_back(40);
    c2.push_back(50);
    c2.push_back(60);

    deque<int> d1{ 1, 2, 3, 4 };
    initializer_list<int> iList{ 5, 6, 7, 8 };
    d1.assign(iList); // deque에서 요소를 지우고 대상 deque에 요소의 새 시퀀스를 복사합니다.

    cout << "d1 = ";
    for (int i : d1)
        cout << i;
    cout << endl;

    cout << "c1 =";
    for (int i : c1)
        cout << i;
    cout << endl;

    c1.assign(++c2.begin(), c2.end()); // 구간을 입력
    cout << "c1 =";
    for (int i : c1)
        cout << i;
    cout << endl;

    c1.assign(7, 4); // 4를 7번 출력
    cout << "c1 =";
    for (int i : c1)
        cout << i;
    cout << endl;
}

 

해당 결과

 

 

해당 게시글은 코딩 테스트를 위한 자료 구조와 알고리즘 with c++를 주교재로,

Microsoft Learn 에서 예제 발췌 및 참고,
이외 각종 사이트를 참조하여 작성되었습니다.