문법
STL
Standard Template Library의 약자!
C++에 미리 정의된 라이브러리
템플릿을 사용하는데 이건 Compile-Time polymorphism이다.
4가지 타입으로
- Containers - 데이터를 저장하는 객체
- Functions - 객체를 함수처럼 사용하게 하는 펑션 콜 "()" 을 오버로딩!
- Iterators - Containers안의 데이터[원소]를 포인팅!(가리키게 해주는 포인터)
- Algorithms - 널리 사용되는 함수들(정렬, 최대값, 최소값~ 등등)
Q >STL의 종류 4가지를 서술하시오.
Containers
| Sequence Containers | Container Adapters | Associative Containers |
| 원소를 순차적으로 접근할 수 있다. | 기능이 추가된 자료구조 | 원소끼리 원소의 값들과 관계지어서 만든 자료구조 |
| Array Vector List Deque ... |
Stack Queue Prioirty_Queue |
Set Multi Set Map Multi Map |
시퀀스 컨테이너 : Array(어레이)
C와 달리 자신의 길이를 알고 있다!
Runtime에서 유효한 인덱스인지 확인한다!
std::array<int, 3> arr;
템플릿 패러미터로 T에는 int, N에는 3이 들어가 있고,
T : 원소의 타입 N : 배열의 크기
로 객체를 생성한다.
main.cc에서 위의 구문을 통해서 std::array<int, 3>라는 클래스를 만들게 되어 arr이라는 객체를 생성.
std::array<int, 3>과 std::arrat<int, 4>는 전혀 다른 클래스라는 거 인지하기!
유효하지 않는 인덱스에 원소 값을 넣어도 에러는 발생하지 않는다!
하지만! .at() 함수를 이용해서 유효하지 않는 인덱스에 접근하면 런타임 에러가 발생한다!
at() 함수에서 인덱스가 유효한지 아닌지 검사한다! [미리 구현된 템플릿에서 Error-exception 처리(try-catch) 해준 거야!- 여기까지는 몰라도 이용하는데 문제는 전혀 없다.]
시퀀스 컨테이너 : Vector(벡터)
어레이와 달리 벡터는 길이가 한정되어 있지 않고 확장이 가능하다!
어레이와 마찬가지로 Random Access가 가능하여 인덱스를 통해 원소의 값에 접근할 수 있다.
길이 확장할 때, 메모리 주소를 충분한 메모리가 있는 곳으로 이사하고, 값들을 카피한다!
std::vector<int> vec;
vec[4] 이렇게 랜덤 엑세스도 가능하고, *(vec.begin() + 4) 이런 식으로 인덱스 4에 접근할 수도 있다! 이게 순차적 메모리의 특성이다.
vec.begin() 은 vec[0]과 같다!
시퀀스 컨테이너 : List(리스트)
벡터처럼 선형적으로 확장이 가능하지만, 랜덤 엑세스는 불가능하다! 얘는 연속적인 메모리 주소를 사용하지 않아!
[] 이거 사용해서 인덱스를 통한 접근이 불가능..
Capacity가 고정되어 있지 않고, 뒤나 앞에서 pop이나 push가 가능하다!
std::list<int> lst;
std::next(lst.begin())으로 리스트의 두 번 째 원소의 접근할 수 있다! std::next()
연속된 메모리 공간이 아니라 *(lst.begin() + 4)는 불가능.. 애초에 이런 행동은 정의되지 않아 에러를 일으킨다.
시퀀스 컨테이너 : Deque(덱)
선형적 확장 가능. double ended Queue로
연속적인 메모리 공간인 청크에 원소를 차례대로 넣고, 청크가 다 차거나 해당 청크 밖에 원소를 넣게될 경우에는 청크가 링크드 리스트로 연결이 된다!
즉, 어레이와 리스트를 모두 이용한 것.
Q > 이렇게 그림이 주어지고, 원소를 넣게 하는 문제가 나올 수도!
청크는 링크드 리스트로 연결된 거 잊지 말기!
청크로 관리하니까 원소를 *(포인터 + 상수)이렇게 할 수는 없다 여전히!
다만 인덱스를 이용할 수는 있다! deq[4]를 하면 위 그림에서는 5에 접근할 수 있다.
스택과 큐
스택은 LIFO (마지막에 들어온 게 제일 먼저 나오는 구조.)
DFS (스택은 세로로 깊이 넣을 수 있으니까~)
큐는 FIFO(처음 들어온 게 제일 먼저 나오는 구조.)
BFS (큐는 가로로 누이고 파이프 처럼 넣으면 나오니까~)
DFS랑 BFS인지 나올까 싶지만, 이렇게 직관적으로 외워!
Functor
펑션 콜 "()"을 오버라이드 한 객체이다! 객체라고! 객체! 그냥 흔히 알고있던 객체인데 오버라이드 () 저거 하나 추가된 걸 펑터라고 부르는 거야!
객체이니까 역시 내부 상태가 있다! - O/X 문제로 나올 수 있다.
객체니까 클래스 만들어지고, 객체의 Type-check가 컴파일러에 의해 확인된다! [객체의 메모리를 할당해줘야하니까 런타임이 아니라 컴파일 타임이야!]
덕분에, 개발자의 실수를 잡아낼 수 있고, 컴파일러에 의해 최적화될 수도 있지.
펑터는 객체인데 "자기이름()" 이런 메소드를 정의한 객체라고 간단하게 이해하자!
원래 메소드는 자기이름.메소드이름(인자) 이렇게 생긴 건데 .메소드이름(인자) 가 ()로만 치환된 거야! 어렵게 생각 마!
반환타입 메소드이름(인자,인자) {return x+y;}
반환타입 (x,y) {return x+y;}
자기이름.메소드(x+y) == 자기이름(x,y)
마치 객체인데 함수처럼 보이니까 Functor라는 이름을 붙여준 거야.
셋과 맵
Set은 원소가 중복으로 들어가지 않아.
Map은 Key-value의 페어 집합으로 동일한 Key값의 원소는 들어가지 않는다.
std::map<std::string, int, FunctorClass> map;
원소끼리 중복으로 들어가지 않도록! 순서를 정하도록! FunctorClass를 집어넣는 거야!
예제보고 조금은 이해해보자! 펑터의 역할을!
Introduction to Template
여기서 잠깐!
Compile-time Polymorphism
펑션 오버로딩 - 어떤 함수 쓸 지 알아야 메모리를 할당해주지! 컴파일러가 해줄게!
Run-time Polymorphism
dynamic dispatch (virtual call in C++) - 어떤 클래스의 함수로 쓸 지 알아서 혀~ 런타임에서 혀~
이걸 다시 말한 이유는 Compile-Time Polymorphism 으로 Template이 구동된다.
제네릭 프로그래밍에 대해서 - O/X 문제 나올 수 있다!
- 템플릿으로 C++은 제네릭 프로그래밍을 할 수 있다.
- 템플릿을 통해 Specialized 된 알고리즘이나 자료구조(벡터, 큐)는 일반적으로 작성된 알고리즘이나 자료구조와 동일하다.
(동일하지 않다! 라고 X 문제가 나올 수도 있다..) - 제네릭 프로그래밍은 폴리모피즘이다! 다른 문맥에서는 다른 방향으로 스페셜라이즈 될 수 있으니까! 이게 Int로 스페셜라이즈 되나~ double로 스페셜라이즈 되나~
- 스페셜라이즈는 컴파일러가 컴파일 타임에 수행된다.
(스페셜라이즈는 런타임에 발생한다! 라고 X 문제가 나올 수도 있다.)
Template<typename T>
void Foo(T x, T y) { ... }
템플릿의 두가지 타입
메타 프로그래밍
메타프로그래밍은 프로그래밍 테크닉으로 프로그램을 생성하는 방식으로 프로그램을 작성하는 것이다.
템플릿이 개발자로 하여금 메타프로그래밍을 수행할 수 있도록 한다.
템플릿은 그 자체만으로 알고리즘이나 자료구조가 아니다! - O/X 문제로 나올 수 있다.
다만, 실제 알고리즘이나 자료구조로 컴파일러에 의해 변환될 수 있다!
템플릿을 이용한 메타프로그래밍은 Template Meta Programming이라는 이름으로 불리기도 한다.
클래스 템플릿
타입만 다른 자료구조를 코드로 복붙해서 타입만 바꿔서 작성..? 너무 비용이 크다. 귀찮다. 로직 좀 변환하면 다 고쳐줘야해...
문법은 이렇고, 실제 사용을 해보면 문법을 완벽히 파악할테니 이론만 말하자면,
탬플릿 파라미터를 줄 때, typename T나 class T나 똑같이 수행한다! 차이가 없다! - O/X 문제로 나올 수 있다.
또한 파라미터를 줄 때, typename T 대신 int k 같은 것도 올 수 있다!
typename T에서 T는 이제 템플릿 클래스에서 자료형이 T인 것들에 대해서 구현할 수 있는 것이다! 스페셜라이즈 되어서 T가 int나 double, char나 내가 만든 클래스든 아무튼 T들이 모두 치환 돼!
템플릿 클래스의 정보를 통해서 컴파일러는 클래스를 만들어! 사용되는 구역(뭐 main.cc에서라든지)에서 사용된 템플릿 파라미터들을 보고 클래스를 스페셜라이즈 하여 만들어.
Pair<T> -> Pair<int>든, Pair<double>이든, 이렇게 스페셜라이즈 된다!
물론 여러 개의 템플릿 파라미터를 줄 수도 있지.
템플릿 파라미터 생략(공제? deduction)
C++ 17 이후로 템플릿 파라미터의 공제를 할 수 있게 됐는데 단!
생성자 호출에서 탬플릿 파라미터가 무엇인지 모두 확인할 수 있다면! <int>이런 거 안 써도 돼!
Pair<int>(3,2) 다 정수네?
Pair(3,2) 이렇게 해도 돼~ 컴파일러가 이해해줄게!
생성자 호출로 하나 이상의 탬플릿 파라미터가 어떤 타입인지를 알 수 없는 경우에는 컴파일 타임 에러가 발생해!
-O/X 문제로 컴파일 타임이 아니다! 라고 나올 수도 있어.
여기서, 템플릿에서 파라미터를 줄 때, primitive 타입(그니까 Int, double, char 처럼 이미 정의된 자료구조)를 줄 수도 있어.
템플릿 프로그래밍 작성
템플릿의 구현은 모두 헤더파일에 작성해야해!
헤더파일에 선언을 정의파일(.cpp)에 정의를 나누어서 해야 obj 파일의 크기가 작아서 프로그램이 무겁지 않게 돌아가게 하는 게 원칙이지!
하지만, 템플릿의 경우에는 스페셜라이즈 할 때 정의파일의 메소드로 몸통을 찾지 못 해. 그래서 클래스가 만들어지지 않아서 Linking 에러가 발생해.
귀찮으면 밑줄만 보기. () 보면서 난독증 영향 받지마..
각 파일을 binary 파일로 컴파일하는 데 까지는 아무 문제가 없어! 템플릿 선언이 있는 헤더파일을 읽은 main은 템플릿 클래스를 사용한 걸 봐도 미리 전방 선언 되었으니까 여기까지는 Ok! 해주거든.
(선언 없으면 컴파일러가 "엥? 이게 뭐여" 하고 컴파일 안 해줘. 근데 일단 선언만이라도 해주면 컴파일러가 "일단 알겠어~ Linking할 때 어딘가 있겠지? Linking 때 다시 확인해볼게~")
그런데 선언을 통해서 템플릿클래스를 보고 클래스를 선언은 한 거야. 컴파일에서 Pair<T>이 Pair<int>로 헤더파일을 통해서 선언 했어! (이것도.. 맞다고 보기엔 그렇지만 이해해)
이제 클래스의 정의 부분을 볼까? 하고 .cpp를 보는 순간!
엥? 뭐야 다 템플릿 클래스의 함수들이잖아?
Pair<T>의 정의들만 있지. Pair<int>에 대한 스페셜라이즈 된 정의가 없잖아?
(기억한다면 템플릿 자체는 알고리즘도 자료구조도 아니라고 했잖아. 스페셜라이즈 되어야만 해. 그래서 스페셜라이즈 되지 않은 몸통들은 구현이 되어 있지 않다고 보고 못 알아보는 거야.)
그럼 선언+몸통으로 클래스가 만들어지는데 몸통이 없으니 클래스 못 만들겠잖아.
클래스 생성 실패~ 클래스 생성 실패로 메인 함수에 있는 생성자도 못 읽고, 메소드도 못 찾고 그래서 링킹 에러가 발생해(undefined reference).
(맞는 설명이라기 보단 비유를 통해 이해하기 쉽게 한 것입니다. 나중에 더 자세히 분석한 내용(컴파일 과정에서 선언,정의에 대한 Disassemble 했을 때, 메모리의 형태 등등)을 올리겠습니다.)
해결 방법:
- 템플릿의 선언과 정의를 모두 헤더파일에 하기.
- 정의.Cpp 파일에 스페셜라이즈되도록 클래스를 넣어버려서, 정의파일 컴파일 할 때, 클래스가 스페셜라이즈 되면서 몸통도 같이 만들어버리기. 정의 파일에서 main에서 사용되는 스페셜라이즈 클래스를 정의 파일에도 넣어서 컴파일로 몸통 만들 수 있게 하기.
위 그림이 2번째. 근데 1번째를 많이 사용한다. 이건 너무 특수한 경우만 다뤄서 프로그램이 좋지 않다.
펑션 템플릿
문법은 다음과 같고, 바로 예제를 보자.
클래스 템플릿을 잘 따라왔으면 이해에 어렵지 않다!
함수도 마찬가지로 함수 호출 때 파라미터를 확인 할 수 있으면 제외 가능하다!
여기서 중요하게 볼 건! 이미 작성된 일반적 함수와 템플릿 함수로 스페셜라이즈된 함수의 충돌이다! 시험에 무조건 나오니까 꼭 이해해 ㅠㅠㅠ
이미 기존의 함수를 이용할 것인가? 아니면 템플릿으로 함수를 만들어서 사용할 것인가? 그것이 문제로다.
- 이미 완벽하게 매치되는 함수가 기존에 있는가? 있으면 그걸 취하고
- 없으면 템플릿으로 만들어서 쓰고, 만들 수 없으면?
- 펑션 오버로드를 하자. (Overload Resolution 룰에 의해서!)
Advanced Template and STL
Default Template Argument
내가 따로 정해두지 않으면 패래미터는 이런 값으로 해줘~ 이런 내용.
이렇게 아무 인자도 안 주면, Ksize =3 으로 두고~ 만약 바꾸고 싶으면 원래대로 5를 인자로 넘겨서 줄 수 있다.
여러 개를 디폴트할 수도 있다.
-----------------주의!!-----------------
에러 발생하는 경우가 생기는데, 디폴트를 주는 인자는 항상 디폴트 없는 것들 바로 뒤부터 정의해줘야 한다!!
디폴트를 주면 그 뒤의 인자들도 다 디폴트 값이 있는 걸로 알고 컴파일하기 때문이다! 안 그러면 컴파일 에러 발생!
- 디폴트 값을 주고, 그 다음 인자를 쓰고 디폴트 값을 쓰면, 이전의 디폴트 값을 따라서 값을 디폴트로 설정한다.
같은 값으로 디폴트 값을 일치할 수 없을 때(위의 예시)는 컴파일 에러를 일으킨다!
Lack of type Information in template
Pair도 템플릿으로 Pair를 담는 Set인 PairSet도 템플릿으로 쓰면? PairSet 템플릿에서 Pair 3번째 것의 첫 번 째원소를 출력하고 싶은데 Pair의 원소가 무슨 타입인지 어떻게 알 수 있지? PairSet 템플릿의 템플릿 파라미터로는 Pair가 무슨 타입인지(Pair<int>,Pair<double> 이런 거)밖에 없는데..
Pair<int>의 int 부분을 PairSet은 int인지 뭔지도 몰라! 일단 Pair를 담기만 한단 말야!
해결 방법은 중첩시켜서 전부 알려줄 수 있게 파라미터를 준비하자!
템플릿 안에 템플릿 파라미터로 템플릿을 주는 거다. typename 인자 2개를 사용해서 만들어지는 typename P의 템플릿을 파라미터로 준 것이다.
T, S, 타입 네임 2개를 이용해 만들어지는 P에 관한 템플릿, KSize 이렇게 4개.
이렇게 P는 타입 네임 2개를 받아야 하는 템플릿이므로 T와 S를 구현부분에서 넣어서 P를 완성.
T와 S로 스페셜라이즈 되는 Pair 클래스를 P가 받게 된다.
가변 개수 인자
인자에 ... 으로 점 3개만 찍으면 가변 개수 인자를 설정할 수 있다! 템플릿 파라미터 팩을 설정하게 된다.
Typename... Ts 라고 하면 Ts 는 템플릿 파라미터 팩이구나! 하고 가변 개수로 설정할 수 있다.
재귀를 거쳐서 인자를 하나씩 처리하고 나서, 템플릿이 인자가 하나 없어진 템플릿이 하나 생기고...
그렇게 파라미터가 한 게 뿐이라면 종료하자! Base Case
아직 패러미터가 1개 초과로 있다면 하나 씩 처리하는 함수를 실시하자. Recursive Case
STL에서의 Iteraotr 와 Algorithm
Iteraotr
컨테이너 안의 원소를 포인팅 하는 객체.
컨테이너가 무엇인지 고려하지 않고 일반적인 인터페이스를 제공한다.
begin은 첫 원소를 포인팅, end는 마지막 원소 뒤의 걸 가리키고 있다.(마지막 원소 뒤의 주소)
iterator를 ++ 하면 그 다음 원소를 가리키게 한다. *은 그 원소의 값 접근.
!= 는 객체가 가리키는 포인터 자체를 비교하는 것이다. 같은 걸 가리키고 있나?
아이터레이터의 종류에 따라서 가능한 연산이 있고 관계들은 이와 같다.
advance는 한 칸 씩 움직이기 귀찮으니까 2칸 씩, 4칸 씩, 이렇게 움직일 수 있게 하기.
next()와 prev()는 iterator를 하나 더 만드는 건데, 기존의 itr을 유지하고 그 다음(혹은 그 이전)의 포인팅한 지점을 새로운 아이터레이턴에 넣을 수 있게 한다.
Algorithm in STL
Sort, Merge
예제로 count - 내가 원하는 값이 컨테이너에 몇 개 있나? -> input iterator
min_element, max_element 이 컨테이너의 최소값과 최대값은? -> Forward Itreator
sort는 정렬 -> RandomAccess Iterator
Exception Handling
'[Computer Science] > [객체지향설계]' 카테고리의 다른 글
| [객체지향설계] 12/05 이론 (0) | 2023.12.05 |
|---|---|
| [객체지향설계] 11/21 이론 (0) | 2023.11.21 |
| [객체지향설계] 11/14 이론 (0) | 2023.11.14 |
| [객체지향설계] 11/7 이론 (0) | 2023.11.07 |
| [객체지향설계] 10/31 이론 -Design Pattern (0) | 2023.10.31 |
