std:forward_list, std:list

배열 벡터 등 연속된 자료구조는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적이다.

탭을 지원하는 브라우저에서 새로운 탭을 임의의 위치에 옮기는 경우

음악 플레이어와 같이 재생목록 중간에 새로운 노래를 추가할 수 있는 프로그램의 경우

연결 리스트 구현 개념

1. 값+포인터

2. new/delete를 활용한 메모리 할당 및 해제

std:forward_list

- 단방향 연결리스트

- 메모리를 적게쓰고 빠른 성능을 유지하기 위해 사용

- 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 기능 X

struct linked_list_node{
    int data;
    doubly_linked_list_node* next;
};

std:forward_list에서 원소 삽입 삭제

- forward_list는 마지막 원소에 직접 접근 X => push_back 제공하지 않음

- 원소 삽입은 insert_after(): 원소 삽입 후, 앞에 있는 next 포인터 수정 (순방향 이동만 허용) / O(1)

#include <iostream>
#include <forward_list>
#include "function.hpp"

int main(){
    std::forward_list<int> fwd_list = {1, 2, 3, 4, 5};

    fwd_list.push_front(0);
    print(fwd_list);

    auto it = fwd_list.begin();
    fwd_list.insert_after(it,5); 
    print(fwd_list);

    fwd_list.emplace_front(3);
    fwd_list.emplace_after(++it, 8); // forward_list에서는 증가 연산자만 가능
    print(fwd_list);

    fwd_list.pop_front();
    print(fwd_list);

    fwd_list.erase_after(it);
    print(fwd_list);

    it = fwd_list.begin();
    fwd_list.erase_after(it);
    print(fwd_list);
    fwd_list.erase_after(it, fwd_list.end());
    print(fwd_list);

}

std:forward_list의 멤버함수

함수	설명	예제
remove(value)	리스트에서 특정 value 값을 찾아 삭제	fwd_list.remove(3);
remove_if(pred)	조건을 만족하는 요소를 삭제합니다. 조건은 함수 또는 람다 표현식으로 정의할 수 있습니다.	fwd_list.remove_if([](int x) { return x % 2 == 0; });
sort()	리스트의 요소를 오름차순으로 정렬	fwd_list.sort();
unique()	인접한 중복 요소를 제거, 리스트가 정렬되어 있어야 제대로 작동	fwd_list.unique();
reverse()	리스트의 요소 순서를 반대로 뒤집기	fwd_list.reverse();

    std::forward_list<int> fwd_list2 = {1, 2, 3, 4, 5};

    // remove: 리스트에서 값이 3인 모든 요소를 삭제
    fwd_list2.remove(3);
    std::cout << "After remove(3): ";
    print(fwd_list2);

    // remove_if: 리스트에서 4보다 큰 요소를 삭제
    fwd_list2.remove_if([](int x) { return x > 4; });
    std::cout << "After remove_if(x > 5): ";
    print(fwd_list2);

std:list

- 양쪽 방향으로 연결된 이중 연결 리스트(doubly-linked list)

- forward_list 보다 메모리 조금 더 사용

struct doubly_linked_list_node{
    int data;
    doubly_linked_list_node* next;
    doubly_linked_list_node* prev;
};

std:list의 멤버함수

- forward_list의 멤버함수를 그대로 가져오고, after()가 필요 없어짐

- 원소 삽입을 위한 이전 원소 반복자 제공할 필요 없음

- push_back(), emplace_back() 등 추가

#include <iostream>
#include <list>
#include "func.hpp"

int main(){
    std::list<int> list = {1, 2, 3, 4, 5};
    list.push_back(6);
    list.insert(next(list.begin()), 0);
    list.insert(list.end(), 7);

    print(list);

    list.pop_back();
    print(list);
}

 

 

반복자 무효화

 

어떤 컨테이너든 원소 접근, 순회, 순회, 삽입, 삭제 등의 작업을 반복자를 사용하여 모두 같은 방식으로 처리된다.

 

그런데 컨테이너가 변경되어 특정 노드 or 메모리 주소가 바뀌면 반복자가 무효화되고, 오류가 난다.

 

 

ex1) vector::push_back()

- 새로 메모리를 할당하고 기존의 모든 원소를 새 메모리 공간으로 복사하는 동작

- 기존에 사용하던 반복자, 포인터, 참조는 모두 무효가 된다.

 

ex2) vector::insert()

- 메모리의 재항달이 없으면 원소 삽입 위치 이후의 모든 원소는 이동

- 기존에 사용하던 반복자, 포인터, 참조는 모두 무효가 된다.

 

#include <iostream>
#include <vector>
#include <list>
#include "func.hpp"

int main(){
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::list<int> lst ={1, 2, 3, 4, 5};

    auto v_it4 = vec.begin() +4;
    vec.insert(vec.begin() +2, 0);

    auto l_it4 = next(lst.begin(), 4);
    lst.insert(next(lst.begin(), 2), 0);
    
    print(vec);
    print(lst);

    // 무효화된 반복자 출력
    std::cout << "Vector's 4th element (v_it4): " << *v_it4 << std::endl; // output:0
    std::cout << "List's 4th element (l_it4): " << *l_it4 << std::endl;  // output: 5
}

 

 

=>  연결 리스트에서는 삽입 or 삭제에서 원소를 이동시킬 필요가 없다.

- 삭제하는 경우만 그 원소만 무효화되고 나머지 원소를 가리키는 반복자는 그대로 사용 가능하다.