C++에서 vector의 단점을 극복한 deque

[프로그래밍언어(Programming Language)/C || C++] - Deque, 덱 , 자료구조 [CPP]

 

물론 덱에 대한 글은 썼지만 그냥 사용법만 적어놨다.

 

아무래도 모든 자료구조는 trade-off 관계일 수 밖에 없다.

하지만 이익을 최대한보고 손해를 최소한으로 하는 인간의 끊임 없는 노력은 

vector의 단점마저 극복하고자 하였다.

 

vector에서 push_front() 는 insert로 대신한다고 하였다. erase도 마찬가지다. 

즉, 맨 앞에서 일어나는 삽입과 삭제는 cost가 높다. 즉, 시간이 오래걸린다.

 

그래서 사람들은 덱을 만들어냈다.

 

---

 

덱은 아래 3가지의 조건을 만족해야 한다.

push_front(), pop_front(), push_back(), pop_back()에 있어서 O(1)의 시간복잡도를 가진다.

모든 원소에 대해 O(1)로 접근이 가능해야 한다.

덱 중간의 원소 삽입에 대해서는 O(N)의 시간복잡도로 동작해야한다 (실제로는 N/2이다.)

 

즉, 저게 가능하다면 굳이 벡터를 쓸 필요는 없을 것 같이 보인다.

벡터는 앞에서의 삭제,삽입이 힘드니까

굳이 써야하나? 이런 생각이 들 것이다.

 

**특히 임의의 위치에서 삽입과 삭제 발생 시

해당 위치의 앞 과 뒤로 나누어질텐데

앞 부분을 뒤로 밀지, 뒷 부분을 앞으로 당길지 선택할 수 있다.

++ 즉, 작은 것을 옮기는 것이 더 낫겠지? 작은 부분의 원소의 개수가 N/2를 넘을 수 없으므로 최대N/2라고 한다.

 

 

---

아니 근데 어떻게 앞 뒤로 확장이 가능한거지???

 

덱에서는 단일 메모리 블럭을 사용하는 것이 아니다.

즉, 여러 메모리 블럭을 사용하지만 그 메모리 블럭이 연속되어 있다는 것이다.

다시 말해서 연속된 메모리 블럭이 필요하다.

그래서 앞 뒤로 확장이 가능하다.

 

임의의 위치 접근은 벡터나 배열과 유사하게 접근이 가능하다.

 

덱 앞에 새로운 원소 추가할 경우

해당 메모리 블럭이 꽉찼다면 앞선 메모리 블럭을 할당하여

이 메모리 블럭의 맨 첫번째를 base address로 삼는다.

즉, 주소를 저장하는 메모리 공간은 새로 할당하지만

해당 메모리 블럭에 있는 데이터는 이동시키지 않아도 된다는 것이다.

 

**

덱을 이용할 때 항상 주소가 메모리 블럭의 맨 앞부터 시작한다면 앞에 원소를 추가하는 일은

무조건적으로 다른 메모리 블럭을 필요로 할 것이다. 

 

때문에 블럭의 중간을 첫번째 주소가 되게 한다면 push_front()에 대한 오버헤드를 어느정도 피할 수 있다. 

 

 

---

 

덱은 위 조건에 부합하는 컨테이너를 의미한다.

 

덱은 벡터보다 좋은 점을 가지고 있지만

여전히 trade-off 이다.

메모리에서 벡터보다는 효율적이지 않은 것을 가지고 있다.

 

양 끝단에서만 삽입과 삭제가 일어난다면 벡터보다 좋은 컨테이너가 되겠다.

 

---

참고로 

덱을 이용해서

스택과 큐 그리고 우선순위 큐가 만들어졌다.

덱에서 필요한 인터페이스만 제공하여 덱의 기능을 제한시켜서 구현했다.

[프로그래밍언어(Programming Language)/C || C++] - Stack, 스택 , 자료구조 [CPP]

[프로그래밍언어(Programming Language)/C || C++] - STL 우선순위 , Priority Queue 사용법 [C++]

[프로그래밍언어(Programming Language)/C || C++] - Queue, 큐 , 자료구조 [CPP]