deque

※ 개인적인 공부를 위해 포스팅 하는 글입니다.

---

▶ 시퀀스 컨테이너 ◀

 

vector : 동적 배열 [                            ]

 

 

 

list : 이중 연결 리스트 [ ] [ ] [ ] [ ] [ ] [ ]

---

 

# deque의 동작 원리

 

deque : double ended queue [         ]  [          ]  [          ]

양방향으로 사용하는 큐..?

deque<int> dq;

dq.push_back(1);
dq.push_front(2);
cout << dq[0] << endl;

ㆍ 벡터와 마찬가지로 배열 기반으로 동작 메모리를 까보자

 

# 테스트 코드

vector<int> v(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);

 

ㆍ 디버그에서 위 vector의 두줄을 실행시켰을때이다. capacity가 초과되어 새로운 메모리로 이동했나보다.

#덱은 어떨까??

ㆍ 하나는 그냥 데이터가 추가됐다.

ㆍ 근데 한줄을 더 살행시키니 데이터가 추가가 안됐다?? 

ㆍ 새로운 메모리블록을 만들어 그곳에 데이터가 들어가서 이 메모리블록 구간엔 데이터가 추가가 안된 것! 

 

# 중간 삽입/삭제  

ㆍ중간에 빈 공간에 있어선 안된다. (각 블록당이여도)  -> 따라서 한칸씩 땅기는 작업이 필요해서 비효율적이다.

# 처음/끝 삽입/삭제 

ㆍ 빠르다. 앞에서도 빠름..? ㅇㅇ 앞에도 블록 추가하면 됨

 

# 임의 접근

ㆍ 빠르게 가능하다. 왜? 내부적으로 한번 어떻게 구현되어 있는지 찾아봤다

ㆍ 엄청 정확한 뜻까지는 잘 모르겠으나... 블록의 위치와 offset의 위치를 찾아주는 그런코드같다.

ㆍ 어느 블록에 있는지, 그 블록의 몇번째 데이터인지를 다른 테이블로 관리 해주고 있는 그런 모습인 것 같다.

 

ㆍ 이래서 중간 삽입삭제가 느린 이유인 것 같다. 이런식의 접근이 가능하려면 빈 공간이 있어선 안된다.