Object Oriented Programming 3 - Template

OOP의 세 가지 중요한 성질 data abstraction, inheritance, polymorphism 중, polymorphism을 실현 하는 방법 중 하나가 template이다. 이는 Generics 라고도 하며 타입을 설정하지 않고 정의하여 사용자가 원하는 타입에 알맞게 사용할 수 있게 하는 것이다.

 

Generics(template) : Leaving certain key types unspecified to be filled in later.

Function template : 서로 다른 타입에 대해 동일한 operation을 반복해야 할 때(max 함수 등) 타입을 설정하지 않고 generic을 사용하여 function template을 만들 수 있다.

함수 템플릿은 함수가 아니다. 실제로 실행되는 함수는 컴파일러가 입력되는 변수와 템플릿을 보고 알아서 생성해주는 함수가 실행된다. 이를 template instantiation이라 한다. 단, 이 때 자동 타입 전환이 일어나지는 않는다. 따라서 입력되는 타입이 서로 다를 경우, T의 타입을 하나로 결정 해줘야 한다. (max<double> (3, 5.5) -> 이 경우, 3이 double로 변환되어 계산되게 된다.)


Class template : template을 이용해 클래스를 만들어 사용하면 stack, que, linked list 등등의 container class를 만들 때 서로 다른 타입의 정보를 모두 저장할 수 있으므로 편리하다.

일반적으로 이런 template을 이용하여 STL(library)에 stack, que 등등이 모두 implement 되어 있기 때문에 타입에 구애 받지 않고 사용하면 된다. 따라서 C++에서 사용하는 자료구조가 더 일반적이고 올바르게 된다. 타입에 구애 받지 않고 자료 구조를 만들어 놓은 다음, 필요한 타입에 따라 그 때 그 때 불러서 사용하기만 하면 되기 때문이다. (List<int> , List<double> … )

Class/function template의 차이점 : class는 항상 <type>을 적어주어야 한다. 함수의 경우, parameter가 한 종류 일 때는 굳이 필요하지 않지만 클래스는 어떤 자료형으로 해당 클래스를 만들지 알 수 없기 때문에 반드시 <>를 적어주어야 한다. 그렇지 않으면 컴파일러가 해당 클래스를 만들 때 어느 타입을 사용할 지 모르므로 컴파일 에러가 나게 된다.

그리고 공통적으로, parameter가 없어서 컴파일러가 type을 infer할 수 없는 경우는 반드시 <>를 붙여서 정의/호출해줘야 한다. 

STL (standard template library) : 이미 C++에 내장되어 있는 라이브러리. Container, iterator, algorithm이 가장 중요한 세가지 구성 요소. (STL = container class + iterator + Algorithm)

Data structure (container class), function(algorithm)을 내장하고 있음.


1. container class

A holder object that stores a collection of other object with any (user defined or built in) data types

-sequences : sequential collection (vector, list, deque…)

-associative container : set(duplication not allow), map(key & value pair를 저장), hash 등으로 구성. set과 map은 balanced BST(binary search tree)로 구성되어 빠른 검색이 가능하다. (그렇지만 traverse time 때문에 극단적으로 빠르지는 않다) Hash는 검색이 매우 빠르다. (O(1)의 시간복잡도) 그렇지만 data element 사이 order가 없고 implement가 어렵다. (hashing algorithm) 따라서 그냥 STL에 있는 hash를 사용하면 편리함.

-container adapters : implemented on top of another container (stack, queue, priority queue …)

 

2. Iterator

Not a pointer, but way to use iterator is Similar to pointer, implemented for each type of container, elements of containers can be accessed through iterator. (stack 의 top pointer 같은 것). Way to access to data elements in container class. (data element에 접근하는 interface를 제공) Algorithm can access to container through the iterators.

Iterator : represent certain position in a container (like pointer). Iterator is not pointer but it behaves like pointer. Iterators are a generalization of pointer. 그러나 작동방식이 같으므로 *나 ->, ++, --, ==, != 등등의 포인터 연산자를 iterator에도 사용할 수 있다.

List/vector/deque 등 container 클래스에 따라 알맞은 iterator가 존재하여 list<int>::iterator p; vector<float>::iterator vp; 처럼 선언하고 사용.

하나만 사용하면 하나의 element를 가리킴. 쌍으로 사용하면 range를 나타냄.

