stl에는 iterator가 없는 컨테이너도 있다.

>>2013-10-09에 구글 드라이브에 작성.

>>2015-01-13에 에버노트로 이동.

1.이야기

회사에서 타일맵 위에서의 A-star 길찾기 알고리즘을 구현할 일이 생겼었다. astar는 고3 때 수능 끝나고 만들던 게임에서 이미 한번 구현 해 봤었고 언어는 java로 회사 엔진에서 쓰는 C++과는 다르지만 그 때의 소스코드도 남아있었기 때문에 그냥 레거시 코드에 맞춰서 적당히 수정해 주면 된다고 생각했었다.

오브젝트가 움직일 수 없는 타일 마스킹 하는 배열 추가, 로직에 맞춰 쓸모없는 코드를 정리해 주기만 하면 문법상 다른 부분만 살짝 고치면 됐으니까. 다른 부분은 다 생각대로 됐었는데 한 가지 문제가 생겼던 부분이 있었다. 예전 자바 코드에는 open list의 container를 F값을 기준으로 정렬해 주기 위해 기본 라이브러리의 우선순위 큐를 사용했다. C++ stl의 우선순위 큐도 아마 비슷하겠거니 하면서 그냥 썼는데, 이런 젠장. stl 우선순위 큐에는 특정 iterator가 가리키는 요소를 지우는 remove 함수가 없었던 것이다.

일단 처음 20분동안은 반항을 좀 했었다. ‘나에게 템플릿이라는 문화충격을 가져다 준 그 위대한 STL에 이런 기능이 없을리가 없어’, ‘나의 STL은 그렇지 않아!’ 정도의 느낌이었다. 약간의 방황 끝에 현실을 직시하고 제 정신을 차렸다. 내가 구현하는 기능인 길찾기가 제대로 되는지 알아보기 위해서 성능은 신경쓰지 않은 더미 코드를 만들었다. 우선순위 큐를 리스트로 바꾸고 (벡터로 해봤는데 벡터는 또 이터레이션이 안됨) remove 할때는 리스트를 정렬 한 다음, 맨 앞에 있는 요소를 제거하는 코드였다. 그때 stl에 배신 당했다는 생각에 정신이 없었는지 아니면 귀찮아서 그랬는지, 잘못된 코드를 짰었다. remove할 요소가 항상 F값이 최소라는 보장이 없다는 점을 깡그리 무시해 버렸던 것이다. 그래도 비록 최단 거리는 아니지만 시작점-끝점 사이를 장애물을 피해 가는 경로는 만들어 졌고, 일단 한 숨 돌리게 되었다. 알고리즘이 F값 정렬 방식만 수정하면 돌아간다는 이야기였으니까.

내가 필요한 우선 순위 큐는 첫 번째로, 특정 요소를 지울 수 있는 remove기능이 필요했다. 그 말은 즉, iteration이 되어야 하고. 두 번째로, F값에 따라 규칙을 유지하면서 컨테이너에 데이터를 넣으면서, Position값이 같은 노드가 있을 경우 F값이 작은쪽으로 덮어 씌워주는 기능이 있어야 했었다. 뭐 고도의 설계능력이 필요한 것도 아니었고, 최대 500번 이하의 삽입이 일어나기 때문에 heap을 사용하지 않고 선형 탐색 O(n) 으로도 성능 저하가 일어나진 않을테니, 그냥 최대한 빠르게 내부에 컨테이너로 list를 쓰고 insert / remove 로직 적당히 넣어서 우선순위 큐를 만들었다.

결과는 뭐 버그 몇개 고쳐주니까 잘 작동했다. 꽤나 험악한(나름) 미로도 빠르게 잘 찾는다.

2. 설명

stack, queue, vector등 deque 기반 컨테이너들은 iterator가 없음, 내부 요소에는 오직 pop,push만으로만 접근함. 그 이외의 방법으로 내부의 데이터 꺼내올 수 없음

list기반 컨테이너가 iterator를 가지고 있음

역방향으로 순회하는 iterator는 ::reverse_iterator임. 일반 base iterator랑 형식이 다름.

reverse_iterator에는 base iterator로 바꿀 수 있는 .base()함수가 있음.

방향이나 1칸 차이 주의

References

http://stackoverflow.com/questions/188942/how-do-you-iterate-backwards-through-an-stl-list

http://stackoverflow.com/questions/1830158/how-to-call-erase-with-a-reverse-iterator