std::list

1. 특징

 

- 상수 시간에 삽입 및 삭제가 가능

 

- 이중 연결 리스트로 구현(양방향 탐색 가능)

 

- 임의 접근(Random access)을 지원하지 않음

 

- 원소 자체가 소멸되지 않는 한 삽입, 삭제 등의 연산으로 iterator는 무효화되지 않는다.

 

 

2. 정의

 

template <

    class T ,

    class Allocator = std::allocator<T>

> class list;

 

- T : T가 complete type이어야 하고 Allocator에 의해 소멸이 가능해야 한다.(Erasable)

 

- Allocator : 메모리 할당과 해제, 원소의 생성과 소멸을 담당하며 value_type이 T와 같아야 한다.

 

3. 시간 복잡도

 

- 임의 접근 : O(1)

- 삽입 및 삭제 : O(n)

 

 

4. 멤버 함수

 

- operator=(const list& other) : allocator가 other의 것으로 대체되고, 달라졌다면 원소를 복사하기 전에 새로운 allocator로 메모리를 할당하고 이전의 allocator는 기존 메모리를 해제하는 데에 사용된다.  원래의 원소는 소멸되거나 새 원소로 대체된다.

 

- operator=(list&& other) : allocator의 특성 값에 따라 other의 메모리를 통째로 가져올 수 있거나, 원소의 개별적 메모리를 하나씩 가져온다. 원래의 원소는 소멸되거나 새 원소로 대체된다.

 

- at(size_type pos) : pos 위치에 있는 원소의 reference를 반환하며 pos < size() 인지 검사한다.

 

- insert(iterator pos , const T& value) : pos 앞에 value를 삽입

 

- resize(size_type count , const T& value) : count < size() 이면 뒤에서부터 count 값에 맞게 자르고, count > size() 이면 빈 공간을 value 값으로 채운다. (단, capacity 값은 줄어들지 않는다. )

 

- merge(T& other , Compare comp) : 정렬된 두 리스트를 하나로 합쳐 오름차순 정렬된 리스트로 재구성하는 함수.

(other는 empty상태가 되고, 크기가 같은 원소에 대해서는 other의 원소가 나중에 오는 stable 한 함수)

 

- splice(iterator pos , list& other) : pos 가 가리키는 원소 앞에 other 의 원소들을 이어 붙이는 함수. 연산 후 other 의 이동한 원소들은 other에서 사라지고 iterator 무효화가 발생하지 않는다.

 

- unique(BinaryPredicate pred) : 연속되는 원소의 중복을 제거하는 함수. pred 로 중복 기준을 정할 수 있다.

 

-sort(Compare comp) : 원소를 오름차순으로 정렬하는 함수. comp 로 비교 기준을 정할 수 있다. iterator 무효화가 일어나지 않는다.