Reference:
- "전문가를 위한 C++" / 마크 그레고리 / 한빛 미디어
- "Optimized C++" / 커트 건서로스 / 한빛 미디어
std::list
std::list는 std::vector, std::deque와 많은 특성을 공유한다.
- vector, deque와 마찬가지로 항목을 뒤쪽에 삽입하는 시간은 상수 시간
- deque와 마찬가지로 항목을 앞쪽에 삽입하는 시간도 상수 시간
- vector, deque와 마찬가지로 리스트를 효율적으로 정렬할 수 있다.
추가로 vector, deque와 달리 삽입 위치를 가리키는 반복자가 주어졌을 때 리스트의 중간에 삽입하는 시간 또한 상수 시간이라는 장점이 있다.
하지만 리스트를 이진 탐색과 같이 효율적으로 검색하는 방법은 없다.
source: https://hackingcpp.com/cpp/std/sequence_containers.html
반복자/참조 무효화
std::list에는 재할당해야 하는 내부 배열이 없으므로, 항목을 삽입하더라도 리스트의 항목을 가리키는 반복자나 참조가 무효화되지 않는다. 반복자나 참조가 가리키는 항목을 삭제한 경우에만 무효화된다.
