[STL] 04. std::forward_list

std::forward_list는 C++ 표준 라이브러리(STL)에서 제공하는 가변 크기의 단순 연결 리스트 컨테이너다.

C++ 11 표준부터 사용할 수 있고 <forward_list> 헤더에 정의되어 있다.

 

 

특징

 

1. 단일 연결 리스트 : std::list와는 다르게 다음 요소를 가리키는 포인터만 가지며, 이전 요소를 가리키는 포인터는 없다.

이에 따라 std::list보다 메모리 사용량이 적다.

 

2. 데이터 삽입 및 삭제 효율성 : 데이터 삽입 및 삭제 작업이 매우 효율적이다.

이전 요소를 찾아가는 작업이 없기 때문에 std::list보다 일반적으로 더 빠르다.

 

3. 검색 시간복잡도 : 요소를 검색할 때 O(n) 시간 복잡도를 가진다. std::list와 마찬가지로 검색이 비효율적이다.

 

데이터의 삽입 및 삭제가 빈번한 상황에서 std::list보다 효율적일 수 있지만

데이터 검색이 주요 작업이라면 std::list와 동일하게 비효율적이기에 다른 컨테이너를 고려해야 하며

std::forward_list는 begin() 함수로 (순방향) 반복자를 얻을 수 있고, 오직 ++연산만 사용할 수 있다.

 

 

사용법

 

#include <iostream>
#include <forward_list>

int main() {

	std::forward_list<int> l1 { 10, 20, 30, 40 };

	l1.push_front(40); // 40, 10, 20, 30, 40
	l1.push_front(30); // 30, 40, 10, 20, 30, 40

	int cnt = distance(l1.begin(), l1.end()); // 6

	l1.remove(40); // 30, 10, 20, 30

	l1.remove_if([](int n) { return n > 20; }); // 10, 20

	for (const auto& a : l1) {

		std::cout << a << ", ";
	}

	std::cout << std::endl;
}

 

 

단일 연결 리스트의 주요 멤버 함수의 기능과 리스트와의 비교

 

std::list	std::forward_list	설명
front(), back()	front()	forward_list는 front() 함수만 제공
begin(), end()	before_begin(), begin(), end()	forward_list는 before_begin() 함수를 추가로 제공하고, 순방향 반복자만 얻을 수 있음
insert(), emplace(), erase()	insert_after(), emplace_after(), erase_after()	forward_list는 특정 위치 다음에 원소를 삽입하거나 삭제하는 함수를 제공
push_front(), push_back(), emplace_front(), emplace_back(), pop_front(), pop_back()	push_front(), emplace_front(), pop_front()	forward_list는 연결 리스트 맨 앞에서만 원소를 삽입 하거나 삭제할 수 있음
size()	N/A	forward_list는 std::distance()함수를 활용해 원소의 개수를 알 수 있음