int21h

Množiny v pascalu

Množiny jsou jeden z nejzvláštnějších rysů jazyka pascal, které, pokud vím, nemají obdobu v jiných, reálně používaných, jazycích. O množinách se sice píše v každé učebnici programování, ale nikde není vysvětleno, jak fungují uvnitř. Málokterý programátor je tudíž umí efektivně využívat.
Typické deklarace množiny v programu vypadají takto:

var a:set of byte;
    b:set of char;
    cisla:set of 0..9;

Prvky množin tedy mohou být pouze jednobajtové ordinální typy. Následující deklarace fungovat nebudou:

var r:set of real;
w:set of word;

Z uvedeného se může zdát, že množina a:set of byte je něco jako b:array[0..255] of byte
Není tomu tak!
Rozdíl vypluje na povrch při použití funkce SizeOf. Pokud použijeme výše deklarované proměnné - tedy:

writeln(SizeOf(a));  {napíše 32}
writeln(SizeOf(b));  {napíše 256}

To je velice zajímavé. Jak je možné, že množina, která obsáhne celý rozsah typu Byte, má pouze 32 bajtů? Odpověď je nasnadě: 32*8 = 256. Množiny jsou tedy uvnitř vlastně bitovými poli. Pokud napíšeme: a:=[20..30] (mimochodem, ne každý ví, že tento zápis je povolen), tak bude nastaven 20. až 30. bit na 1.
Názorně to vynikne na tomto zdrojáku:

var a:set of byte;
    b:array[0..31] of byte absolute a; {A a B budou sdílet stejný paměťový prostor}
    c:byte;
begin
a:=[];         {prázdná množina}
a:=a+[0];      {do množiny přidám 0. Jinak řečeno, nastavím 0.bit nultého bajtu}
a:=a+[1];      {do množiny přidám 1. tedy - nastavím 1.bit nultého bajtu}
a:=a+[8];      {do množiny přidám 8. tedy - nastavím 0.bit prvního bajtu}

writeln(b[0]);     {napíše 3}
writeln(b[1]);     {napíše 1}
readln;
end.

Takže, budete-li někdy psát program, který často přistupuje přímo k jednotlivým bitům, tak množiny mohou být dobrá volba.
Ještě zbývá upozornit na jeden zádrhel. Na množiny menší než 0..255 elementů. Deklarace množiny mohou totiž vypadat i takto:

type tyden = (po,ut,st,ct,pa,so,ne);
var cisla:set of 0..9;
    velka_an_pismena:set of 'A'..'Z';
    dny:set of tyden;

Jde o to, že dosud jsme předpokládali, že množina má vždy velikost 32 bajtů. Pořád sice platí, že může mít maximálně 32 bajtů, ale v těchto případech to bude méně. A překladače se navíc v tomto ohledu trošičku liší:
Turbo pascal a Freepascal 1.0.10 to mají tak, že všechny množiny, obsahující méně než 32 elementů, mají velikost 4 bajty a ty větší mají našich známých 32 bajtů.
Freepascal 2.x.x ale používá velikost množiny přesně podle počtu nutných bajtů nutných pro uložení rozsahu. Například množina cisla může uložit 10 elementů. 10 elementů = 10 bitů = 2 bajty. Množina velka_an_pismena umožňuje uložit 26 elementů = 26 bitů = 4 bajty.