일반화 프로그래밍, STL기초

자료구조의 기초:최적의 자료구조는 없으며, 때에 따라서 맞는 자료구조를 선택해야한다.

<일반화 프로그래밍>

일반화 프로그래밍이란? 

 => OOP이후로 좀더 발전된 재사용성을 제공하는 프로그래밍으로써, 데이터와 행동을 나누는것을 기반으로 하며,
객체지향의 다음 세대라고 불러지기도한다.

특징:

1. 임의타입에 사용할 수 잇는 자료구조를 만들수 있다. (템플릿사용)
2. 내부구조에 상관없이 임의의 데이터 집합에 접용할 수 있는 일반화된 알고리즘을 제공한다.
    (반복자라는 일반화된 포인터를 사용)

<STL>

STL이란? 

(Standard Template Library)의 약자로, 일단은 라이브러리이되 템플릿의 집합을 제공하는 라이브러리이며, 현재 C++의 표준으로 채택되어있다.

STL의 장점

1. 일반화를 지원함.( 하나의 알고리즘으로 복수 개의 컨테이너에 동일한 작업을 똑같은 방법으로 수행할 수 있다.)

2. 컴파일 타임 매커니즘을 사용하기 때문에 실행시의 효율 저하가 거의 없다.

3. 객체 지향적이지 않다.

(객체를 사용하기는 하지만 STL자체가 객체를 반드시 요구하는것은 아니다.)

4. 표준이므로 이식성이 당연히 확보됨

(어떠한 컴파일러로도 문제없이 컴파일할 수 있다.)

5. 확장가능하다.

STL의 단점

1. 템플릿 기반이므로 타입마다 함수와 클래스가 매번 구체화되어 코드가 비대해지는 고질적인 문제가 있다.

(약간의 속도 향상을 위해 크기를 완전히 포기한 것과 같음)

(요즘 시대가 용량이 많더라도 이건 좀 무식한 방법?! ㅋㅋ)

2. STL로 작성한 코드는 가독성이 심하게 떨어짐

(소스가 난해해서 팀프로젝트에 불리)

3. 배우기가 결코 쉽지 않다.

4. 템플릿을 사용하므로 C++예외코드(try-catch구문)와 같이 사용하기가 힘들다.

STL을 왜 배워야되는것 인가?

=>장점이 많지만 단점이 많은데 꼭 배워야하는가?
선택적으로 배워야되는게 아니라 필수다!

많이 사용하니 적어도 다른 사람의 소스를 읽을 수 있어야하지 않겠나?

<STL의 구조>

컨테이너

반복자

알고리즘

할당기

어댑터

함수객체

컨테이너 (==컬렉션)

컨테이너는 똑같이 생긴 것들을 모아 놓는 장소이다!

컨테이너를 뜻 그대로 직역하면 통, 그릇이다.
쌍통에 쌀을 담고 술통에 술을 저장하듯이 컨테이너는 무엇인가를 저장하는것이다.

STL의 컴테이너는 타입이 같은 즉, 동직적인 객체의 집합을 저장하고 관리하는 역할을 함!

( 컨테이너의 예: 배열,연결리스트,스택,큐)

1). 시퀀스 컨테이너

자료의 선형적인 집합이며 자료를 저장하는 기본 임무에 충실한 가장 일반적인 컨테이너

삽인된 자료를 무조건 저장하는 특징이 있음

임의 위치에 원하는 요소를 마음댈 삽입,삭제할 수 있다.

(STL:벡터, 리스트, 데크)

2). 연관 컨테이너

자료를 일정한 규칙에 따라 자료를 조직화하여 관리하는 방법.

검색 속도가 빠른것이 장점.

(STL: 셋, 맵)

3). 어댑터 컨테이너

시퀀스 변형된 형태이다.

자료를 미리 정해진 일정한 방식에 따라 관리하는것

(스택,큐,우선순위 큐)

세 부류로 컨테이너를 나눈 것은?
=>세부류는 삽입, 삭제 규칙에 있어서 차이가 있다.

시퀀스는 제약없음

연관은 검색을 위한 곳에 자동 삽입

어댑터는 FIFO, LIFO같은 미리정한 규칙이있음

최고의 컨테이너는?

=> 그딴것은 없다.

상황에 따라 달라지는것이 자료구조의 기본아니겠나?

많이 쓰는 컨테이너들을 공부해보자

<벡터>

벡터란? 
벡터는 시퀀스 컨테이너의 한종류 

벡터: 동적배열이다.
그래서 제일 중요한것은 메모리가 연속된 공간에 저장된다. 

벡터는 많은 함수와 연산자들을 가지고 있다.

#include <vector>

vector<T> 변수(개수)

*배열과 벡터의 공통점 

벡터도 요소를 인접한 메모리 위체에 연속적으로 저장

(그래서 첨자 연산만으로 원하는 요소 빠르게 읽을 수 있음 )

(즉! 벡터[2] 이게 가능하다는것이다.)

*배열과 벡터의 차이점

=>배열은 정적 크기를 가지므로 반드시 상수로 크기를 정의해야하지만

벡터는 실행중에 결정되므로 변수로도 정의가 가능하다
(이렇게 정의했다. 이것을 위해서 벡터가 존재하는것?!이다!)

---

리스트

리스트란?
리스트는 시퀀스 컨테이너의 한종류 
stl에서 리스트란 이중 연결 리스트로 구현된 컨테이너이다.

노드라는 구조체로 관리

리스트는 결국 읽기속도는 느리지만 삽입삭제가 용이함

