[C++ STL] 1.6 std::list

std::list

---

복습

• std::forward_list는 기본적인 형태로 구현된 연결 리스트임
  • 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능을 제공하지 않음
  • 빠른 원소 삽입이 필요한 모든 경우에 어울리는 container는 아니다.

---

• std::forward의 단점을 보완하기 위해 c++에서 std::list를 제공한다
• std::list
  • 양쪽 방향으로 연결된 리스트, 즉 이중 연결 리스트(doubly-linked-list) 구조로 되어 있다.
  • 따라서 더 많은 기능을 제공한다. (메모리는 조금 더 많이 사용한다)

// 이중 연결 리스트 노드 기본 형태
struct doubly_linked_list_node
{
    int data;
    doubly_linked_list_node* next;
    doubly_linked_list_node* prev;
};

• doubly-lined-list의 경우 이전 노드를 가리키는 포인터가 추가로 있기 때문에 역방향으로 이동이 가능하다
• 맨 마지막 원소와 리스트 크기를 따로 저장하여 push_back() 또는 size() 함수를 지원할 수 있다
• std::forward_list처럼 템플릿 매개변수로 사용자 정의 할당자를 지정할 수 있다

std::list 멤버 함수

• 전반적으로 std::forward_list와 유사하지만, 약간의 차이가 존재한다
  • forward_list의 insert_after()와 emplace_after()는 list의 insert()와 emplace()에 대응
• 원소 이동을 역방향으로 할 수 있으므로 원소 삽입을 위해 특정 원소의 이전 원소 반복자를 제공하지 않아도 된다
  • 대신 새로운 원소가 삽입될 위치를 가리키는 반복자를 함수 인자로 전달한다

example: std::list 삽입/삭제 함수

#include <iostream>
#include <list>

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

    // { 1, 2, 3, 4, 5, 6 }
    list1.push_back(6);

    // { 1, 0, 2, 3, 4, 5, 6 }
    list1.insert(next(list1.begin()), 0);

    // { 1, 0, 2, 3, 4, 5, 6, 7 }
    list1.insert(list1.end(), 7);

    // { 1, 0, 2, 3, 4, 5, 6 }
    list1.pop_back();

    std::cout << "삽입 & 삭제 후 리스트 : ";

    for(auto i : list1)
        std::cout << i << " ";

    return 0;
}

• prev 포인터와 next 포인터를 모두 수정해야 하므로, std::foward_list에 비하면 두 배의 연산량이 필요하다

std::list 기타 함수

• remove(), remove_if(), sort(), unique(), reverse() 등의 함수도 std::list에서 제공된다
  • std::foward_list와 같은 형태로 동작한다

양방향 반복자

• std::list의 경우 역방향으로의 연산이 필요한 경우에는 역방향 반복자를 사용할 수 있다
• random access iterator 보다는 유연하지 않다
  • 어느 방향으로 원하는 만큼 이동할 수 있지만, random access iterator 처럼 특정 위치로 한 번에 이동하는 것이 불가능함
  • 특정 위치로 이동하는 작업은 선형 시간 복잡도를 가진다
• 어느 방향으로 이동할 수 있으므로 양방향 반복자(bidirectional iterator)라고 부른다

반복자 무효화

• 반복자는 메모리 주소를 가리키는 포인터를 이용하여 구현되었기 때문에 컨테이너가 변경될 경우 제대로 동작하지 않을 수 있다
  • 컨테이너가 변경되어 특정 노드 또는 원소의 메모리 주소가 바뀌면 반복자가 무효화될 수 있고, 예측할 수 없는 동작이 발생할 수 있다
• vector::push_back() 함수의 경우 capacity에 따라 새로 메모리 공간을 할당하고 새 메모리 공간에 복사는 작업을 한다
  • 이 경우 기존에 사용하던 모든 반복자, 포인터, 참조는 모두 무효화된다
• vector::insert() 함수를 수행할 때 메모리 재할당이 필요한 경우라면 이 경우에도 기존의 반복자, 포인터, 참조는 모두 사용하면 안 된다
• 메모리 재할당 없이 원소를 삽입하는 경우 원소 삽입 위치 이후에 있는 원소를 모두 이동해야 하므로 이 위치를 가리키는 반복자는 모두 무효화 된다
• 연결 리스트에서는 삽입/삭제 동작에서 원소를 이동할 필요가 없으므로 반복자가 무효화되지 않는다
  • 다만 특정 원소를 삭제하는 경우, 삭제되는 원소를 가리키던 반복자는 당연히 무효화된다. 나머지는 그대로 사용 가능

std::vector<int> vec = { 1, 2, 3, 4, 5 };

// v_it[4]는 vec[4] 원소를 가리킴
auto v_it4 = vec.begin() + 4;

// v_it4 반복자는 무효화됨, v_it4를 이용하여 원소에 접근하면 예상하지 못한 에러가 발생할 수 있다
vec.insert(vec.begin() + 2, 0);

std::list<int> lst = { 1, 2, 3, 4, 5 };

auto l_it4 = next(lst.begin(), 4);

// l_it4 반복자는 유효함
lst.insert(next(lst.begin(), 2), 0);