IT's me

[C++ STL] C++의 선형 검색

전 포스팅에서 보았던 C로 작선된 find1은 char 형식의

배열만을 검색할 수 있었다. C++의 경우에는 템플릿을

이용해서 함수 인수의 형식을 매개변수화할 수 있으므로,

find1을 char 이외의 형식에 대해 일반화하는 것이 가능하다.

template <typename T>

T* find2 (T* first , T* last, T value);

상당히 명백하고도 직관적인 일반화이다.

하지만 STL은 약간은 덜 명백한 일반화를 사용한다.

template <typename Iterator. typename T>

Iterator find (Iterator first, Iterator last, const T& value){

while (first != last && *first != value)

++first;

return first;

}

이런 형태의 find가 find2보다 나은 점은 무엇일까?

find가 더욱 일반적이라는 데 있다. find2에는 

first, last가 포인터이어야 한다는 테한이 있지만,

find에는 그런 제한이 없다. 물론 포인터 연산의

구문을 사용하기는 하지만, Iterator가 반드시

포인터이어야 하는 것은 아니다. 

Iterator가 포인터 같은 인터페이스를 지원하기만 하면 된다.

find는 1차원적인 요소들의 순차열이라는 개념을 지원하는

임의의 자료구조에 대해 검색을 수행하는 하나의 일반적 알고리즘이다.

1. 선형 검색을 위해 필요한 것은, 하나의 요소를 조사하고,

2. 다음 요소로 넘어가고, 3. 모든 요소들을 처리했는지 판정하는 것이다.

[C++ STL] C의 선형 검색

선형적인 구간에 대해 작동하는 알고리즘의

중요한 아이디어에 대해 이야기해보자.

선형적인 구간이란, 하나의 첫 번째 요소와 하나의 마지막

요소가 존재하며, 마지막 요소를 제외한 모든 요소들에는 '그 다음 요소'가 있고,

첫 번째 요소에서 시작해서 다음 요소들을 계속 따라가다 보면 마지막 요소에

도달하게 되는 1차원적인 요소들의 모음을 말한다. 이러한 선형적인 구간들에

대해 작동하는 알고리즘들이 STL의 핵심부를 이루고 있다.

C의 선형 검색

C의 라이브러리 함수 strchr을 보도록 하자.

char* strchr(char* s, int c);

char* strchr( char* s, int c){

while ( *s != '\0' && *s != c)

++s;

return *s == c ? s : (char*) 0;

}

선형 검색의 일반적인 아이디어는

1. 순차열의 시작에서부터 요소 하나씩 거쳐가면서 주어진 값다 비교한다

2. 현재 요소가 주어진 값과 같으면, 알고리즘은 순차열 안에서의 현재 요소를 리턴

3. 같지 않다면 다음 요소로 넘어간다.

4. 다음 요소가 없다면 실패했음을 알리는 뭔가를 리턴

이러한 선형 검색을 구현할 때에는 몇 가지 이슈가 있다.

1. 검색하고자 하는 순차열을 어떻게 지정할 것인가?

2. 순차열 안의 한 위치를 어떻게 표현할 것인가?

3. 다음 요소로 넘어가려면 어떻게 할 것인가?

4. 순차열의 끝에 도달했음을 어떻게 알아낼 것인가?

5. 실패했음을 알리는 값으로 무엇을 사용할 것인가?

1. ctrchr 함수를 호출할 때 검색할 문자열의 첫 번째 요소를

가리키는 포인터를 넘겨준다.

2. 문자열 안의 한 위치 또한 포인터로 나타낸다.

3. 포인터 연산을 통해 접근한다.

4. 검색할 순차열은 하나의 C문자열, 즉 널로 끝나는 문자열이다.

때문에 현재 포인터가 \0을 가르킨다면 끝에 도달한 것

5. 선형 검색을 하는 동안 해당 문자를 찾지 못했다면

포인터는 문자열의 끝에 가 있을 것이므로 널 포인터를 리턴.

하지만 strchr은 일반적이지 않다. 이 함수는 char들의 배열 안에서

하나의 char를 검색하는 데에만 사용할 수 있다.

그리고, strchr의 첫 번째 인수는 널 종료 문자 배열을 가리키는

하나의 포인터이어야 하는데, 이는 보기보다 일반적이지 않다.

C에서는 널 종료 문자열이 대부분이긴하지만 부분문자열을

표현하려한다면 문제각 생기는 것도 사실이다.

부분 문자열을 지원하기 위해 strchr의 인터페이스를 수정해보자.

