forward_list

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=257288899

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

본 책을 사용하여 공부하는 내용이고 해당 글은 상업적으로 배포하고자 하지 않고 개인 공부용입니다

 

• 배열, 벡터와 같은 연속된 자료구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적임
• 따라서 연결 리스트와 같은 형태의 자료구조가 등장하게 됨 -> 연결 리스트 컨테이너
• 기본적인 연결 리스트를 구성하기 위해서는 포인터를 하나 가지고 있어야 하고 new와 delete 연산자를 이용해 메모리를 할당하고 해제할 수 있어야 함

forward_list

 

• 기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능을 제공함
• 성능 유지를 위해 전체 리스트의 크기를 반환하거나 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않음, front( )는 있는데 back( )같은거느 없다 이말이여
• 대신 원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 제공을 함
• 이러한 기능은 연결 리스트의 메모리 사용량이나 성능에 영향을 주지 않기 때문임

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}

 

• 시간 복잡도는 1임 O(1)

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}

• it나 fwd_list.end( )가 가리키는 것은 주소임(포인터 값)
• 그 자체로는 출력이 안되고 궁금하면 *it 해서 begin 값이 2이겠구나라고 생각할 수 있음
• 한편 remove( )와 remove_if( )라는 함수도 있고 이는 리스트 전체를 순회하면서 조건에 맞는 원소를 모두 삭제하므로 O(n)의 시간복잡도를 가짐
• 추가 메서드

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}