[C++ STL] 1. list

대학교 2학년 때는 다양한 종류의 stl을 사용했는데, 막상 알고리즘 공부를 하다 보니 stl을 사용하는 횟수가 적어져서 이렇게나마 정리하려고 한다.

List는 sequence container로 상수시간 삽입과 삭제 연산을 할 수 있다. 단순히 말해서 링크드 리스트의 stl 버전이라고 생각하면 될 것 같다. doubly-linked list로 구성되어 있다.

멤버 함수는 다음과 같다(일부만 서술)

begin	iterator의 시작부분을 return한다
end	iterator의 끝부분을 return한다
empty	list가 비었는지 알려줌
size	list의 원소 개수
front	첫번째 원소에 접근한다
back	마지막 원소에 접근한다
assign	새롭게 list를 할당한다(임의의 값)
push_front	맨앞에 원소를 삽입한다
push_back	맨뒤에 원소를 삽입한다
pop_back	마지막 원소를 삭제한다
insert	원소를 삽입한다(임의 위치)
erase	원소를 삭제한다(임의 위치)
clear	list를 초기화한다
sort	list를 정렬한다(기본값 오름차순)
reverse	list의 순서를 반대로한다
merge	두개의 list를 합병한다(정렬하면서)
remove_if	해당 조건에 맞는 원소들을 삭제한다
unique	list의 원소중 중복되는 값을 제거한다

 

* 주의 할 점

erase() 함수를 이용해 list의 원소를 삭제할 때 유의해야 한다.

erase 함수의 return 값은 삭제된 원소 다음에 있는 iterator라고 한다.

			// 16235 백준 
            list<int>::iterator iter;
			for (iter = trees.begin(); iter != trees.end();) {
				if ((*iter) <= current_nutrient) {
					//양분이 충분하면
					current_nutrient -= (*iter); // 양분 먹고
					(*iter)++; // 나이 증가
					iter++;
				}
				else {
					int tmp = (*iter);
					trees.erase(iter++);
					deadtrees.push(tmp); // 큐에 넣는다
					if (trees.empty()) break;
				}

위의 예시는 16235번을 푼 나의 코드의 일부이다. 중요한 부분은 trees.erase(iter++)이다.

처음에는

for(iter=list.begin();iter!=list.end();++iter){
	if(조건) list.erase(iter);
}

이런 식으로 for문에서는 iterator가 계속 하나씩 증가되고 조건이 true라면 iterator가 가리키는 원소를 삭제하는 식으로 했다.

하지만 삭제될 원소가 맨 마지막 원소라면 iterator가 end() 다시 반환하고, for문에서 end()인 iterator를 이용해 다시 ++ 연산을 하려고 하여 에러가 난다.

그래서 for문에서 증가 연산을 하지 않고 그때마다 증가하는 방식으로 바꾸었더니 문제 해결이 되었다.

for( Iterator = List.begin(); Iterator!= List.end(); ) { Iterator = List.erase(Iterator); } 뭐 굳이 ++을 쓰고 싶다면... for( Iterator = List.begin(); Iterator != List.end(); ) { List.erase(Iterator++); } 출처: https://gamepro.tistory.com/263 [게임프로그래밍 자료모음]

++를 사용하지 않고 하는 방법은 위와 같다.

출처에 들어가 보면 더 자세히 설명되어 있으니 들어가 보는 것도 좋을 것 같다.