[자료구조] 연결 리스트의 이해(2)


오늘은 연결 리스트의 초기화, 삽입, 조회, 삭제가 어떻게

동작하는 지에 대해 알아보고 가는 시간을 갖도록 하겠다.


자료구조란 학문은 그림을 그리면서 이해하는 것이 가장 중요하다.

아래의 포스팅은 코드만 나와있지만, 공부를 제대로 하고자 한다면

자신이 직접 그림을 그리면서 이해를 해야한다.




01. 초기화




02. 삽입




03. 조회




04. 삭제




연결 리스트가 어떻게 동작하는지 간단한 코드 예시를 보았다.

앞서 말했듯이 자료구조라는 학문은 그림을 그리면서 이해하는

것이 무엇보다 중요하다. 그림도 같이 올려서 포스팅 하고 싶지만

많은 시간이 걸리기 때문에 소스 코드만 포스팅하게 되었다.




위의 소스 코드를 보면 연결 리스트의 삽입, 조회, 삭제의 과정에서

첫 노드와 첫 노드 이외의 모든 노드의 처리과정이 분리되어

있다는 것을 알 수 있다. 이 보다 좀 더 좋은 코드가 되기 위해서는

모든 처리가 while(1){ .. } 안에 들어가야 할 것이다.




하지만 이는 좀 더 복잡한 코드가 나오게 할 뿐이다.

이에 대한 해결책은 더미 노드라는 것인데,

이렇게 첫 노드와 나머지 노드를 나누어 처리하는 이유와

더미 노드란 무엇이며 어떻게 적용되는 지에 대해서는

다음 포스팅에서 계속 이어 가도록 하겠다.





public 상속은 반드시 is-a 관계를 따르도록 하자.


사람 <------ 학생

위의 표현은 C++ 기본서에서

public 상속을 설명할 때 가장

빈번히 활용되는 예이다.




학생은 사람이라서 사람이 할 수 있는

(먹기, 앉기, 눕기 등등)을 할 수 있지만

모든 사람은 학생이 아니기 때문에

모든 사람은 학교를 다닌다가 참이 될 수 없다.




즉, Base클래스 (사람) 은 일반적인 개념을 타나내며

Drived클래스 (학생) 은 좀 더 특수화된 개념을 나타낸다.


public 상속과 is-a 관계가 똑같은 뜻이라는 이야기는

꽤 직관적이고 간단하긴 하지만, 그 직관 때문에 잘못된

판단을 하는 경우가 있다. 아래의 예제를 보도록 하자.

펭귄은 새의 일종이고, 새는 날 수있다는 것을 알고있다.




class Bird{

public:

virtual void fly();            // 새는 날 수 있다.

...

};

class Penguin: public Bird{    // 펭귄은 새이다.

...

};


새는 날 수 있다는 사실을 바탕으로 클래스를 디자인 했는데

펭귄이라는 새는 날지 못한다. 모든 새는 날지 못한다는 점도 

구분하여 좀 더 현실에 가까운 클래스 계통구조를 만들어야 한다.




class Bird {

...                                            // fly 함수가 없다.

}


class FlyingBird : public Bird{

public:

virtual void fly();

...

};


class Penguin: public Bird {

...                                            // fly 함수가 없다.

};




좀 더 현실에 가까운 클래스 구조가 되었다.

하지만 어떠한 소프트웨어 시스템이냐에 따라

새의 비행능력을 고려하지 않아도 되는 경우가 있다.

만약 새의 서식지와 먹이에 대한 응용프로그램이라면

처음 디자인한 클래스가 더욱 만족스러울 것이다.

즉, 프로그램의 요구 사항에 맞게 디자인 하는 것이 중요하다는 것이다.




이번에는 위의 펭귄문제를 런타임 에러를 통해 해결해보자.


void error(const std::string& msg);


class Penguin : public Bird {

public:

virtual void fly() { error ("Attempt to make a penguin fly!"); }

...

};


