list

std::list는 std::forward_list의 단점을 보완하기 위해서 C++ 제공하는 Container이다.

std::list는 양방향 연결된 리스트이다.

즉, 이중 연결 리스트 double-linked list 구조로 되어있다.

기본적으로 push_back(), emplace_back(), pop_back() 함수를 제공한다.

삽입/삭제

forward_list와 마찬가지로 push_front(), insert(), pop_front(), erase()제공하고 시간복잡도가 forward_list와 같지만 실제 연산은 조금 더 덜린다.

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

한가지 봐야할게 insert(list.end(), 6) 일때 end()는 nullptr인데 end() 바로 앞에 삽입하는것이 확인 가능하다.

iterator

std::list의 iterator는 random access iterator보다 유연하지는 않다.

random access iterator경우처럼 특정 위치로 한 번에 이동하는 것은 불가능하다.

따라서 std::list의 iterator를 이용하여 특정 위치로 이동하는 작업은 '선형 시간 복잡도'를 가진다.

(만약 시간복잡도가 O(n)이면, 이 알고리즘은 O(n)시간 혹은 선형 시간을 갖는다고 말할 수 있다.)

std::list의 iterator는 어느방향으로든 이동할 수 있으므로 bidirectional iterators(양방향) 라고도 부른다.

반복자 무효화

어떠한 STL Container든 원소 접근, 순회, 삽입, 삭제를 iterator를 통해 모두 같은 방식으로 처리를 한다.

iterator는 메모리 주소를 가르키는 포인터를 이용하여 구현되어 있기 때문에 경우에 따라 container가 변경될 경우 동작하지 않는 문제가 발생할 수도 있다.

예를 들어 vector insert하다가 capacity를 넘는 경우나 push_back을 많이 하는 경우

기존의 모든 원소를 새 메모리 공간으로 "복사"하는 동작이 발생을 한다.

이 경우 기존에 사용하던 모든 반복자와 포인터, 참조는 "무효화"된다.