주로 begin()을 할당하고 end()와 같지 않을 때 까지 순환하는 식으로 iterator를 사용함. 이 때 end()는 마지막 element를 지나서 그 뒤를 가리킨다. (next to the last element) 이 개념은 iterator를 쌍으로 사용하여 범위를 나타낼 때도 동일하게 적용된다. It1, it2 -> [it1, it2) (it1은 포함, it2는 미포함)

이런 iterator를 사용하면 편리한 이유는 하나의 함수가 서로 다른 container class에 대해 구별하지 않고 element에 access 할 수 있게 해주어 STL algorithm과 container를 구분 지을 수 있게 해주기 때문이다.

STL에 정의된 sort, find 등등 수많은 알고리즘들을 container에 따라 따로 정의하지 않고 iterator를 받아 어떤 container class에도 작동하게 해준다. Algorithm을 정의할 때 iterator나 container의 정보, iterator를 어떻게 움직여야 하는지에 대한 정보들이 없다. (vector라면 다음 원소, list라면 포인터가 가리키는 것. Set(tree)라면 순회. Container에 따라 다음 element를 찾는 방법(logic)이 서로 다르다. 그렇지만 각 type의 iterator는 container에 따라 이런 것들이 implement되어 있으므로 값을 증가시킴으로써 이런 서로 다른 방법의 순환을 동일하게 나타낼 수 있다.) 그렇지만 어떤 container와 해당 iterator에 대해서 사용할 수 있다. 따라서 중요한 것은 이런 세부적인 implement가 algorithm(function)에서 해주지 않아도 template(container/iterator)에서 이미 정의되어 있다는 것이다. 따라서 algorithm(function)은 container independent 하고, 각 container의 implement는 각 container에 들어 있다.

begin 등등은 built in type이 아니라서 원래라면 ++ 등 사용 불가. 그리고 어떤 containe인지에 따라 다음 원소를 찾는 방법도 다름. 그렇지만 template(container/iterator)에서 모두 implement(각각의 container iterator에서 operator overloading이 됨) 되어 있어서 각 함수는 신경쓰지 않아도 됨. 따라서 함수의 코드 (알고리즘)은 그런 것을 신경 쓰지 않고 그냥 자신의 논리만 서술하면 된다.

 

3. Algorithm : Perform operations on STL objects. Header <algorithm>을 포함해야 됨.

Vector : kind of superset of array

데이터를 저장하는 방식은 배열과 비슷하지만 크기를 automatically resize 할 수 있다는 것이 차이점. (when call pushback function in STL)

Elements are stored in contiguous(=continuous, 연속적인) storage location. (just like array) 이것이 배열과 벡터의 가장 중요한 요소 중 하나이다. (좋은 방향으로) 왜냐하면 index화 하여 검색이 편리하기 때문이다. (directly access = random access, O(1)) 따라서 각 element에 대한 검색이 매우 빠르게 가능하다. (by index) linked list(O(n))이나 tree(O(logn))에 비해 빠르다.

그러나 중간에 입력/삭제를 할 경우 그 뒤의 element를 모두 한 칸 씩 당기거나 밀어야 하므로 O(n)의 시간이 걸린다. 따라서 비효율적이다. 반대로 linked list는 중간에 입력/삭제를 할 때 O(1) 밖에 걸리지 않으므로 효율적이다.

Advantage of vector (compare to array) : able to resize itself automatically when inserting or erasing a vector element

Disadvantage of vector (compare to array) : 동적할당을 위한 시간이 필요하다. Performance(speed) is not good compare to array. Because it’s dynamic memory allocation and memory management is done during run time which makes it slower. Array is static memory so allocation is occurred in compile time and not affect in run time. 그러나 이 차이는 매우 적고 현대의 하드웨어는 매우 빠르기 때문에 벡터의 편리성을 사용하는 것이 좋다. 단 빠른 반응이 필요한 경우에는 배열을 사용하는 것이 더 좋을 때도 있다. (스마트 폰의 스크롤 등)

vector를 통해서 user input을 받을 경우 크기를 정해주지 않고 그냥 pushback을 하고, size()로 개수를 쉽게 셀 수 있다는 것을 알 수 있다. 따라서 사용하기가 매우 편리하다.

만약 벡터를 사용할 수 없는 경우(빠른 반응 속도가 필요하다거나 등의 이유로) 배열을 사용해야 한다면, dynamic memory allocation으로 일정 량을 먼저 할당하고, 그 값이 넘을 경우 n 배를 한 배열을 새로 만들어서 그 값을 복사하고, 복사한 배열에 값을 이어서 입력한다. 그 배열도 가득차면 또 n배를 한 배열에 복사하고 이어서 입력하는 방식을 사용하면 된다.

