Masterujeme pole v céčku

22.10.2010 14:00 | Přečteno: 1514× | Osobní | poslední úprava: 22.10.2010 13:58

I když tento server není zaměřen na programování, Linux je napsán v céčku a céčková pole je oblast, která lidi často mate. V tomto zápisku bych ji chtěl trochu objasnit.

Za většinu problémů může tvrzení, že pole je to stejné co ukazatel. Toto zjednodušení platí ve většině případů, nicméně kdokoliv se pokusí o složitější konstrukce a trochu se v nich vrtá, začne narážet na nesrovnalosti. Takže: pole není ukazatel a ukazatel není pole. Začneme od začátku. Ještě dodám, že jako typ dat předpokládám 32bitový integer.

Co je to ukazatel?

Ukazatel je proměnná, která obsahuje jedinou hodnotu, a to adresu v paměti. Situace vypadá takto:

jméno:   | ptr  |
hodnota: | 1424 |
adresa:  | 2124 |

jméno:   |      |      |      |      |      |
hodnota: |  5   |   6  |   7  |   8  |   9  |
adresa:  | 1424 | 1428 | 1432 | 1436 | 1440 |

Proměnná ptr má hodnotu 1424, což je adresa prvního prvku pole (získaného např. funkcí malloc()). Pokud napíšeme ptr[i], kde i == 2, vyhodnotí se výraz takto: vezmi hodnotu ukazatele ptr (tedy 1424), přičti k ní i-krát velikost datového typu, na který ptr ukazuje (takže 2*4) a vrať hodnotu na této adrese (1424 + 2*4 = 1432, hodnota 7).

Co je to pole?

Pole je (strukturovaná) proměnná, která obsahuje více hodnot stejného typu. Situace v paměti:

jméno:   | numbers                                  |
hodnota: |     3 |   4  |   5  |   6  |   7  |   8  |
adresa:  | 4000  | 4004 | 4008 | 4012 | 4016 | 4020 |

Všimněte si, že identifikátor numbers se vztahuje na celé pole. Jak se potom vyhodnotí numbers[i], kde i == 2? Naprosto stejně jako v předchozím případě. Vezme se hodnota numbers... a tady je zakopaný pes. Identifikátor numbers obsahuje pole několika čísel, které jako takové hodnotu nemá. Proto se použije adresa prvního prvku pole (tedy ta s indexem 0) a dál se postupuje stejně jako v předchozím případě: k adrese se přičte i*velikost prvku pole a hodnota, která se nachází na výsledné adrese (4000 + 2*4 = 4008, hodnota 5) se vrátí.

Porovnání

Pro pole a ukazatele tedy můžeme použít ono zjednodušení, protože ve většině případů se pole tváří jako ukazatel na první prvek. Říkám většině, protože se najdou dvě výjimky:

Operátor sizeof()

Zatímco sizeof(ptr) vrátí velikost ukazatele (na 32bitovém stroji 4), sizeof(numbers) vrátí součin počtu prvků a velikosti jednoho prvku (velikost pole v bytech, v našem případě 6*4 = 24).

Operátor &

Pro ukazatel je situace jednoduchá: výsledkem je adresa ukazatele na integer (datový typ **int). Pro pole je zajímavější: vznikne ukazatel na pole n čísel.

Pozor, ukazatel na pole N čísel (N musí jít vyhodnotit v době překladu) definujeme takto:

int (*ptrarr)[N]; //ukazatel na pole N integeru
int  *ptrarr[N];  // SPATNE! pole N ukazatelu na integer

Tady se zastavím, i když zápis nemusí být na první pohled jasný, protože se dostáváme k dvourozměrným polím, ke kterým je potřeba udělat odbočku stranou. Tedy prosím o kritiku, než se dostanu k něčemu zajímavějšímu.

Použitá literatura:
Ing. Miroslav Virius, Csc: Pasti a propasti jazyka C++, 2. aktualizované a rozšířené vydání, ISBN 80-251-0509-1

       

Komentáře

[black boy]

už som to skoro prečital ako "Masturbujete pole v céčku"

[pht]

Ono to ale tak nějak ve výsledku je.

[mess]

Zní to zajímavě, pokračuj

[realharo]

Je nejaký rozdiel medzi int x(char *c) {} a int x(char c[]) {}?

[____]

Prakticky snad ne.

[Dadam]

Tohle je to samé. Pro dvojrozměrné pole to už ale neplatí (dostanu se k tomu).

[ext3fs]

Me by treba zajimalo zda je naprosto akvivalentni z hlediska kompilatoru:

*(pole + i) = 1; a pole[i] = 1;

Nekde jsem cetl ze praci s poli pres [] si stejne kompilator prevadi na *(). Je tomu tak?

[David Watzke]

Zkusil jsem zkompilovat obě varianty pomocí GCC a binárky nejsou zcela identické.

[michich]

Binárky se blbě porovnávají. Zkompiluj si to do assembleru s gcc -S soubor.c. Tam by mělo být vidět, že je to stejné.

[David Watzke]

Není to stejné.

$ diff -u test1.s test2.s
--- test1.s     2010-10-23 20:01:04.090000164 +0200
+++ test2.s     2010-10-23 20:01:08.480000156 +0200
@@ -1,4 +1,4 @@
-       .file   "test1.c"
+       .file   "test2.c"
        .text
 .globl main
        .type   main, @function
@@ -10,9 +10,7 @@
        movq    %rsp, %rbp
        .cfi_offset 6, -16
        .cfi_def_cfa_register 6
