boost::icl::interval_map 원하는대로 변경해서 사용해보기

by Lyn posted Sep 23, 2013
?

단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

이 코드는 Visual Studio 2012 Update3에서 테스트 되었습니다.


boost 1.46 부터 추가된 icl 컨테이너들은 범위를 가지는 데이터들을 넣을 수 있게 되어 있는 컨테이너다


이것들은 주로 일정 등의 데이터를 관리하기에 아주 좋게 되어 있고(boost 예제도 대부분 그런쪽입니다) 매우 확장성이 좋게 설계 되어 있어 다양한 용도로 활용 가능하지만 개인적으론 map의 기본형인 boost::icl::intervap_map<T1, T2> 의 형태가 매우 비상식적이라고 생각한다.


그래서 interval_map 을 원하는 형태로 만들어서 쓰고 싶었고 그 과정에서 알게된 것을 정리 해 본다.

내가 최종적으로 원하는 형태는 프로그램이 처음 시작할때 로딩되는 범위를 가지는 데이터를 관리 하고, 중복되는 경우가 있을경우 데이터 오류로 취급하여 예외를 발생 하는 형태입니다.


하나씩 알아보자면 interval_map 의 기본 개념은 기존의 std::map 과 같지만, 몇가지 추가적인 개념이 존재한다.

1. 구간.

구간이란 0~1, 2~3, 12:00~13:00 처럼 범위를 가지는 데이터. 수학시간에 배웠던것처럼 개구간, 폐구간, 반폐구간(좌/우) 가 존재합니다.
뭐 이건 문제될 것 없는 당연한 경우라고 보입니다.


2. Combine

입력한 구간이 서로 겹칠 경우 그 구간에 대해 Combine 동작을 시행합니다.
이것에 대해선 아래에서 마저 합니다.


3. 기본값

웃기게도 왠지 모르겠지만 (...) 기본값에 대한 처리를 변경할 수 있습니다.

여기에서 기본값이란 static T; 로 선언 했을때의 초기값입니다. int라면 0, float 라면 0.0f, std::string 이라면 길이0인 문자열인 식입니다.


1번 구간에 대해서는 별로 문제가 될 경우가 없을겁니다. 상식적으로 사용 할 수 있지요.
계속 울궈먹을 기본 코드 하나 넣겠습니다


#include <boost/icl/interval_map.hpp>
#include <string>
#include <utility>
#include <cstdio>

void wmain()
{
	using namespace std;
	using namespace boost;
	using namespace boost::icl;

	interval_map<int, wstring> ivm;

	ivm.add(make_pair(interval<int>::right_open(0, 2000), L"Right"));
	ivm.add(make_pair(interval<int>::left_open(2000, 3000), L"Left"));
	ivm.add(make_pair(interval<int>::closed(3000, 4000), L"closed"));
	ivm.add(make_pair(interval<int>::open(4000, 5000), L"Open"));

	auto it = ivm.find(1000);
	if(it != ivm.end())
	{
		wprintf(L"Find %s\n", it->second.c_str());
	}
	else
	{
		wprintf(L"Not Found");
	}
}


기본적인 사용 방법은 위와 같습니다. 구간을 지정해서 데이터를 넣고 find로 찾아오는형식으로 map과 완전히 동일합니다.

결과도 별다를게 없구요


1.png


위 코드를 자세히 보시면 3000 이라는 값은 left, closed 두개의 데이터가 겹치는 구간이라는 것을 알 수 있습니다.
이때 3000을 찾아서 출력해 보면 어떤 결과가 일어 나냐면....


2.png


이런 상황이 벌어집니다 (...) 
왜냐면 interval_map은 구간이 겹칠 경우 Combine 작업을 진행 하는데 이 단순히 interval_map<T1,T2> 로 선언한 Combine의  동작이 + 연산입니다.

즉 겹치는 구간의 데이터를 몽땅 더해서 출력해 버립니다. 숫자라면 값이 더해질것이고 문자열이라면 위처럼 문자열일 경우 두 문자열이 붙어서 나타납니다.

이 Combine 연산을 미리 몇가지 제공 하고 있는데, 이렇게 더한다던지, stl 컨테이너에 insert 를 한다던지 최대값/최소값으로 교체한던지 하는 기본적으로 많이 쓸만한 연산을 제공 하고 있습니다....만 내가 필요한 문제있을시 예외던지는 Combine은 제공 하지 않습니다.


두번째로 기본값 문제입니다. 위 코드를 수정해서 아래처럼 바꾼 후 실행해보겠습니다.


3.png



[0~2000) 구간에 빈 문자열을 넣었지만 찾을수 없다고 하고 있습니다.

왜냐면 그 Type의 기본값이 들어갈 경우 데이터를 넣지 않는것이 interval_map 기본형의 동작입니다


하지만 이 상황에서 내가 원한건 데이터 없음과, 빈 문자열을 데이터로 가지는것을 확실하게 구별 해야 하는겁니다.

값이 빈값인건 빈값이고,  없는건 없다고 할수 있어야되는 상황이더 많다고 생각되는데.... 왜 이런지는 모르겠습니다.


이 동작을 바꾸는 기능을 icl 은 제공 하고 있는데 두가지 옵션을 하나의 구조체로 만들어 총 4종류의 형태를 제공합니다.
partial_absorber, partial_enricher, total_absorber, total_enricher 의 4가지입니다.

여기서 뒤에 붙은 absorber, enricher 이 기본값을 어떻게 처리할지 결정합니다.
absorber는 날려버리고(초기형태) enricher 는 보존합니다. partial_enricher 로 바꾼 뒤 다시 한번 실행해 보겠습니다.


4.png


보다시피 찾아오는것에 성공하는 것을 볼 수 있습니다.

다음으로 앞에 붙은 partial, total 은.... 당췌 이게 어떻게 돌아가는지 모르겠습니다 =_=;;;;; 뭘로 하던 내가 원하는 동작에 지장이 없었기에 넘어갔습니다.
차후 추가적인 확인이 필요할듯 합니다. 아마 사용자 정의 type 에서만 영향을 미치는지도 모르겠습니다. 기본형은 이미 다 되어있고 ...


그리고 이제 combine 을 방지해야 하는데... combine functor 를 새로 만듬으로서 가능했습니다. 
겸사겸사 실수로 substract 를 호출하는것을 방지하기 위해 inverse functor 도 만들었습니다. 어차피 오류낼거니 궂이 따로 만들 필요는 없어서 그냥 같이 쓰도록 되었네요.


5.png


그 결과가 이 코드입니다. 중간에 less는 std::less 입니다. 비교 functor 가 템플릿에서 앞에 있는 바람에 저렇게 들어가버렷네요.

어쨋든 멋지게 assert 를 내 주네요. 원하는 동작이 만들어 졋습니다. 구간별 데이터를 안전하게 저장 할때 사용할수 있겠습니다.
궂이 사용 예를 추가해 보자면 ip 별 지역 정보를 넣어놓고 빠르게 검색할때 사용할 수 있겠네요.

TAG •