STL 리스트(List)

Vector와 deque처럼 원소가 상대적인 순서를 유지.

List는 시퀸스 컨테이너로 시퀸스 컨테이너가 갖는 모든 특징을 갖는다.

양방향 반복자를 제공한다.

원소 탐색으로는 ++ , -- 를 사용한다.

 

특징 : 차열 중간에 원소를 삽입(insert) 제거(erase)하더라도 상수 시간복잡도의 수행 성능을 보인다.

Vector나 deque처럼 원소를 밀어내지 않고 노드를 로 연결하기만 하면 된다.

 

노드기반 컨테이너의 삽입과 제거 동작은 반복자를 무효화시키지 않는다.

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

하지만 배열기반 컨테이너(vector, deque)는 삽입, 제거 동작이 발생시 메모리가 재 할당되거나 원소가 이동할 수 있으므로 반복자가 무효화된다.

 

List는 다른 list와 결합할 때 좋은 컨테이너이다. Splice() 맴버 함수는 노드의 연산만으로 두 list를 하나의 리스트로 결합할 수 있으며, merge()맴버 함수는 두 list를 하나의 list로 정렬하며 결합한다.