-       leaq    -16(%rbp), %rax
-       addq    $4, %rax
-       movl    $1, (%rax)
+       movl    $1, -12(%rbp)
        movl    $0, %eax
        leave
        .cfi_def_cfa 7, 8

test1 používá *(pole+1)=1 a test2 používá pole[1]=1.

Ovšem jakmile povolím optimalizaci, alespoň -O1, tak to stejné je.

[Martin Mareš]

Ano. Operátor a[b] je definován jako *(a+b).

A jelikož *(a+b) je totéž jako *(b+a), pak také a[b] je totéž jako b[a].

[pht]

Není to hezké, když je implementace vzdálena účelu natolik že z ní lezou obskurní vedlejší efekty typu i[pole]=1.

[Martin Mareš]

Hu? Vzdálena účelu? V čem?

[pht]

No, účel pole[i] je ítý prvek pole, ne? Tak by měla znít definice. Že je to interně v implementaci převedeno na *(pole+i) by mělo být každému putna respektive do toho by nikomu nemělo být nic. A nezávisle na tom na co se to interně převede by němělo jít napsat i[pole] protože to je prostě sémantický nesmysl...

[Martin Mareš]

Ono je to jinak: Céčkové pole prostě je definováno jako ta pointerová konstrukce (data chovající se jako pole mohou vzniknout spoustou způsobů, které mají společné jen to, že se dají indexovat pomocí pointerové aritmetiky) a hranaté závorky jsou jen a pouze syntaktická zkratka. To je propastný rozdíl od pole definovaného pomocí hranatých závorek a pak nějak přes pointery (interně) implementovaného.

[pht]

hranaté závorky jsou jen a pouze syntaktická zkratka

S tím souhlasím, i když je to zkratka jen pro indexování, nikoliv definice což je matoucí věc č.1 (int[2][3] a int** není totéž; nelze napsat int 3[foo] místo int foo[3])

A matoucí věc č.2 je že syntaktická zkratka foo[3] nemusí a nemá mít za následek syntaktickou zkratku 3[foo].

[Martin Mareš]

Pokud je ta zkratka syntaktická, tak jí do typů hodnot nic není (na úrovni syntaxe neexistují).

[pht]

To je pravda, v tom případě jsem se vyjádřil špatně - ta implementace je vzdálena účelu v tom, že je to jen syntaktická záležitost, protože na hlubší úrovni jedno z toho smysl má a druhé je něco divného.

[Martin Mareš]

Co napáše větší škodu? Featura jazyka, kterou lze použít jak přirozeným, tak nepřirozeným způsobem, nebo taková, která je zbytečně komplikovaně definovaná, jenom proto, aby tím nepřirozeným způsobem použít nešla? Pan Occam by věděl

[pht]

Pan Occam by věděl

Cimrman taky... "spočítali jste padlé".

V podstatě by se dalo říct, že škoda na uživatelích toho jazyka je neomezeně velká, protože tuhle pitomost se musí každý učit. Na druhou stranu je jen malé množství překladačů, kde by bylo třeba řešit aby to nebyla pitomost.

[Martin Mareš]

To je s prominutím naprostá pitomost. Naprostá většina uživatelů Céčka o tom nikdy nepřemýšlela a hranaté závorky nepoužila jiným než intuitivním způsobem. Kde jste vzal nějakou škodu?

[Dadam]

Já jsem tuhle "fíčuru" radši ani nezmiňoval. Jediné, co jsem o ní kdy četl, je, že je to syntaxe podobná některým assemblerům. Neznáte někdo nějaký takový?

[pht]

Naprostá většina uživatelů Céčka o tom nikdy nepřemýšlela a hranaté závorky nepoužila jiným než intuitivním způsobem.

Což je docela dobrý důvod proč by tam ta další "feature" *neměla* být.

Kde jste vzal nějakou škodu?

Já nikde... to byl Váš dotaz. Abychom nemluvili o dvou různých věcech - pro mne je zrovna *tahle* feature dost nezajímavá, respektive chápu důvody jejího vzniku. Spíš mě to štve jako instance neustále opakujícího se principu který jsem naznačil v 1. příspěvku.

[Martin Mareš]

Což je docela dobrý důvod proč by tam ta další "feature" *neměla* být.

Ona to ale není další featura, nýbrž prostý důsledek definice.

[pht]

No budiž, tak to řekneme jinak: "... proč by definice měla být taková aby neměla takovéto důsledky [které nikdo nepotřebuje]". Pointa je furt stejná.

[Martin Mareš]

Protože pak ta definice bude zbytečně složitá?

[pht]

A takhle jsou zbytečně složité její důsledky - tak si vyberte.

[Martin Mareš]

Ty důsledky jsou triviální, pouze pohled, který jste si na ně zvolil Vy, je zbytečně složitý.

(Mimochodem, definice libovolného turingovsky úplného programovacího jazyka má nepředstavitelně složité důsledky, počínaje třeba prostou existencí nevyčíslitelných problémů. Proti tomu jsou nějaké syntaktické a sémantické detaily naprosto irelevantní.)

[pht]

Ty důsledky jsou triviální, pouze pohled, který jste si na ně zvolil Vy, je zbytečně složitý.

Já si nemyslím, že by to bylo o složitosti, ale souhlasím, že máme dva různé úhly pohledu.

Mimochodem, definice libovolného turingovsky úplného programovacího jazyka má nepředstavitelně složité důsledky, počínaje třeba prostou existencí nevyčíslitelných problémů. Proti tomu jsou nějaké syntaktické a sémantické detaily naprosto irelevantní.

Nemyslím si, že by míra složitosti měla být záminkou pro "držet hubu a krok"