초보자를 위한 C++ STL forward_list 정리

1)forward_list 사용 이유

앞서 살펴본 STL array, vector같은 연속된 자료 구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이  비효율적입니다. 따라서 C++는 자료 추가, 삭제 작업을 효율적으로 할 수 있는 연결 리스트의 기본 형태인
forward_list 클래스를 제공합니다

---

2)forward_list 사용 방법

forward_list는 전체 리스트 크기를 반환하거나 또는 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는
기능은 제공하지 않습니다. 즉, front() 함수는 있지만 back() 함수는 없습니다.

 

2-1.forward_list 초기화

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
	//크기가 0인 forward_list 선언
	forward_list<int> list0;

	//지정된 초깃값으로 이루어진 크기가 5인 forward_list 
	forward_list<int> list1 = { 1,2,3,4,5 };

	//크기가 7인 forward_list
	forward_list<int> list2(7);

	//크기가 10이고, 모든 원소가 5로 초기화된 forward_list선언
	forward_list<int> list3(10, 5);
}

forward_list는 vector처럼 원소 크기를 지정하지 않거나 사이즈를 정해 자신이 원하는 원소로
초기화 할 수 있습니다.

push_front()	연결 리스트 맨 앞에 새로운 원소를 삽입합니다.
insert_after()	특정 위치 원소 뒤에 새로운 원소를 삽입합니다.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
	forward_list<int> fwd_list = { 1,2,3 };

	fwd_list.push_front(0); // 맨 앞에 0 추가:{0, 1, 2, 3}

	forward_list<int>::iterator it = fwd_list.begin();

	fwd_list.insert_after(it, 5); // 맨 처음 원소 뒤에 5 추가: {0, 5, 1, 2, 3}

	fwd_list.insert_after(++it, 7); // 두 번째 원소 뒤에 7 추가: {0, 5, 7, 1, 2, 3}
}

forward_list는 마지막 원소에 직접 접근할 수 없으므로 push_back() 함수를 제공하지 않습니다.
따라서 push_front()를 이용해 맨 앞에 새로운 원소를 삽입합니다. 또한 insert()가 아닌 insert_after()를
사용하는데 이는 연결 리스트에서 새로운 원소를 삽입한 후, 해당 위치 앞에 있는 원소의 next 포인터를
수정해야 하기 때문입니다. forward_list는 반대 방향으로 이동하는 것이 허용되지 않기 때문에 특정 원소
뒤에 새로운 원소를 삽입한 후, 해당 원소의 next 포인터를 수정하는 것이 타당합니다.

​

연결 리스트에서 원소 삽입은 노트의 포인터 조작으로 구현되기 때문에 삽입 후 다른 원소를 이동시킬
필요가 없기 때문에 리스트의 원소 크기에 영향을 받지 않으며, 시간 복잡도 O(1)입니다. 또한 vector처럼
forward_list도 emplace() 함수와 유사한 emplace_front() 와 emplace_after() 함수를 제공합니다.

[만약 emplace() 함수에 대하여 잘 모른다면 https://khjtoy.tistory.com/14를 참고하세요.]

 

2-3.forward_list에서 원소 삭제

pop_front()	리스트의 맨 처음 원소를 제거합니다.
erase_after()	1.특정 원소를 가리키는 반복자를 인자로 받아서 바로 다음 위치의 원소를 삭제합니다. 2.삭제할 범위의 시작 원소 앞으로 가리키는 반복자와 삭제할 범위 끝 원소를 가리키는 반복자를 인자로 받아 그 범위를 삭제합니다.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
	forward_list<int> fwd_list = { 1,2,3,4,5 };

	fwd_list.pop_front(); //맨 앞 원소를 삭제:{2, 3, 4, 5}

	forward_list<int>::iterator it = fwd_list.begin();

	fwd_list.erase_after(it); //맨 앞의 다음 원소를 삭제:{2, 4, 5}

	fwd_list.erase_after(it, fwd_list.end()); 
	//맨 앞 원소 다음부터 맨 마지막 원소까지 삭제:{2}
}

