[C++] STL Container list(리스트)

STL의 여러 컨테이너를 사용해보면서 내부적으로 어떻게 구현이 되어있는지에 대한 고민을 해보지 않았던 것 같다. 그래서 vector를 사용해서 push_back()을 할 때에는 당연히 삽입이므로 시간복잡도가 O(1)일 거라 생각했다. 이번에 한 문제를 풀면서 O(N)이라는 걸 알게 됐다. 

STL에서 삽입, 삭제에 시간복잡도가 O(1)로 사용할 수 있는 컨테이너는 list다. list는 들어만 보고 vector나 queue를 쓰면 되니까 크게 필요성을 느끼지 못했었다. 그런데 시간복잡도에 대한 고려를 해보면서 시간제한이 있는 문제를 풀 때는 list를 써야된다는 것을 알았다.

list 는 시퀀스 컨테이너이고, 노드 기반의 컨테이너이다. (vector와 deque는 배열 기반 컨테이너)

따라서 list는 중간에 데이터 삽입이나 삭제가 자주 발생 할 경우 사용하면 좋다.(at, [] 를 통해 원소에 접근할 수 없기 때문에 랜덤접근을 사용할 경우에는 list보다 vector를 사용하는 것이 좋다.)

헤더파일과 type은 다음과 같다.

#include<list>

list<자료형> 변수명;

list<자료형>::iterator 변수명;

list<자료형>::reverse_iterator 변수명; (사실 처음 들어본 반복자다. 그냥 iterator일 때와 다르게 반대로 ++, -- 된다! 신기함!)

list<자료형>::size_type 변수명;

<list의 메소드>

메소드	설명
begin()	list의 첫번째 위치를 가리킨다.
end()	마지막 위치의 다음을 가리킨다. (for문에서 != list명.end()를 사용하는 이유)
ex)	list<int> a;  for(list<int>::iterator iter =a.begin(); iter != a.end(); iter++) cout<<*iter<<endl;
rbegin(), rend()	역방향으로 첫번째, 마지막 위치를 가리킨다. reverse_iterator를 반환하기 때문에 이걸로 받아줘야 한다.
push_front(넣을 데이터)	첫번째에 데이터를 추가한다.
push_back(넣을 데이터)	마지막 위치에 데이터를 추가한다.
pop_front() pop_back()	첫번째, 마지막 위치의 데이터를 삭제한다.
front(), back()	첫번째, 마지막 데이터의 값을 반환!(iterator X 값을 복사해서 주는 것!)
clear()	모든 데이터를 다 삭제한다.
insert(), erase()	원하는 위치에 데이터를 삽입, 삭제한다.  ex) a.insert(a.begin(), 1);
remove(지울값)	지울값에 해당하는 모든 데이터를 삭제한다.
sort(원하는 조건)	원하는 조건(compare함수)에 따라 정렬한다. sort()만 하면 오름차순으로 정렬된다.
splice()	다른 list로 부터 원소를 가져올 수 있다.
ex)	- splice(붙일 위치, 가져올 컨테이너): 가져오는 컨테이너의 모든 원소를 붙일 위치에 붙인다. - splice(붙일 위치, 가져올 컨테이너, 가져올 원소위치): 가져올 컨테이너의 가져올 위치의 원소를 붙일 위치   에 붙인다. - splice(붙일 위치, 가져올 컨테이터, x, y): 붙일 위치에 가져올 컨테이너의 [x, y) 의 원소를 붙인다. (x는 포함 y는 포함안함)