상세 컨텐츠

본문 제목

[C++ 11] 문자가 특정 문자 집합에 속하는지 우아하게 테스트하기

프로그래밍/테크닉

by 적분 ∫2tdt=t²+c 2020. 3. 30. 02:02

본문

고전적 방법으로 문자 집합 소속 여부 테스트하기

문자열 처리를 하다보면 빠질수 없는 작업이 어떤 문자가 특정 문자 집합에 속하는지 확인하는 것일 겁니다. 예를 들어 'b'가 A~F 범위에 속하는지, '간'이 가~깋 범위에 속하는지 비교하는 것처럼요. 일반적으로 이 작업은 if문을 몇번 써서 수행할 수 있습니다. 예를 들어 특정 문자가 A-F 범위에 속하는지를 확인하는 함수는 다음과 같이 작성할 수 있지요.


아주 간단한 작업입니다. 그런데 테스트해야하는 문자 집합이 복잡해지다보면 위 함수도 차츰 복잡해지게 되겠죠? 예를 들어 특정 문자가 A~F, a~f, 0~4, !, ? 중에 속하는지 확인해야 한다면 함수 내의 if문이 늘어나게 될 겁니다.


비교문이 참 많습니다. 위 함수를 굉장히 많이 호출해야 한다면 어떨까요? 최선의 경우는 A~F 사이의 문자가 입력되어서 비교 2번만에 return true;로 탈출하는 것입니다. 만약 입력 문자가 '?'이거나 해당 집합에 속하지 않는 전혀 엉뚱한 문자라면 is_in_something 함수 내에서는 비교 연산이 총 8번 수행될 겁니다. 더 빠르게 할 수는 없을까요?

당연히 있습니다. 문자에 대한 룩업테이블(Lookup table, LUT)을 만들어서 특정 집합에 소속된 문자에는 1, 그렇지 않은 문자에는 0을 부여해주면 됩니다. 이러면 배열을 한 번 참조함으로써 비교 연산을 바로 끝낼 수 있지요.

룩업테이블을 관리하는 클래스를 만들었습니다. 생성시에 A~F, a~f, 0~4, !, ?에 해당하는 위치는 true로 설정하고 나머지는 모두 false로 설정합니다. 그리고 실제 문자 테스트시에는 배열을 참조하기만 하는 것이죠. 이러면 위의 함수보다 훨씬 빠르게 (대신 256바이트를 더 쓰게 됩니다.) 문자 비교가 가능하지요. 문자 비교를 굉장히 많이 실시해야하는 경우 유용하게 쓰일 수 있습니다.

그런데 이 방법은 귀찮습니다. 문자 집합별로 IsInSomething과 같은 클래스를 만들어줘야 하지요. 지금은 A~F, a~f, 0~4, !, ? 하나였지만, 이런 비교 세트가 수십개가 있다면 각각 저런 클래스를 만들어둬야합니다. 매우 단순한 작업인데 귀찮습니다. 이걸 자동화할 수 없을까요?

가변인자 템플릿을 이용해 문자 집합 소속 여부 테스트하기

C++11에서 도입된 가변인자 템플릿을 사용하면 이를 자동화할 수 있습니다! 기본적인 아이디어는 다음과 같습니다. 

  1. 문자 1개를 비교하는 템플릿 클래스, 문자 범위를 비교하는 템플릿 클래스를 정의한다

  2. 1에서 정의한 템플릿 클래스를 여러 개로 OR로 이을 수 있는 가변 인자 템플릿 클래스를 정의한다

  3. 1,2에서 정의한 템플릿 클래스로부터 LUT를 생성하여 비교에 사용할 수 있게하는 템플릿 클래스를 정의한다.

  4. PROFIT!!

간단하죠? 코드를 보면서 같이 나아가봅시다.

먼저 문자 1개를 비교하는 템플릿 클래스와 문자 범위를 비교하는 템플릿 클래스를 정의해봅시다.

어머, 너무 간단해서 부연설명이 필요없을 정도입니다. 근데 각각의 템플릿 클래스는 말그대로 문자 1개, 혹은 문자 범위 하나만을 비교할 수 있으므로 좀더 복잡한 케이스를 비교하기엔 역부족입니다. 이를 위해서 OR 연산으로 이 클래스들을 이어줄 수 있는 가변인자 템플릿 클래스를 만들어봅시다.


가변인자 템플릿의 핵심은 1)재귀 처리를 어떻게 정의하는지, 2) 종료 조건을 어떻게 설정하는지입니다. 위 경우는 N개의 인자를 받는 경우에 그 중 첫번째 인자에 대해서만 직접 비교를 수행하였고, 나머지 비교 연산은 나머지 N-1개의 인자를 가지는 템플릿 클래스에게로 넘겼습니다. 그러면 N-1개의 인자를 가지는 템플릿에서는 또 1개를 꺼내 비교를 수행하고, N-2개의 인자를 가지는 템플릿에게로 작업을 토스하겠죠? 이를 계속 반복하여 최종적으로는 0개의 인자를 가지는 템플릿으로 넘어오고 여기서 재귀가 종료됩니다. 

지금까지 만든 CharOr클래스는 그냥 비교 연산을 여러번 수행하여 문자가 특정 집합에 속하는지를 확인하는 함수를 자동으로 만들어주는 역할에 불과합니다. 앞서 이야기했듯이 이는 확인할 집합이 복잡해질수록 비교연산이 늘어나므로 복잡한 경우에는 LUT를 사용해 최적화하는게 필요합니다. 이것도 템플릿으로 자동화해봅시다.


