[c++] forward_list container(std::forward_list)

배열이나 벡터 같은 연속된 자료 구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적이다. 그래서 연결 리스트와 같은 형태의 자료 구조를 사용한다.

기본적인 연결 리스트를 구성하려면 포인터를 하나 가지고 있어야 하고, new와 delete 연산자를 이용해 메모리를 할당하고 해제할 수 있어야 한다. c++에서는 배열에 대한 래퍼 클래스 std::array를 제공하듯이 연결리스트에 대한 래퍼 클래스인 std::forward_list 클래스를 제공한다.

 

std::forward_list

std::forward_list는 기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능을 제공한다. 성능 유지를 위해 std::forward_list는 전체 리스트의 크기를 반환하거나 또는 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않는다. 즉, 맨 처음 원소에 접근하는 front() 함수는 제공하지만, 반대 방향의 원소로 이동하는 back()과 같은 함수는 제공하지 않는다는 말이다. 원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 제공한다. 이러한 기능은 기본적인 연결 리스트의 메모리 사용량이나 성능에 영향을 주지 않는다.

 

 

forward_list에서 원소 삽입

forward_list에서 원소를 삽입할 때는 push_front()와 insert_after() 함수를 사용한다. 이 두 함수는 std::vector에서 원소를 삽입할 때와 조금 다르게 동작한다.push_front() 함수는 연결 리스트 맨 앞에 새로운 원소를 삽입한다. forward_list는 앞서 말했듯이 마지막 원소에 직접 접근할 수 없으므로 push_back() 함수를 제공하지 않기 때문이다. 특정 위치에 원소를 삽입하려면 insert() 함수가 아닌 insert_after() 함수를 사용해야 한다. 연결리스트에서 새로운 원소를 삽입한 후, 해당 위치 앞에 있는 원소의 next 포인터를 수정해야 하기 때문이다.

연결 리스트에서 원소 삽입은 노드의 포인터 조작으로 구현된다. 그렇기 때문에 삽입 후 다른 원소를 이동할 필요가 없다. 이러한 std::forward_list의 삽입 함수는 모두 배열 기반 구조에서의 삽입 함수에 비해 매우 빠르게 동작한다.

#include<iostream>
#include<forward_list>

int main() {
	std::forward_list<int> list = { 1,2,3 };
	list.push_front(0);		//맨 앞에 0추가 : {0, 1, 2, 3}
	auto it = list.begin();
	list.insert_after(it, 7);	//맨 처음 원소 뒤에 7추가 : {0, 7, 1, 2, 3}
}

 std::forward_list는 std::vector의 emplace()함수와 유사한 emplace_front()와 emplace_after() 함수를 제공한다. 이 두 함수는 삽입 함수와 같은 기능을 수행하지만 추가적인 복사 또는 이동을 하지 않기 때문에 효율적이다.

 

 

forward_list에서 원소 삭제

forward_list에서 원소를 삭제할 때에는 pop_front()와 erase_after() 함수를 사용한다. pop_front() 함수는 리스트의 맨 처음 원소를 제거한다. 이 작업은 원소 이동이 필요하지 않기 때문에 매우 빠르게 동작한다. erase_after()는 두 가지 형태로 제공된다. 하나는 ①특정 원소를 가리키는 반복자를 인자로 받아서 바로 다음 위치의 원소를 삭제한다. ②일련의 원소를 제거할 때에도 erase_after() 함수를 사용할 수 있으며, 이 경우에는 삭제할 범위의 시작 원소 앞을 가리키는 반복자와 삭제할 범위 끝 원소를 가리키는 반복자를 인자로 받는다.

#include<iostream>
#include<forward_list>

int main() {
	std::forward_list<int> list = { 0,1,2,3,4 };
	list.pop_front();		//맨 앞에 원소 제거 : {1, 2, 3, 4}
	auto it = list.begin();
	list.erase_after(it);	//맨 앞의 다음 원소를 삭제 : {1, 3, 4}
	list.erase_after(it, list.end());	//맨 앞 원소 다음부터 맨 마지막 원소까지 삭제 : {1}
}

 

 

forward_list에서 기타 멤버 함수

반복자로 원소 위치를 지정하여 삭제하는 erase() 함수 말고도 원소 값을 검사하여 삭제하는 remove()와 remove_if() 함수도 있다.

remove() 함수는 삭제할 원소 값 하나를 매개변수로 받는다. 이 함수는 저장된 데이터 타입에 정의된 등호 연산자를 사용하여 전달된 값과 일치하는 모든 원소를 찾아 삭제한다. 저장된 데이터 타입에서 등호연산이 지원되지 않으면 remove() 함수를 사용할 수 없다. 이 때는 컴파일러에서 에러를 발생시킨다. remove() 함수는 오직 등호 연산에 근거하여 원소를 삭제하며, 다른 조건에 근거하여 삭제 여부를 결정할 수 없다.

