list 컨테이너는 vector와 deque처럼 스퀀스 컨테이너로 원소가 상대적인 순서로 유지한다. 그러나 list는 노드 기반 컨테이너로 원소가 노드 단위로 저장되며 list는 이중 연결 리스트로 구현된다.
템플릿 형식
| 설명 | |
|---|---|
| template<typename T, typename Allocator = allocator> class list | T는 list 컨테이너 원소의 형식 |
인터페이스
생성자
| 생성자 | 설명 |
|---|---|
| list lt | 빈 컨테이너 |
| list lt(n) | 기본값으로 초기화된 n개의 원소를 갖는다 |
| list lt(n,x) | x값으로 초기화된 n개의 원소를 갖는다 |
| list lt(lt2) | lt2 컨테이너의 복사본이다. (복사 생성자 호출) |
| list lt(b,e) | 반복자 구간 [b,e]로 초기화된 원소를 갖는다. |
멤버 함수
| 멤버 함수 | 설명 |
|---|---|
| lt.assign(n,x) | x값으로 n개의 원소를 할당한다 |
| lt.assign(b,e) | 반복자 구간 [b, e]로 할당한다 |
| lt.back() | 마지막 원소를 참조한다 |
| p=lt.begin() | 첫 원소를 가르키는 반복자(const, 비const 버전이 있음) |
| lt.clear() | 모든 원소를 제거한다 |
| lt.empty() | 비어있는지 조사한다 |
| p=lt.end() | lt의 끝을 가르키는 반복자(const, 비const 버전이 있다) |
| q=lt.erase(p) | p가 가르키는 원소를 제거한다. q는 다음 원소를 가르킨다 |
| q=lt.erase(b,e) | 반복자 구간 [b, e]의 원소를 제거한다. q는 다음 원소 |
| lt.front() | 첫번째 원소를 참조한다(const, 비const 버전이 있다) |
| q=lt.insert(p,x) | p가 가르키는 위치에 x값을 삽입한다. q는 삽입한 원소를 가리키는 반복자다 |
| lt.insert(p,n,x) | p가 가르키는 위치에 n개의 x값을 삽입한다 |
| lt.insert(p,b,e) | p가 가르키는 위치에 반복자 구간 [b,e]의 원소를 삽입한다 |
| x=lt.max_size() | x는 lt가 담을 수 있는 최대 원소의 개수이다. (메모리 크기) |
| lt.merge(lt2) | lt2를 lt로 합병 정렬한다. (오름차순:less) |
| lt.merge(lt2,pred) | lt2를 lt로 합병 정렬한다. pred(조건자)를 기준으로 합병한다.(pred는 이항 조건자) |
| lt.pop_back() | 마지막 원소 제거 |
| lt.pop_front() | 첫 원소 제거 |
| lt.push_back(x) | 끝 위치에 x 값 추가한다 |
| lt.push_front(x) | 첫 위치에 x 값 추가한다 |
| p=lt.rbegin() | p는 lt의 역순차열의 첫 원소를 가리키는 반복자다. (const, 비 const 버전이 있음) |
| lt.remove(x) | x 원소를 모두 제거한다. |
| lt.remove_if(pred) | pred (단항 조건자)가 '참'인 모든 원소를 제거한다. |
| p=lt.rend() | p는 lt의 역 순차열의 끝을 표식하는 반복자다.(const, 비 const 버전이 있음) |
| lt.resize(n) | lt의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화한다 |
| lt.resize(n,x) | lt의 크기를 n으로 변경하고 확장되는 공간의 값을 x 값으로 초기화한다 |
| lt.reverse() | lt 순차열을 뒤집는다. |
| lt.size() | lt 원소의 개수 |
| lt.sort() | lt의 모든 원소를 오름차 순(less)으로 정렬한다 |
| lt.sort(pred) | lt의 모든 원소를 pred(조건자)를 기준으로 정렬한다. pred는 이항 조건자 |
| lt.splice(p,lt2) | p가 가르키는 위치에 lt2의 모든 원소를 잘라 붙인다 |
| lt.splice(p,lt2,q) | p가 가르키는 위치에 lt2의 q가 가리키는 원소를 잘라 붙인다 |
| lt.splice(p,lt2,b,e) | p가 가르키는 위치에 lt2의 순차열 [b, e]을 잘라 붙인다 |
| lt.swap(lt2) | lt1와 lt2를 swap한다 |
| lt.unique() | 인접한 원소의 값이 같다면 유일한 원소의 순차열로 만든다 |
| lt.unique(pred) | 인접한 원소가 pred(이항 조건자)의 기준에 맞다면 유일한 원소의 순차열로 만든다 |
연산자
| 설명 | |
|---|---|
| lt1==lt2 | lt1과 lt2의 모든 원소가 같은가? (bool 형식) |
| lt1!=lt2 | lt1과 lt2의 모든 원소 중 하나라도 다른 원소가 있는가? (bool 형식) |
| lt1<lt2 | 원소를 하나씩 순서대로 비교하여 lt2가 lt1보다 큰가? (bool 형식) |
| lt1<=lt2 | lt2가 lt1보다 크거나 같은가? (bool 형식) |
| lt[i] | lt의 i번째 원소를 참조한다 |
템플릿 멤버 형식
| 설명 | |
|---|---|
| allocator_type | 메모리 관리자 형식 |
| const_itorator | const 반복자 형식 |
| const_pointer | const value_type* 형식 |
| const_reference | const value_type& 형식 |
| const_reverse_iterator | const 역 반복자 형식 |
| difference_type | 두 반복자 차이의 형식 |
| iterator | 반복자 형식 |
| pointer | value_type* 형식 |
| reference | value_type& 형식 |
| reverse_iterator | 역반복자 형식 |
| size_type | 첨자[index]나 원소의 개수 등의 형식 |
| value_type | 원소의 형식 |
설명
list는 스퀀스 컨테이너이므로 원소의 저장 위치(순서)가 정해지며 노드 기반 컨테이너이므로 원소가 각각의 노드에 저장된다. 각 노드는 앞, 뒤 쪽 노드와 연결된 형태로 이중 연결 리스트이다.
list는 스퀀스 컨테이너로 스퀀스 컨테이너가 갖는 모든 특징을 갖는다. 컨테이너 앞, 뒤 쪽에 차례로 원소를 추가&제거할 수 잇으며, 첫, 마지막 원소를 front(), back()으로 참조할 수 있다. 또한 지정한 위치에 원소를 삽입 & 제거하는 insert(), erase()를 갖는다
list는 노드 기반 컨테이너로 at()과 [] 연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자를 제공한다. 그래서 모든 원소를 탐색하려면 양방향 반복자의 연산인 ++,--를 사용한다
list의 가장 큰 특징 중 하나는 순차열 중간에 원소를 삽입, 제거하더라도 상수 시간 복잡도의 수행 성능을 보인다. 배열 기반 컨테이너 vector & deque처럼 원소를 밀어내지 않고 노드를 서로 연결하기만 하면 되기 때문이다.
또한 노드 기반 컨테이너의 삽입과 제거 동작은 반복자를 무효화시키지 않는다. 반복자가 가리키는 원소 자체가 제거되지 않는 한 반복자가 가르키는 원소는 그대로 존재한다. 하지만 배열 기반 컨테이너의 반복자는 삽입 및 제거 동작이 발생하면 메모리가 재할당되거나 원소의 이동할 수 있으므로 반복자가 무효화된다.
list는 스퀀스 컨테이너이며 노드 기반 컨테이너입니다. 그래서 순차열 중간에 삽입, 제거가 빈번하게 발생하며 원소의 상대적인 순서가 중요하다면 list 컨테이너를 사용해야 한다.
