[C++] std::forward_list, std::list

이전 포스팅에서 살펴본 std::array, std::vector의 경우 담겨져 있는 임의 데이터를 확인하기엔 좋지만 데이터의 추가/삭제가 잦은 경우에는 비효율적이라고 소개한적 있습니다.

[C++] std::array, std::vector

데이터의 추가 삭제가 많은 경우에는 연결리스트를 사용하는게 더욱 효율적일 수 있지만 사용자가 임의로 연결리스트를 구현하기 위해서 노드를 구현하고 그를 위해 동적할당을 한다면 memory leak이 발생할 가능성이 큽니다. 이럴 때 사용할 수 있게 std::array와 마찬가지로 std::forward_list를 제공합니다.

 

std::forward_list는 기본적인 연결리스트 기능을 갖추고 있고 추가 기능을 제공합니다. std::forward_list에서 데이터를 삽입하기 위해서는 push_front()와 insert_after()를 사용합니다. push_front 함수는 연결리스트 가장 앞에 데이터를 삽입하고 insert_after 함수는 반복자를 이용해서 원하는 위치 뒤로 데이터를 삽입합니다.

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

void printFwdlist(std::forward_list<int>& list) {
	for ( int i : list ) {
		cout << i << ' ';
	} cout << endl;
}

int main(int argc, char* argv[]) 
{
	std::forward_list<int> fwd_list = {1,2,3};
	
	fwd_list.push_front(0);
	printFwdlist(fwd_list);
	
	auto it = fwd_list.begin();
	
	fwd_list.insert_after(it, 5);
	fwd_list.insert_after(++it, 7);
	
	printFwdlist(fwd_list);
}

삭제의 경우에는 pop_front()와 erase_after()를 사용합니다. 삽입과 마찬가지로 각각 첫번째, 그리고 해당 위치 다음 데이터를 조작합니다. erase_after의 경우에는 두가지 형태가 제공되는데 그냥 반복자만 넘겨 해당 위치 다음의 데이터를 제거하는 것과 위치값을 2개를 넘겨 해당 범위의 데이터를 모두 삭제시키는 형태가 있습니다.

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

void printFwdlist(std::forward_list<int>& list) {
	for ( int i : list ) {
		cout << i << ' ';
	} cout << endl;
}

int main(int argc, char* argv[]) 
{
	std::forward_list<int> fwd_list = {1,2,3,4,5,6,7,8};
	
	fwd_list.pop_front();
	printFwdlist(fwd_list);
	
	auto it = fwd_list.begin();
	
	fwd_list.erase_after(it);
	printFwdlist(fwd_list);
	
	fwd_list.erase_after(it, fwd_list.end());
	printFwdlist(fwd_list);
}

위 함수 외에도 remove, remove_if 함수가 제공되는데 remove 함수는 매개변수 값이 std::forward_list 내에 존재할 경우 지워주게 되고 remove_if 함수는 람다함수를 매개변수로 넘겨 사용하며 함수 몸체에 등호 연산을 통해 해당 데이터를 지우게 됩니다.

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

void printFwdlist(std::forward_list<int>& list) {
	for ( int i : list ) {
		cout << i << ' ';
	} cout << endl;
}

int main(int argc, char* argv[]) 
{
	std::forward_list<int> fwd_list = {1,2,3,4,5,6,7,8};
	
	fwd_list.remove(1);
	printFwdlist(fwd_list);
	
	fwd_list.remove_if([](int n) { return n > 4; });
	printFwdlist(fwd_list);
}

이 외에도 정렬을 위한 sort 함수, 역순으로 뒤집는 reverse 함수, 인접하는 중복 데이터를 제거하는 unique 함수 등이 있습니다.

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

void printFwdlist(std::forward_list<int>& list) {
	for ( int i : list ) {
		cout << i << ' ';
	} cout << endl;
}

int main(int argc, char* argv[]) 
{
	std::forward_list<int> fwd_list = {4,1,3,2,5,9,7,8};
	printFwdlist(fwd_list);
	
	fwd_list.sort();						// 오름차순 정렬
	printFwdlist(fwd_list);
	
	fwd_list.sort(std::greater<int>());		// 내림차순 정렬
	printFwdlist(fwd_list);
	
	fwd_list.reverse();
	printFwdlist(fwd_list);
	
	std::forward_list<int> fwd_list2 = {1,1,2,3,3,4,5,4};
	fwd_list2.unique();
	printFwdlist(fwd_list2);
}

std::forward_list - cppreference.com

std::foward_list에 존재하지 않는 기능이 추가된 연결 리스트가 std::list 입니다. std::list의 경우 이중연결리스트로 구현되어 있습니다. std::list에서는 임의의 위치에 데이터를 삽입/삭제할 때 _after가 빠진 함수 insert(), erase()를 사용하며 std::forward_list에서는 제공하지 않는 push_back(), pop_back()도 제공합니다.

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

void printList(std::list<int>& list) {
	for ( int i : list ) {
		cout << i << ' ';
	} cout << endl;
}

int main(int argc, char* argv[]) 
{
	std::list<int> list = {1,2,3};
	list.push_back(4);
	
	printList(list);
	
	list.insert(list.begin(), 0);
	printList(list);
	
	list.insert(list.end(), 5);
	printList(list);
	
	list.push_back(6);
	list.pop_front();
	list.pop_back();
	
	printList(list);
}

std::list - cppreference.com