std::forward_list
std::forward_list (단일 연결 리스트 컨테이너)
컨테이너의 어디에서든 빠른 삽입·제거를 지원하는 컨테이너예요. 빠른 임의 접근은 지원하지 않아요. 단일 연결 리스트(singly-linked list)로 구현돼요. C++11부터 있어요.
출처: cppreference
본문
<forward_list> 헤더에 정의돼 있고, 단일 연결 리스트 컨테이너예요.
template<
class T,
class Allocator = std::allocator<T>
> class forward_list;
C++17부터 pmr 별칭도 있어요: std::pmr::forward_list<T> = std::forward_list<T, std::pmr::polymorphic_allocator<T>>.
std::forward_list는 컨테이너의 어디에서든 빠른 삽입·제거를 지원하는 컨테이너예요. 빠른 임의 접근은 지원하지 않아요. 단일 연결 리스트로 구현돼요. std::list와 비교해 이 컨테이너는 양방향 순회가 필요 없을 때 더 공간 효율적인 저장을 제공해요.
리스트 안에서(또는 여러 리스트에 걸쳐) 원소를 추가·제거·이동해도 현재 리스트의 다른 원소를 가리키는 반복자는 무효화되지 않아요. 다만 해당 원소가 리스트에서 제거되면(erase_after를 통해) 그 원소를 가리키는 반복자나 참조는 무효화돼요.
std::forward_list는 Container(다만 size 멤버 함수가 없고 operator==의 복잡도가 항상 선형), AllocatorAwareContainer, SequenceContainer 요구사항을 만족해요. C++26부터 모든 멤버 함수가 constexpr이에요. 단 constexpr std::forward_list 변수를 정의하는 건 일반적으로 오류인데, 상수 평가는 동적 할당 저장소를 같은 평가에서 해제해야 하기 때문이에요.
템플릿 매개변수
T: 원소 타입. (C++17부터) 일반적으로Erasable요구사항을 만족해야 하고, 할당자가 할당자 완전성 요구사항을 만족하면 이 컨테이너(멤버는 아님)는 불완전 원소 타입으로도 인스턴스화할 수 있어요.Allocator: 메모리 획득·해제 및 원소 생성·파괴에 쓰는 할당자.Allocator::value_type이T와 다르면 (C++20부터) 프로그램은 ill-formed예요.
멤버 타입
value_type=T,allocator_type=Allocator,size_type(보통std::size_t),difference_type(보통std::ptrdiff_t),reference=T&,const_reference=const T&,pointer=std::allocator_traits<Allocator>::pointer,const_pointer,iterator=LegacyForwardIterator(및 C++26부터 ConstexprIterator),const_iterator.
멤버 함수
- 생성자, 소멸자,
operator=,assign,assign_range(C++23),get_allocator. - 원소 접근:
front. - 반복자:
before_begin/cbefore_begin(시작 앞 원소),begin/cbegin,end/cend. - 용량:
empty,max_size. - 수정자:
clear,insert_after,emplace_after,insert_range_after(C++23),erase_after,push_front,emplace_front,prepend_range(C++23),pop_front,resize,swap. - 연산:
merge(두 정렬 리스트 병합),splice_after,remove/remove_if,reverse,unique(연속 중복 제거),sort.
비멤버 함수
operator==,!=,<,<=,>,>=,<=>: 두 리스트 사전식 비교.std::swap(std::forward_list)(C++11):std::swap특수화.erase,erase_if(C++20): 특정 기준을 만족하는 원소 모두 제거.
C++17부터 추론 가이드가 있어요. 피처 테스트 매크로 __cpp_lib_incomplete_container_elements(C++17), __cpp_lib_containers_ranges(C++23), __cpp_lib_constexpr_forward_list(C++26)가 있어요.
forward_list는 std::list와 달리 before_begin() 반복자를 제공해 첫 원소 앞에 삽입할 수 있어요. 단일 연결 구조라 노드당 저장 비용이 더 적고, 양방향 순회가 필요 없는 시나리오(예: head 삽입이 많은 스택류 용도)에서 유용해요.