forward_list
forward_list (std::forward_list — 단일 연결 리스트)
std::forward_list는 원소를 언제 어디서나 일정한 시간에 삽입·제거할 수 있는 컨테이너예요. 단일 연결 리스트(singly linked list)로 구현돼 있어요. std::list(이중 연결)와 달리 뒤로 순회할 수 없고 역방향 이터레이터가 없어요.
출처: cppreference
본문
std::forward_list는 Container, AllocatorAwareContainer, SequenceContainer의 요구 사항을 만족하고, ReversibleContainer 요구 사항은 만족하지 않아요.
std::forward_list의 주요 특징은 다음과 같아요.
- 단일 연결 리스트로, 앞쪽에서만 일정한 시간에 삽입·제거가 가능해요.
push_front,pop_front가 상수 시간이에요. size()멤버가 없어요. 대신std::distance(begin(), end())로 크기를 구해야 해요.- 뒤로 돌아갈 수 있는 이터레이터가 없어요.
insert_after,erase_after처럼 "특정 위치 뒤"를 기준으로 연산해요. - 메모리 효율이
std::list보다 좋고,std::deque·std::vector보다도 어떤 경우엔 나아요. - 노드 기반이라 이터레이터 무효화가 제한적이에요. 삽입·제거가 해당 원소의 이터레이터에만 영향을 줘요.
템플릿 매개변수
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— 전방 이터레이터를 만족
멤버 함수
- 생성자/파괴자,
operator=,assign,assign_range,get_allocator - 원소 접근:
front - 이터레이터:
before_begin,begin,end - 용량:
empty,max_size - 수정자:
clear,insert_after,insert_range_after,emplace_after,erase_after,push_front,emplace_front,prepend_range,pop_front,resize,swap,merge,splice_after,remove,remove_if,reverse,unique,sort - 비멤버 함수:
operator==,operator<=>(C++20),std::erase,std::erase_if,std::swap, 그리고std::ranges::알고리즘
비멤버 함수
operator==,operator<=>: 사전식 비교std::erase,std::erase_if: 값/술어 기준 일괄 제거std::swap: 내용 교환(특수화)