[C++ STL] list 개요

※ std::list 요약

std::list는 double linked list(이중 연결 리스트)라는 자료구조를 이용하여 만든 시퀀스 컨테이너다.
템플릿 기반이므로 임의 타입을 요소로 가질 수 있으며, 요소 개수에 따라 동적으로 메모리를 관리한다.
double linked list로 되어 있기에 double linked list의 특징을 거의 그대로 가지고 있으며 linked list 자료구조에 대한 이해가 있어야 알맞는 상황에 알맞게 사용할 수 있다. 필자는 std::list를 거의 사용하지 않는다. 나뻐서 안 사용한다기 보다는 std::vector로도 충분한 상황이 대부분이기 때문이다.

 

 

 

※ std::list 특징

- 고정 길이인 배열에 비해 길이가 가변적이다.
- std::vector와 달리 데이터의 중간 삽입, 중간 삭제 속도가 빠르다.
- 데이터 중간 삽입, 삭제시 요소 개수에 상관없이 동일한 상수시간이 소요된다.(상수 시간 복잡도의 수행 성능 보장)

- list의 순회 속도는 O(n), 즉 요소 개수가 많을 수록 순회 속도는 느리다.

- 각 노드는 앞쪽, 뒤쪽 노드와 연결된 이중 연결 리스트다.(반대는 std::forward_list로써, 단일 연결 리스트다)

- 노드 기반이므로 []나 at()을 지원하지 않는다.

 

 

 

 

※ std::list를 사용해야 하는 경우

- 저장할 데이터의 개수가 가변적일때
- 저장된 요소를 자주 검색하지 않을때
- 중간에 데이터 삽입, 삭제가 자주 발생할때
- 랜덤 엑세스를 자주 안할때

 

 

분 류	멤버 함수	설 명
Iterators	begin	첫 번째 원소를 가리키는 반복자를 리턴한다.
	cbegin	첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
	end	마지막 원소를 가리키는 반복자를 리턴한다.
	cend	마지막 원소를 가리키는 상수 반복자를 리턴한다.
	rbegin	역 순차열의 첫 번째 원소를 가리키는 반복자를 리턴한다.
	crbegin	역 순차열의 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
	rend	역 순차열의 마지막 원소를 가리키는 반복자를 리턴한다.
	crend	역 순차열의 마지막 원소를 가리키는 상수 반복자를 리턴한다.
Element access	at	제공 안 함
	operator[]	제공 안 함
	front	첫 번째 원소의 참조를 리턴한다.
	back	마지막 원소의 참조를 리턴한다.
Capacity	empty	원소 존재 유무를 체크한다. 아무것도 없으면 true, 있으면 false를 리턴한다.
	size	원소의 개수를 리턴한다.
	max_size	담을 수 있는 원소의 최대 개수를 리턴한다.
	resize	list의 크기를 변경하고 default 값이나 임의 값으로 초기화한다.
	capacity	제공 안 함
	reserve	제공 안 함
	shrink_to_fit	제공 안 함
Modifiers	clear	list의 모든 원소를 제거한다.
	assign	기존 원소들은 모두 제거 후, 임의 값으로 n개의 원소를 할당한다.
	insert	임의 위치에 임의 값을 삽입한다.
	emplace	원소 삽입시 컨테이너 내부에서 생성 후 임의 위치에 임의 값을 삽입한다.
	emplace_hint	제공 안 함
	erase	임의 위치의 원소나 지정 범위의 원소를 삭제한다.
	push_front	list의 처음에 원소를 추가한다.
	emplace_front	원소 삽입시 컨테이너 내부에서 생성 후 컨테이너의 처음에 원소를 추가한다.
	pop_front	list의 처음 원소를 제거한다.
	push_back	list의 끝에 원소를 추가한다.
	emplace_back	원소 삽입시 컨테이너 내부에서 생성 후 컨테이너의 끝에 원소를 추가한다.
	pop_back	list의 마지막 원소를 제거한다.
	swap	list1.swap( list2 )일때 list1과 list2를 swap한다.
List operations	merge	list1.merge( list2 )일때 list1에 list2를 정렬하면서 병합한다.
	splice	2개의 list 중 인자로 주어지는 list의 지정된 원소들을 대상 list로 이동시킨다.
	remove	인자로 받은 값으로 받은 값과 같은 값의 원소를 모두 제거한다.
	remove_if	함수객체의 조건을 만족하는 원소를 모두 제거한다.
	reverse	list에 담긴 원소의 순서를 역순으로 바꾼다.
	unique	list에 담긴 원소 중 연속적으로 중복된 값이 배치된 원소를 제거한다.
	sort	list에 담긴 원소를 정렬한다. 예 : list.sort( std::greater<int>() )
Lookup	count	제공 안 함
	find	제공 안 함
	lower_bound	제공 안 함
	upper_bound	제공 안 함
	equal_range	제공 안 함
Observers	key_comp	제공 안 함
	value_comp	제공 안 함
	hash_function	제공 안 함
	key_eq	제공 안 함
Allocator	get_allocator	list의 allocator 객체를 반환한다.