C++ list 자료형 사용법

 

백준 문제를 풀다가 왠지 배열로 풀면 시간초과가 날 것 같고, 벡터로 풀기 애매한 문제가 있었다. 그래서 링크드 리스트를 기반으로 한 STL 컨테이너를 찾다가, 비교적 적절한 방법을 발견했다. 바로 list를 이용하는 것이다.

 

 

list 기본 개념

---

list는 기본적으로 양방향 링크드 리스트 구조를 가지고 있다. 그래서 쉽게 붙이고, 잘라낼 수 있다. 하지만 인덱스로 찾는 것이 불가능 (예 : at, [] ) 하다. 그래서 iterator를 이용하여 탐색을 해야 한다.

 

 

list 선언

---

1. 기본 선언 -> list<T> l ;

 

 

list 함수

---

assign(a, b) : b값을 가진 a개 원소 할당

insert(a, b) : iter a 의 위치에 b 삽입 

begin() : 시작 iter 반환

end() : 마지막 iter 반환

front() : 맨 앞의 값 반환

back() : 맨 뒤의 값 반환

clear() : 모든 원소 초기화

empty() : 비어있으면 1, 차있으면 0 반환

remove(a) : a랑 일치하는 값 삭제

erase(a) : (a 는 iter) iter에 해당하는 값 삭제, 반환값은 삭제한 반환값 앞의 iter

 

 

특정 인덱스에 쉽게 접근하기

---

advance 함수를 이용하자. 특정 iter에 쉽게 접근할 수 있게 해 준다.

사용법 : advance(iter, a) : iter 부터 a 만큼의 증감 연산자를 실행한 결과를 반환한다.

 

입력 변수로 사용된 iter도 증감 연산자의 영향을 받으니 주의하자!

 

 

erase 함수를 사용할 때 주의할 점

---

erase안에 들어갈 iter가 일회성이면 상관이 없으나, 계속 사용할 변수면 알아두어야 할 것이 있다. 

위의 그림을 보면은 마지막 원소를 제거하려는 모습이다. 마지막 원소를 가리킨 iter에 의해서 마지막 원소는 사라지게 된다. 제거된 이후의 iter를 탐색하게 되면 어떠한 값이 있을까? 아무것도 가르키지 못할 것이다. 여기서 iter-- 같은 증감 연산자를 사용한다고 해서 다른 원소로 갈 수도 없다. 이미 링크가 끊겨 있기 때문이다. 

 

erase 를 사용하고 사용한 입력 변수를 증감연산자를 이용해 재사용하고자 하면 반드시 반환값을 통해서 이전 iter를 받아 두자. 

 

예) iter = lst.erase(iter);

 

이것 때문에 시간 많이 잡아먹은 것 같다.