std::list
std::list (양방향 연결 리스트 컨테이너)
어디에서든 상수 시간 삽입·제거를 지원하는 시퀀스 컨테이너예요. 양방향 연결 리스트(doubly-linked list)로 구현돼요. 빠른 임의 접근은 지원하지 않아요.
출처: cppreference
본문
<list> 헤더에 정의돼 있고, 양방향 연결 리스트 컨테이너예요.
template<
class T,
class Allocator = std::allocator<T>
> class list;
C++17부터 pmr 별칭도 있어요: std::pmr::list<T> = std::list<T, std::pmr::polymorphic_allocator<T>>.
std::list는 어디에서든 상수 시간 삽입·제거를 지원하는 시퀀스 컨테이너예요. 빠른 임의 접근은 지원하지 않아요. 보통 양방향 연결 리스트로 구현돼요. std::forward_list와 비교해, list는 양방향 반복을 지원하지만 각 노드가 추가 포인터를 저장하므로 공간 오버헤드가 커요.
리스트 안에서(또는 여러 리스트에 걸쳐) 원소를 추가·제거·이동해도 현재 리스트의 다른 원소를 가리키는 반복자·참조는 무효화되지 않아요. 즉 원소를 제거할 때 그 원소를 가리키는 반복자·참조만 무효화돼요.
std::list는 Container, AllocatorAwareContainer, SequenceContainer, ReversibleContainer 요구사항을 만족해요. C++26부터 모든 멤버 함수가 constexpr이에요.
멤버 타입
value_type=T,allocator_type=Allocator,size_type(보통std::size_t),difference_type(보통std::ptrdiff_t),reference=T&,const_reference=const T&,pointer,const_pointer,iterator(양방향 반복자),const_iterator,reverse_iterator,const_reverse_iterator.
멤버 함수
- 생성자, 소멸자,
operator=,assign,assign_range(C++23),get_allocator. - 원소 접근:
front,back. - 반복자:
begin/cbegin,end/cend,rbegin/crbegin,rend/crend. - 용량:
empty,size,max_size. - 수정자:
clear,insert,insert_range(C++23),emplace,erase,push_back,emplace_back,append_range(C++23),pop_back,push_front,emplace_front,prepend_range(C++23),pop_front,resize,swap. - 연산:
merge,splice,remove/remove_if,reverse,unique,sort.
비멤버 함수
operator==,!=,<,<=,>,>=,<=>: 두 리스트 사전식 비교.std::swap(std::list):std::swap특수화.erase,erase_if(C++20): 특정 기준을 만족하는 원소 모두 제거.
C++17부터 추론 가이드가 있어요.
list는 중간 삽입·삭제가 빈번한 컨테이너에 적합해요. 삽입·제거가 상수 시간이라 어떤 위치에도 저렴하게 원소를 추가·제거할 수 있어요. 각 원소가 앞·뒤 노드를 가리키는 포인터를 저장하므로, 이전·다음 원소로 양방향 이동할 수 있어요. 임의 접근이 필요하면 std::vector를 쓰는 게 더 나아요.