Lazarus中用TFPSList和TFPGList排序

刘华煜

摘要：排序是一个常见的操作。在Lazarus中，经常选择使用TFPSList和TFPGList来进行排序。

关键词：Lazarus;排序;TFPSList;TFPGList

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2020）28-0083-03

Abstract： Sorting is a common operation. In Lazarus， TFPSList and TFPGList are often used for sorting.

Key words： Lazarus;sort; TFPSList; TFPGList

1 背景

在编程中经常会用到排序，由于排序涉及语言层面本身，所以每种语言实现排序的方法各不相同。在Lazarus中，通常用TFPSList和TFPGList实现排序功能。

2 TFPSList和TFPGList

TFPSList实现的是线性表，线性表每个元素都只能以Pointer形式访问，这样就需要在使用元素的时候先强制类型转换。假设要在一个TFPSList中存储整数，那么就得这样写代码：

var

list： TFPSList;

k： Integer;

begin

list：=TFPSList.Create（sizeof（Integer））;

k：=3;

list.Add（@k）;

k：=-7;

list.Add（@k）;

writeln（PInteger（list[0]）^）;

writeln（PInteger（list[1]）^）;

end;

在创建TFPSList时要指定元素所占字节数，这样的话才可以根据传入的指针把元素复制到TFPSList中。加入元素的方法是调用TFPSList的Add方法，取出元素则通过下标取出，由于通过下标得到的是Pointer，所以需要强制转换成指向整数的指针PInteger再进行操作。

TFPGList实现的也是线性表，它的元素是通过模板指定的。下面的代码展示了如何在一个TFPGList中存储整数：

type

LI = specialize TFPGList;

var

list： LI;

k： Integer;

begin

list：=LI.Create;

k：=3;

list.Add（k）;

k：=-7;

list.Add（k）;

writeln（list[0]）;

writeln（list[1]）;

end;

首先要创建一个数据类型，以模板形式指定TFPGList元素类型，然后通过Add方法加入元素，通过下标取出元素。

3 用TFPSList排序

为叙述方便，假设每个数据项都由两个整数组成：key和index，依据key来排序。

首先需要定义表达数据项的记录以及指向它的指针：

type

KI = record

key， index： Integer;

end;

PKI = ^KI;

然后定义比较函数，排序需要比较函数来确定两个记录哪个比较大，需要注意的是TFPSList要求比较函数是成员函数，那么就需要单独定义一个类：

coo = class

function CompFunc（k1， k2： Pointer）： Integer;

end;

function coo.CompFunc（k1， k2： Pointer）： Integer;

begin

Result ：= PKI（k1）^.key - PKI（k2）^.key;

end;

比较函数的参数是两个指针，所以需要强制转换成PKI再比较二者的key，函数返回值大于0，表示第一个数据大于第二个数据，返回值等于0，表示两个数据相等，返回值小于0，表示第一个数据小于第二个数据。

然后进行排序：

procedure foo;

var

list： TFPSList;

k： KI;

c： coo;

begin

list：=TFPSList.Create（sizeof（KI））;

k.key ：= …

k.index ：= …

list.Add（@k）;

…

list.Sort（@c.CompFunc）;

Writeln（PKI（list[0]）^.index）;

end;

list.Sort（@c.CompFunc）執行排序，由于用不到c的成员变量，所以用不着创建c对象直接调用其成员函数CompFunc。排序后PKI（list[0]）^.index就是最小的数据项的index成员值。

单独给比较函数创建一个类显得不够优雅，如果排序本身就在一个类的成员函数里，那么可以把比较函数放入这个类中：

function TForm1.CompFunc（k1， k2： Pointer）： Integer;

begin

Result ：= PKI（k1）^.key - PKI（k2）^.key;

end;

如果在Form1窗体里排序，那么就用不着为了排序函数单独创建一个类，把比较函数作为TForm1的成员函数即可。

相应的排序修改成：

procedure TForm1.foo;

var

list： TFPSList;

k： KI;

begin

list：=TFPSList.Create（sizeof（KI））;

k.key ：= …

k.index ：= …

list.Add（@k）;

…

list.Sort（@CompFunc）;

Writeln（PKI（list[0]）^.index）;

end;

注意排序函數foo从顶层函数变成TForm1的成员函数，list.Sort的参数也变成了@CompFunc。

