데이터를 자동으로 정렬해서 저장한다 - CSortedArray, CSortedArrayEx

invalid-file

특정 타입의 데이터를 저장하긴 해야겠는데, 이것을 자동으로 정렬해가면서 저장하고 싶을 때가 있습니다. 이럴 때 사용하는 자료구조입니다. 템플릿 형태로 되어 있기 때문에 타입만 지정해주면 됩니다.

이 템플릿 클래스의 원래 출처는 이곳입니다 : http://www.naughter.com/sortedarray.html

남의 소스를 왜 자기것처럼 업로드했냐고요? 그것은, 이 소스의 최신버전은 VS2005 이상만 지원을 하기 때문입니다. 이 포스트에 올라온 버전은, VS2003에서도 쓸 수 있도록 약간 수정을 가한 버전입니다. (디버그 관련 명령어 하나만 바꾼 거지만.-_-) 첨부파일을 참고하세요. 그 부분 이외에 다른 Copyright부분이라든지 코멘트 부분 등은 전혀 손을 대지 않았습니다.  

내부 구조는, MFC를 이용하는 프로젝트일 경우 CArray템플릿을 이용하며, 그렇지 않을 경우 CSimpleArrayEx를 이용하도록 되어 있습니다. (CSimpleArrayEx는 ATL의 CSimpleArray를 확장하여 삽입 기능을 추가한 버전인데, ATL 라이브러리쪽으로 작업을 하시는 분은 분은 위의 출처 링크로 가서 CSimpleArrayEx의 소스를 받아서 추가하시면 ATL버전을 쓸 수 있습니다.) 

CSortedArray는 자체적으로 Binary Tree를 사용하여 정렬과 검색을 빠르게 실시합니다. 입력과 동시에 정렬이 자동으로 되기 때문에, 따로 정렬 알고리즘을 구현하지 않아도 된다는 결정적인 장점이 있습니다. 다만, CArray를 상속한 것이기 때문에 직접 어레이에 값을 쓰는 메서드도 오픈이 되어 있어서, 수동으로 정렬을 하는 메서드도 따로 준비를 해두었네요.

사용 방법은 무척 간단합니다. 메모리 관리 클래스를 사용해보신 경험이 한번이라도 있다면, 사용상 전혀 무리가 없을 만한 수준입니다. 다만, 자료구조에 담기는 데이터가 항상 단순 수치인 것은 아니기 때문에, 서로의 값을 비교하는 룰(비교함수)을 제공해야 합니다.

이 라이브러리에는 버전이 두 개가 있습니다. CSortedArray와 CSortedArrayEx가 그것인데요, 기능적인 부분은 같고, 다만 CSortedArray는 일반적인 콜백 함수로 비교 함수를 지정하며, CSorrtedArrayEx는 콜백함수가 아닌 콜백클래스(Functor)를 이용하는 점이 다릅니다. 펑터에 대해서 궁금하신 분은 http://www.newty.de/fpt/functor.html 링크를 참조하시기 바라며, 간단히 설명드리면 컴파일타임에 메서드가 인라인 처리되어 빠른 속도를 낼 수 있는 처리방법이라고 생각하시면 됩니다. 콜백으로 펑션과 펑터를 사용한다는 차이점을 제외하면, 나머지 기능은 완전히 동일합니다. 다음은 콜백 구현의 예입니다. 왼쪽이 펑션, 오른쪽이 펑터입니다.

왼쪽 함수야 따로 설명드릴건 없을것 같고.. 오른쪽 펑터 버전은 함수 호출에 해당하는 오퍼레이터를 재정의해서 빠른 속도를 꾀하고 있군요. 실제 개발자가 테스트해본 바에 의하면 훨씬 속도가 빠르다 합니다. 펑터의 장점이지요. 사용법이 많이 어려운 것도 아니니 펑터 버전의 사용을 권장합니다. 다만, VS2008에서는 컴파일러 최적화 기능이 좋아져서 거의 차이가 없어진다고는 하는군요. 창피한 일이지만 함수 호출도 오퍼레이터로 처리되는줄은 미처 몰랐습니다^^;;

펑터 버전, 즉 CSortedArrayEx를 가지고 간단한 예제 프로그램을 만들어 보겠습니다. 맨 윗줄에 있는 CompareIntsClass는 물론 앞서 적어둔 비교용 콜백 펑터입니다. 당연하지만 소스에 그것을 먼저 적어주셔야 합니다.

CSortedArrayEx<int, int&, CompareIntsClass> idata;

 int d = 7;  idata.OrderedInsert(d);
 d = 3;  idata.OrderedInsert(d);
 d = 4;  idata.OrderedInsert(d);
 d = 5;  idata.OrderedInsert(d);
 d = 2;  idata.OrderedInsert(d);

템플릿의 파라미터는 각각 저장할 값의 타입, 참조 타입, 그리고 비교펑터로 선언하게 되어 있습니다. 그리고 OrderedInsert가 데이터를 정렬시켜가며 입력하는 메서드입니다. 아주 간단하지요? 이렇게 데이터를 무작위로 넣어도, 어레이에는 항상 0번째 인덱스부터 오름차순으로 데이터가 정렬되어 저장된다는 겁니다. 즉, 아래 루틴을 루프로 돌리면 작은 수부터 출력이 잘 이루어지지요. 2, 3, 4, 5, 7 이렇게 출력된다는 겁니다. RemoveAt(0)으로 값을 빼내도 그즉시 다시 자동정렬이 돼서 옆에 있던 값이 채워집니다.

 int intData = idata.GetAt(0);

 printf("%d\n", intData); idata.RemoveAt(0);

자, 그럼 이것을 어디에 이용하느냐? 저는 이것을 서버-클라이언트 이벤트 처리에 이용했었습니다. "특정 시각에 해야 할 일"을 처리하는 용도로 사용했지요. 시각을 수치화시켜서(GetTickCount등을 이용) 위 자료구조에 집어넣으면, 가장 빠른 시간에 해야 할 일을 항상 찾아낼 수가 있습니다. 현재 시간과 비교해서 맞는 시간에 해당하는 일부터 처리하고, 현재 시각에 맞는 일이 아직 없으면 기다리면 되니까 편리하게 이용할 수가 있는 거지요. 기타, 데이터 입력이 런타임으로 계속 일어나는 그런 상황에서의 정렬에 쓰시면 됩니다. 하지만, 데이터 입출력 시점이 명확하게 정해진 상황에서의 정렬이라면 일반적인 정렬 알고리즘을 쓰는 게 더 좋은 방법이 될 수도 있겠죠.

결론

용도 : 우선순위, 또는 자동정렬이 필요한 작업

장점 : 추가적인 정렬 함수 호출 없이도 항상 정렬된 결과를 보장해준다. Binary Tree를 이용하기에 따로 정렬을 하지 않으므로 퍼포먼스가 뛰어나다. Functor 콜백을 선택적으로 제공하여 상황에 따라 편리하게 사용할 수 있다.

단점 : 중복 값이 있을 경우에는 탐색 기능만으로는 원하는 오브젝트를 바로 찾아낼 수 없다. ATL도 MFC도 이용할 수 없는 환경에서는 쓸 수 없다. (..단점이라 하긴 좀^^)