1-4. std::forward_list

서론

지금까지 살펴본 배열, 벡터 같은 연속된 자료 구조에서는 데이터 중간에 자료를 추가하건 삭제하는 작업이 매우 비효율적이다. 

그래서 연결 리스트와 같은 형태의 자료 구조가 등장한다. 

많은 응용 프로그램에서는 자료 구조 중간에 삽입 도는 삭제 작업을 필요로 하기 때문이다. 

 

기본적으로 연결 리스트를 구성하려면 포인터를 하나 가지고 있어야 하고, new와 delete 연산자를 이용하여 메모리를 할당하고 해제할 수 있어야 한다. 

이러한 기능을 구현하는 것이 그리 어렵진 않지만 자칫 잘못하면 찾기 어려운 버그를 양산할 수 있기 때문에, 

C++에서는 C 스타일 배열에 대한 래퍼 클래스 std::array를 제공하듯이 기본적인 연결 리스트에 대한 래퍼 클래스인 std::forward_list 클래스를 제공한다. 

 

std::forward_list는 기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능을 제공한다. 

성능 유지를 위해 std::forward_list는 전체 리스트의 크기를 반환하거나 또는 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않는다. 

원소의 삽입, 삭제, 순서 뒤집기, 분할과 같이 기본적인 연결 리스트의 메모리 사용량이나 성능에 영향을 주지 않는 기능은 제공한다. 

 

std::vector와 마찬가지로 std::forward_list도 두 번째 템플릿 매개변수에 사용자 지정 할당자를 지정할 수 있다. 

 

std::forward_list에서 원소 삽입과 삭제

std::forward_list에서 원소를 삽입할 대에는 push_front()와 insert_after() 함수를 사용한다. 

이 두 함수는 std::vector에서 원소를 삽입할 때와는 조금 다른 동작을 수행한다. 

 

push_front() 함수는 연결 리스트 맨 앞에 새로운 원소를 삽입한다. 

std::forward_list는 마지막 원소에 직접 접근할 수 없으므로 push_back() 함수를 제공하지 않는다. 

특정 위치에 원소를 삽입하려면 insert()가 아니라 insert_after() 함수를 사용해야 한다. 

이는 연결 리스트에서 새로운 원소를 삽입한 후, 해당 위치 앞에 있는 원소의 next 포인터를 수정해야 하기 때문이다. 

std::forward_list에서 반대 방향으로 이동하는 것이 허용되지 않으므로 특정 원소 뒤에 새로운 원소를 삽입한 후, 해당 원소의 next 포인터를 수정하는 것이 타당하다. 

 

연결 리스트에서 원소 삽입은 노드의 포인터 조작으로 구현되므로, 삽입 후 다른 원소를 이동할 필요가 없다. 

그러므로 std::forward_list의 삽입 함수는 모두 배열 기반 구조에서의 삽입 함수에 비해 매우 빠르게 동작한다. 

std::forward_list의 삽입 함수는 리스트의 원소 크기에 영향을 받지 않으며, 시간 복잡도는 O(1)이다. 

 

std::forward_list<int> fwd_list = {1, 2, 3};
fwd_list.push_front(0);  //맨 앞에 0 추가 : {0, 1, 2, 3}
auto it = fwd_list.begin();
fwd_list.insert_after(it, 5);  //맨 처음 원소 뒤에 5 추가 : {0, 5, 1, 2, 3}
fwd_list.insert_after(it, 6);  //같은 위치에 6 추가 : {0, 6, 5, 1, 2, 3}

 

std::forward_list는 std::vector의 emplace() 함수와 유사한 emplace_front()와 emplace_after() 함수도 제공한다. 

이 두 함수는 삽입 함수와 같은 기능을 수행하지만 추가적인 복사 또는 이동을 하지 않기 때문에 더 효율적이다. 

 

 

 

std::forward_list에서 원소를 삭제할 때에는 pop_front()와 erase_after() 함수를 사용한다. 

pop_front() 함수는 리스트의 맨 처음 원소를 제거한다. 

