일반화 segment tree 구현 - 1. 일반화 프로그래밍이란?

평소와 다름없이 stl로 알고리즘 문제를 풀다가 문득 궁금증이 생겼다.

stl은 queue, vector 등등과 같이 어떤 자료형이든 사용할 수 있게 일반화되어 있는데 어떻게 이런 것이 가능할까?

언뜻 보기에 자바의 제네릭과 같은 기능을 하고 있었기에 찾아보니 c++에도 제네릭과 비슷한 template라는 것이 존재했다. 아래는 template의 구조체와 함수 각각에서의 사용 예시이다.

#include<bits/stdc++.h>
using namespace std;

template<typename T> struct s {
	T val;
}; //구조체에서의 사용

template<typename T> T mySum(T a,T b) {
	return a+b;
} // 함수에서의 사용

int main() {
	
	s<int> s1={3};
	cout<<s1.val<<"\n";
	//출력: 3  
	
	s<string> s2={"abc"};
	cout<<s2.val<<"\n";
	//출력: abc  
	
	int a=3,b=5;
	double c=1.2,d=3.6;
	
	cout<<mySum(a,b)<<"\n";
	//출력: 8
	
	cout<<mySum(c,d)<<"\n";
	//출력: 4.8  
}

또한 아래처럼 선언하여 하나의 함수나 구조체에 여러 타입을 두는 것도 가능하다.

template<typename T1,typename T2> struct s {
	T1 val1;
	T2 val2;
};

이런식으로 데이터와 무관한 코드를 작성하는 것을 일반화 프로그래밍이라고 한다.

이쯤 공부하다 보니 일반화 프로그래밍으로 직접 자료구조를 만들어 보고 싶다는 생각이 들어 세그먼트 트리를 일반화 프로그래밍으로 만들어보기로 했다.