[Programming/C++] STL (Standard Template Library)

STL은 이름 그대로 템플릿을 사용해서 만들어진 라이브러리다. STL은 일반적으로 많이 사용하는 클래스와 함수들이 만들어져 있는데, 예를 들어 링크드 리스트 클래스, 동적 배열 클래스, 정렬 함수, 검색 함수 등과 같이 범용적인 클래스와 함수들이 있다. 또한 이런 클래스와 함수들은 템플릿으로 만들어져 있기 때문에 확장이 용이하다. 

STL은 사용함으로써 얻을 수 있는 장점들이 있다.

첫번째, STL은 표준이다. 이는 지구 반대편에 있는 개발자도 나와 똑같은 클래스와 함수를 사용한다는 것을 의미한다. 때문에 상대방이 작성해놓은 코드를 쉽게 알아볼 수 있다.
두번째, STL은 전문가들이 만들어 놓은 것이기 때문에 직접 만든 것보다 효율적이고 안전하다. 물론 엄청난 실력자라 STL에 있는 것보다 훌륭하게 만들 수 있겠지만 차라리 그 시간 동안 생산성 있는 다른 일을 하는 것이 유익할 것이다.

STL 컨테이너

컨테이너(Containers)란 다수의 정보를 담는 역할을 하는 클래스를 말한다. 보통 링크드 리스트나 동적인 배열, 큐(Queue), 맵(Map) 등의 클래스들을 컨테이너라고 부른다. 

list 클래스 사용하기

#include <list>
#include <iostream>

int main() {
    // int 타입을 담을 링크드 리스트 생성
    std::list<int> intList;

    // 0~9까지 링크드 리스트에 넣는다.
    for (int i = 0; i < 10; ++i) {
        // list 클래스의 멤버함수를 이용하여 노드를 추가한다.
        // 리스트의 뒤쪽(back)에 노드를 추가(push)하는 역할을 한다.
        intList.push_back(i);
    }

    // 5를 찾아 제거한다.
    intList.remove(5);

    // 링크드 리스트의 내용을 출력한다.
    std::list<int>::iterator it;
    for (it = intList.begin(); it != intList.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}


// 결과
0 1 2 3 4 6 7 8 9

STL 역시 C++ 표준 라이브러리므로 std 네임스페이스 안에 정의되어 있다. 또한 템플릿 클래스므로 보관할 데이터의 타입을 지정해줄 필요가 있다. 위의 코드에서는 int 타입의 값을 보관할 수 있는 링크드 리스트를 만들기 위해서 std::list<int> 처럼 해주었다.

iterator 클래스의 객체인 it를 생성하고 있다. std::list<int>:: 처럼 선언한 것은 iterator 클래스를 정의한 위치를 알려주기 위한 용도일 뿐이다. 중요한 것은 iterator 클래스의 객체를 생성하고 있다는 점인데, 바로 이 iterator 클래스가 노드의 위치를 가리키는 역할을 한다.

즉, iterator 객체 it를 사용해서 첫번째 노드부터 마지막 노드까지 반복적으로 가리키려는 것이다.

intList.begin()과 intList.end() 함수를 호출하고 있는데, 각각 리스트의 첫번째 노드와 마지막 노드의 위치를 반환하는 멤버 함수다. 또한 it에 의해서 it는 다음 노드를 가리키게 되는데, 마치 배열의 원소를 가리키는 포인터에 ++p처럼 해주면 다음 원소를 가리키게 되는 것과 같다. iterator 클래스를 만들 개발자가 일부터 포인터를 흉내내기 위해 ++ 연산자를 오버로드한 것이다.
마지막으로 *it로 노드에 보관된 값을 읽어오고 있다. 이 역시 포인터에 *p 처럼 해주면 포인터가 가리키는 곳에 보관한 값을 읽어오게 만드는 것과 같다. 마찬가지로 iterator 클래스를 만든 개발자가 일부러 포인터를 흉내내기 위해서 *연산자를 오버로딩한 것이다.

STL에서는 다음과 같은 컨테이너 클래스들을 제공한다.

클래스	요약
vector	동적인 배열, 동적으로 원소의 개수를 조절할 수 있는 배열이다.
list	링크드 리스트
deque	배열과 링크드 리스트의 장점을 모아놓은 컨테이너. 배열만큼 원소에 접근하는 시간이 빠른 동시에 맨 앞과 끝에 원소를 추가하고 제거하는 시간은 링크드 리스트만큼 빠르다.
map	맵은 원소를 가리키는 인덱스까지도 다양한 타입을 사용할 수 있다. 예를 들어 다음과 같이 문자열 타입의 인덱스를 사용할 수도 있다. map<string, string> m; m["add"] = "더하기";

중요한 것은 이런 컨테이너 클래스들이 모두 유사한 인터페이스를 가진다는 점이다. 예를 들어 list 클래스가 아닌 vector 클래스를 사용하는 코드를 만들고 싶다면, 간단하게 list라고 적힌 부분을 vector라고만 바꿔주면 된다. 어차피 사용법은 동일하기 때문이다.

바로 이 대목에서 STL의 철학을 배울 수가 있다. 최소한의 소스 코드 수정으로 컨테이너를 다른 것으로 교체할 수 있는 것이다. 예를 들어 노드에 빨리 접근하는 것이 중요한 프로그램이 있다면 vector 클래스를 사용하는 것이 좋다. 배열이 링크드 리스트보다 노드에 대한 접근 속도가 빠르기 때문이다.

그런데 나중에 프로그램의 성격이 변해서 노드의 추가나 삭제가 빈번하게 일어난다면 list 클래스를 사용하게 바꿀 필요가 있다. 링크드 리스트는 노드를 추가하고 제거하는 속도가 배열보다 훨씬 빠르기 때문이다. STL을 사용하면 이렇게 컨테이너 클래스를 바꿔야 하는 경우에도 단지 몇 줄의 코드만 수정하면 된다. 이런 특징은 프로그램의 개발이나 유지보수 시간을 단축하는 데 큰 도움이 된다.

---

STL 알고리즘

STL의 알고리즘(Algorithm)이란 STL에서 제공하는 함수들을 의미한다. 예를 들어 정렬(sortring)이나 검색(searching)과 같은 알고리즘을 구현해놓은 함수들을 생각해볼 수 있다. 다음의 예제를 살펴보자.

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    // 동적 배열을 생성해서 임의의 영문자 추가
    std::vector<char> vec;
    vec.push_back('e');
    vec.push_back('b');
    vec.push_back('a');
    vec.push_back('d');
    vec.push_back('c');

    // sort() 함수를 사용해서 정렬. 첫번째와 마지막 원소의 위치를 인자로 건네준다.
    std::sort(vec.begin(), vec.end());

    // 정렬 후 상태 출력
    std::cout << "vector 정렬 후" << std::endl;
    std::vector<char>::iterator it;
    for (it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it;
    }

    // 일반 배열
    char arr[5] = { 'd', 'c', 'b', 'a', 'e' };
    
    // sort() 함수 사용해서 정렬. 평범한 배열까지도 정렬할 수 있다.
    std::sort(arr, arr + 5);

    // 정렬 후 상태 출력
    // vector 클래스를 비롯한 컨테이너 클래스의 사용 방법이 평범한 배열과 매우 닮아있음을 
    // 보여주기 위해 일반적인 배열을 STL 컨테이너와 유사한 방법으로 탐색하는 코드 작성.
    std::cout << std::endl << std::endl << "일반 배열 정렬 후" << std::endl;
    for (char* p = arr; p != arr + 5; ++p) {
        std::cout << *p;
    }

    return 0;
}