이 경우는 "펭귄은 날 수 없다." 가 아닌

"펭귄은 날 수 있다. 하지만 날려고 하면 에러가 난다" 이다.

"펭귄은 날 수 없다" 라는 것은 컴파일러가 판단할 수 있지만,

"날려고 하면 에러가 난다" 는 런타임에만 발견할 수 있다.




자 그럼 이번에는 컴파일 타임에서 이 문제를 해결해 보도록 하자.


class Bird{

...                                    // fly 없음

};


class Penguin : public Bird {

...                                    // fly 없음

};


Penguin p;

p.fly();                                    // 에러


이제 펭귄을 날려 보려고 하면, 컴파일 단계에서 문제가 생기게 된다.

런타임 에러를 내주는 것은 p.fly를 호출하는 것에 대해 문제가 없다.

런타임, 컴파일 타임 과연 어떤 해결책이 더 좋은 것일까?




유효하지 않은 코드를 컴파일 단게에서 막아 주는 인터페이스가

좋은 인터페이스이다. 즉 , 펭귄의 비행을 컴파일 타임에 거부하는

설계가 그것을 런타임에 뒤늦게 알아내는 것보다 훨씬 좋다는 것이다.




새와 펭귄 문제는 이쯤하고, 사각형과 정사각형을 클래스의

상속 계통으로 만드는 문제로 넘어가 보자. 초등학교 수학시간에

배운 기억을 바탕으로 우리는 "정사각형은 직사각형이다."라는

사실을 알고 있을 것이다. 때문에 정사각형은 직사각형을

상속받도록 디자인 해야한다고 생각하는 것도 당연할 것이다.




하지만 직사각형은 넓이와 높이 모두 자유자재로 바뀌어도

직사각형이라는 것을 만족한다. 하지만 이를 상속받는

정사각형은 가로 새로가 항상 일치해야 한다는 조건이 있다.

때문에 직사각형에 가로 혹은 세로를 마음대로 조정하는

함수가 있다면, 정사각형에는 적용할 수 없는 함수이다.

때문에 이 케이스틑 is-a관계가 적용될 수가 없다.




여기서 중요한 부분은 public 상속은 기본 클래스 객체가

가진 모든 것들이 파생 클래스 객체에도 그대로 적용되는 상속이다.

때문에 직사각형과 정사각형은  public 상속으로 표현한다면

틀린 것이고, 컴파일 수준에서 무사히 통과과 되었다 해도

제대로 동작할 것이라는 보장은 없다.




코드가 컴파일된다는 것이 제대로 동작한다는 의미는 아니다.

이런 점 때문에 프로그래머는 계속 배움의 길을 개척해 가야한다.


Point!!

public 상속의 의미는 is-a 이다.

기본 클래스에 적용되는 모든 것들이

파생 클래스에 그대로 적용되어야 한다.

모든 파생 클래스 객체는 기본 클래스 객체의 일종이기 때문이다.




[자료구조] 연결 리스트의 이해(1)


연결 리스트는 크게 배열 기반 연결 리스트와

연결 리스트 기반 연결 리스트가 있는데

우리가 흔히 사용하는 연결리스트는 후자이기 때문에

연결 리스트 기반의 연결 리스트에 대해 알아보도록 하겠다.




들어가기에 앞서 배열과의 비교가 우선시 되어야 할 것같다.

배열이라 함은 기본 제공되는 상당히 훌륭한 자료구조이다.

배열의 가장 큰 장점 중 하나는 index를 통한 순차접근이다.


배열의 가장 큰 단점 중 하나는 크기가 결정되어야 한다는 것인데

이는 매우 큰 부담으로 작용한다. 물론 크기를 바꿀 수 있는 방법이 없는 것은

아니지만, 그에 따른 비용이 만만치 않기 때문에 큰 단점이라 할 수 있다.




