• 5 min read

stl[0] - Template란?

알고리즘을 위한 STL
stl[0] - Template란?

저는 알고리즘 문제풀이를 C언어로 시작했지만, STL의 존재로 인해 요즘은 C++로 알고리즘 문제풀이를 시작하는것이 매우 편리합니다.

STL, Standard Template Library를 구성하고 있는 핵심 개념인 Template에 대해 알아보도록 합니다.

Template

템플릿, 번역하자면 틀 정도인 Template는 그 단어에 맞게 틀에 박힌 찍어낼수 있는 무언가를 의미합니다. 여기서는 소스코드를 틀에 맞추어 찍어낼 수 있다는 의미로 쓰이고 있는데, 먼저 문제상황을 정의해봅시다.

Problem

저는 두 자료형 중 더 큰 값을 반환하는 간단한 함수를 작성하고 싶습니다. 일반적인 경우 int에 대한 최댓값 반환 함수는 아래와 같습니다.

int max(int a, int b){
  if(a > b) return a;
  return b;
}

이 문제를 골치아프게 만드는 지점은 자료형에 있습니다. float/double/char/string 등등에 대한 모든 데이터 타입에 대한 max 함수를 따로 다 만들어 줘야 하고, 이들은 C++에서의 함수 오버로딩을 통해 정상적으로 동작합니다.

함수를 매번 만드는게 상당히 귀찮을 듯 한데, 한번만 작성해서 사용할 수 없을까요?

Solution

C++의 함수 템플릿 기능을 사용하면 위와 같은 문제를 극도로 단순하게 해결할 수 있습니다. 변수 자료형에 마치 빈칸을 뚫어놓듯이 template <typename T> 라는 빈칸을 뚫어놓고, 실제 자료형처럼 사용할 수 있습니다.

template <typename T>
T max(T a, T b){
  if(a > b) return a;
  return b;
}

Class Template

이제 STL의 핵심 구현 방법 중 하나인 Class Template에 대한 새로운 문제 상황을 정의해봅시다.

Problem

저는 세그먼트 트리 클래스를 작성해놓고 백준문제를 날먹하고 싶습니다. 백준 문제에서 segtree에는 int형이나 long long형 등 다양한 자료형이 들어가게 되는데, 이 모두들에 대한 세그트리를 미리 작성해놓아야 할까요?

Solution

클래스 템플릿을 통하면 클래스의 멤버 변수, 메소드의 반환형 등의 타입을 빈칸으로 남겨둘 수 있습니다.

template <typename T>
class SegTree{
  T tree[1234567];

  void update(...){
    ...
  }

  T query(...){
    ...
  }
}

세부 소스코드 구현은 생략합니다.

이때 주의해야 할 점으로 클래스 내부에서 template를 사용하는 경우, 실제로 해당 클래스의 인스턴스를 만들때 타입명을 명시해주어야 합니다.

int main(){
  SegTree<int> A; // int타입 세그트리
  SegTree<double> B; // double타입 세그트리
  ...
}

다음과 같은 구현을 통하여 다양한 타입에 대응하는 세그트리, 즉 자료구조 를 정의할 수 있다는게 핵심입니다.

STL

C++ Standard Library - cppreference.com
cppreference.com

세그먼트 트리와 같은 심화적인 자료구조에 대한 정의를 해두진 않았지만, 다양한 자료구조와 메서드들이 template를 활용해서 미리 구현되어 있습니다. 따라서 이러한 자료구조를 처음부터 구현할 필요 없이, 제공되는 템플릿에 맞게 바로 사용할 수 있기에 대단히 편리합니다.

STL은 크게 네가지 구성요소로 이루어져 있습니다.

Container

자료구조에 대한 사전 정의된 소스코드
  • array
  • vector
  • stack
  • queue
  • deque
  • set, unordered_set
  • map, unordered_map
  • priority_queue (min/max heap)

등등의 자료구조들이 정의되어 있습니다.

Iterator

Container에 대한 일관적인 접근 방법의 제공

반복자 의 구현체입니다. 앞서 보았던 자료구조들에 대한 일관된 탐색 방법을 제공하고 있으며 set이나 priority_queue같은 비선형 자료구조에 대해서도 반복문 한번으로 순회가 가능하도록 합니다.

Algorithm

사전 정의된 알고리즘 함수들
  • min/max element
  • sort
  • lower/upper bound

등의 자주 사용하는 알고리즘들이 미리 구현되어 있습니다. 반복자를 인자로 받기 때문에 Container와 섞어서 사용하면 좋습니다.

Functor

function call operator ()를 오버로딩

함수 객체를 전달하여 Algorithm에 정의된 함수들로 하여금 보다 복잡한 처리를 진행하게 할 수 있습니다.

  • Greater<int>()

정도가 PS에서 유의미하게 쓰이는 듯 하고, 보통 알고리즘 문제를 해결할 때 펑터를 직접 정의해서 사용하지는 않습니다.

앞으로

STL의 넓은 개념들을 한개 한개씩 짚으며 약팔이를 해보고자 합니다. 시간복잡도에 대한 이해가 있으면 추후 발행될 글들을 보기 편할듯 싶습니다. STL을 사용하지 않는 구현체와 STL을 사용하였을 때의 소스코드 길이를 비교해보면서, STL을 사용해 해결할 수 있는 수많은 백준 문제들을 짚어볼 예정입니다.

Prerequisites

  • Time Complexity O(f(n))
  • Data Structures
  • Basic C++ Knowledge
  • Algorithms
    • Solved AC 기준 Silver V ~ Gold I 정도
    • binary search
    • sorting

추천 글

featured