2009.09.01 00:04 책 정리/Modern C++ Design

이번 테크닉은 Typelist에 들어 있는 찾고자하는 자료타입이 몇번 인덱스에 존재하는지 찾기 위한 테크닉이다. 만약 원하는 결과가 있다면, 그 인덱스를, 원하는 결과가 없다면 -1을 리턴하면 좋을듯 싶다.

가지고 있는 정보를 토대로 로직을 구상해 보면 다음과 같다.
1. 탐색하는 흐름이 NullType까지 왔다면, 찾고자 하는 타입이 없는 것이므로, -1을 리턴한다.
2. 탐색하는 흐름이 원하는 타입을 typelist::Head 에서 찾았다면 0을 리턴한다.

이 탐색하는 흐름은 뒤에서 이야기 하고, 여기서 나열한 두개의 조건에 대해서만 생각해 보자.

찾지 못했을 때, 어떤 값을 리턴해야 하지?
나는 처음에 이 생각을 했었다. 검색하지 못했을 때, 아무값으로 해도 되지 않을까? 라고 자문해 보았을 때, 다음과 같은 이유 때문에 되지 않았다.
"범위를 모르기에 어떤 수치가 의미없는 값인지 typelist 마다 다르게 된다." 그러므로 음수의 값(0은 첫번째 인덱스이므로 쓸수 없다)으로 리턴해야 했고, 대표적인 -1 을 선택해야 했다.


찾았을 때, 왜 0을 리턴해야 하지?
typelist의 Head와 같다면 첫번째 인덱스가 0이기 때문이다. 여기서 문제가 되는 것은 typelist::Tail의 경우에서 typelist::Tail::Head 이 같다해도 0을 리턴하는 것인데, 찾을 때 부터 Tail에 들어갈 때부터 1씩 더해 주면 될꺼 같다.


그렇다면 찾는 도중에 찾지 못했을 때, 어떻게 -1을 만들어 줄 것인가?
이것이 꽤 큰 난관이였다. 하나씩 Tail 을 카운팅 하면서 타입을 찾다가 결국에 못 찾을 경우 어떻게 -1 로 만들어 줄 것인가 인데, 만약 -1일 경우 -1을 리턴하고, 아닐 경우, 1씩 더한 값을 리턴한다. 라고 하면 정말 끝내주기 손 쉬울텐데라고 생각만 했었다. 그러다가 책을 보니 컴파일 타임에 조건을 체크 할 수 있는 문법이 삼항 연산자(조건 ? 참일경우 : 거짓일 경우)라고 되어 있었다.

결국 어떻게 -1을 만들어 줄 것인가를 해결 할 수 있었다.

자. 시나리오는 끝났으니, 코드를 만들어 보자.

여기서 흐름만 이해 하면 되는데, 21번째 라인에서 value 값이 무엇인지 제일 처음 찾고, 그것이 -1이라면 계속 -1을 리턴하게 하고, -1이 아닐 경우, + 1 씩 더해 주는 것이다.

후~ 이것으로 3.7 탐색이 끝났다. 문제가 되는건 제일 처음 찾은 타입의 인덱스만 벹어 내는 것인데, 두번째 동일한 타입이 있을 경우, 그 위치는 찾지 못한다. 재귀 알고리즘이기에 끝까지 갔다가 되돌아 올 방법이 없기 때문에 어쩔수 없다.

posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요