검색할 배열의 끝을 가리키는 포인터를 또 다른 인수로 지정해 보자.

char* find1 (char* first, char* last, int c){

while (first != last && *first != c)

++first;

return first;

}

이 find1 구현은 배열의 끝을 루프 반복의 종료 조건으로 해서

포인터로 배열을 훑는, 흔히 볼 수 있는 C관용구를 이용한다.

이 루프는 first가 last와 같으면 즉시 끝나며, 따라서 last는

역참조 되지 않는다. 즉, last 바로 전까지 모든 요소를 검색한다.

위의 함수에서는 3가지 포인터들이 사용된다.

1. 역참조할 수 있는 보통의 포인터

2. NULL 같은 유효하지 않은 포인터

3. 역참조할 수 없지만 포인터 산술에 사용할 수 있는 끝을 넘어선 포인터

char A[N];

C의 모든 배열에는 끝을 넘어선 포인터가 하나 존재한다. (A+N)

아무것도 가리키지 않기 때문에 역참조해서는 안되며,

딱 하나만 있으므로 포인터를 증가시키려 해서도 안된다.

오직 포인터 산술 연산에만 사용된다. (시작 이전 포인터 같은 것은 없다. A-1과 같은 ... )

[C++ STL] 선형 검색(find 알고리즘) 그리고 단순 연결 리스트

먼저 C++에서의 선형 검색에 대해 알아보자.

STL의 일반화된 선형 검색 알고리즘인

find는 다음과 같이 구현된다.

find는 1차원적인 요소들의 순차열이라는 개념을

지원하는 임의의 자료구조에 대해 검색을 수행한다.

선형 검색을 위해 필요한 것인, 하나의 요소를 조사하고,

다음 요소로 넘어가고, 모든 요소들을 처리했는지 판정하는 것이다.

애초에 [first , last]가 하나의 선형적인 구간이라고 가정하지 않는다면 무의미

이러한 find 알고리즘이 정말 일반적이라면

배열 뿐만 아니라 단순 연결 리스트의 검색도 가능해야 한다.

다음은 연결 리스트의 구성과 이러한 노드들의 목록을

훑을 때 사용하는 코드의 예시이다.

int_node들의 리스트는 하나의 선형 순차열이므로,

선형 검색 알고리즘을 다시 작성하는 것은 낭비이다.

 find를 재사용하는 게 바람직한데, 어떻게 해야 할까?

기존에는 단순하게 ++first라는 포인터 연산으로

다음 요소를 얻었지만, 지금은 검색하고자 하는 것이

배열이 아니라 하나의 연결 리스트이기 때문에

그런 포인터 연산은 통하지 않는다.

p가 int_node를 가리킨다면, 다음 노드는

++p (p+1)가 아니라 p->next이다.

이러한 문제는 C++의 연산자 오버로드로 해결할 수 있다.

우리가 원하는 행동을 하도록 구체적으로 정의하면 된다.

그런데 int_node* 형식의 인수들에 대해

operator++를 다시 정의하는 것은 불가능하다.

때문에 int_node*처럼 보이면서도 operator++를

좀 더 적절하게 정의하는 간단한 래퍼 클래스를 만들면 된다.

int_node 뿐만아니라 next 포인터를 가진

어떠한 형식의 노드에도 작동하도록 설계

이제 로프를 사용하지 않고도 특정한 값을 가진

int_node를 찾을 수 있다. find 함수를 재사용 해보자.

find(node_wrap<int_node>(list_head) , node_wrap<int_node>(), val)

두 번째 인자 node_wrap<int_node>()는 기본 생성자를 호출.

널 포인터를 가진다. 즉 리스트의 마지막을 나타낸다.

node_wrap이라는 래퍼는 사소해 보여도, 상당히 놀라운 기능을 한다.

위에 정의한 int_node는 어떻게 보면 C++이 나오기도 전에 정의된

구조체일 수도 있다. 이렇게 오래된 자료구조와 새로운 알고리즘

find를 함께 사용할 수 있게 되었다. 즉 node_wrap 클래스는

오래된 자료구조와 새로운 알고리즘 사이의 중재자 역할을 한다.

또한 모든 멤버 함수들은 인라인으로 정의되어 있다.

때문에 효울성을 전혀 손상시키지도 않는다.

오늘은 STL의 선형 검색 알고리즘 (find 알고리즘)과

단순 연결 리스트에 대해 알아 보았다.

이제부터 C++ STL의 개념적인 이야기보다

