📌 std::forward_list
: 연결 리스트와 같은 형태의 자료 구조
: 기본적인 연결 리스트에 대한 래퍼 클래스 (C++이 제공)
: C++에서 제공하는 연결 리스트 관련 컨테이너
✔️ 기본적인 연결 리스트를 구성하려면 포인터를 하나 가지고 있어야 하고, new와 delete 연산자를 이용하여 메모리를 할당하고 해제할 수 있어야 한다.
-> 이러한 기능을 구현하는 것이 그리 어렵지는 않지만 자칫 잘못하면 찾기 어려운 버그를 양산할 수 있다.
✔️ 많은 응용 프로그램에서는 자료 구조 중간에 삽입 또는 삭제 작업을 필요로 한다.
Ex) 탭을 지원하는 브라우저 : 언제든 새로운 탭을 임의의 위치에 옮길 수 있어야 한다.
음악 플레이어 : 재생 목록 중간에 새로운 노래를 추가할 수 있어야 한다.
-> 빠른 동작을 위해 연결 리스트를 사용할 수 있다.
(음악 플레이어를 만드는 '실습 문제 1: 음악 재생 목록 구현하기'에서 연결 리스트의 사용 예를 확인할 수 있다.)
1. 추가적인 기능 제공
-
기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능을 제공한다.
-
성능 유지를 위해
std::forward_list는 전체 리스트의 크기를 반환하거나 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않는다.
-> 맨 처음 원소에 접근하는front()함수 제공
-> 반대 방향의 원소로 이동하는back()같은 함수 제공 X -
원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능을 제공한다.
-> 기본적인 연결 리스트의 메모리 사용량이나 성능에 영향을 주지 않는다. -
std::vector와 마찬가지로 두 번째 템플릿 매개변수에 사용자 지정 할당자를 지정할 수 있다.
-> 맞춤형 메모리 관리가 필요한 고급 응용 프로그램에서도std::forward_list를 사용할 수 있다.
2. 원소 삽입/ 삭제
- 원소 삽입
-
push_front() 함수
-> 연결 리스트 맨 앞에 새로운 원소를 삽입
->std::forward_list는 마지막 원소에 직접 접근할 수 없으므로push_back()함수 제공 X -
insert_after() 함수
-> 특정 위치에 원소를 삽입시 사용
-> 연결 리스트에서 새로운 원소를 삽입한 후, 해당 위치 앞에 있는 원소의 next 포인터를 수정해야 하기 때문에insert()사용 X
📌 백준 문제 풀이
