list
list (std::list — 이중 연결 리스트)
std::list는 상수 시간에 어디서든 원소를 삽입·제거할 수 있는 컨테이너예요. 이중 연결 리스트(doubly linked list)로 구현돼 있어요.
출처: cppreference
본문
std::list는 Container, AllocatorAwareContainer, SequenceContainer, ReversibleContainer의 요구 사항을 만족해요.
std::list의 주요 특징은 다음과 같아요.
- 이중 연결 리스트로, 앞쪽과 뒤쪽 모두에서 상수 시간에 삽입·제거가 가능해요.
push_front,push_back,pop_front,pop_back이 모두 상수 시간이에요. insert,erase가 특정 원소를 가리키는 이터레이터가 있으면 상수 시간이에요. 단, 임의 위치를 찾으려면 선형 탐색이 필요해요.- 이터레이터 무효화가 제한적이에요. 삽입·제거는 해당 원소의 이터레이터에만 영향을 줘요. 단
unique()·remove()·merge()·sort()는 관련 참조를 무효화하지 않아요. - 빠른 임의 접근(
operator[],at)은 지원하지 않아요. - std::forward_list와 비교하면 양방향 순회가 필요할 때 유리해요. 메모리 효율은 forward_list가 더 좋아요.
템플릿 매개변수
T: 저장된 원소의 타입. T가 CopyInsertable을 만족해야 해요.Allocator: 메모리 획득/해제를 관리하는 할당자. 기본값은std::allocator<T>예요.
멤버 타입
value_type=Tallocator_type=Allocatorsize_type= 할당자 관련 부호 없는 정수 타입difference_type= 할당자 관련 부호 있는 정수 타입reference=value_type&,const_reference=const value_type&pointer=std::allocator_traits<Allocator>::pointeriterator,const_iterator— 양방향 이터레이터를 만족reverse_iterator,const_reverse_iterator
멤버 함수
- 생성자/파괴자,
operator=,assign,assign_range,get_allocator - 원소 접근:
front,back - 이터레이터:
begin,end,rbegin,rend - 용량:
empty,size,max_size - 수정자:
clear,insert,insert_range,emplace,emplace_front,emplace_back,push_front,prepend_range,pop_front,push_back,append_range,pop_back,resize,swap,merge,splice,remove,remove_if,reverse,unique,sort - 비멤버 함수:
operator==,operator<=>(C++20),std::erase,std::erase_if,std::swap
비멤버 함수
operator==,operator<=>: 사전식 비교std::erase,std::erase_if: 값/술어 기준 일괄 제거std::swap: 내용 교환(특수화)