// 결과
vector 정렬 후
abcde

일반 배열 정렬 후
abcde

배열의 첫번째 원소와 마지막 원소의 위치(메모리 주소)만 넘겨주면 sort() 함수가 알아서 정렬해준다.

위의 코드에서 vector 클래스를 사용했는데 list 클래스와 비교했을 때 사용상의 차이점이 전혀 없다는 것을 알 수가 있다. 또한 일반적인 배열까지도 STL의 컨테이너와 유사한 방식으로 다룰 수 있다는 점이다.

이 부분에서도 STL의 철학을 엿볼 수가 있는데, 정보를 담는 컨테이너와 정보를 처리하는 알고리즘이 서로 독립적이다. 예를 들어 sort() 함수는 어느 한 컨테이너에 특화된 것이 아니라 모든 컨테이너를 다룰 수 있게 범용적으로 만들어졌다. 이런 특징은 제네릭 프로그래밍이라는 관점에서 알아볼 수 있다.

아래의 표는 유용한 알고리즘을 간단하게 정리한 것이다.

함수	요약
find()	선형 검색 알고리즘. 선형 검색이란 첫번째 원소부터 하나씩 비교해보는 방법을 말한다.
replace()	특정한 값을 가진 원소를 찾아 다른 값으로 교체한다.
reverse()	원소들의 순서를 거꾸로 뒤집는다.
sort()	오름차순으로 정렬한다.
binary_search()	이진 탐색 알고리즘. 이진 탐색이란 원소들이 정렬되어 있는 경우에 사용할 수 있는 탐색 방법 중 하나다.

---

참고로 list 클래스는 sort() 함수를 사용할 수 없다.

sort()함수는 어떤 컨테이너라도 다룰 수 있게 구현되어 있다고 하였지만 모두 그렇지는 않다. 이는 컨테이너마다 물리적인 차이점을 가지고 있기 때문인데, 예를 들어 링크드 리스트를 구현하고 있는 list 클래스는 링크드 리스트라는 물리적인 특징 때문에 a[2]처럼 직접적으로 노드에 접근할 수가 없다. 대신에 '헤드 노드의 다음 다음 노드'라는 식으로 밖에 접근할 수 없다.