좀 더 원론적인 이야기를 포스팅해나가겠다.

C++ UML 다이어그램 중

클래스 다이어그램에 대해 알아보자.

이때까지 C++을 공부하면서 UML 기호를

가끔 접했었는데, 내용 이해에 크게 문제가

되지 않아서 대충 넘어갔었다. 하지만 패턴을

공부하다보니 UML 다이어그램에 대해

꼭 알아야 할 것 같아서 포스팅을 진행한다.

배경지식이나 기본적인 이론에 대해서는 생략하겠다.

UML설계 방식은 제껴두고 클래스들간의

관계에 대해서만 짚고 넘어가겠다.

UML Class Diagram

1. 상속 (Inheritance)

02. 인터페이스 구현 (Interface Implimentation)

03. 연관 (Association)

한 클래스가 다른 클래스를 사용한다. 때문에 두 클래스 사이의

life time은 전혀 상관이 없다. 각각 독립적으로 생성되고

연결이 될 수도, 연결이 되지 않을 수도 있다.

ex)

class Car --------- class Person

class Car {

private:

Person person;

public:

setPerson(Person _p){

this.person = _p;

// setPerson 메소드를 호출해서 사용

}

}

04. 집합 (Aggregation)

Aggregation 관계로 표현되는 전체 객체의 생성 시기가

꼭 동일할 필요는 없다. 소멸시에도 Aggregatin 관계의

클래스들이 다른 객체에 의해 공유될 수도 있다.

ex)

class Car <>------------ class Engine

class Car{

private:

Engine engine;

public:

Car(Engine _e){

this.engine = _e;

// 생성자의 매개 변수로 들어온 놈이

// 꼭 Car과 같이 생성될 필요는 없으며

// 외부에서 생성된 Engine은 다른 객체에서도

// 사용되고 있을 수도 있다.

}

};

05. 구성 (Composition)

객체의 생성과 소멸 시기가 동일하다.

즉 Car 클래스 생성자 내에서 Engine 클래스를 생성한다.

ex)

class Car <<>>------------- class Engine

class Car{

private:

Engine engine;

public:

Car(...){

this.engine = new Engine( ... );

}

};

06. 의존 (Dependency)

객체의 생성과 소멸 시기와는 연관이 없다.

 ex)

Car - - - - - - - - - > Aircon

class Car{

...

public:

void Air( Aircon con){

con.turnOn();

// Aircon 클래스를 인자로 받아 메소드를 내부적으로 호출한다.

// Aircon 의 turnOn 의 정의가 바뀌면

// Car 에 영향을 주게 되므로 의존 관계에 있다고 말한다.

}

};

UML 다이어그램(클래스 다이어그램)에 대해

간략하게 알아보았다. 이 정도만 알고있어도

책에 나오는 UML기호는 어느정도 알아볼 수 있다.

간단한줄로만 알았던 UML 다이어그램이

상당히 복잡하고 덩치가 큰 분야라는 것을 알았다.

다음에 기회가 된다면 좀 더 자세히 알아보는 시간을 가지겠다.

오늘은 C++의 캐스트 연산자에 대해 알아보겠다.

01. static_cast

c언어의 형변환과 유사하다.

double d = 5.5;

int n = static_cast<int>(d);

C에서는 n = (int)d;

실수형에서 정수형으로 형변환을 하였다.

당연히 소수점 부분은 잘려버리게 된다.

하지만 컴파일러가 허용하는 범위이기 때문에 가능.

stirng str = "abcd";

int n = static_cast<int>(str);

string을 int로 바꾸고 있다. 

이 경우는 컴퍼일러가 허용하지 않는다.

그리고 static_cast는 포인터 형변환이 안된다.

int n = 10;

int *pi;

double *pd;

pi = &n;

pd = static_cast<double*>(&n);

이런 식으로의 포인터 형변환은 되지 않는다.

포인터 형변환이 의미가 있는 경우는

클래스 상속과 연관될 때이다.

class AAA{

public:

int na;

};

calss BBB : public AAA {

public:

int nb;

};

AAA a;

AAA *pa;

BBB b;

BBB *pb;

pa = static_cast<AAA*>(&b);       1번

pb = static_cast<BBB*>(&a);      2번

2번의 경우 Base 클래스 자료형의 값을

Drieved 클래스 자료형에 할당하고 있기 때문에

다운 캐스팅을 하는 경우이다. 1번은 2번과

반대의 경우인 업 캐스팅을 하는 경우이다.