4 用TFPGList排序

TFPGList也需要比较函数，但和TFPSList不同的是，TFPGList的比较函数是顶层函数：

function CompFunc（const k1， k2： KI）： Integer;

begin

Result ：= k1.key - k2.key;

end;

TFPSList的比较函数的参数类型是指针，需要强制转换，而TFPGList的比较函数的参数类型是数据项本身，无须强制转换。

在TFPGList的元素是记录的情况下，需要重载记录的相等操作符：

type

KI = record

key， index： Integer;

class operator Equal（k1， k2： KI）： Boolean;

end;

class operator KI.Equal （k1， k2： KI）： Boolean;

begin

Result ：= k1=k2;

end;

然后进行排序：

procedure foo;

type

LKI = specialize TFPGList;

var

list： LKI;

k： KI;

begin

list ：= LKI.Create;

k.key ：= …

k.index ：= …

list.Add（k）;

…

list.Sort（@CompFunc）;

Writeln（list[i].index）;

end;

需要注意的是，class operator Equal函数需要预编译指令{$mode delphi}，TFPGList需要预编译指令{$mode objfpc}，而这两个预编译指令是互斥的，这就是说KI的定义和LKI的定义必须分别在两个文件中，这就造成了麻烦。

如果TFPGList的元素不是记录，而是对象，那么就无须重载相等操作符，也就不需要预编译指令{$mode delphi}，那么KI的定义和LKI的定义也就可以在一个文件中了：

type

KI = class

key， index： Integer;

end;

LKI = specialize TFPGList;

比较函数不变，排序则变成下面这样：

procedure foo;

var

list： LKI;

k： KI;

begin

list ：= LKI.Create;

k ：= KI.Create;

k.key ：= …

k.index ：= …

list.Add（k）;

…

list.Sort（@CompFunc）;

Writeln（list[i].index）;

list[0].Free;

…

end;

既然KI的定义从记录变成类，那么也就需要创建对象和销毁对象。

同样，如果TFPGList的元素不是记录，而是指向记录的指针，那么也无须重载相等操作符，KI的定义和LKI的定义也可以在一个文件中：

type

KI = record

key， index： Integer;

end;

PKI = ^KI;

LKI = specialize TFPGList;

比较函数需要改一下：

function CompFunc（const k1， k2： PKI）： Integer;

begin

Result ：= k1^.key - k2^.key;

end;

排序也要改：

procedure foo;

var

list： LKI;

i，n： Integer;

begin

list ：= LKI.Create;

list.Add（…）;

…

list.Sort（@CompFunc）;

Writeln（list[0]^.index）;

end;

5 結束语

TFPSList和TFPGList都可以实现排序功能，从直观性上来说，TFPGList直接用数据项作为元素最为直观，但可惜的是如果元素是记录类型，则需要单独一个文件放记录定义，在多一个文件也无所谓的情况下，这是最好的选择，另外如果数据项只有一项数据，根本无须记录类型，那么TFPGList直接用数据项也是最好的选择。TFPSList的最大缺点是它的元素被泛化成通用指针Pointer，必须进行强制转换才能访问其元素，这样就带来很多麻烦。TFPGList的元素是指向记录的指针这种方法的一个缺点是必须解引用，但这还不是最大的缺点，最大的缺点是记录本身不保存于TFPGList中，还需要让记录本身不要因为超出作用域而失效，在记录本身无须维护的情况下，是一个好的选择。TFPGList的元素是对象这种方法比较均衡，在直观性上和TFPGList直接用数据项作为元素一样直观，并且因为对象保存在堆里，即使对象引用超出作用域，对象内容也不会失效，只是可能需要排序前创建对象，排序后释放对象，不过这并不麻烦，另外在对象的创建和释放都无须排序本身处理的情况下，这种方法和TFPGList直接用数据项作为元素并无区别。

参考文献：

[1] Booth J.Lazarus & Object Pascal Notebook[M].北京：机械工业出版社，2014.

[2] 徐新华.IDE和Object Pascal语言[M].北京：人民邮电出版社，1998.

[3] Knuth D E.计算机程序设计艺术（卷3）：排序与查找[M].北京：机械工业出版社，2010.

【通联编辑：谢媛媛】