그렇지만 이런 방법은 사용하기 어렵고 implement 하는데 많은 문제가 발생한다. Memory management는 항상 힘들다. 따라서 굳이 이렇게 하지 않고 STL & vector를 사용하면 된다. 실제로 implement된 방법은 언급한 것과 비슷하다. (vector도 dynamic memory allocation으로 크기 변경을 함)

 

STL algorithms : container classes & algorithms that operates on them. Need #include<algorithm>

1. sort()

Vector<T> A;

Vector<T>::iterator p, q;

Sort(p, q); // A의 p부터 q까지 sort.

일반적으로 sort(A.begin(), A.end()); 형태로 처음부터 끝까지 오름차순 정렬 가능. (increasing order)

Sort는 random access sequence container에만 사용가능. 따라서 list는 사용불가. Quick sort의 variant를 사용하여 O(nlogn)의 시간을 보장함. 최근 버전의 STL sort는 worst case에서도 O(nlogn)을 보장한다.

*quick sort : 가장 많이 사용되는 정렬 알고리즘 중 하나. 실용적으로 빠르기 때문 – 평균 O(nlogn), 가장 나쁠 경우 O(n^2). 보통 정렬 알고리즘을 평가할 때 worst를 고려한다. 이 경우 quick sort의 n2는 좋지 않다. 그러나 average case의 nlogn은 빠른 편이기 때문에 사용한다. 따라서 이론적으로 별로 좋지 않을 수 있지만 실용적으로 사용하기 좋은 알고리즘이다.

 

User define type의 경우, 대소 관계를 정의해줘야 정렬을 할 수 있다. 따라서 class에서 static bool 등으로 정의해주어야 한다. (static이 아니면 object에 dependent 하기 때문) -> sort(a.begin(), a.end(), student::comp_a); 등으로 비교 함수를 parameter로 주어야 한다.

아니면 operator overloading을 이용하여 >,< 등을 정의하면 sort 함수가 알아서 이를 사용한다.  이 경우 비교 함수를 argurment로 전달해주지 않아도 된다.

또 다른 방법은 functor(function object)를 이용하는 것이다. Functor는 클래스의 오브젝트이지만 함수처럼 작용함. 따라서 1번 방법처럼 sort에 매개변수로 주어질 수 있다.

마지막으로는 lambda function을 이용하여 sort 변수에 계산 방법을 설정할 수 있다. 이 함수는 이름이 없으므로 argument에 full implementation을 서술해야 한다.

 

2. find()

P=find(a.begin(), a.end(), “targetString”); // 찾고자 하는 value가 있는 iterator를 반환.

Sequence를 따라 순차탐색을 하고 exact match value가 있어야 한다. 이 때 특이한 점은, iterator를 순차탐색하면서 해당 value와 찾고자 하는 값을 ==으로 비교한다는 것이다. 따라서 user define class이면 ==operator도 overloading을 해주어야 한다. 당연하게도 built in type의 find는 굳이 해줄 필요 없다.

Find_if(p, q, func) 함수는 범위 내에서 적용한 함수의 값이 true가 되는 맨 처음 iterator를 반환한다.

 

Transform : input container의 원소들에 대해 operation을 적용한 결과를 반환. 즉, list의 각 원소에 연산을 적용할 수 있음. (apply operation to each element sequentially and return the result) 이 때 어떤 리스트의 시작과 끝 iterator, 값을 저장할 container의 iterator, operation(함수)가 필요하다. 리스트의 시작과 끝까지 연산을 적용한 값을 output container의 iterator가 가르키는 곳부터 저장한다. 또는 input을 두 개 넣어서 두 리스트의 input을 각각 받아 연산을 적용하고 저장할 수도 있다. 이 때도 두 번째 리스트는 시작 iterator만 있으면 된다. 저장도 마찬가지로 동일하게 하나의 iterator만 있으면 된다.

이런 transform은 병렬 처리에 사용될 수 있다. Transform은 operation을 element에 sequentially apply 하는 것이므로 각 작업을 코어에 나누어 동시에 작업할 수 있다. 따라서 각 원소에 적용하는 여러 작업을 동시에 할 수 있다. Transform 뿐 아니라 sort 함수 등 다른 stl function도 모두 병렬화 하도록 코드를 짜면 멀티 코어를 사용하여 더 빠르게 연산할 수 있다.