IT's me

new 및 delete를 사용할 때는 형태를 반드시 맞추자.

string* sArray = new string[100];

...

delete sArray;

new

1. 먼저 operator new 에 의해 메모리가 할당된다.

2. 할당된 메모리에 한 개 이상의 생성자가 호출된다.

delete

1. 기존 할당된 메모리에 한개 이상의 호멸자가 호출된다.

2. operator delete에 의해 메모리가 해제된다.

여기서 핵심은 삭제되는 포인터 sArray는 객체 하나만

가리키느냐, 객체 배열을 가리키고 있느냐 이다.

단일 객체와 객체 배열은 메모리 배치구조가 다르다.

객체 배열은 배열원소의 개수에 대한 정보를 가지고 있다.

하지만 단일 객체는 이러한 정보를 가지고 있지 않다.

따라서 이 둘의 배치구조가 다르기 때문에 delete를 사용해

메모리를 해제해 줄때, 배열 크기 정보가 있다는 것을

알려줘야 한다. 이 때 delete[] 를 써주면 이 포인터가

배열을 가리키고 있구나 라고 가정하게 된다.

string sPtr1 = new string;

string sPtr2 = new string[10];

delete sPtr1; --> 단일 객체로 인식하고 한 개를 삭제.

delete[] sPtr2;  --> 배열의 원소 개수 정보를 넘겨줌

주의점

1. sPtr1에 delete[]를 쓸 경우

delete는 sPtr1 앞쪽의 메모리 몇 바이트를 읽고

이 것을 배열 크기라고 해석하고, 배열 크기에

해당하는 만큼 소멸자를 호출하기 시작한다.

2. sPtr2에 delete를 쓸 경우

sPtr2를 단일 객체로 인식하고 소멸자를

단 한번만 호출하게 된다. 소멸자가 없는

기본제공 타입이라 해도 이들의 배열에 대해

[]를 쓰지 않으면 미정의 동작이 나타난다.

new 표현식에 []를 썼으면, 여기에 대응 되는

delete 표현식에도 []를 써야 한다.

반대로 new에서 []를 쓰지 않았으면

delete 에도 []를 쓰지 않으면 된다.

동적 할당된 메로리에 대한 포인터를

멤버 변수로 가지고 있는 클래스라면

이 클래스에서 제공하는 모든 생성자에서는

new 형태를 똑같이 맞춰줘야 한다.

왜?? 소멸자에서 어떠한 형태의 delete를

써야할지 구분하기 어렵기 때문이다.

주의점

배열을 typedef로 사용할 경우

typedef string Address[10];

...

stinrg *p = new Address;

어떠한 delete를 써야할까?

혼란의 여지가 다분하다.

1. delete p --> 배열인데 객체 하나만 지운다.

2. delete[] p --> 제대로 동작한다.

배열을 typedef로 만들지 말자. --> 알아보기 힘들다.

대신 stiring 또는 vector 같은 클래스 템플릿을 잘 활용하자.

잘 활용한다면 동적 할당된 배열이 필요해질 경우가 거의 없다.

POINT!!

1. new와 delete의 형식을 맞추자.

자원 관리 클래스의 복사 동작에 대해 진지하게 고찰하자.

자원 관리 클래스의 주축 아이디어

자원 획득 즉 초기화 (RAII) --> 전 시간에 포스팅

1. auto_ptr

2.shared_ptr

힙에 생기지 않는 자원은 위의

두 스마트포인터로 처리해 주지 못한다.

예제) 동적 할당되지 않는 경우의 자원 관리 클래스

스레드 동기화를 위한 Mutex 타입의 객체가 있다.

위의 객체가 제공하는 함수 중엔 lock와 unlock가 있다.

void lock(Mutex *pm) --> pm이 가리키는 뮤텍스를 잠금

void unlick(Mutex *pm)  --> 뮤텍스 잠금 해제

이제 뮤텍스의 잠금을 관리하는 클래스를 만들어 보자.

이전에 걸어 놓았던 뮤텍스의 잠금을 잊지 말고 풀어주기 위함.

이런 용도의 클래스는 RAII 법칙을 따라

생성 시에 자원을 획득하고, 소멸 시에 그 자원을 해제 한다.

