[STL] List

오늘은 List에 대해 정리해 볼까 합니다.

 

LIST

 리스트들은 연속적인 컨테이너 종류중 하나입니다. 원소들은 선형 연속성에 의해 정렬되어 있습니다. 리스트 컨테이너 들은 더블 링크드 리스트의 한 종류이며, 더블 링크드 리스트들을 사용해 메모리 상으로 인접하지 않은 곳(다른곳)에 원소들을 저장할수 있습니다. List를 정렬시 각각의 원소들이 앞에 링크된 원소와 뒤따르는 원소의 연관관계에 의해 정렬됩니다.

LIST의 장점으로는 컨테이너의 특정 위치에 원소 삽입, 삭제가 효율적이며, 앞(forward) 혹은 뒤(backward)방향으로 반복 접근이 가능한 장점이 있습니다. 위에서 작성한것과 같이 메모리 상에 꼭 인접한 공간에 할당되지 않으므로 효율적인 이동이 가능합니다.

다른 기본 표준 연속 컨테이너(벡터, 덱)과 비교하면, 리스트는 컨테이너 안의 어떤 위에 있는 원소들의 삽입, 추출, 이동의 수행능력이 좋습니다.

한편 단점으로는 리스트는 요소에 대한 직접접근이 불가능합니다. 예를 들자면, 리스트에 있는 다섯번째 자리에 있는 요소에 접근 하려고 하면 이미 알고 있는 자리에서부터(첫번째 혹은 마지막) 차례차례 접근하는 수밖에 없습니다. 따라서 요소에 접근하는 시간이 추가적으로 소요되게 됩니다. 또한 리스트들은 각각의 원소들을 연결시켜 놓기 위해 Link되는 포인터 부분이 존재하기 때문에 데이터 저장공간 외에 추가적으로 Pointer 메모리를 추가적으로 사용합니다. 만약에 작은 용량이 아닌 큰 사이즈의 리스트를 사용할 때 이 부분이 문제가 될수 있으므로 주의해야 합니다.

리스트가 확장되거나, 필요에 의해 작아질때  리스트의 크기는 STL에서 자동적으로 조절합니다.

C++ 표준 템플릿 라이브러리의 리스트 에서는 두개의 파라메터를 갖습니다.

 

template <class T ,class Allocator = allocator<T>> class list;

    T : 요소의 타입

    Allocator : 용량 할당 model를 정의하기 위해 사용된 allocator 객체(object)타입

 

Member functions

 

Iterators

 

Capacity

 

Element access

 

Modifiers

 

Allocaotr

 

Operations

 

Member types

of template <class T, class Allocator = allocator<T> class list;