STL 뜯어보기 - std::map

알고리즘 수업에서 C/C++로 레드블랙트리를 직접 구현한 후 프로그램을 만드는 과제가 있었습니다. 되도록이면 코드를 나중에 읽거나 활용하기 편리하도록(STL을 제끼고 쓸 일이 있을까 싶지만-_-), 또는 적어도 내가 코딩하는 데 메소드의 일관성을 유지할 수 있도록 최대한 STL에 가깝게 짜기로 했습니다. STL의 map이 레드블랙트리로 구현되어 있다고 들어서 최대한 map의 인터페이스를 참고하여 최대한 동일하게 작성해 보았습니다. 트리의 순회를 구현하려 하니까, STL 상으로는 레드블랙트리(map)클래스만에서 되는 것이 아니라 iterator 객체를 이용해서 ++하며 iterator.end()까지 돌아야 한다는 것을 깨달았습니다. 이 구절에서 실제 STL 구현에서는 이터레이터를 어떻게 구현하는지 궁금해져서 GNU 라이브러리 소스를 열어보기로 했습니다. STL의 코드는 libstdc++에 있으며 이는 git://gcc.gnu.org/git/gcc.git에서 GCC 자체의 소스코드와 함께 호스팅되고 있습니다. 또 같은 소스가 깃허브 https://github.com/gcc-mirror/gcc에서 미러링되고 있습니다.