pop_front() 함수는 원소 이동이 필요하지 않기 때문에 매우 빠르게 동작하며 시간 복잡도는 O(1)입니다.
erase_after()는 삭제할 원소 개수의 선형 함수 형태에 따라 시간 복잡도가 달라집니다. 이는 연결 리스트에서
각각의 노드는 전체 메모리의 임의 위치에 산재되어 있으며, 각각의 노드에 사용된 메모리를 개별적으로
해제해야 하기 때문입니다.

 

2-4.forward_list 원소 접근

forward_list는 원소를 차례대로 접근하기 위해서는 반복자(iterator)를 이용하여 원소에 차례대로 접근
할 수 있습니다.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
	forward_list<int> fwd_list = { 1,2,3,4,5 };

	for (forward_list<int>::iterator it = fwd_list.begin(); it != fwd_list.end(); it++) {
		cout << *it << " ";
	}
}

forward_list는 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않기 때문에 for문에​​

반복자를 이용하여 차례대로 원소를 접근할 수 있습니다.

 

2-5.forward_list 원소 값을 검색하여 삭제

remove()	저장된 데이터 타입에 정의된 등호 연산자를 사용하여 전달된 값을 일치하는 모든 원소를 찾아 삭제합니다.
remove_if()	데이터 원소 값 하나를 인자로 받아 bool 값을 반환하는 조건자 함수를 인자로 받은 후, 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제합니다.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
	forward_list<int> fwd_list = { 10,20,30,40,50,10,20,30,40,50 };

	fwd_list.remove(10); 
	//10인 원소를 삭제:{20, 30, 40, 50, 20, 30, 40, 50}

	fwd_list.remove_if([](const int& c) {
		return (c <= 30);
		});
	//30보다 작거나 같은 원소를 삭제:{40, 50, 40, 50}

	for (auto i = fwd_list.begin(); i != fwd_list.end(); i++) {
		cout << *i << " ";
	}
}

remove() 함수는 등호 연산을 사용하기 때문에 데이터 타입이 등호 연산이 지원되지 않으며, 이 경우
컴파일러는 에러를 발생시킵니다. 따라서 remove()함수는 조건에 근거하여 삭제 여부를 결정할 수는
없습니다. 이때 remove_if() 함수를 이용하여 삭제할 수 있습니다. remove_if()는 조건자 자리에
람다 표현식을 사용하면 쉽게 사용 할 수 있습니다.

2-6.forward_list 순서 뒤집기, 정렬, 중복 제거

reverse()	원소의 순서를 역순으로 변경합니다.
sort()	원소의 순서를 정렬하여 변경합니다.
unique()	리스트에서 홀로 나타나는 원소는 놔두고, 인접하여 중복되는 원소에 대해서는 첫 번째만 남겨두고 나머지는 제거합니다.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
	forward_list<int> list1 = { 1,2,3,4,5 };
	list1.reverse();
	cout << "list1:";
	for (forward_list<int>::iterator it = list1.begin(); it != list1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	forward_list<int> list2 = { 4,7,3,2,1,4,7,3,2,1 };
	list2.sort(); //오름차순
	cout << "list2:";
	for (forward_list<int>::iterator it = list2.begin(); it != list2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	forward_list<int> list3 = list2; //깊은 복사
	list3.sort(greater<int>()); //내림차순
	cout << "list3:";
	for (forward_list<int>::iterator it = list3.begin(); it != list3.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	list3.unique();
	cout << "중복제거:";
	for (forward_list<int>::iterator it = list3.begin(); it != list3.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

list1:5 4 3 2 1
list2:1 1 2 2 3 3 4 4 7 7
list3:7 7 4 4 3 3 2 2 1 1
중복제거:7 4 3 2 1

reverse()함수의 걸리는 시간은 리스트 원소 개수에 비례하여 시간 복잡도는 O(n)입니다.
forward_list는 또한 원소 데이터를 정렬하는 sort() 멤버 함수를 제공합니다.
이 함수는 array, vector를 정렬 할 수 있는 std::sort(first_iterator,last_iterator) 함수와 다르며
반복자도 다릅니다. 원소를 중복제거하기 위해서는 리스트를 정렬한 후, unique()함수를 사용하면 됩니다.

---

위 블로그의 내용은 코딩 테스트를 위한 자료 구조와 알고리즘 with C++를 참고하여 작성하였습니다.

https://product.kyobobook.co.kr/detail/S000001834528

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ | 존 캐리 - 교보문고