파스칼의 RTL중의 generic list인 fgl에 대해 알아보자.
이 유닛에는 크게 2가지가 있다.
먼저 List계열의 클래스들을 알아보자.
TFPGList
TFPGList 이 클래스는 C++의 템플릿과 비슷한 클래스이다.
내부 자료구조는 ==벡터로== 구현이 되어있다. TFPGList는 모든 타입을 담을 수 있지만, 반면 TFPGObjectList 는 클래스 밖에 담을 수가 없다.
따라서 모든 자료형을 담는 TFPGList에 대해 간략하게 알아본다.
사용 방법은 아래 코드에 주석으로 명시한다.
program main;
uses fgl; {fgl을 가져온다.}
type
{intlist라는 타입을 새로 정의한다.(포인터형을 정의하는것과 같음)}
intlist=specialize tfpglist<longint>;
{intlist_enumerator 라는 열거자를 선언한다.}
intlist_enumerator=specialize tfpglistenumerator<longint>;
var
v:intlist;
it:intlist_enumerator;
i,n,r:longint;
{이 함수는 TFPGList의 비교 함수로 사용된다.}
function cmp(const a,b:longint):longint;
begin
if a<b then
cmp:=-1
else if a>b then
cmp:=1
else
cmp:=0
end;
begin
v:=intlist.create; {생성자로 초기화를 해준다.}
readln(n);
for i:=1 to n do
begin
readln(r);
v.add(r); {add 함수로 값을 추가한다.}
end;
v.Remove(1);
v.sort(@cmp); {정렬은 함수의 주소를 받아서 실행한다.}
for i:=0 to v.count-1 do {count는 개수를 반환한다.}
writeln(v.get(i)); {get으로 배열첨자값을 얻을 수 있다.}
it:=v.GetEnumerator; {새 열거자를 반환한다.}
while(it.MoveNext())do
writeln(it.current);
{이렇게 순회가 가능하다}
it.Free;
v.Free;
end.위 코드에서 처럼 열거자를 통해 순회도 가능하고. get 메소드로 첨자 순회 또한 가능하다.
기본적인 메소드들은 아래 링크에서 모두 확인이 가능하다.
http://www.freepascal.org/docs-html/current/rtl/fgl/tfpgobjectlist.html
TFPGMap
이건 Map이긴 한데 구현이 완전히 잘못된 Map이다.
트리도 아니고 해시도 아니다. 배열이다.
배열에 InsertSort 방식으로 삽입하여 정렬하고, 이진탐색으로 값을 가져오는 방식이다.
Add를 호출시 이진탐색으로 삽입지점을 검색한후, System.Move (C언어에서 memmove) 함수로 배열을 밀고 그곳에다 데이터를 삽입힌다.
당연히 Add의 시간복잡도는 O(n) 이며, 검색인 IndexOf나 Find는 O(lgn) 이다.
TFPGMap은 사용하기전에 정렬이 되게 삽입을 하느냐, 아니면 그냥 삽입을 하느냐를 결정할 수 있는데,
정렬을 하지 않으면 그냥 벡터마냥 동작한다. 당연히 검색시 복잡도는 O(n)
분명히 쓰레기 자료구조 라이브러리라고 말할 수 있지만, 사용법은 그래도 올려놓는다.
program main;
uses fgl; {fgl을 가져온다.}
type
{intmap라는 타입을 새로 정의한다.<key,value>}
intmap=specialize tfpgmap<longint,longint>;
var
v:intmap;
i,r:longint;
const
n=5;
begin
v:=intmap.create; {생성자로 초기화를 해준다.}
v.sorted:=True;
for i:=1 to n do
v.add(i*2-1,i*i*i); {add 함수로 홀수 키만 추가.}
{현재 map 상태 : [1,1][3,8][5,27][7,64][9,125]}
v.add(2,222);
{현재 map 상태 : [1,1][2,222][3,8][5,27][7,64][9,125]}
v.add(4,444);
{현재 map 상태 : [1,1][2,222][3,8][4,444][5,27][7,64][9,125]}
{삽입정렬 형태로 삽입함}
for i:=1 to n*2 do
begin
r:=v.Indexof(i); {키의 인덱스를 알아옴 없는 키면 -1 반환}
if r<>-1 then
writeln(v.Data[r]); {Data 프로퍼티로 value를 가져온다.}
end;
v.Free;
end.가장 중요한건 Sorted 프로퍼티를 True로 설정해야 이진탐색을 수행할 수 있다. 기본적으로 False값인데,
삽입을 느리게 하느냐, 검색을 느리게하느냐의 선택인데 무엇을 골라도 망한다.
Sorted를 True로 했을때 IndexofData도 있는데, 데이터로 키의 인덱스를 알아오는 함수이다. 당연히 복잡도는 O(n).
본 클래스의 소스코드는 아래에서 볼 수 있다.
소스크드는 어렵지않으며 훓어보면 자료구조의 구현이 쓰레기라는걸 알 수 있다.
https://github.com/graemeg/freepascal/blob/master/rtl/objpas/fgl.pp