때문에 배열보다 좀 더 유연하고 순차 접근을 훌륭히

 수행할 수 있는 것이 필요한데 이것이 바로 연결 리스트이다.


malloc를 이용한 동적할당이 기본이 되어야하고,

할당된 메모리를 어떻게 접근하고 관리할 것인가가

연결 리스트를 이해하는 것의 가장 큰 이슈가 될 것이다.




1. 구조체의 이해

2. 동적 할당 (malloc)

3. 어떻게 연결할 것인가?

4. 어떻게 순차 접근할 것인가?




1. 구조체의 이해

힙에 할당되어 저장되는 자료를 우리는 노드(node)라고 부른다.

노드는 C에서 구조체 변수이다. (기본 제공 타입이 아님)


이렇듯 노드에는 데이터를 담을 공간과

다음 노드를 가리킬 구조체 포인터를 가지고 있다.




2. 동적 할당

malloc, free는 C언어 기본서 참고




3. 어떻게 연결할 것인가?

들어가기에 앞서 노드의 연결과 참조를 위한 핵심을 훑어보자.



next는 현재 노드의 다음 노드를 가리키고 있다.

이렇게 노드들을 쭉 연결 한다면 비엔나 소시지처럼

연결된 모양이 될 것이고, 결과적으로는 첫 노드의

주소값만 알고 있다면 모든 노드를 탐색할 수 있다.


n1,n2는 노드이고 각각의 데이터를 가지고 있다.

next라는 구조체 포인터는 자신의 다음 노드를 가리키도록 한다.

( 주의할 점은 꼭 현재 노드의 뒤에만 새로운 노드가 올 수 있는 것은 아니다. )

현재 노드의 앞 뒤 어느 곳에서든 노드가 추가될 수 있어야 한다.




4. 어떻게 순차 접근을 할 것인가?

n1의 next는 자신의 다음 노드를 가리키고 있기 때문에

*를 사용한다면 자신의 다음 노드에 접근할 수 있다.




연결 리스트와 배열과의 차이점 그리고 연결 리스트를

구현하기에 앞서어떠한 핵심을 공략해야하는지에 대해

간단하게 알아보았다. 다음 포스팅부터는 이슈들을 하나하나

 해결해가며 연결 리스트를 구현해 보도록 하겠다.