CharTrait을 도입하여 OneChar, CharRange, CharOr가 섞여 있는 경우 그 문자 범위의 시작 지점과 끝지점을 알 수 있도록 했습니다. 이제 이걸 이용해서 LUT를 만들어 내는 클래스를 짜봅시다.


길고 긴 구현이 끝났습니다. 이제 CharSet<CharOr<CharRange<'A', 'F'>, CharRange<'a', 'f'>>> is_a_f; 와 같은 모양으로 A~F, a~f 범위에 속하는 문자를 테스트하는 LUT를 생성하고 비교하는 작업을 수행할 수 있습니다. 이는 템플릿으로 정의되므로 코드를 컴파일하는 과정에서 A~F, a~f에 대한 LUT 생성 코드가 풀어써지므로 런타임의 오버헤드를 줄일수 있다는 장점이 있습니다. 근데.. 와... 너무 지저분하다~

C++의 템플릿 문법은 강력하지만 가독성이 너무나도 나쁩니다. 저렇게 쓰라고 하면 아무도 안 쓰겠지요? 정규표현식을 쓰듯이 [A-Fa-f]처럼 간단하고 우아하게 쓸 수는 없을까요?

정규표현식과 유사하게 쓸 수 있도록 유틸리티 템플릿을 만들기

위의 지저분한 문법대신 "A-Fa-f"처럼 깔끔하게 써서 A~F, a~f 범위의 문자를 테스트할 수 있도록 개선하는 것도 템플릿으로 가능합니다. 아이디어는 템플릿 인자로 "A-Fa-f"를 받으면 이를 해석하여 CharSet<CharOr<CharRange<'A', 'F'>, CharRange<'a', 'f'>>> 타입으로 치환해주는 템플릿 클래스를 만들면 됩니다. 단, 현재 C++11에서 템플릿 인자로 문자열을 바로 받는게 안되므로, 가변인자 템플릿을 이용해 문자를 하나씩 하나씩 받도록 해야합니다.

이 역할을 수행하는 유틸리티 템플릿 클래스를 CharSetParser라고 해봅시다. 그러면 CharSetParser<'A', '-', 'F', 'a', '-', 'f'>와 같은 식으로 템플릿 인자로 입력이 들어가는 것이구요, 이 때 CharSetParser<'A', '-', 'F', 'a', '-', 'f'>::type이 CharSet<CharOr<CharRange<'A', 'F'>, CharRange<'a', 'f'>>>가 되도록 하는 것입니다. 구현하기 복잡해보이지만, 생각보다 복잡하지는 않아요!


쪼오오금 복잡하긴 하지만, 일단 X-Y처럼 중간에 -가 들어간 경우는 CharRange로, 그렇지 않은 경우는 OneChar로 해석하여 CharOr로 모두 이어주는 파서를 만들었습니다. 그리고 C++11에서 지원하지 않는 문자열 템플릿 인자를 우회하기 위해 다음과 같이 매크로를 사용하도록 합시다.


드디어 지저분한 식을 간단하게 쓸수 있게 되었습니다. CharOr<CharRange<'A', 'F'>, CharRange<'a', 'f'>> is_a_f; 대신 CharSetParserImpl<PP_GET_64("A-Fa-f", 0)>::type is_a_f; 라고 쓸 수 있어요~~!

마지막으로 기왕하는김에 정규표현식의 문자 집합마냥 negation 기능도 넣어봅시다. 정규표현식에서는 [A-Fa-f]는 A~F, a~f에 속하는 문자를 매칭하지만, ^가 앞에 붙은 [^A-Fa-f]의 경우 반대로 A~F, a~f에 속하지 않는 문자를 매칭하지요. 우리의 CharSet도 저걸 하도록 해봅시다.

드디어 길고 긴 구현이 끝났습니다. 이제는 CharSetParser<PP_GET_64("A-Fa-f0-4!?", 0)>::type is_in_something;처럼 써서 제일 위에서 구현한 is_in_something 함수의 LUT버전을 손쉽게 만들 수 있습니다. negation이 필요한 경우는 CharSetParser<PP_GET_64("^A-Fa-f0-4!?", 0)>::type is_not_in_something; 처럼 쓰면 되겠죠.

한계

이 구현방법은 컴파일 타임에 입력된 패턴 문자열에 따라 타입을 생성하는 방식이므로, "A-Fa-f0-4!?"와 같은 문자열이 실시간으로 입력되어서 그걸 분석해서 판단해야하는 경우는 쓸수 없습니다. 또한 아직 C++11에서는 문자열을 템플릿 인자로 받아들이는 기능이 없어서 PP_GET_과 같이 여전히 지저분한 매크로를 써야한다는 문제도 있습니다. C++17이후로는 이 제한이 풀리므로, 해당 버전을 사용한다면 훨씬 이쁜 코드도 가능합니다. 

구현을 하다보니 좀만 더 노력하면 아예 정규표현식을 템플릿으로 구현할 수 있을거 같아 보이죠? 사실 C++의 템플릿 문법이 그 자체로 튜링 완전하기 때문에 어떤 작업도 템플릿을 통해서 구현할 수 있습니다. (다만 그 작업이 너무 고통스러울 뿐이지...) 실제로 C++17 및 그 이후 문법을 통해 정규표현식을 컴파일 타임에 분석하는 라이브러리도 있습니다. (https://github.com/hanickadot/compile-time-regular-expressions) 그러나 아직 C++11도 제대로 사용할 수 없는 레거시 환경들이 많기 때문에 손가락만 빨면서 구경할 뿐입니다.

다행히도 오늘 소개한 코드는 gcc 4.8에서부터는 컴파일 가능하므로 조금 지저분하고 기능은 미약하지만  범용성은 있다고 할 수 있겠습니다. 

태그

관련글 더보기

댓글 영역