STL의 컨테이너들은 거의 동일한 인터페이스를 가지고 있지만 이런 물리적인 제약으로 인해서 약간의 차이를 가지고 있는 것이 사실이다. 이런 경우에는 컨테이너에 특화된 알고리즘 함수를 사용할 수가 있는데, list 클래스의 경우에는 링크드 리스트에 적합하게 구현된 sort() 함수를 멤버 함수로 가지고 있다. list 클래스를 정렬하려면 이 sort() 함수를 사용해야 한다.

---

제네릭 프로그래밍 (Generic Programming)

제네릭 프로그래밍이란 객체지향 프로그래밍처럼 프로그램을 만드는 방법론 중 하나다. 제네릭 프로그래밍에서 가장 중요하게 생각하는 것은 정보의 타입과 정보를 처리하는 알고리즘을 분리하는 것이다.

위의 STL 컨테이너 클래스들과 알고리즘 함수들이 제네릭 프로그래밍을 적용한 좋은 예가 된다. 예를 들어 sort() 함수는 일반적인 배열이나 vector, deque 등과 함께 사용할 수 있게 범용적(Generic)으로 설계됐다. 여기서 컨테이너들을 '정보의 타입'이라고 볼 수 있고, sort() 함수를 비롯한 알고리즘 함수들을 '정보를 처리하는 알고리즘' 이라고 볼 수 있다.

이렇게 타입과 알고리즘을 분리하게 되면 여러 가지 장점을 갖게 된다. 우선은 타입과 알고리즘간의 불필요한 연관성이 제거(Decoupling)되는 점을 생각해볼 수 있다. 예를 들어 vector 클래스의 세부 구현을 변경했다고 해도 sort() 함수는 영향을 받지 않을 것이고, 역으로 sort() 함수의 세부 구현을 변경하는 경우에도 vector 클래스는 영향을 받지 않을 것이다.

연관성이 제거되면 자동적으로 재사용성(Reusability)이 증가하게 된다. sort() 함수와 vector 클래스를 항상 함께 사용해야 하는 것이 아니기 때문에 sort() 함수만 가져다가 다른 컨테이너와 함께 사용하는 등의 재사용이 용이해진다. 만약에 컨테이너별로 sort() 함수를 하나씩 만들어서 쓰게 된다면, sort() 함수를 다른 용도로 재사용하는 것이 불가능해진다. 아마도 새로운 컨테이너를 위한 sort() 함수를 새로 만들어야 될 것이고, 불필요한 코드의 중복이 발생할 것도 뻔한 일이다.

또 다른 장점으로는 확장의 용이함을 들 수 있다. 컨테이너와 알고리즘을 분리할 수 있는 이유는 STL의 컨테이너들이 begin(), end()와 같은 공통적인 인터페이스를 유지하고 있기 때문이다. 새로운 컨테이너 클래스를 만들 때 이 공통의 인터페이스를 유지하기만 한다면 STL의 모든 알고리즘을 사용할 수 있게 된다. 마찬가지로 알고리즘 함수를 새로 만들 때에도 이 공통의 약속만 지킨다면 STL의 모든 컨테이너를 사용할 수 있게 된다.

제레릭 프로그래밍의 좋은 예로써 STL을 들 수 있다. 그리고 굳이 STL을 사용하지 않더라도 개발중인 프로젝트에 제네릭 프로그래밍의 철학을 적용할 수가 있다.

또 한 가지 기억해야 할 것이 바로 템플릿의 역할이다. 템플릿을 사용하면 모든 타입을 다룰 수 있는 코드를 손쉽게 작성할 수 있고, 이는 결국 타입과 알고리즘을 분리시키는 작업을 간단하게 만들어준다.

지금까지 설명한 것처럼 템플릿을 사용한 제네릭 프로그래밍은 재사용성이 높고 불필요한 중복이 없는 간결한 코드를 만드는 데 중요한 역할을 한다. 게다가 템플릿은 컴파일 시간에 코드를 생성하기 때문에 실행 효율 또한 좋다. 그러므로 잘 익혀두기만 한다면 템플릿과 STL은 높은 생산성과 성능을 동시에 가져다 주는 커다란 무기가 될 것이다.

다형성

다형성을 사용해도 타입과 알고리즘을 분리할 수 있다. 같은 부모를 가진 타입이라면 실제 객체 타입에 상관 없이 동일하게 다룰 수 있기 때문이다. 하지만 템플릿을 사용한 경우가 조금 더 빠르게 실행된다. 가상 함수를 사용하는 경우에는 어떤 클래스의 함수를 호출해야 하는지 계산하는 시간을 소모하지만 템플릿은 컴파일 시간에 미리 계산해서 코드를 만들어 두는 것이기 때문이다. 하지만 템플릿을 사용하게 되면 컴파일러가 만들어낸 코드가 많아지기 때문에 프로그램의 크기가 커지는 단점이 있다. 또한 디버깅 시에 조금 더 복잡한 경향이 있다.