deque & list 컨테이너

deque 컨테이너는 vector 컨테이너와 기능과 동작이 가장 비슷한 컨테이너로 시퀀스 컨테이너이며 배열기반 컨테이너이다.

둘중에 차이점은 메모리 블록 할당 정책이다.

vector의 장점이나 단점인 하나의 메모리 블록 할당 정책은 배열처럼 정수 연산만으로 원소에 접근하고 빠르게 값을 읽고 쓸 수 있다. 하지만 새로운 원소가 추가될 때 메모리 재할당과 이전 원소 복사 문제가 발생하여 성능이 저하될 수 있다.

(메모리 삭제 -> 메모리 할당 -> 원소복사 반복..)

그래서 deque는 이처럼 vector의 단점을 해결하기 위해 여러 개의 메모리 블록을 할당하고 사용자에게는 하나의 블록처럼 보이게 한다.

즉 메모리 부족할 때마다 일정한 크기의 새로운 메모리 블록을 할당하여 이전 메모리를 제거하거나 이전 원소를 복사하는 등의 연산을 수행하지 않는다.

(부족시 메모리 할당 -> 메모리 할당..)

(또한 새로운 원소를 순차열 중간에 삽입제거 하더라도 원소의 개수가 작은쪽으로 밀어내게 된다(

 

STL 컨테이너 중 deque와 vector는 배열 기반 컨테이너로서 임의 접근 반복자를 지원한다.

노드 기반 컨테이너인 나머지 컨테이너 list, set, multiset, map, mutilmap은 양방향 반복자를 지원한다.

그래서 임의 접근 반복자가 제공하는 +, -, += -=, [] 연산을 모두 수행할 수 있다.

 

---

list 컨테이너는 vector와 deque처럼 시퀀스 컨테이너로 원소가 상대적인 순서를 유지한다.

그러나 노드 기반 컨테이너로 원소가 노드 단위로 저장되며 이중 연결리스트로 구현된다.

양방향 반복자 이므로 ++ 연산과 * 연산 != 연산으로 모든 원소를 출력할 수 있다.

중간에 원소를 삽입하게 되면 vector나 deque처럼 밀어내지 않고 서로 연결만 다시하면된다.

 

또한 삽입과 제거 동작은 반복자를 무효화 시키지 않는다.

반복자가 가리키는 원소 자체가 제거되지 않는 한 반복자가 가리키는 원소는 그대로 존재한다.

하지만 배열 기반컨테이너의 반복자는 원소의 삽입과 제거 동작이 발생하면 메모리가 재할당되거나 원소가 이동하므로 무효화가 된다.

(즉 반복자가 가리키는값이 계속 유지 된다는 것.)

 

☆ 반복자를 이용해 원소를 제거하는 erase() 말고도 원소의 값으로 원소를 제거하는 remove()멤버함수가 있다. 모든 원소를 순차적으로 검색하며 해당 원소를 삭제한다.(알아서~)

☆ 유일하게 list만이 remove()멤버 함수가 있으므로 잘 활용..