std::forward_list

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

 

 

std::vector의 단점

• 중간에 원소를 추가/삭제하는 작업이 O(n)으로 매우 비효율적이다.

 

std::forward_list

• STL에서 제공하는 단일 연결 리스트 컨테이너이다.
• 단일 연결 리스트이기 때문에 순방향 반복자만을 지원한다.
  (그렇기 때문에 std::sort가 아닌 컨테이너 자체적으로 sort 함수를 제공한다.)
• 메모리나 성능을 극단적으로 최적화해야 하는 경우가 아니라면 std::list를 사용하는 것이 보통이다.

 

std::forward_list의 성능

• 성능 유지를 위해 O(n) 복잡도의 크기 반환, 중간 원소 접근을 제공하지 않는다.
• 원소의 삽입은 O(1) 복잡도를 갖는다.
  (삽입할 위치 전의 반복자를 알고 있다는 전제 하에)

 

std::forward_list의 원소 삽입 의사 코드

insert_after(it, val):
    node = new Node {val, null}

    node->next = it->next
    it->next = node

 

#include <iostream>
#include <forward_list>

using namespace std;

template <typename T>
ostream& operator<<(ostream& os, const forward_list<T> fwd_list)
{
    for (T e : fwd_list)
        os << e << ' ';

    return os;
}

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

    // 맨 앞에 0 추가
    fwd_list.emplace_front(0);

    // 맨 앞 원소 뒤에 5 추가
    fwd_list.emplace_after(fwd_list.begin(), 5);

    // 맨 앞 원소 뒤에 6 추가
    fwd_list.emplace_after(fwd_list.begin(), 6);

    cout << fwd_list << endl;

    // 맨 앞 원소를 삭제
    fwd_list.pop_front();

    // 맨 앞 원소의 다음 원소를 삭제
    fwd_list.erase_after(fwd_list.begin());

    // 맨 앞 원소의 다음 원소부터 마지막 원소까지 삭제
    fwd_list.erase_after(fwd_list.begin(), fwd_list.end());

    cout << fwd_list << endl << endl;

    forward_list<int> fwd_list2 = {-3, 9, 1, 2, 5, 4, 9, 3, 2, 1, 6, 2, 11, 8};

    // 모든 2를 삭제
    fwd_list2.remove(2);

    // 10보다 큰 모든 수 삭제
    fwd_list2.remove_if([](const int& e) { return 10 < e; });

    cout << fwd_list2 << endl;

    // 오름차순 정렬
    fwd_list2.sort();

    cout << fwd_list2 << endl;

    // 내림차순 정렬
    fwd_list2.sort(std::greater<int>());

    cout << fwd_list2 << endl;

    // 원소 순서를 역순으로 변경
    fwd_list2.reverse();

    cout << fwd_list2 << endl;

    // 중복 원소를 제거
    // 인접한 원소들을 비교하여 O(n)에 처리된다.
    // 정순 혹은 역순 정렬된 상태에서만 정상 작동한다.
    fwd_list2.unique();

    cout << fwd_list2 << endl;
}

 

출력

0 6 5 1 2 3
6

-3 9 1 5 4 9 3 1 6 8
-3 1 1 3 4 5 6 8 9 9
9 9 8 6 5 4 3 1 1 -3
-3 1 1 3 4 5 6 8 9 9
-3 1 3 4 5 6 8 9