[C#] string 그리고 가비지 컬렉션


유니티를 통해 3D 게임을 만들 때

최적화 문제로 굉장히 고생했던 적이 있다.

그 때 봤던 최적화 팁에서 string + string 은

가비지를 생성한다해서 StringBuilder의 Append를

이용하여 문자열을 병합하라고 했다. 그런데 도대체 왜?




해답은 바로 문자열은 변경할 수 없는 객체라는 것에 있다. (immutable)

그렇다면 변경할 수 없는 거랑 가비지 컬렉션이랑 무슨 관계가 있는 것일까?


앞서 말했듯 문자열은 한번 생성되면 변경되지 않는다.

하지만 사실 문자열을 사용하면서 변경에 대해 어려움을

느낀 경우는 잘 없을 것이다. 이러한 문자열의 표면적인

변경은 쉽지만 내부적으로는 항상 새로운 문자열이 만들어지게 된다.




string str = "하하하";

str += "쏭";


예상대로 "하하하쏭"이라는 결과가 나온다.




그러나 메모리 측면에서는 처음 생성한 str과

이후 추가 문자가 덧 붙여진 str은 완전 다른 객체이다.


즉, "쏭"이라는 글이 추가될 때 새로운 객체가 메모리에 할당되고

이 것을 str이 다시 참조하도록 되는 것이다. 처음에 만들었던

"하하하"라는 객체는 사라지게 되는 것이다. (가비지)




성능을 위해서라면 String 대신 StringBuilder를 사용하자.


후에 좀 더 자세히 다뤄볼 StringBuilder에 대해 알아보자.

앞에 말했듯이 문자열은 변경될 수 없는 객체이기 때문에

문자열에 대한 어떠한 변경도 항상 새로운 객체를 생성하게 된다.


문자열 변경 작업이 빈번하다던지, 대량으로 문자열을 연결할

경우에는 성능을 반드시 고려해볼 필요가 있다.

왜냐하면 앞서 말했듯 문자열의 변경은 가비지를 유발하기 때문.




이 대안으로 StringBuilder 클래스를 생각해 볼 수 있다.

자 그렇다면 string + string을 어떻게 하면 가비지없이

수행해낼 수 있는지 알아보도록 하자.


System.Text.StringBuilder sb = new System.Text.StringBuilder();

sb.Append("하");

sb.Append("하하");

sb.Append("쏭");


StringBuilder는 String과는 달리 변경 가능한 액체이기 때문에

(mustable) string + string의 가비지 문제를 해결할 수 있다.




추가

MSDN의 성능 고려사항을 짚고 넘어가 보자.


MSDN에 따르면 Concat 및 AppendFormat 메서드는 새 데이터를

기존 String 또는 StringBuilder 개체에 연결한다. String개체 연결

작업에서는 항상 기존 문자열과 새 데이터로 새 개체를 만든다. 


StringBuilder 개체는 연결된 새 데이터를 수용할 버퍼를 유지한다.

새 데이터는 공간이 있을 경우 버퍼 끝에 추가되고, 그렇지 않으면

더 큰 새로운 버퍼가 할당되고, 원래 버퍼의 데이터가 새 버퍼에

복사된 다음, 새 데이터가 새 버퍼에 추가된다.




String 또는 StringBuilder 개체에 대한 연결 작업의 성능은 얼마나

자주 메모리를 할당하는지에 따라 달라진다. StringBuilder 연결

작업에서는 StringBuilder 개체 버퍼가 너무 작아 새 데이터를 넣을 수 없는

경우에만 메모리가 할당되는 반면, String 연결 작업에서는 항상 메모리가 할당된다. 


따라서 고정된 수의 String 개체를 연결하는 연결 작업에는

String 클래스가 더 적합하다. 이 경우 개별 연결 작업이 컴파일러를

통해 단일 작업으로 결합될 수 있다. 임의의 개수의 문자열을 연결하는

(예 : 루푸에서 읨의의 개수의 사용자 입력 문자열을 연결할 경우)

연결 작업에는 StringBuilder 개체가 더 적합하다.





[C#] 이벤트와 델리게이트




어떠한 일이 생겼을 때 이를 알려주는 객체가

필요한 경우가 있다. 예를 들어 사용자가 버튼을

클릭했을 때 이를 알려주는 객체가 그 것이다.

이런 객체를 만들 때 사용하는 것이 바로 이벤트이다.

이벤트의 동작 원리는 델리게이트와 거의 비슷하다.


이벤트는 델리게이트를 event 한정자로 수식해서 만든다.




자 그럼 이벤트는 어떻게 만드는지 차근차근 보도록 하자.

1. 델리게이트 선언. 클래스 밖에 선언해도 되고 안에 해도 된다.

2. 선언한 델리게이트의 인스턴스를 event 한정자로 수식해서 선언

(여기서는 클래스 내부에 있어야 한다.)

3. 이벤트 핸들러를 작성한다. 선언한 델리게이트와 일치하는 메소드여야 한다.

4. 클래스의 인스턴스를 생성하고 이 객체의

이벤트에 3에 작성한 이벤트 핸들러를 등록한다.

5. 이벤트가 발생하면 이벤트 핸들러가 호출된다.






앞서 보았듯이, 이벤트는 델리게이트에 event 키워드로

수식해서 선언한 것에 불과하다. 과연 무엇이 다를까?


이벤트와 델리게이트의 가장 큰 차이점은 바로

외부에서 접근을 할 수 있느냐 없느냐




이벤트는 public 한정자로 선언되어 있어도

자신이 선언되어 있는 클래스 외부에서는

호출이 불가능하다. 반면 델리게이트는

public이나 internal로 수식되어 있으면

클래스 외부에서라도 얼마든지 호출 가능하다.





이벤트의 이러한 특성은 견고한 이벤트 기반

프로그래밍을 가능하게 한다.

때문에 이벤트는 객체의 상태 변화나

사건의 발생을 알리는 용도로 사용이 되고

델리게이트는 콜백용도로 사용이 된다.



'C#, 유니티' 카테고리의 다른 글

[C#] C/C++/C# 메모리 할당과 가비지 컬렉터  (0) 2017.04.03
[C#] string 그리고 가비지 컬렉션  (0) 2017.03.29
[C#] 익명 메소드  (0) 2017.03.05
[C#] 일반화 델리게이트  (0) 2017.03.05
[C#] 델리게이트 (delegate)  (0) 2017.03.05

[C#] 익명 메소드


C#에서는 익명 메소드라는 것이 있는데

말그대로 이름이 없는 메소드이다.


어떻게 이름이 없는 메소드가 있을까?

생각할 수 있지만 델리게이트를 통해

선언하고 사용될 수 있다. (밑의 예제 참고)




위의 궁금증보다 사실 이런 메소드를

대체 어디다 쓰려는 것일까? 라는 의문이 드는데

익명 메소드는 람다식에서 아주 유용하게

쓰인다고 하니 람다식을 공부하면서 좀 더

깊게 공부해보는 시간을 가지도록 하겠다.




delegate int Calculate (int a , int b);


public static void Main(){

Calculate Calc;

Calc = delegate ( int a, int b ){

return a + b;

}


Console.WriteLine("3+4 : {0}", Calc(3,4);

}




익명 메소드는 delegate 키워드를 이용하여 선언한다.

익명 메소드는 자신을 참조할 델리게이트의 형식과 동일해야 한다.

익명 메소드는 매개 변수의 형식, 개수까지도 동일해야 한다.


델리게이트가 참조할 메소드를 넘겨야 할 일이 생겼는데,

이 메소드가 두 번 다시 사용할 일이 없다고 판단 되면 그 때

사용하는 것이 익명 메소드란다. 매번 사용되고 복잡한

메소드라면 익명 메소드를 사용하지 않는 것이 바람직할 것이다.

(아직은 익명 메소드에 대해 감이 잘 잡히지 않는다.)




아래의 익명 메소드 예제를 보면서 포스팅을 마치도록 하겠다.




이렇듯 익명 메소드는 구현부가 항상 따라다니기 때문에

여러번 사용될 메소드라면 꽤나 번거로울 것이다. 그리고

복잡한 내용의 메소드라면 가독성을 해칠 수 있기 때문에

이 경우에도 사용하지 않는 것이 좋을 것이다. 이 익명 메소드는

후에 공부할 람다식에서 다시 자세하게 알아보도록 하겠다.


[C#] 일반화 델리게이트


델리게이트는 보통의 메소드뿐 아니라

일반화 메소드도 참조할 수 있다.

물론 이경우에는 델리게이트도 일반화

메소드를 참조할 수 있도록 형식 매개 변수를

이용해서 선언을 해주어야 한다.


delegate int Compare<T>(T a, T b);




그 전 포스팅에서 다루었던

오름차순 내림차순 함수를 참조하는 델리게이트와

이를 매개 변수로 받아서 정렬 방식을 결정하는

버블 소트의 예제를 일반화 버전으로 바꾸어 보겠다.




결과




일반화된 델리게이트로 수정했다.

위 부분에서 IComparable<T>를 상속받는부분이 있는데

이 부분에 대해서 좀 짚고 넘어가 보자.


System.Int32Pint), System.Double(double)을 비롯한

모든 수치 형식과 System.String(string)은 모두

IComparable을 상속해서 CompareTo() 메소드를구현하고 있다. 

CompareTo() --> 자신 보다 크면 -1, 같으면 0, 작으면 1을 반환




위의 코드에서 where T : IComparable<T>는

T가 무조건 IComparable<T>를 상속하는 파생클래스여야 한다는 뜻이다.

때문에 T는 CompareTo() 라는 메소드를 쓸 수 있어야 한다.




일반화된 델리게이트에 대해 알아보았다.

형식 매개 변수 제약에 관한 내용이 잠깐 나왔는데

이 부분에 대해서는 나중에 일반화 프로그래밍을

포스팅할 때 다뤄보도록 하겠다.




[C#] 델리게이트 (delegate)


델리게이트란?

델리게이트는 메소드에 대한 참조이다.

델리게이트에 메소드의 주소를 할당한 후

델리게이트를 호출하면 이 델리게이트가

메소드를 호출해준다.




언제 사용하는가?

프로그래밍을 하다 보면 '값'이 아닌 '코드'를 매개 변수로 넘기고

싶을 때가 있다. 배열을 정렬하는 메소드를 예로 들자면,

이 메소드가 오름차순으로 정렬할 것인지, 내림차순으로

정렬할 것인지, 아니면 특별한 계산식에 의해 정렬할 것인지

이 메소드가 정렬을 수행할 때 사용하는 비교 루틴을

매개 변수로 넣을 수 있다면 아주 유연한 프로그램이 될 것이다.

이에 대한 예시는 밑에서 다시 다루도록 하겠다.




C++ STL의 알고리즘에 함수 포인터를

이용한 콜백 메커니즘이 사용되는데

델리게이트 또한 이 함수포인터와

유사하다고 생각하면 될 듯하다.




한정자 delegate  반환형식 델리게이트 이름 ( 매개변수 목록 );

ex) delegate int MyDelegate ( int a , int b);


--> 참조할 메소드의 반환 형식과 매개 변수를 명히해줘야 한다.

--> 델리게이트는 인스턴스가 아닌 형식이다.

--> 따라서 MyDelegate의 인스턴스를 따로 만들어야 한다.




ex)

int Plus (int a, int b){ ... }

MyDelegate CallBack;

CallBack = new MyDelegate(Plus);

--> new 연산자를 사용하여 인스턴스를 만든다.




ex)




결과




오늘은 C#의 델리게이트(delegate)에 대해 알아보았다.

그냥 함수 포인터인 것 같다. (아직까지는..)

다음 시간에는 일반화된 델리게이트에 대해 알아보겠다.




[C++] 타입 변환이 모든 매개변수에 대해 적용되어야

한다면 비멤버 함수를 선언하자.


유리수를 나타내는 클래스를 만들고 있다.

이 클래스를 디자인할 때 정수에서 유리수로

암시적 변환은 허용하자고 판단을 했다.

int -> double 변환과 별반 다르지 않기 때문에.




class Rational {

public:

Rational ( int numerator = 0 , int denominator = 1 );

// explicit으로 선언하지 않았다.


int numerator() const;    // 분자 접근 함수

int denominator() const;    // 분모 접근 함수


private:

...

}



유리수를 나타내는 클래스이기 때문에 덧셈이나

곱셈 등의 수치연산은 기본으로 지원해야 할 것이다.


멤버 함수로 연산자 오버로딩을 해보자.

const Rational operator* (const Rational& rhs) const;

이로써 곱셈 연산이 가능해진다.


Rational oneEighth (1 , 8);    // 가능

Rational oneHalf(1, 2);    // 가능


Rational result = oneHalf * oneEighth;    // 가능

result = result * oneEighth;    // 가능




이제 혼합형 수치 연산을 해보자.

유리수를 int(정수)와 곱셈을 가능하게

하는 것도 어떻게 보면 당연한 일이다.


result = oneHalf * 2;    // 가능

result = oneHalf.operator(2);    // 가능


result = 2 * ontHalf;    // 에러

result = 2.operator(oneHalf);    // 에러




첫 번쨰 줄에서 oneHalf 객체는 operator* 함수를 멤버로

가지고 있는 클래스의 인스턴스이기 때문에, 컴파일러는

이 함수를 호출한다. 하지만 두 번째 줄에서 정수 2에는

클래스 같은 것이 연관되어 있지 않기 때문에 operator*

멤버 함수도 있을리가 없다. 따라서 컴파일러는 비멤버

버전의 operator*를 찾아본다.


result = operator*(2,oneHalf);


비멤버 버전의 operator*가 없기 때문에 실패.




여기서 위의 성공 케이스를 다시 보도록 하자.

매개변수가 정수 2인데 Rational 객체를 받도록

되어 있는 operator*의 호출을 가능하게 한다.

이게 어떻게 가능한 것일까?


바로 암시적 타입 변환에 의해 가능하게 되는 것이다.

컴파일러는 이 int를 Rational 클래스의 생성자에 주어

호출하면 Rational로 둔갑시킬 수 있다는 사실도 알고 있다.




따라서

const Rational temp(2);

result = oneHalf * temp;

이런식으로 동작을 하게 된다.


물론 생성자를 명시호출 (explicit)로 선언되었다면 모두 불가능.



자 다시 돌아와서 둘 다 비명시호출을 했는데도 하나는 되고

하나는 왜 되지 않는지 고민해 보도록 하자.


result = oneHalf * 2; --> 비명시호출 생성자

result = 2 * ontHalf; --> 비명시호출 생성자인데도 안됨




결론

암시적 타입 변환이 먹혀들려면 매개변수 리스트에 들어있어야만 한다.

전자의 경우 매개변수 리스트에 있는 객체가 쓰이고 있지만

후자는 그렇지 않다. operator*의 구현부를 살짝 보자면

this * rhs 두 개의 매개 변수로 이루어져 있을 것인데

this란 놈은 매개변수 리스트에 없고 rhs란 놈만 있다.

따라서 매개변수 리스트에 있는 rhs란 놈만 암시적 타입변환이 일어난다.

암시적 타입 변환이 모든 매개변수에 대해서 이루어 지지 않고 있다.


그렇다면 모든 인자에 대해 암시적 타입변환을 수행하도록 하려면

어떻게 해야할까? operator*를 비멤버 함수로 만들어버리면 된다.




const Rational operator* (const Rational& rhs, const Rational& rhs){

return Rational (lhs.numerator() * rhs.numerator(),

   lhs.denominator() * rhs.denomiator());

}


Rational oneForth (1, 4);

Rational result;


result = oneFourth * 2;    // 가능

result = 2 * oneFourth;    // 가능




위의 함수는 비멤버이지만 프렌스 함수로 선언해야

하는 것 아닌가 의아해 할 수도 있다. 하지만 위의 

operator*는 클래스의 private 부분을 하나도

건드리지 않고 있다. 오로지 public 부분만을

사용하기 때문에 프렌드 선언은 적절하지 않다.


--> 프렌드 함수는 피할 수 있으면 피할 것




POINT!!

어떤 함수에 들어가는 모든 매개변수(this도 포함)에 대해

타입 변환을 해 줄 필요가 있다면, 그 함수는 비멤버이어야 한다.

[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++' 카테고리의 다른 글

[C++ STL] C++의 선형 검색  (0) 2017.04.04
[C++ STL] C의 선형 검색  (0) 2017.04.04
[C++] UML 다이어그램 (클래스 다이어그램)  (0) 2017.01.17
[C++] static_cast , dynamic_cast  (0) 2016.12.27
[C++ STL] STL에 필요한 템플릿 예제  (0) 2016.12.21

+ Recent posts