remove_if() 함수는 데이터 원소 값 하나를 인자로 받아 bool값을 반환하는 조건자 함수를 인자로 받는다. 그리고 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제한다.

 

연결리스트 같은 자료 구조는 특정 원소에 임의 접근이 불가능하므로 std::sort() 함수를 사용할 수 없었다. 또한 forward_list에서 사용하는 반복자는 std::vector와 std::arrary와 다르다. 하지만, forward_list에서는 두가지 형태의 sort() 함수를 제공한다.

하나는 < 연산자를 기반으로 정렬하고, 다른 하나는 매개 변수로 전달된 비교자를 사용한다. 기본 sort()함수는 std::less<value_type>을 비교자로 사용한다. 이 비교자는 첫 번째 인자가 두번째보다 작으면 true를 반환하며, 사용자 정의 타입 원소를 사용할 경우에는 < 연산자가 재정의되어 있어야 한다. 이외에도 다른 기준을 이용하여 원소를 비교하고 정렬하려면 이항 조건자를 지정할 수 있다.

#include<iostream>
#include<forward_list>

int main() {
	std::forward_list<int> list = { 5,4,1,3,2 };
	list.sort();	//{1,2,3,4,5}
	list.sort(std::greater<int>());	//{5,4,3,2,1}
}

코드에서 std::greater<int>는 표준으로 제공되는 비교 함수 객체이며, 원소를 내림차순으로 정렬하기 위한 > 연산자에 대한 래퍼이다.

 

reserve() 함수는 저장된 원소의 순서를 역순으로 변경한다.

unique() 함수는 리스트에서 홀로 나타나는 원소는 놔두고, 인접하여 중복되는 원소에 대해서는 첫번째만 남겨두고 나머지는 제거한다. 이 함수는 두 원소가 같은지를 판단하는 방식에 따라 두가지 형태로 제공된다. 하나는 인자가 없는 형태이며 원소 타입의 등호 연산자를 사용하여 같은지를 판단한다. 다른 하나는 bool 값을 반환하는 이항 조건자를 인자로 받으며, 이 조건자는 리스트 원소 타입의 인자를 두개 받는다. 실제로 unique() 함수는 서로 인접한 원소끼리 같은지를 판단하고 만약 서로 같으면 앞에 있는 원소는 남기고 뒤의 원소는 제거한다. 그러므로 리스트 전체에서 유일한 원소들만 남게 만들려면 먼저 리스트를 정렬한 후 unqiue() 함수를 사용해야 한다.

#include<iostream>
#include<forward_list>

int main() {
	std::forward_list<int> list = { 5,4,1,3,2 };
	list.reverse();	//{2,3,1,4,5}

	std::forward_list<int> list1 = { 1,2,2,1,5,5,4,3,0 };
	list1.unique();	//{1,2,1,5,4,3,0}

	std::forward_list<int> list2 = { 1,2,2,1,5,5,4,3,0 };
	list2.sort();	//{0,1,1,2,2,3,4,5,5}
	list2.unique();	//{0,1,2,3,4,5}

	std::forward_list<int> list3 = { 1,2,2,1,5,5,4,3,0 };
	list3.unique([](int a,int b){ return (b-a)<2;});
	//리스트에서 특정 원소가 바로 앞 원소보다 2이상 크지 않으면 삭제 : {1,5}
}

 

 

반복자

배열과 벡터의 경우 연속된 자료 구조를 사용하기 때문에 특정 위치의 원소에 곧바로 접근할 수 있다. 이러한 반복자를 임의 접근 반복자라고 한다. 하지만 forward_list의 경우 기본적으로 역방향으로 이동하는 기능을 제공하지 않기 때문에 바로 이전 노드로 이동하려면 맨 처음 노드부터 시작해서 찾아가야 한다. 따라서 forward_list에서는 증가 연산만 가능하며, 이러한 반복자를 순방향 반복자라고 한다.

반복자 타입에 따라 사용할 수 있는 함수 중에 advance(), next(), prev() 함수가 있다. advance() 함수는 반복자와 거리 값을 인자로 맏고, 반복자를 거리 값만큼 증가 시킨다. next()와 prev() 함수도 반복자와 거리 값을 인자로 받고, 해당 반복자에서 지정한 거리만큼 떨어진 위치의 반복자를 반환한다. 이 함수들은 해당 반복자가 지원할 경우에만 동작한다. 만일 순방향으로만 이동 가능한 순방향 반복자에 대해 prev()함수를 사용하면 에러가 발생한다. 

 

 

 

shaeod.tistory.com/493

[C++11 STL] std::forward_list 주요 멤버 함수 목록

www.yes24.com/Product/Goods/95863013

코딩 테스트를 위한 자료 구조와 알고리즘 with C++