이 작업은 원소 이동이 필요하지 않으므로 매우 빠르게 동작하며 시간 복잡도는 O(1)이다. 

erase_after()는 두 가지 형태로 제공된다. 

1. 특정 원소를 가리키는 반복자를 인자로 받아서 바로 다음 위치의 원소를 삭제한다
2. 삭제할 범위의 시작 원소 앞을 가리키는 반복자와 삭제할 범위 끝 원소를 가리키는 반복자를 인자로 받아서 일련의 원소를 제거한다. 

erase_after() 함수를 사용하여 일련의 원소를 삭제하는 시간 복잡도는 삭제할 원소 개수의 선형 함수 형태로 나타난다. 

이는 연결 리스트에서 각각의 노드는 전체 메모리의 임의 위치에 산재되어 있으며, 각각의 노드에 사용된 메모리를 개별적으로 해제해야 하기 때문이다. 

 

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

 

std::forward_list의 기타 멤버 함수

반복자로 원소 위치를 지정하여 삭제하는 erase() 함수 외에도 std::forward_list는 원소 값을 검사하여 삭제하는 remove()와 remove_if() 함수도 제공한다. 

 

remove() 함수는 삭제할 원소 값 하나를 매개변수로 받는다. 

이 함수는 저장된 데이터 타입에 정의된 등호 연산자를 사용하여 전달된 값과 일치하는 모든 원소를 찾아 삭제한다. 

저장된 데이터 타입에서 등호 연산이 지원되지 않으면 remove() 함수를 사용할 수 없으며, 이 경우 컴파일러는 에러를 발생시킨다. 

remove()는 오직 등호 연산에만 근거하여 원소를 삭제하며, 다른 조건에 근거하여 삭제 여부를 결정할 수 없다. 

좀 더 유연한 조건부 삭제를 수행하려면 remove_if() 함수를 사용할 수 있다. 

 

 

remove_if()는 데이터 원소 값 하나를 인자로 받아 bool 값을 반환하는 조건자(predicate) 함수를 인자로 받는다. 

그리고 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제한다. 

 

최신 C++ 버전을 이용한다면 조건자 자리에 람다 표현식(lambda expression)을 사용할 수 있다. 

 

std::forward_list<citizen> citizens = {
{"Kim", 22}, {"Lee", 25}, {"Park", 18}, {"Jin", 16}
};

citizens.remove_if([](const citizen &c) {
	//나이가 19세보다 작으면 리스트에서 제거합니다.
    return(c.age <19);
});

 

remove_if() 함수는 주어진 조건에 대해 참을 만족하는 원소를 모두 제거한다. 

위 예제는 조건이 간단하므로 람다 표현식을 사용했다. 

복잡한 조건이라면 리스트에 저장된 원소를 인자로 받아서 bool 값을 반환하는 일반 함수를 사용해도 된다. 

 

---

c++ 람다표현식이란?

#include<iostream>
#include<string>
using namespace std;
 
// 일반 함수 정의
void sum1(int a, int b)
{
    cout << "sum1 func : " << a + b << endl;
}
 
int main(void) {
 
    //일반 함수 호출
    sum1(10, 20);
 
    //람다 함수
    [](int a, int b)
    {
        cout << "sum2 lambda : " << a + b << endl;
    }(30, 40);
 
    return 0;
}

위 코드를 보면 우리가 일반적으로 알고있는 함수의 모양인

반환형 함수이름(매개변수)

{

//함수동작

} 

이런식으로 함수가 이루어저 있는 것을 볼 수 있다. 

 

람다함수를 보면 [] (int a, int b) { couot << " " << endl;}(30, 40);

와 같은 방식으로 함수를 표현한다. 

즉, 함수의 이름과 반환형이 보이지 않는 것을 볼 수 있다. 

 

람다함수는 아래와 같이 이루어진다

