[자료구조] std::forward_list

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

std::forward_list

개요

　앞서 포스팅한 std::vector, std::array같은 연속된 자료 구조에서는 데이터를 임의로 추가하거나 삭제하는 작업이 매우 비효율적이다. vector 자료 구조에서 insert() 함수와 erase() 함수를 예로 들어보자. insert() 함수를 통해 데이터를 삽입하려 하면 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요하고, erase() 함수도 특정 위치의 원소를 삭제한 후, 뒤쪽의 원소들을 모두 앞으로 이동해야 한다. 따라서 연결 리스트와 같은 연결된 자료 구조가 필요한 것이다.

　

　기본적인 연결 리스트를 구성하기 위해서는 포인터가 필요하고, new와 delete 연산자를 이용하여 메모리를 할당하고 해제할 수 있어야 한다. C++에서는 기본적인 연결 리스트의 성능을 유지하며 추가적인 기능을 제공하는 std::forward_list를 제공한다. 이때 성능 유지(메모리 혹은 속도의 측면에서)를 위해 원소에 직접 접근하는 기능은 아주 제한적으로 제공된다. 만약 기본적인 연결 리스트를 구현한 코드를 보고 싶으면 여기서 확인하면 된다.

 

c++ reference에서의 forward_list 정의. 출처: https://en.cppreference.com/w/cpp/container/forward_list

---

원소 삽입, 삭제

　기본적으로 std::forward_list를 사용하기 위해선, <forward_list> 라이브러리를 받아와야 한다. forward_list에서 제공하는 원소 삽입, 삭제 함수는 맨 앞의 head를 기준으로 삽입하거나 삭제한다(FIFO 구조).

 

출처: https://en.cppreference.com/w/cpp/container/forward_list

 

　원소 삽입/삭제는 노드의 포인터 조작으로 구현되므로, std::vector와 다르게 삽입 후 다른 원소를 이동할 필요가 없어 시간 복잡도가 O(1)로 매우 빠르다. 이를 좀 더 쉽게 이해하기 위해 음악 플레이 리스트 예제를 작성해보자. 

 

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

int main()
{
	forward_list<string> playList;

　기본적인 라이브러리를 받아오고, 음악들의 제목은 문자열이므로 string 타입으로 forward_list를 선언해준다.

 

	for (int i = 0; i < 5; i++)
	{
		string music;
		cin >> music;
		playList.push_front(music);
	}

　5개의 음악 목록을 push_front() 함수를 이용해 사용자가 입력해 플레이 리스트에 넣는다.

 

	for (string& str : playList)
		cout << str << ' ';

　현재 재생 목록을 출력하고 결과를 확인해보자.

 

aa, bb, cc, dd, ee, ff를 입력했을 때 출력

 

	cout << '\n' << "Input the name of music for removing: ";
	string name;
	cin >> name;
	
	playList.remove(name);

	for (string& str : playList)
		cout << str << ' ';

　주어진 재생 목록에서 'cc'라는 제목의 노래를 remove() 함수를 이용해 제거하고 출력을 확인해보자.

 

재생 목록에서 cc가 제거되었음.

 

	cout << "Enter the number and title of the number you want to add to the playlist in the following format(num title): ";
	int index;
	string title;
	auto it = playList.begin();
	cin >> index >> title;

	for (int i = 0; i < index; i++)
		it++;

	playList.insert_after(it, title);

	for (string& str : playList)
		cout << str << ' ';

　이번에는 특정 위치에 노래를 추가해보자. 정수와 제목을 입력 받아서, 정수만큼 반복자를 옮겨주고 그 다음 위치에 추가할 제목을 입력받아 insert_after() 함수를 이용해 추가하면 된다.

 

결과

 

총합본

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

int main()
{
	forward_list<string> playList;

	for (int i = 0; i < 5; i++)
	{
		string music;
		cin >> music;
		playList.push_front(music);
	}

	for (string& str : playList)
		cout << str << ' ';

	cout << '\n' << "Input the name of music for removing: ";
	string name;
	cin >> name;
	
	playList.remove(name);

	for (string& str : playList)
		cout << str << ' ';
	cout << '\n';

	cout << "Enter the number and title of the number you want to add to the playlist in the following format(num title): ";
	int index;
	string title;
	auto it = playList.begin();
	cin >> index >> title;

	for (int i = 0; i < index; i++)
		it++;

	playList.insert_after(it, title);

	for (string& str : playList)
		cout << str << ' ';
}

---

한계

　지금까지 간단한 연결 리스트인 std::forward_list를 알아보았다. 개요에서 언급했지만, forward_list는 아주 기본적인 형태로 구현되어 있어 그 용도가 한정적이다. 따라서 다다음 포스팅에서 std::list를 통해 연결 리스트에 대해 더욱 심도깊게 알아보도록 하자.

---

요약

std::forward_list
1. 정의: 기본적인 단방향 리스트 기능을 제공하는 컨테이너
2. 특징
　- 리스트의 기본적인 기능들이 구현되어 있음
3. 한계
　- 기본적인 기능만 구현되어 있어 용도가 한정적임