class Lock{

private:

Metex* mutexPtr;

public:

explicit Lock(Mutex *pm) : mutexPtr(pm) {   // 생성과 동시에 자원 획득

lock (mutexPtr);                                     // 이 클래스에서는 잠금을 걸어 준다.

}

~Lock { unlock(mutexPtr) }                           // 자원 해제

}                                                                            // 이 클래스에서는 잠금을 해제.

int main(){

Mutex m;                             // 뮤텍스 정의

...

{

Lock m1(&m);              // 뮤텍스에 잠금을 건다.

...

}                                         // 블럭이 끝나면 Lock의 소멸자가 호출되면서

    // 뮤텍스의 잠금을 풀어주게 된다.

문제제기

Lock 객체가 복사된다면 어떻게 해야 할까?

위와 같은 스레드 동기화 객체에 대해서는

사본에 대한 의미가 없다. 위와 같은 경우가

아니라도 RAII 클래스를 만들 때 복사에 대해

주의를 기울여야 한다.

해결책

1. 복사를 금지 한다.

위와 같은 예제의 경우 사본에 대한

의미가 없기 때문에, 복사를 금지 한다.

복사를 금지하는 방법에 대해서는

지난 포스팅에서 언급했기 때문에 패스~

2. 관리하고 있는 자원에 대해 참조 카운팅을 수행한다.

shard_ptr (RCSP)이 참조 카운팅 방식의 스마트 포인터 라는 것을

지난 포스팅을 통해 알고 있다. 그리고 그 방식 또한 알고 있다.

해당 자원을 참조하는 객체의 개수를 카운팅하는

방식으로 복사를 진행하겠다 이 말이다. 

때문에 자원관리 객체 내에서 shared_ptr을 써보겠다.

Lock 클래스 내에서 Mutex* mutexPtr 이 아니라

shared_ptr<Mutex> mutexPtr; 로 바꿔주자는 말이다.

하지만 이 자원 관리 객체를 만든 의미를 다시 한번 생각해보자.

뮤텍스 객체를 잠그고 해제하는 용도이지 뮤텍스 객체를 사용하고

제거해버리는 용도가 아니다. 하지만 shared_ptr은 뮤텍스 객체를

가리키고 있고, 스마트 포인터 특성에 따라 객체가 없어지면서

뮤텍스 객체를 삭제해 버린다. 해결할 수 있는 방법이 없을까?

다행히도 shared_ptr은 삭제자 지정을 허용한다.

무슨말인고 하면 shared_ptr이 유지하는 참조 카운트가

0이 되면 무조건 소멸이 아니라 특정 함수 혹은 함수 객체를

호출할 수 있다는 것이다. 생성자의 두 번째 매개변수로 넣어 준다.

class Lock{

private:

shared_ptr<Mutex> mutexPtr;

public:

explicit Lock(Mutex* pm) : mutexPtr (pm, unlock) {

lock(mutexPtr.get()); --> 다음 포스팅에서 다룰 것이다.

}

};

이렇게 만들어주면 shared_ptr은 자신이 소멸 시에

가리키는 객체를 삭제해주는 것이 아니라 unlock() 함수를 호출한다.

또한 위의 클래스에는 소멸자가 없는데, 기본 소멸자를 호출한다.

3. 관리하고 있는 자원을 진짜 복사한다.

"자원을 다 썻을 때 각각의 사본을 확실히 해제한다" 는

전제 하에 이 정책을 들이도록 하자.

또한 자원관리 객체는 깊은 복사를 수행해야 한다.

4. 관리하고 있는 자원의 소유권을 옮긴다.

어디서 들어본 말인고 하니 auto_ptr의 복사 동작이다.

즉 그 자원을 실제로 참조하는 RAII 객체는 단 하나만

유지하겠다는 것이다. (흔한 경우는 아님).

POINT!!

1. RAII 객체의 복사는 그 객체가 관리하는 자원의 복사 문제를 안고가기 때문에,

 그 자원을 어떻게 복사하느냐에 따라 RAII 객체의 복사 동작이 결정된다.

2. RAII 클래스에 구현하는 일반적인 복사 동작은 복사를 금지하는 것,

그리고 참조 카운팅을 해주는 방법이다.

그리디 알고리즘02 소시지 공장 (정올)

며칠 전에 소시지공장의 터무니 없는 풀이를 올렸었다.

계속 풀어도 똑같은 결과가 나오길래 이상하다 싶었는데

문제 자체를 잘못 이해하고 있었다.

제대로된 풀이를 올리려는 포스팅은 아니지만

그래도 100점이 나와서 한번 올려본다.

(어차피 보는 사람도 없겠지만..)

한창 STL을 공부하고 있고, 클래스 디자인에 관심이 많을 때라

클래스라던지, 함수 객체, 벡터 등 왜 굳이 이렇게 풀어야할까..

의문이 드는 부분이 있겠지만, 공부하는 입장에서 이곳 저곳에서

써보면서 좀 익숙해지려고 생각나는 대로 다 써보았다.

따라서 절대 정답이 될 수 없는 풀이이다.

이렇게 푸는 놈도 있구나.. 하고 참고하시길

1. 클래스 선언

2. 초기화

3. 정렬을 위한 함수 객체 선언

4. 알고리즘과 함수 객체를 이용한 정렬 그리고 재귀 함수 호출

5. 답을 찾는 재귀 함수 구현

w_FindAnswer() 또한 같은 방법으로 구현

6. 답을 출력하는 함수와 메인 함수

코드가 복잡하다. 하지만 풀었다는 것에 의의를 두겠다.

그럼 다음 알고리즘 풀이로 돌아오겠다.

STL에 필요한 템플릿 예제

for_each() 함수를 직접 구현해 보겠다.

int에 대한 For_each와 출력 함수

 string에 대한 For_each와 출력 함수

template을 이용해 일반화를 시켜보자.

일반화를 시키면 어떠한 타입이 들어가도 OK!

(단, 함수 내에서 요구하는 인터페이스를 가지고 있어야 한다.)

(예를 들어 함수 내에서 +연산을 한다고 하면

매개 변수로 들어간 타입은 +연산 인터페이스가 제공되어야 한다.)

템플릿의 매개변수와 함수 객체를 결합하면

반환 타입과 함수 매개변수 타입을 클라이언트가

결정하는 아주 유연한 함수 객체를 만들 수 있다.

아래 예제를 보자.

STL에서 쌍을 표현할 때 항상 사용되는

pair 클래스를 템플릿으로 구현한 예제

pair 클래스는 두 객체를 하나의 객체로 취급할 수 있게

두 객체를 묶어준다. 대표적으로 map 컨테이너의 key, value

자원 관리에는 객체가 그만!

class Investment { ... }  --> Base 클래스

Investment* createInvestment();

--> Drived 클래스들의 객체를 동적 할당하고

      그 포인터를 반환하는 팩토리 함수.

이 객체의 해제는 호출자 쪽에서 직접 해야 한다.

void f(){

investment *pInv = createInvestment();

....

....

delete pInv;

}

언뜻 보기엔 별 문제 없어 보인다.

1. 하지만 ... 부분에서 return; 이 있을 경우

2. continue, goto가 있을 경우

3. 예외가 발생될 경우

위의 경우 delete는 실행 되지 않고

메모리가 누출되고 자원이 새게 됩니다.

해결책

createInvestment() 함수로 만들어낸 자원이

항상 해제되도록 만드는 방법은

자원을 객체에 넣고 그 자원 해제를

소멸자가 맡도록 하며, 그 소멸자는 실행 제어가

f를 떠날 때 호출 되도록 만드는 것이다.

개발에 쓰이는 상당수의 자원이 힙에서 동적으로

할당되고, 하나의 블록 혹은 함수 안에서만 쓰이는

경우가 잦기 때문에 그 블록 혹은 함수로부터

실행 제어가 빠져 나올 때 자원이 해제되는 것이 맞다.

스마트 포인터 auto_ptr을 써보자.

가리키고 있는 대상에 대해 소멸자가

자동으로 delete를 불러주도록 설계되어 있다.

void f(){

auto_ptr<Investment> pInv (createInvestment());

...

...

}

--> 블럭이 끝나면 auto_ptr의 소멸자를 통해 pInv를 삭제한다.

위와 같이 자원 관리 객체를 사용하는 

방법의 중요한 특징에 대해 알아보자.

1. 자원을 획득한 후에 자원 관리 객체에 넘긴다.

createInvestment() 함수가 만들어준 자원을

auto_ptr 객체를 초기화 하는 데 쓰이고 있다.

--> 자원 획득 초기화 (RAII)

자원 획득과 자원 관리 객체의 초기화가 

한 문장에서 이루어지는 것이 일반적이다.

2. 자원 관리 객체는 자신의 소멸자를 사용해

자원이 확실히 해제되도록 해야한다.

소멸자는 객체가 소멸될 때 자동적으로

호출되기 때문에, 실행 제어가 어떤 경위로

블록을 떠나가는가에 상관없이 자원 해제가

제대로 이루어지게 되는 것이다.

주의점!!

auto_ptr은 자신이 소멸될 때, 자신이 가리키는

객체를 자동으로 delete를 해주게 된다.

따라서 같은 객체를 두개의 auto_ptr이

가리키고 있다면 자원이 두번 삭제되는 결과.

---> 때문에 auto_ptr은 객체를 복사하게 되면

원본객체는 null로 만들어버린다.

예제를 보도록 하자.

auto_ptr<Investment> pInv1(createInvestment());

auto_ptr<Investment> pInv2(pInv1);

--> pInv2가 객체를 가리켜 pInv1은 null

pInv1 = pInv2;

--> 이제는 pInv2가 null

문제점 : STL 컨테이너의 경우엔 원소들의 정상적인 복사 동작을

가져야 하기 때문에 auto_ptr은 최선의 방법이 아니다.

해결책

참조 카운팅 방식 스마트 포인터 (RCSP)를 쓰자!

참조 카운팅은 여러개의 객체(자원 관리 객체)들이 동일한 값을 가질 때,

그 객체들로 하여금 그 값을 나타내는 하나의 데이터를

공유하게 하여 데이터의 양을 절약하는 기법이다.

어떠한 자원을 참조하는 횟수를 기록하여 자원의 생명주기를 관리한다.

이 횟수가 있다는 것은 메모리 어딘가에서 쓰이고 있다는 것이다.

함부로 자원을 삭제하면 사용 중인 정보가 무효화 될 것이다.

따라서 참조 횟수가 0이 되기 전에는 이 자원이 삭제되지 않는다.

TR!에서 제공하는 std::tr1::shared_ptr이 대표적인 RCSP이다.

void f(){

shared_ptr<Investment> pInv1 (createInvestment());

shared_ptr<INvestment> pInv2(pInv);

pInv1 = pInv2;

}

--> 복사와 대입 문제없이 실행된다.

주의점!

스마트 포인터의 소멸자에서는 delete 연산자를

사용하고 있다는 것이다. delete[]가 아니라는 점!

따라서 동적 할당된 배열에 대해 스마트 포인터를

사용하지 말자는 것. 동적 할당된 배열은 vector이나

string을 통해 거의 대체할 수 있기 때문이다.

POINT!!

1. 자원 누출을 막기 위해, 생성자 안에서 자원을 획득하고

소멸자에서 그것을 해제하는 RAII객체를 사용하자.

2. 널리 쓰이는 RAII는 대표적으로 auto_ptr, shared_ptr이 있다.

그리디 알고리즘01 회의실 배정 (정올)

처음으로 100점이 나왔다.

정말 쉬운 문제이긴 하지만

답을 보지 않고 처음부터 끝까지

내가 푼 문제라 더 뿌듯하다.

물론 최적화된 코드는 절대 아니다.

1. 일단 종료시간을 기준으로 오름차순으로 정렬

2. 정렬된 후에 맨 앞에 있는 회의는 무조건 맨 처음에 들어갈 수 있다.

따라서 FindAnswer(0) 으로 함수를 호출한다.

3. if(0번 째 회의라면) 넌 답이니까 v에 들어가라.

4. 그리고 다음 회의를 찾아간다.

for문으로 자신의 오른쪽 방향으로 하나씩 탐색.

맨 처음에 들어갈 회의가 결정났기 때문에

맨 처음 회의의 종료시간과 그 다음 회의의

시작시간을 비교 if(종료시간 <= 다음 놈 시작시간)

5. 해당하는 회의를 찾았다면 그 회의의 num을

v에다가 집어 넣고, 그 회의의 인덱스로

다시 FindAnswer(index) 함수 호출.

그리고 본 함수는 종료시켜준다. return;

6. 재귀를 통해 답을 찾다가

해당하는 회의가 없어 for문 루프를 빠져나오면

함수를 종료 시킨다. return;

재귀 함수

재귀 함수의 기본적 이해

-> 자기 자신을 다시 호출하는 형태의 함수

재귀를 공부해야 하는 이유

자료구조나 알고리즘을 공부할 때

재귀 함수가 유용하게 사용되어 진다.

탈출 조건의 필요성

 - 무한 재귀 호출을 피하기 위해서 (무한 루프)

 - 무한 재귀 호출 -> stack overflow

 탈출 조건의 이해

void Re(int n){

...

if(n==1)

return;

Re(n-1);

}

int main(){

int a= 5;

Re(5);

}

--> return은 값의 반환 뿐만 아니라

      함수를 빠져나올 때 쓸 수 있다.

재귀 함수 Design

- 팩토리얼 계산을 위한 알고리즘

int factorial(int n){

if(n==1) return 1;

else return n * factorial(n-1);

}

재귀함수의 효율성

속도나 메모리의 절약을 의미하는 것이 아니다.

오히려 잦은 함수 호출로 인한 속도 저하와 

stack overflow, 즉 다룰 수 있는 범위를

초과하는 문제가 발생 할 수 있다.

논리적 사고를 그대로 옮기거나

코드를 단순화 하기에 적합하다!

static 변수

1. 함수 내부 및 외부에 선언 가능하다.(전역, 지역)

2. 한번만 초기화 된다. (전역 변수의 특징)

3. 함수 내부에서 선언될 경우 함수 내에서만

    접근이 가능하다. (지역 변수의 특징)

void fct(){

static int val = 0;

val++;

printf("%d ", val);

}

int main(){

int i;

for(i = 0; i<5; i++)

fct();

}

1. fct() 함수가 끝나도 static 변수는 

메모리 상에서 지워 지지 않는다.

2. static 변수의 초기화는 단 한번.

때문에 함수가 다시 호출되도

초기화 부분은 무시하게 된다.

따라서 출력 결과는

1 2 3 4 5

가 된다.

프로그램 실행 전 컴파일 과정에서 메모리 공간을 할당 받고

전체 프로그램이 종료될 때까지 동일 메모리 공간을 보유한다.

--> 전역 변수의 특징과 같다. 전역 변수도 static 변수이다.

전역 변수와 static 변수의 차이점?

누구나 접근 가능한 전역 변수와는 달리

선언된 지역 내에서만 접근이 가능하다는 장점이 있다.

함수 포인터를 이용한 간단한 콜백 메커니즘

어떤 기능이나 서비스를 제공하는 코드 측을 서버라 한다.

그 기능을 제공받는 코드 측을 클라이언트라 한다.

/////////////////서버

void print(){

cout<<"Hello"<<endl;

}

////////////////클라이언트

int main(){

print();

}

print()는 출력 기능을 제공 하니까 서버

main()은 print()함수를 호출해서

출력 기능을 제공받으니까 클라이언트

클라이언트 측에서 서버를 호출하고 기능을 사용하지만

때때로 서버가 클라이언트를 호출해야 하는 경우가 있다.

클라이언트가 서버를 호출하면 콜(call)

서버가 클라이언트를 호출하면 콜백(callback)이라 한다.

void print(){

client();

     --> 콜백

--> 서버에서 클라이언트 함수를 호출

}

void client() { ... }

int main(){

print();

-->콜

}

간단한 콜백 메커니즘이다.

하지만 서버가 실제 이럴수는 없다.

클라이언트가 어떤 함수를 가지고

있는지 알 수 없기 때문이다.

따라서 콜백 메커니즘을 구현하려면 클라이언트 정보를

서버에 제공을 해야하는데 그 방법 중 하나가

 함수 포인터 매개변수를 이용해 콜백 함수의 주소를 전달 하는 방법이다.

서버는 배열의 원소에 대해 반복적인 작업을 수행할 뿐

고체적인 작업은 알지 못한다. 구체적인 작업은

클라이언트에서 콜백 함수를 이용해 수행.

콜백 메커니즘을 이용하면 알고리즘 정책을

클라이언트에서 유연하게 바꿀 수 있게 서버를

더욱 추상화할 수 있다. 또한 대부분 GUI의 강력한

이벤트 기능도 콜백 메커니즘으로 구현된다.

또한 지금부터 공부하게 될 STL의 많은 알고리즘도

콜백을 이용해 클라이언트 정책을 반영한다.

따라서 함수 포인터를 이용한 콜백 메커니즘을 꼭 기억하자.

객체의 모든 부분을 빠짐없이 복사하자.

이 항목의 핵심은

복사생성자, 복사 대입연산자를 (복사 함수)

내가 직접 선언할 경우에 대한 문제점이다.

이러한 복사 함수를 직접 선언할 경우

어떤 문제점이 있는지 들여다 보자.

class AAA{

private:

int a;

public:

AAA(int _a) : a(_a){};

AAA(const AAA& ra){

a = ra.a;

}

AAA& operator=(const AAA& ra){

a = ra.a;

return *this;

}

}

모든 멤버(하나밖에 없긴 하지만)를

복사하는 복사함수이다. 여기까진 문제가 없어보이지만

클래스의 멤버 변수로 int b; 라는 놈이 선언되었다면

이 복사함수 내에서 a는 복사가 되지만 b는 복사가 되지 않는다.

더 큰 문제점은 컴파일러가 어떠한 경고 메세지도 주지 않는다는 점!

클래스의 상속에서 이러한 문제는 더 뚜렷하게 드러난다.

출력 결과

1

2

파생클래스에서 복사 대입연산자를 선언하고

자신의 멤버를 빠짐없이 대입한다.

하지만 기본 클래스의 멤버의 대입은 이루어 지지 않는다.

만약 이 대입 연산자를 자신이 생성하지 않았다면

기본 클래스의 멤버까지 말끔하게 복사 대입해준다.

(복사 생성자도 위와 같은 현상을 보인다.)

위의 경우에 복사생성자는 선언해 주지 않았다.

기본 클래스의 멤버 변수까지 완벽하게 복사가 되었다.

(기본 복사 생성자에 의해)

자신이 복사생성자를 선언해주려면

BBB(const BBB& rb) : AAA(rb) , b(rb.b) {};

이런 식으로 기본생성자에 대한 복사를

빠뜨리지 않도록 각별히 주의해야 한다.

복사 대입 연산자의 경우에도

BBB& operator=(const BBB& rb){

AAA::operator(rb);

...

return *this;

}

정리

1. 해당 클래스의 데이터 멤버를 모두 복사한다.

2. 이 클래스가 상속한 기본 클래스의 복사 함수도

꼬박 꼬박 호출을 해주어야 한다.

주의 사항!!

복사생성자 복사 대입연산자 내의

코드의 중복이 심하다고 해서

복사생성자 내에서 대입연산자를 호출한다거나

대입 연산자 내에서 복사 생성자를 호출하는 짓은 하면안된다.

왜??

1. 복사 대입 연산자에서 복사생성자를 호출하는 것은

이미 만들어져 있는 객체를 다시 생성하는 행위이다.

2. 복사생성자에서 대입 연산자를 호출 하는 것 또한 넌센스

생성자의 역할은 새로 만들어진 객체를 초기화 하는것

대입 연산자의 역할은 이미 초기화가 끝난 객체에 값을 주는 것

따라서 초기화된 객체에만 적용되는 것이다.

대신 코드의 내용이 비슷하다면

겹치는 부분을 별도의 함수로 만들어 놓고

private 멤버로 두고 호출해서 사용하는 방법도 있다.

POINT!!

1. 복사 함수는 모든 데이터멤버를 포함해

기본 클래스의 부분도 빠뜨리지 말아야 한다.

2. 두개의 복사 함수 한쪽을 이용해서 다른 한쪽을

구현하려는 시도는 절대로 하지 말아야한다.