잘 알다시피 프로그램은 자료 구조와 알고리즘으로 구성된다. 자료 구조는 처리하고자 하는 데이터를 표현하는 방법이고 알고리즘은 이 자료들을 가공하여 유용한 정보를 생산하는 기법이다. 좋은 프로그램을 만들려면 이 두 가지가 모두 필요하며 어느 한 쪽이 허술하면 전체적인 프로그램의 질이 떨어진다.
어떤 자료 구조를 사용할 것인가는 프로그램의 특수한 상황에 따라 달라진다. 대용량의 자료를 빠른 속도로 읽어야 한다면 배열이 적합하고 삽입과 삭제가 빈번하다면 연결 리스트가 유리하다. 또한 자료를 관리하는 방법이 일정하다면 스택이나 큐같이 입출력 순서가 미리 정해져 있는 자료 구조를 사용해야 한다. 각 자료 구조마다 고유한 특징과 장단점이 있어서 모든 형태의 데이터에 다 어울리는 이상적인 자료 구조는 없으며 상황에 따라 가장 효율적인 자료 구조를 선택해야 한다.
자료 구조를 조작하는 알고리즘은 헤아릴 수 없이 많다. 삽입, 삭제, 추가, 검색, 정렬, 뒤집기, 병합, 추출, 누적 합계 등의 일반적인 알고리즘외에도 각 자료 구조에만 사용할 수 있는 독특한 알고리즘들이 존재한다. 데이터가 조직화되는 내부 구조와 관리 방법이 자료 구조마다 상이하기 때문에 매 자료 구조마다 알고리즘의 구현도 다르다.
한 번 만든 자료 구조나 알고리즘을 수정없이 재사용할 수 있다면 좋을 것이고 이런 시도는 오래 전부터 있어 왔다. 그 중의 하나가 바로 객체 지향 프로그래밍 방법인데 OOP는 재사용성에 있어서 탁월한 성능을 보여주며 그 성능이 이미 입증되었다. OOP이후의 또다른 시도인 STL은 일반화 프로그래밍 기법이라는 좀 더 발전된 개념의 재사용성을 제공한다. 일반화(Generic)는 객체 지향의 다음 세대라고 일컬어지는데 두 가지 측면에서 일반성을 제공한다.
① 임의 타입에 사용할 수 있는 자료 구조를 만들 수 있다. 정수, 실수 등의 기본 타입은 물론이고 사용자 정의형 타입과 그 유도형까지도 관리할 수 있는 자료 구조를 정의할 수 있다. 자료 구조의 일반성을 구현하기 위해 인수로 전달된 타입으로 클래스를 정의하는 C++의 템플릿 문법이 사용된다.
② 자료 구조의 형태나 내부 구조에 상관없이 임의의 데이터 집합에 적용할 수 있는 일반화된 알고리즘을 제공한다. 자료 구조에 상관없이 사용 방법이 동일하므로 어떠한 형태의 데이터에 대해서도 적용할 수 있다. 논리적으로 비슷한 작업은 같은 방법으로 수행할 수 있으며 이를 위해 반복자라는 일반화된 포인터를 사용한다.
이런 일반화의 개념에 의해 자주 사용되는 자료 구조와 알고리즘을 제공하는 라이브러리가 바로 STL이다. 개발자는 자료 구조를 일일이 구현할 필요없이 STL이 제공하는 자료 구조를 선택해서 사용할 수 있으며 하나의 알고리즘을 임의의 자료 구조에 대해 일관되게 사용할 수 있다. 최소한의 의사표현만으로 모든 처리가 자동으로 수행된다.
STL은 Standard Template Library의 약자이다. 일단은 라이브러리이되 템플릿의 집합을 제공하는 라이브러리이며 현재 C++의 표준으로 채택되어 있다. C 언어가 printf, strcpy, atoi 등 함수 수준의 라이브러리를 제공하는데 비해 C++은 템플릿 수준의 훨씬 더 범용적인 라이브러리를 제공한다.
사용 방법을 연구하기 전에 먼저 간략한 역사에 대해 알아보자. STL은 1979년경 알렉산더 스테파노프(Alexander Stepanov) 한 사람에 의해 창안되었다. 이 시기는 스트로스트룹이 C++의 초기 디자인을 한 시점과 거의 일치한다. C++과 STL은 최초 따로 탄생했고 각자의 길을 걸어가다가 90년대 중반에 비로소 하나로 통합되었다.
스테파노프는 최초 Ada로 STL의 원형을 작성했는데 Ada는 일반화 프로그래밍을 위한 적절한 특징들을 많이 가지고 있었다. 그러나 Ada 자체가 대중의 인기를 얻지 못하고 C++이라는 더 적합한 언어가 발표됨에 따라 C++로 개발 언어를 변경했다. 스테파노프가 STL을 발전시키는 동안 C++은 템플릿을 언어의 일부로 지원하기 시작했다. C의 강력한 포인터와 C++의 템플릿 기능은 STL을 구현하기 위한 최적의 환경이었다.
연구가 진행되면서 Dave Musser, Meng Lee 등의 공동 작업자들이 합류하여 STL을 더욱 정교하게 발전시켜 나갔으며 많은 사람이 STL로 프로젝트를 작성하기 시작했다. 결국 STL은 94년 7월 ANSI/ISO의 최종 승인을 거쳐 국제 표준이 되었으며 98년 C++ 표준인 14882의 일부로 채택됨으로써 C++ 라이브러리의 근간을 이루게 되었다. 표준 채택 이전에도 각 컴파일러 제작사들은 STL을 자사 라이브러리의 일부로 이미 제공하고 있었으며 실제 프로젝트에서도 활용되었다. 현재는 국제 표준으로 그 구조가 통일됨으로써 호환성과 이식성을 걱정할 필요없이 마음놓고 STL을 사용할 수 있다.
이 장 이후의 예제는 가급적이면 최신 컴파일러로 실습을 진행하도록 하자. 예제가 간단해서 비주얼 C++ 6.0으로도 대부분 잘 컴파일되기는 하지만 불필요한 경고가 출력되기도 하고 새로 추가된 기능에 대해서는 제대로 컴파일하지 못하는 문제와 약간의 버그까지 있어 실습이 원활하지 못하다. 비주얼 C++ 8.0이나 Dev-C++은 표준을 잘 준수하므로 최신 컴파일러들로 예제를 컴파일하기 바란다.