업캐스팅의 경우에는 문제가 안되지만

다운캐스팅의 경우에는 문제가 생긴다.

1번의 경우 pa가 Drived 객체에 있는 멤버에

접근을 하지 못하지만 문제가 되진 않는다.

하지만 2번의 경우 즉 다운캐스팅이 된 경우를 보자.

Drived 클래스에는 Base에는 없는데 자신만 가지고 있는

멤버의 존재가 가능하다. 이 경우 원래 존재하지도 않는

값을 참조하게 될 수 있다는 문제가 발생한다.

pb -> nb; 같은 식으로 말이다.

02. dynamic_cast

위와 같은 문제 때문에 나타난 것이 바로 dynamic_cast이다.

상속 관계에 있는 클래스 포인터끼리의 형변환을 허용하되,

다운 캐스팅이 일어나면 null 값을 대신 리턴하여 위험을 알린다.

따라서 이 형변환을 사용할 때는 먼저 결과가 null이

아닌지 확인하는 것이 좋다. 또한 이 형변환을 사용하기 위해서는

클래스가 다형성을 가져야 한다. 가상함수가 있어야 한다는 말.

class AAA{

public:

virtual void print() { cout<<"부모 객체"<<endl }

};

class BBB : public AAA{

public:

virtual void print() { cout<<"자식 객체"<<endl }

};

AAA aaa;

AAA *pa;

BBB bbb;

BBB *pb;

1번

pa = dtnamic_cast<AAA*>(&aaa);

if(pa) pa->printf();

else cout<<"캐스팅 실패"<<endl;

2번

pa = dtnamic_cast<AAA*>(&bbb);

if(pa) pa->printf();

else cout<<"캐스팅 실패"<<endl;

3번

pb = dtnamic_cast<AAA*>(&aaa);

if(pa) pa->printf();

else cout<<"캐스팅 실패"<<endl;

4번

pb = dtnamic_cast<AAA*>(pa);

if(pa) pa->printf();

else cout<<"캐스팅 실패"<<endl;

1번의 경우 당연히 성공

2번의 경우도 당연히 성공 (다형성의 중요한 부분)

3번의 경우 다운캐스팅이기 때문에 실패한다.

4번의 경우 Base 형 포인터의 값을 가져왔으나

그게 사실 Drived 형 객체를 가리키기 때문에 성공.

따라서 위의 결과는

부모 객체

자식 객체

캐스팅 실패

자식 객체

위에서 살펴본 형변환의 이점은 가독성과 디버깅의 편리함이다.

dynamic_cast는 엉뚱한 다운캐스팅으로 인한 오류를

경우에 따라 훨씬 빨리 찾아내는게 가능해진다.

STL에 필요한 템플릿 예제

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

int에 대한 For_each와 출력 함수

 string에 대한 For_each와 출력 함수

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

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

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

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

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

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

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

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

아래 예제를 보자.

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

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

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

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

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

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

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

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

void print(){

cout<<"Hello"<<endl;

}

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

int main(){

print();

}

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

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

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

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

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

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

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

void print(){

client();

     --> 콜백

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

}

void client() { ... }

int main(){

print();

-->콜

}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

STL에 필요한 주요 연산자 오버로딩

이번 시간은 STL에 필요한

연산자 오버로딩에 대해 알아보겠다.

연산자 오버로딩에 대한 기초적인 지식만 있다면

충분히 따라올 수 있는 내용이다.

1. 함수 호출 연산자 오버로딩

2. 배열 인덱스 연산자 오버로딩

3. 멤버 접근 연산자 오버로딩

스마트 포인터란?

일반 포인터를 사용하면 new 연산 후

delete 연산을 꼭 해주어야 한다.(안해주면 메모리 누수)

스마트 포인터는 소멸자에서 자신이

동적으로 생선한 객체를 자동으로

소멸시켜주기 때문에 메모리 누수의 위험이 없다.

4. 타입 변환 연산자 오버로딩

전방 선언에 대해 알아보자.

먼저 전방 선언이란?

불필요한 헤더 파일이 복잡하게 포함되는 것을 방지하며, 컴파일 속도를 향상시켜준다.

전방 선언은 헤더 포함 의존성을 줄이기 위해 사용된다.

특정 클래스를 정의할 때, 멤버 변수나 리턴 값, 파라미터 등으로

또 다른 클래스를 사용한다면 해당 클래스의 정의도 포함시켜야 한다.

즉, AAA 라는 클래스를 정의할 때

BBB 를 사용한다는 것이다.