[] (매개변수) {//함수동작} (호출 시 인자);

이렇게 우리가 아는 일반 함수에서 함수 이름이 없어지고 동작만 있는 함수를 람다 함수, 이름 없는 함수, 람다 표현식이라고 한다. 

 

람다 표현식 생성(함수를 만들기만 함)
[](int a, int b) {return a + b};

람다 표현식 사용(함수를 만들고 호출)
[](int a, int b) {return a + b}(10, 20);

---

remove()와 remove_if() 함수는 리스트 전체를 순회하면서 조건에 맞는 원소를 모두 삭제하므로 O(n)의 시간 복잡도를 갖는다. 

 

 

std::forward_list는 원소 데이터를 정렬하는 sort() 멤버 함수를 제공한다. 

std::array, std::vector 등에 저장된 데이터는 범용적인 std::sort(first_iterator, last_iterator) 함수를 이용하여 원소를 정렬할 수 있다. 

그러나 연결 리스트와 같은 자료구조는 특정 원소에 임의 접근이 불가능하므로 std::sort() 함수를 사용할 수 없다. 

또한 std::forward_list에서 사용하는 반복자는 std::array 또는 std::vector의 반복자와 다르다. 

 

std::forward_list에서 제공하는 sort() 함수는 두 가지 형태를 지원한다. 

1. < 연산자를 기반으로 정렬
2. 매개변수로 전달된 비교자(comparator)를 사용

기본 sort() 함수는 std::less<value_type>을 비교자로 사용한다. 이 비교자는 첫 번째 인자가 두 번째보다 작으면 true를 반환하며, 사용자 정의 타입 원소를 사용할 경우에는 < 연산자가 재정의되어 있어야 한다. 

이외에도 다른 기준을 이용하여 원소를 비교하고 정렬하려면 이항 조건자(binary predicate)를 지정할 수 있다. 

두 가지 형태의 sort() 함수 모두 선형 로그 시간 복잡도 O(nlogn)을 갖는다. 

 

다음 예제 코드는 두 형태의 sort() 함수 사용법을 보여준다. 

std::forward_list<int> list1 = {23, 0, 1, -3, 34, 32};
list1.sort();  //{-3, 0, 1, 23, 32, 34} 순서로 바뀜
list1.sort(std::greater<int>()); //{34, 32, 23, 1, 0, -3} 순서로 바뀜

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

 

std::forward_list에서 제공하는 다른 멤버 함수로는 reverse()와 unique()가 있다. 

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

unique() 함수는 리스트에서 홀로 나타나는 원소는 놔두고, 인접하여 중복되는 원소에 대해서는 첫 번째만 남겨두고 나머지는 제거한다. 

unique() 함수는 두 원소가 같은지를 판단하는 방식에 따라 두 가지 형태로 제공된다. 

1. 인자가 없는 형태이며, 이때는 원소 타입의 등호 연산자를 사용하여 같은지를 판단한다
2. bool 값을 반환하는 이항 조건자를 인자로 받으며, 이 조건자는 리스트 원소 타입의 인자를 두 개 받는다. 

unique() 함수의 시간 복잡도도 선형 함수로 표현되는데, 이는 unique() 함수가 각각의 원소를 나머지 원소 전체와 비교하는 형태로 동작하는 것이 아님을 암시한다. 

그러므로 리스트 전체에서 유일한 원소들만 남게 만들려면 먼저 리스트를 정렬한 후 unique() 함수를 사용해야 한다. 

 

std::forward_list<int> list1 = {2, 53, 1, 0, 4, 10};
list1.reverse();  // 실행결과 : {10, 4, 0, 1, 53, 2}

list1 = {0, 1, 0, 1, -1, 10, 5, 5, 10, 0};
list1.unique();  //실행결과 : {0, 1, 0, 1, -1, 10, 5, 10, 0}

list1 = {0, 1, 0, 1, -1, 10, 5, 5, 10, 0};
list1.sort();  //실행결과 : {-1, 0, 0, 0, 1, 1, 5, 5, 10, 10}
list1.unique(); //실행결과 : {-1, 0, 1, 5, 10}

//다음 예제 코드는 리스트에서 특정 원소가 바로 앞 원소보다 2 이상 크지 않으면 삭제한다
list1.unique([](int a, int b) {return (b-a) <2;}); //실행 결과 : {-1, 1, 5, 10}