다시 정리하는 C++ STL 자료구조 list

 

 

 

[ STL 자료구조 list ]

 

STL의 list는 이중 연결 리스트이다.

원소를 한 번에 하나씩 앞 뒤로 순회할 수 있는 양방향 반복자(bidirectional iterator)를 제공한다.

어느 위치에서든 상수 시간에 원소를 삽입 & 삭제할 수 있다.vector와 달리 항상 상수 시간에 원소를 접근할 수 있는 랜덤 반복자를 제공하지는 않지만,많은 알고리즘 함수는 순차적으로 액세스할 수만 있으면 충분하다.

 

 

[ STL list 원소 추가 ]

list는 양방향으로 원소에 접근할 수 있기 때문에

vector와 달리 컨테이너의 앞, 뒤로 원소를 추가할 수 있다.

 

 

[ STL list 원소 제거 ]

1. 전역함수 remove

전역함수 remove

4라는 원소가 제거됐지만, remove() 함수는 제거하려는 원소가 어떤 컨테이너의 원소인지 알 방법이 없다. 

알고리즘과 컨테이너는 서로 모르는 사이이기 때문이다.

따라서 일단 제거하려는 값이 있다면 그 값을

컨테이너의 마지막 값으로 치환하는 방식으로 원소를 제거한다.

 

 

2. 멤버함수 remove

멤버함수 remove

list의 remove() 멤버 함수를 사용하니, 우리가 원하는 대로 원소가 제거됐다.

list의 remove()는 멤버 함수이기 때문에 list의 특성을 그대로 다 이용할 수 있다.

따라서 STL에서 같은 기능의 전역함수와 멤버 함수가 있다면

두 말할 것도 없이 멤버함수를 선택해서 사용해야 한다.

 

3. 멤버함수 erase

list의 erase() 멤버 함수는 반복자를 통해서 원소를 제거할 수 있다.

 

 

 

 

[ STL vector와 list ]

 

1. vector는 연속된 메모리지만, (배열 기반)

list의 메모리는 연속되어있지 않다. (노드 기반)

 

2. vector는 빠른 데이터 참조에 유리하다.

[] 연산자가 오버 로딩돼있어 원하는 원소에 바로 접근 가능하기 때문이다.

list는 반복자를 통한 순차 탐색만 가능하다. 

 

3. 빈번한 삽입, 삭제가 필요한 경우에는 list가 유리하다.

vector는 메모리 정책에 따라 메모리의 빈번한 할당, 재할당이 일어날 수도 있고

할당한 메모리에 비해 훨씬 적은 메모리를 사용할 경우도 있을 수 있다.

반면, list는 노드 기반이기 때문에 원소의 개수만큼 메모리를 사용한다.