일반적으로는 

#include "BBB.h"

class AAA{

...

...

}

별 문제없는 방법으로 보일 수 있으나,

임포트한 헤더 파일에는 현재 클래스에서 필요로 하는

정보 외에도 많은 정보를 포함하고 있다.

또한 BBB.h에 다른 h들도 포함되어 있다면..?

필요이상의 시간을 소비하는 결과를 낳게 된다.

이러한 문제의 해결을 위해 우리는 전방선언과 친하게 지내야 한다.

문제가 되었던 상호 참조 문제라던가

컴파일 부하문제를 깔끔하게 해결해준다.

예제를 보자.

AAA 클래스.

BBB 클래스.

BBB 클래스 --> AAA를 include하지 않고 전방선언을 해주고 있다.

주의 할 점은 BBB클래스는 AAA라는 클래스의 존재 유무만 알고있다.

때문에 AAA의 구체적인 크기에 대해선 알지 못한다.

따라서 포인터로만 선언될 수 있다.

이를 동적 생성하거나 함수를 호출하면 에러!!

AAA a; 로 선언 되어도 에러!!

다시 한번 말하지만 전방 선언은 단순히 선언이기 때문에

생성, 호출은 실제 데이터 구조를 모르는 상태에서 진행될 수 없다.

전방 선언된 AAA를 BBB.cpp에서 구현

전방 선언을 하는 것은 선언된 클래스의 이름을 간단히 컴파일러에게

심볼 테이블에 추가하라고만 하는 것이 아니라, 실제로 이 클래스가

필요할 때 그 정의를 함께 제공하겠노라고 약속하는 것이다.

따라서 전방선언한 클래스에 접근하는 cpp 파일에는

반드시 #include "AAA.h" 를 선언하고 사용해야 한다.

예제를 보았지만 예제가 매우 허접하여 감이 안잡힌다.

전방선언이 요긴하게 쓰이는 부분에 대해 더 짚어보자.

1. 포인터/ 참조 형식으로 이름만 참조할 경우

class AAA;

class BBB{

public:

BBB doSomething1 (const AAA* a);

BBB doSomething2 (const AAA& a);

};

2. 매개변수나 리턴 타입을 위한 이름만 참조할 경우

class AAA;

class BBB{

public:

void SetData(AAA a);

AAA GetData() const;

};

이 경우 컴파일러가 AAA의 크기를 알아야 한다고 생각할 수 있지만,

함수를 구현하는 코드와 호출하는 코드에서만 클래스의 크기를 요구한다.

간단하게나마 전방선언에 대해 알아보았다.

그 필요성에 대해서는 알겠으나,

아직 많이 낯선것도 사실. 분발하자.

팩토리 함수

팩토리 함수, 팩토리 메소트, 팩토리 메소드 패턴이라 불리는데

객체를 생성하기 위한 인터페이스를 제공하는데, 어떤 클래스의

인스턴스를 만들지는 서브클래스에서 결정한다.

즉, 클래스의 인스턴스를 만드는 일은 서브클래스가 한다는 말이다.

팩토리 메서트 패턴은 추상클래스에서 객체를 만드는 인터페이스만 제공한다.

추상클래스는 어떤 객체가 생성될지 전혀 모른다.

어떤 객체가 생성될 지는 이 추상클래스를 상속받은

서브클래스에서 실제로 팩토리 함수를 구현함으로써 이뤄진다.

말로만 해서는 모르겠다. 예제를 보도록하자.

MonMgr이라는 클래스는 객체를 생성하기 위한 인터페이스만 제공한다.

그리고 객체의 포인터를 리턴하는 팩토리 함수를 멤버로 가지고 있으며

MonMgr의 파생클래스에서 이 함수를 구현함으로써 어떤 객체가 생성될지 결정된다.

예제가 많이 허접하다. 그래도 팩토리 함수가 무엇인지는 감이 오는 것 같다.

그렇다면 이 팩토리 함수를 어떤 경우에 써야 효율적인 것일까.

1. 구체적으로 어떤 객체를 생성해야할지 알 수 없는 경우

2. 하위 클래스가 객체를 생성하기를 원할 때

3. 하위 클래스들에게 개별 객체의 생성 책임을 분산시켜

객체의 종류별로 객체 생성과 관련된 부분을 국지화 시킬 때

음.. 어떤 것인지는 알았으나 어떤 경우에 써먹어야 하는지

아직은 모르겠다.. 코딩 경험이 쌓이다보면 자연스레 알게되겠지