리스트의 주소를 참조하기위해 반복자를 씀

tip:
반복자: 흔히 노드를 가리키는 포인터라고 생각하면 됨

#include <list>

list<T> 변수

//인수(개수)는 존재하지 않음

//이유:리스트는 통상 최초빈 상태로 만들어서 추가해서 사용하지 않느냐? 

---

<맵>
 

맵이란?

연관 컨테이너의 한종류

자료를 수집할때 위치를 정하는 개념으로 검색하기가 용이함

키와 값을 가진다.

당근 반복자를 이용함~

it->first, it->second 가 존재한다

반복자

반복자는 STL의 핵심문법

C언어의 핵심? =>포인터

C+의 핵심? => 다형성

STL의 핵심? => 반복자

반복자란? 

반복자는 포인터와 하는 역할이나 사용방법이 비슷한데 일반화되있는것!!!!

반복자를 사용하는 이유? 

이유는
내부구조가 다르기때문에 컨테이너 별로 순회를 하는 방법이 제각각일 것이기때문에 포인터로 사용하기엔 한계가 있다.
내부구조가 다르므로 컨테이너마다 반복자는 다를것이다. 반복자는 순회방법을 일반화하기 위해 STL에서 사용하는 개념이며, 컨테이너마다 반복자 객체를 일반화시켜 만들어 놓고 쓰는 개념이다. 

어떤 경우엔 포인터가 되기도 하고,
어떤 경우에는 첨자가 되기도 하며
또 어떤경우엔 다소 복잡한 객체가 요구되기도 함.

 

반복자 특징

1. 컨테이너의 요소 하나를 가리키는 기본적인 역할

2. 가리키는 지점의 요소를 읽고 쓸 수 있다. (* 연산자 오버로딩)

3. 증감에 의해 주변요소로 이동가능 ( ++,-- 연산자 오버로딩)

4. 반복자끼리 대입, 비교 가능 ( = 연산자 오버로딩 )

=>신기한게 벡터든, 리스트든 다 ++로 다음지점을 가르키는게 가능하다는것이다.

왜신기하냐고?
벡터는 연속된 메모리공간이고, 리스트는 연속적이지 않은 메모리 공간이니까~ 신기한거지~요
 

컨테이너는 맨 시작점과 끝다음점을 조사하기위해 begin,end멤버함수를 제공함

(끝다음점: 범위의 경계를 넘어선 지점을 의미)

각컨테이너의 내부 구조는 상당히 다르지만 반복자를 사용하면 똑같은 방법으로 순회할 수 있다.

반복자 정리 

 반복자는 컨테이너를 순회하는 방법과 컨테이너의 한 요소를 참조하는 방법을 획일화함으로써 알고리즘들이 컨테이너의 내부 구조에 대해 독립성을 가지도록 한것!

<알고리즘>

알고리즘이란? 

STL의 알고리즘 함수들은 대부분 특정 컨테이너의 멤버함수가 아닌 일반 전역 함수로 작성되있다!!!!!!!!!!!!!!!!!(헐!?)
 

STL알고리즘이 전역함수로 정의 되있는 이유? 

반복자에 의해 컨테이너를 다루는 방법이 일반화되어 모든 컨테이너에 대해 적용할 수 있으므로 멤버 함수가 될 필요도 없고 멤버함수가 되어서도 안 된다.

즉! 캡슐화를 적극적으로 사용하지 않는다. 

또한 컨테이너 클래스들은 표현하고자 하는 자료구조를 위한 데이터멤버와 연산자만을 정의하며 알고리즘 구현은 반복자와 전역 함수에게 맡긴다. (일반화 프로그래밍과 객체지향의 차이)

많이 쓰이는 알고리즘 간단정리

모든 알고리즘함수들은 대부분 <algorism.h> 헤더에 있음

#include <algorism.h>

1.컨테이너에 특정값이 존재하는지 찾는 find함수

template <typename Init, typename T>

Init find( Init first, Init last, const T& val);

특징:

임의의 모든 타입에 대해 동작할 수 있어야 하므로 STL 알고리즘 함수들은 예외없이 템플릿으로 구현되어 있다.

C언어함수들은 검색에 실패할 경우 보통 NULL을 리턴하지만 stl함수는 검색실패하면 반복자로 리턴한다(맨끝다음주소값)

2.sort함수

=>퀵정렬을 사용한다.

template<typename Init>

void sort(Init first, Init last)

first~last 사이의 모든요소를 정렬

<,>연산자오버로딩 꼭 되어있어야함

3. reserse함수

template <typename Init>

void reverse(Init first, Init last);

지정한 구간의 요소들 순서를 반대로 뒤집는다.

4. randim_suffle함수

template <typename Init>

void random_shuffle( Init first, Init last );

4. count 조건에 맞는 요소의 개수를 센다.

5. for_each 각 요소에 대해 지정한 작업을 한다.
 

6. equal 구간이 일치하는지 비교한다.
 

7. search 일치하는 부분 구간을 검색한다.
 

8. copy 구간끼리 복사한다.
 

9. fill 일정한 값으로 지정 구간을 채운다.
 

10. swap 컨테이너를 교환함
 

11. binary_search 이분 검색을 함
 

12. merge 구간을 병합하여 새로운 구간으로 복사한다.
 

13. accumulate 구간의 값을 모두 합한다.

www.winapi.com 혼연을 보고 공부한후 정리 하였다.
아 역시 정리를 해야 머리에 쏙 들어옴 +_+ ㅎㅎㅎㅎㅎ