Lineární spojový seznam v C

15.1.2014 21:15 | Přečteno: 8499× | Ostatní | poslední úprava: 15.1.2014 21:13

Ukázka lineárního spojového seznamu v C. Kdyby se vám něco nezdálo, klidně napište do diskuze. Ve mně trochu budí pochyby funkce a na přidání seznamu, ale funguje.


#include <stdio.h>
#include <stdlib.h>

typedef struct rec {
   int x;
   struct rec *n;
} list;

void c(list **l);
void p(list *l);
void f(list *l);
void d(list **l, int i);
void a(list **l);

/*vytvori seznam*/

void c(list **l)
{
   list *p, *q;
   int i;

   printf("Zadejte cisla a ukoncete znakem:\n");

   if ((scanf("%d", &i)) == 0)
      exit(1);

   if ((*l = (list *) malloc(sizeof(list))) == NULL)
      exit(1);

   (*l)->x = i;
   (*l)->n = NULL;
   p = *l;

   while ((scanf("%d", &i)) != 0) {
      if ((q = (list *) malloc(sizeof(list))) == NULL)
         exit(1);

      q->x = i;
      p->n = q;
      p = q;
   }

   p->n = NULL;

   while(getchar() != '\n')
      ;
}

/*pripoji k seznamu dalsi seznam*/

void a(list **l)
{
   list *l2, *p, *q;
   c(&l2);
   q = *l;

   if (*l) {
      while (q) {      /* while (q != 0) */
         p = q;
         q = q->n;
      }
      p->n = l2;
   }
   else {
      *l = l2;
   }
}

/*odebere cislo*/

void d(list **l, int i) {

   list *p, *q;

   for (q = p = *l; p != NULL;) {
      if (p->x == i) {
         if (p == q) {
            q = p->n;
            (*l) = q;
         }
         else {
            q->n = p->n;
         }

         free(p);
         p = q;
      }
      else {
         q = p;
         p = p->n;
      }
   }
   if (!*l)      /* if (*l == 0) */
      printf("seznam je prazdny\n");
}

/*vytiskne seznam*/

void p(list *l)
{
   while (l != NULL) {
      printf("%d, ", l->x);
      l = l->n;
   }
}

/*uvolni pamet*/

void f(list *l)
{
   list *p;

   while (l != NULL) {
      p = l->n;
      free(l);
      l = p;
   }
}

int main()
{
   int i, z;
   list *l;

   c(&l);
   printf("\n");
   printf("p = pridat\no = odebrat\nz = zobrazit\nu = ukoncit\n");

   do {
      printf("\n");
      z = getchar();

      switch(z) {
         case 'o':
            printf("Cislo:\n");
            scanf("%d", &i);
            d(&l, i);
            while(getchar() != '\n')
               ;
            break;

         case 'z':
            p(l);
            break;

         case 'p':
            a(&l);
            break;

         default:
            break;
      }
   } while (z != 'u');

   f(l);

   return 0;
}        

Komentáře

[w4rr10r]

Jsem to jenom já, nebo jsou ty identifikátory opravdu poněkud... ne moc vypovídající?

[vlastikroot]

Jo, fakt hruza Ja mam vycitky kdyz pouziju promenou s nazvem x nebo i ve foru

[kralyk z abclinuxu]

+1, ještě vymazat whitespace a bylo by to jak minified jquery

[repli]

Skoro kód, který by se měl ukazovat pro zastrašování studentů, že tohle je stihne, když budou přílíš líní vymýšlet pro proměnné názvy.

[pavlix]

Já bych ty názvy proměnných viděl v tomto případě jako ten nejmenší problém, i když je člověk vidí jako první.

[xxx]

Nevim, mne to zrovna u spojaku prijde dost jednoznacne. Ale asi je to tim, ze clovek vi, co tam cekat. Tedy z n bude next, atp.

[Václav "Darm" Novák]

No, pak se na to mrkne po dvou letech, nebo to ukáže někomu jinému… Jestli takhle vypadá celý program, tak au.

[jekub]

mne pripadaji docela vypovidajici

[hjkgkjhg]

tyvole, to je hruza kod... ten printf tam v c()... ty nazvy...

[Antonym]

odhlednu-li od tech desnych identifikatoru - neni to noseni drivi do lesa? Zajimalo by me, kolik je tu lidi, co nikdy ve skole tohle napsat nemuseli...

[sad]

Třeba já, který se učí programovat a snaží se pochopit lineární seznamy, a díky tomuto programu je už docela chápe. Zveřejnil jsem to sem, kdybych dostal chuť tento základ rozšířit o další položky struktury, třeba řetězce, čtení a zápis seznamu do souboru atd. No, a ty identifikátory... u funkcí c jako create, a add, f free, d delete, p print, ve struktuře x číslo, n node, struktura l list, i čislo, p q pomocné proměnné, z znak.

[sad]

n může být i next.

[Václav "Darm" Novák]

Uč se psát identifikátory tak, abys je nepochopil jen ty podle klíče který si pamatuješ, ale aby byly jasné komukoliv, kdo se podívá na kód. Zlozvyků se špatně zbavuje a těch pár písmen navíc tě nezabije

[sad]

Samozřejmě, kdybych tu strukturu obohatil o další položky, tak už bych je pojmenoval normálně, jako například jméno, věk, hloubka atd. Mně se jen líbilo, že takhle to vypadá velice čistě.

[Václav "Darm" Novák]

A nečitelně, zvlášť když to ukazuješ dál

[pubertak]

... jméno, věk, hloubka ...

Co to píšeš za databázi?

[sad]

Jen vtip.

[pochybnik]

c jako clear, a jako allocate, f jako find, d jako declare, p jako purge, x jako eXtension, n jako pocet (pro 1 ..n), l jako label, i jako inode, z jako zdroj.

Ano, je mi to naprosto jasne, urcite neudelam ani po letech chybu.

[jekub]

opravdu vas to zajima? tak ja se hlasim - nemusel.

[kozzi]

Kdyz vidim zase po nejake dobe kod v C tak uz vim proc mam rad D :D

import std.stdio;
import std.range;
import std.algorithm;
import std.conv;

List!T list(T)(T[] data)
{
    return new List!T(data);
}

class List(Type)
{
    Type value;
    List!Type next;

    this() {}

    this(Range)(Range data) if (isInputRange!Range && is(Type : ElementType!Range))
    {
        auto current = this;
        current.value = data.front;
        foreach (value; data.dropOne)
        {
            current = current.next = new List(value);
        }
    }

    this(Range)(Range data) if (isInputRange!Range && !is(Type : ElementType!Range))
    {
        this(data.map!(a=>to!Type(a)));
    }

    this(Type value)
    {
        this.value = value;
    }

    @property Type[] values()
    {
        Type[] values;
        foreach (v;this) values ~= v;
        return values;
    }

    @property auto end()
    {
        auto current = this;
        while (current.next !is null) current = current.next;
        return current;
    }

    List!Type opBinary(string op)(List!Type list) if (op == "~")
    {
        end.next = list;
        return this;
    }

    List!Type opBinary(string op, OtherType)(List!OtherType list) if (op == "~" && !is(Type == OtherType))
    {
        auto l = new List!Type(list.values);
        return opBinary!op(l);
    }

    auto ref opUnary(string op)() if (op == "++")
    {
        return next;
    }

    void remove(Type value)
    {
        auto current = new List!Type();
        current.next = this;
        while (!(current is null || current.next is null))
        {
            if (current.next.value == value)
                current.next = current.next.next;
            else
                current = current.next;
        }
    }

    int opApply(int delegate(ref Type) dg)
    {
        int result = 0;
        List current = this;
        while (current !is null)
        {
            result = dg(current.value);
            if (result)
                break;
            current = ++current;
        }
        return result;
    }
}

void main(string[] args)
{
    auto l = list([10, 12, 7, 18, 4, 6]);
    foreach (v;l) writeln(v);

    auto l2 = list(["10", "12", "7", "18", "4", "6"]);
    foreach (v;l2) writeln(v);

    auto l3 = l ~ l2;
    foreach (v;l3) writeln(v);
}

[Jardík]

Tu procku na vytvoření můžeš trochu zkrátit:

void create(struct list **list)
{
    struct list *link;
    int val;
    
    printf("Zadejte cisla a ukoncete znakem:\n");
    
    while (scanf("%d", &val) == 1)
    {
        *list = link = malloc(sizeof(struct list));
        
        if (!link) exit(1);
        link->val = val;
        link->next = NULL;
        list = &link->next;
    }
    
    while (getchar() != '\n')
        ;
}

Jinak v C nemusíš přetypovávat void*.

[Jardík]

A ten append v podobným stylu:

void append(struct list **list)
{
    struct list *l2;
    create(&l2);
    
    while (*list)
        list = &(*list)->next;
    
    *list = l2;
}

[sad]

Díky za radu. Jen se možná zeptám, na tohle si přišel sám, nebo jsi to někde vyčetl, viděl. Protože mám takový pocit, že asi nikdy nebudu dobrý programátor. Trvalo mi asi týden, než jsem pochopil tyhle seznamy, a pochybuji, že bych takové takové krátké a elegantní řešení, které jsi mi sem hodil, vymyslel sám.

[kozzi]

Tak ono hlavni problem v tvem kodu jsou nazvy (ale to jsem ochotnej akceptovat pokud jde jen o ukazku nebo o datovou strukturu ktera bude nekde schovana a nebude se na ni sahat), ale jako mnohem vetsi

problem vidim to ze v metode pro spojovani seznamu (metoda a) vytvaris pole (volani metody c), to je asi to nejhorsi co programator muze udelat. Jiank dobry programator s tebe byt urcite za par let muze. Pokud k tomu ma clovek vlohy a chut zlepsovat se, tak nevidim duvod proc by to nemelo jit.

[pavlix]

Popravdě bych ti doporučil si projít pár nejznámějších knížek a podívat se, jak to řeší oni. Na druhou stranu, ty jsi věděl, že máš použít dvojtý ukazatel? Mně osobně to musel nejdřív někdo říct.

[dad]

zajimalo by me, proc si se rozhodl zrovna pro hodnotu 12 a ne treba 13, 14 nebo 8456? Vubec mi to cele nedava nejak smysl.

[sad]

?

void append(struct list **list)

[dad]

*list = 12; ...

[sad]

*list = L2;

[Jardík]

O.o to je malý "L" a dvojka, stejnej název, jako si tam měl ty.

[pavlix]

Na jednu stranu mě blog se spojáky v C zrovna moc nebaví, navíc s tou nepřehlednou implementací. Na druhou stranu mi to připomnělo glib, kde je API k lineárním spojákům tak debilní, jak jen může být. Kromě vkládání na začátek jaksi vývojáři této knihovny implementovali API jako pro pole, kdy hlavním a nejpoužívanějším API je indexace, která je u pole mnohem rychlejší.

Takže proč se nepodívat na kvalitu API této ukázky (přehlednost kódu už pomluvili jiní)?

typedef struct ... {
    ...
} list;

Záleží na zvyklostech, ale pokud už se to musí jmenovat list, dal bych přednost struct list. Pokud to musí být nutně typedef, tak použít nějakou konvenci, aby list zůstalo volné.

Tedy...

struct list {
    int data; /* V reálné implementaci spíše typ 'void *'. */
    struct list *next;
}

Vytvoření seznamu

c(list **l)

Funkce by neměla dělat žádné IO operace, tedy žádný printf ani scanf a její prototyp by měl být navržen účelně. U seznamu s hlavou dává smysl:

list_init(struct list *head)

Nebo:

struct list *list_new(void)

V případě seznamu bez hlavy nemá inicializace smysl a stačí používat:

struct list *list = NULL

Zrušení seznamu

void f(list *l)

Doporučuju dávat hned pod vytvoření, původně jsem si myslel, že chybí.

Volající je zodpovědný za ukončení používání hodnoty pointeru. Tomu se dá v případě zájmu vyhnout:

void list_clear(struct list **list)

Připojení dalšího seznamu

Zcela nesmyslné ač pokročilé API, které nedělá nic, co by bylo k něčemu dobré.

Odstranění prvku dle hodnoty

Pokročilá funkce, která se občas hodí, API v celku dává smysl, ale chybová hláška je zbytečná. Pokud je opravdu potřeba vracet informaci o počtu smazaných prvků, je lepší použít návratovou hodnotu.

int list_delete_all(struct list **list, int value)

Může dávat smysl i funkce pro smazání jednoho:

bool list_delete_one(struct list **list, int value)

(Lze samozřejmě použít opět typ int.)

Debugovací výpis

void p(list *l)

Dává smysl.

Co chybí?

Jenom namátkou.

/* Přidej na začátek. */
void list_push(struct list **list, int data);
/* Odeber ze začátku, v reálné implementaci návratový typ 'void *'. */
int list_pop(struct list **list);
/* Bez obrácení se s jednosměrným seznamem špatně pracuje. */
void list_reverse(list **list);

Proč obousměrný seznam

Jednosměrný spojový seznam je vskutku debilní datová struktura vhodná k jednoduchým operacím typu push/pop na začátku seznamu a operacím, které iterují nad celým seznamem.

Dvousměrný spojový seznam, ideálně s hlavou, oproti tomu nabízí možnost vytvořit velice příjemné a jednoduše implementovatelné API:

struct list {
    int data; /* Ve reálu 'void *'. */
    struct list *previous;
    struct list *next;
};

void list_init(struct list *head);
void list_clear(struct list *head);
/* Nebo dynamicky:
 *   struct list *list_new(void);
 *   void list_free(struct list *head);
 *   void list_clear(struct list **head);
 */

/* Přidat před/za libovolný prvek. Vložení za hlavu znamená na začátek, před hlavu znamená na konec. */
void list_add_before(struct list *item, int data);
void list_add_after(struct list *item, int data);
/* Odstranění libovolného prvku. */
int list_remove(struct list *item);
/* Zkratka pro vložení na začátek/konec. */
#define list_insert(head, data) list_add_after(head, data)
#define list_append(head, data) list_add_before(head, data)
/* A další */

Na konec...

Uhlazené API by pak rozlišovalo objekt, který reprezentuje celý seznam a objekty, které reprezentují jednotlivé prvky a případně by poskytovalo callback API pro uvolňování dat a podobné věcičky.

[sad]

Díky, projdu si to. Seznamy jsem se učil z knihy Algoritmy a programovací techniky od Topfera, kde jsou příklady v Pascalu a je tam i trochu vysvětlen ten obousměrný seznam, ale bez hlavy, a ještě mám Učebnici jazyka C od Herouta. Nicméně programování není vůbec jednoduché, a to se ještě snažím naučit C++. Zatím si ty třídy představuji jako takové vylepšené struktury, které obsahují nejen proměnné, ale i funkce. Samozřejmě jsem byl docela překvapen z konstruktorů a destruktorů (jedni třídu inicializují, druhý ničí, že?), Možná bych se zeptal, jestli se v C++ vůbec používají datové struktury jako seznamy, binární stromy, grafy, zásobníky, fronty, nebo už je to tam vyřešené jinak. Protože jsem četl, že objektové programování je hodně odlišné.

[kozzi]

Datove struktury se samzrejme pouzivaji, ale u vetsiny jazyku uz jsou predpripravene a nemusis si je sam tvorit. Napriklad pro c++ http://www.cplusplus.com/reference/stl/. Jinak doporucuji zacit jen jednim jazykem, ackoliv C a C++ se da ucit naraz, tak je dobre ze zacatku pochopit jen jedno paradigma  a pak az druhe. Pokud budes od zacatku mixovat proceduralni a OOP tak se v tom muzes zamotat.

 

BTW. Proc C++? To bych nedoporucoval, neni to zrovna idealni jazyk na kterem by si mel IMHO zacinat.

[sad]

Bohužel to tak nevypadá, ale nejsem úplný začátečník, Céčko se učím s přestávkami už asi dva roky. Pak jsem si přidal i tyhle datové struktury, než jsem pochopil k čemu vůbec jsou, také trvalo strašně dlouho. A nakonec jsem zjistil, že vlastně vůbec nic neumím a že potřebuji nějakou knihovnu, tak jsem si chvíli hrál s ncurses, A teď bych chtěl zkusit Qt, proto to C++. Díky za odpověď. Já na to svým programování budu muset zapracovat.

[kozzi]

Tak Qt mohu vrele doporucit je to velmi fajn toolkit nejen pro tvorbu UI. Jinak sam jsem v nem kdysi pracoval a v QtCreatoru to s C++ nebylo vubec tak zle. Ale s porovnanim s kombinaci napriklad pyqt (Python + Qt) to bylo furt takove zbytecne slozite.

Jinak dva roky s prestavkami to zase neni tak dlouho. Ja uz programuji od 12 let mozna drive a ted mi je 25, to znamena polovinu sveho zivota a stale si dovolim tvrdit ze se ohledne programovani mam co ucit.

[pavlix]

Jestli chceš rychle něco tvořit, doporučuju to zkusit v Pythonu. Datové struktury tam řešit nemusíš, jsou vestavěné a můžeš se velmi rychle dopracovat k funkčním programům bez nějakého extra hlubokého porozumění tomu, jak počítač přesně pracuje. Zda to považuješ za výhodu nebo nevýhodu, je na tobě.

[Miloslav Ponkrác]

A čas od času si jenom pořeší přepsání zdrojáků, až Rossumovi zase prdne v hlavě, a rozhodne se nekompatibilně změnit syntaxi Pythonu.

[pavlix]

Už je to otravné.

[Bystroushaak]

To tvrzení skoro předpokládá, že někdy nebylo.

[Miloslav Ponkrác]

V realitě se to stalo, v matrixu ne.

[pavlix]

Tak jednou to může být zajímavá připomínka nebo opakovaně v kontextu, kdy to dává smysl, ale vyhledávat vlákna, kde se vyskytuje Python a opakovat pořád do kola pochybné předpovědi, na to snad musí být člověk nějak nemocný.

[Miloslav Ponkrác]

Ta připomínka je tu proto, aby bylo jasné, že priorita Pythonu je jinde, než u řady jiných jazyků.

Že Python nebere za důležité ochránit časové a duševní investice programátorů do jejich pythonovských kódů, takže programátor musí s tímto počítat.

Jednoduše i projekt musíte plánovat podle záruk. Některé jazyky investice programátorů do zdrojáků chrání, jiné ne.

Budovat velký nebo dlouhodobý projekt na jazycích, které si jen tak mir nichts dit nichts mění syntaxi jazyce zpětně nekompatibilně, je neivita hrubého zrna, které nezůstane nepotrestána.

Python je pěkný jazyk. Líbil by se mi. Ale bez záruky zpětné kompatibility a trvalosti napsaných zdrojových kódů to není seriózní programovací jazyk. Rossum dal najevo, že dává přednost hračičkování s Pythonem před jeho povýšením na seriózní jazyk.

Učit se programovat na Pythonu, proč ne? Je to pěkný jazyk a solidní jazyk pro velmi krátkodobé projekty. Stejně tak si naskriptovat něco, co momentálně potřebuji a za rok to nebude mít smysl. Ale nic trvalého, nic důležitého, nic seriózního – na to je třeba určitá záruka zpětné kompatibility.

[kralyk z abclinuxu]

Na mém systému:

$> python2 some-code-written-in-python2.py

Takže v čem je problém?

[pavlix]

V tom případě asi podle pana Ponkráce děláš něco chytrého.

[Miloslav Ponkrác]

Ještě nezjistil existenci toho, že existuje čas. Nicméně díky tomu nemá strach z budoucnosti a jeho duše má věčný klid a mír na rozdíl od věčně se stresujících Čechů, kteří se bojí co nastane zítra. To je chytré, to potvrzuji.

[pavlix]

s/chytrého/špatně/

Nevím, na co jsem myslel.

[Miloslav Ponkrác]

Problém je v tom, že python2 nebude použitelný věčně. Postupně se správci různých důležitých knihoven vykašlinkají na to, aby podporovali starou verzi pythonu.

Stejně tak, jako je jisté, že ani python2 nebude vyvíjen věčně, až jednoho dne nebude kompatibilní třeba s os, třeba s něčím jiným.

Jednoduše starší verze věcí a programů upadají vždy do nepodpory, pokud to někdo krvavě nezaplatí.

Proč dnes nikdo nevyvíjí Linux 1.0 tak, aby plně běhal a podporoval všechny aspekty nejnovějšího hw? Protože existuje novější jádro.

Proč python2 časem budete mít problém používat. Protože na jeho vývoj se bude čím dál více kašlinkat až bude časem méně a méně použitelný, až se jednoho dne stane nepoužitelným zcela. Stejně tak jako marně doufáte, že si budete stavět servery s Linux kernelem 1.0 v roce 2020, budete nepoužitelností této verze donucen k přechodu na vyšší verzi, nebo třeba na jiný os.

Jinak řečeno, zastarávání pythonu 2 váš dříve či pozdějí donutí zahodit či přepsat na novější verzi pythonu všechny zdrojáky s pythonem 2 či jiný programovací jazyk.

Divím se, že vám to musím vysvětlovat. Buďto děláte, že jste se včera narodil, a nebo ze sebe děláte hloupého, nebo jste právě měl lysohlávky. Jinak si váš příspěvěk nedokáži vysvětlit. Je totiž z cesty.

Tím hlavním, co zlikviduje použitelnost starších verzí pythonů je velký mistr čas. To, že něco můžete udělat dneska neznamená, že to budete moci udělat za rok, za dva, za pět.

Mějte se hezky, a přeji více selského rozumu, než začnete protiargumentovat. Omlouvám se za ostřejší slova.

[kralyk z abclinuxu]

No, tak to, že jednou v budoucnu bude python2 zastaralý, je pravděpodobné, ale stejně tak je pravděpodobné, že tou dobou budou zastaralé programy napsané v python2, podobně jako jsou dnes zastaralé programy napsané pro Linux 1.0.

Takže selský rozum použit, ale přesto opět nevidím problém.

[xxx]

Si myslim, ze problem nejsou ani tak stare programy. Protoze pokud se program neudrzuje, tak zastara sam o sobe, zastaraji knihovny, ktere pouziva. Takze jestli ve vysledku po 10 letech nejde program prelozit, protoze je nekompatabilni prekladac, nebo protoze knihovny ztratili za tu dobu kompatabilitu, je celkem jedno.

Jako problem bych spis videl, ze se neco 2 roky vyviji, a v nejblizsi dobe to nevypada na konec vyvoje, tak to znamena nutnost cely kod prepsat najednou. Pokud se to neudela, pak postupne zacnou odumirat ext. veci, az se prepsani nakonec stejne nevyhnutelne.

[Miloslav Ponkrác]

„Už je to otravné.“

It's annoying because it's true.

[Martin Mareš]

To, že v C/C++ se podobné věci nestávají, je oblíbený mýtus. S překládáním 30 let starých Céčkových zdrojáků si člověk užije spoustu legrace: například v ANSI C oproti K&R přibývala klíčová slova, takže nastanou zajímavé časy, pokud autor programu pojmenoval nejčastěji používanou proměnnou "auto" :)

Podobně v C++: staré dialekty měly zmatek v tom, zda proměnná deklarovaná unvitř for platí jen uvnitř cyklu, nebo až do konce bloku. Standard to pořádně nedefinoval, tak to každý překladač dělal po svém.

Od C99 se už kompatibilita Céčka bere dost vážně (u C++ je to nejspíš podobné, ale nepovažuji se za znalce normy), u čehokoliv staršího je problematická.

[Miloslav Ponkrác]

Základní zmatek C/C++ je spíše v neznalosti standardů.

Klíčové slovo auto existovalo i u K & R. A také fungovalo stejně jako v ANSI C. Kdo znal standard, nemohl mít problémy.

Problém je, že K & R nebyl normován, a tak kompilátory dělalu ledacos.

U C++ je problém v tom, že C++ existovalo mnohem déle, zatímco první norma C++ přišla až v roce 1989. Od doby normy C++ je vše jednoznačně definované. Takže proměnná uvnitř cyklu for podle normy vplatí jen uvnitř cyklu, viz část 6.5.3.2 C++ normy ISO/IEC 14882.

Základní problém je, že kompatibilita a dodržování norem jazyka C se nikdy nebralo vážně, a ani nyní standard C neberou kompilátory příliš vážně. Pokud máte takový dojem, že snad ano, je spíše věc GCC, které v posledních letech začalo normy brát jako závazné.

U C++ se norma brala vždy vážně a závazně. Po vydání normy ovšem trvalo několik let, než kompilátory přešly z nepsaného standardu na normu.

Jinak řečeno, cokoli píšete není problém ani v C, ani v C++, pokud si programátor přečte normu obou jazyků a dodržoval jí.

[Martin Mareš]

Klíčové slovo auto existovalo i u K & R. A také fungovalo stejně jako v ANSI C. Kdo znal standard, nemohl mít problémy.

Pardon, už zapomínám. Není to auto, nýbrž const. To v K&R není a až ANSI C ho zavádí.

[Miloslav Ponkrác]

V K & R C toho moc nebylo. Nebylo tam ani klíčové slovo unsigned, to také přišlo až s ANSI C.

[Martin Mareš]

unsigned tam bylo, signed nikoliv.

[kralyk z abclinuxu]

Napriklad pro c++ http://www.cplusplus.com/reference/stl/.

Doporučil bych spíš cppreference.com, imho kvalitnější.

Jinak +1 k tomu C++: Pokud si tazatel nepřipadá jako zdatný programátor a/nebo nemá OOP v malíku, určitě by bylo lepší začít s něčím jiným než C++. Např. ten python, object pascal a podobně.

(To říkám na základě vlastní zkušenosti: můj první progam v C++ byla hrozná obludná příšerná prasečina )

[Saljack]

Ja bych doporucil javu a to z duvodu, ze je to podobny cecku a je mnohem jednodusi nez C++ (pro zacatecnika).

[kralyk z abclinuxu]

Hm, tak to bych nedoporučil, začátečník se s Javou naučí, že o paměť se není potřeba starat a je jí vždycky dost a podobný zlozvyky...

[mich]

Před chvílí jsi zmiňoval python, ale Java je podle tebe fuj kvůli gc?

[kralyk z abclinuxu]

Python je skriptovací jazyk (resp. je tak většinou použit), to považuju za jinou kategorii... Ale ja pravda, že pokud by někdo třeba přešel k C z předchozí zkušeností pouze v pythonu, mohl by mít problém.

[kozzi]

Tak tady bych nesouhlasil. Ne kvuli Jave. Tu sam moc nedoporucuji. Ale kvuli duvodu ze o pamet se neni potreba starat. Prave ze pro zacatek je fajn mit jazyk kde to neni potreba. Pokud ten jazyk ma spravu pameti resenou solidne tak nebyva problem. Napriklad me se velmi libi jazyk D. Viz ma ukazka vyse. Nikde tam neresim uvolnovani pameti a obecne ja pametova narocnost cca 3x vetsi nez u manualni spravy. Ano muze se to zdat dost ale v dnesni dobe to vubec nebyva zas takovy problem.

Jinak Java vs. D. Tak D je mnohem jednodusi. Teda aspon pro me bylo peklo snazit se psat v Jave potom co jsem si navykl na jazyky jako python a D.

[kralyk z abclinuxu]

Prave ze pro zacatek je fajn mit jazyk kde to neni potreba.

Tahle poučka se hodně často opakuje, ale mě přijde, že to není moc opodstatněný. Pro opravdu úplného úplného začátečníka to asi je lepší, ale jakmile začne mít někdo ambice psát algoritmy, struktury a případně užitečné programy, měl by k nějakým základům memory managementu přičichnout (IMHO).

[Miloslav Ponkrác]

Nehledě na to, že garbage collector taky není ideální součástka, protože funguje v reálném světě. Ideální garbage collector je drahý a žere mnoho výkonu, takže se dělají různé švindly.

Obecně garbage collector nezaručuje, že zruší objekt vůbec, ani za jak dlouho to bude.

Takže stejně nakonec musíte ručně řešit uvolňování různých zdrojů systému (soubory, grafické objekty, …), takže ono to úplně až tak automaticky nefunguje.

---

Podle mého názoru jsou dvě cesty, jak se výborně naučit programovat.

1. cesta: Chci se rovnou učit jen ten jazyk, který budu používat v praxi. (Je to ta horší cesta.)

Pak je to jasné – učte se jazyk, na kterém chcete dělat.

2. cesta: Jsem ochoten se na začátku učit na jazyce, který je pro praxi nevhodný a počítám s tím, že poté se naučím jiný jazyk, který budu používat.

Podle mého není lepší cesta než Pascal na začátek.

---

Poznámky: Jestli chcete neumět nikdy programovat, učte se programovat na Javě, nebo Perlu, nebo PHP, nebo C#. Tyto jazyky mohou být praktické, ale jsou tak zmatené ve svých konceptech, že začátečník po jejich naučení je ve stejné situaci, jako karatista, který se naučil 20 základních věcí špatně a pak se je zoufale a bolestně, mnohem pracněji, musí učit správně. Nejhorší na začátek z těchto jazyků je Java.

Jestli mohu velmi dobře poradit, neučte se jazyky uvedené v předchozím odstavci jako první. Hodně si prodloužíte cestu k dobrému programátorovi.

---

Miloslav Ponkrác

[Saljack]

S timhle naprosto nesouhlasim Pascal je mrtvi uz peknou radku let oproti tomu, kdyz zacne nekdo s Javou jiste najde nekoho kdo mu s necim poradi. Programovani neni o sprave pameti, to se podle me kazdy dokaze behem chvilky doucit. Pokud programuje v Jave uz bude umet dynamickou alokaci a mazani uz neni takovy problem.

[kralyk z abclinuxu]

Už jsem narazil na příliš mnoho začátečníků v Javě (a příliš mnoho jsem jich např. musel mít v týmu), abych si dělal iluze o snadnosti zvládnutí Javy pro začátečníky. Někteří měli plnou hlavu dizajn patternů, ale přitom mezery v základech programování. Možná je to chyba výuky, těžko říct...

Pokud programuje v Jave uz bude umet dynamickou alokaci a mazani uz neni takovy problem.

To je otázka. Já bych spíš sázel na to, že začátečník ti řekne "Nó, tady si dám new Foo() a tím si udělám novej objekt" a pojmy jako dynamická alokace/dealokace nebo heap mu nic neřeknou.

Suma sumárum, IMHO programovat v Javě dobře je ve výsledku úplně stejně náročné jako v ostatních jazycích...

[OldFrog {Ondra Nemecek}]

Někteří měli plnou hlavu dizajn patternů, ale přitom mezery v základech programování.

Tož bylo by fajn říct, co ty základy programování jsou - zajímalo by to mě a zřejmě i tazatele.

Jonak celé programování je o dizajn patternech, ne? Akorát na různých úrovních.

[kralyk z abclinuxu]

Tož bylo by fajn říct, co ty základy programování jsou - zajímalo by to mě a zřejmě i tazatele.

Jeden začátečník na jednom projektu asi před 2 lety střemhlav aplikoval několik "dizajn patternů" (byly tam nějaký singletony a nějaký factory nebo co to tehdá bylo), ale přitom v návrhu tý aplikace byly zcela elementární chyby, jako např. GUI načítalo data stále znova z disku a ze sítě a ignorovalo, že data už byly načtený a připravený k zobrazení o vrstvu níž apod. Ten dotyčný ani pořádně nevěděl, co ten program dělá, měl v tom naprostej guláš, ale když jsem ho konfrontoval, tvrdil, že "takhle se to dělá". A to jsem přitom na něj ani nebylo nějak zlej nebo něco

Jinak celé programování je o dizajn patternech, ne? Akorát na různých úrovních.

Tak v zásadě se za disajn pattern asi dá označit ledacos. Já nejsem nějak zásadně proti, znát best practices je určitě dobrá věc, ale na dizajn patternech (zejména na jejich výuce) se mi nelíbí to, že svádí lidi (zejména začátečníky) k tomu, aby kopírovali nějaký postup, aniž by věděli, proč je dobrý ten problém řešit zrovna tím způsobem, nebo dokonce v horším případě aniž by vůbec věděli, co daný kód znamená/dělá.

[OldFrog {Ondra Nemecek}]

To ale jen znamená, že ten začátečník danou oblast neobsáhl a tápal. Patterny jsou náročné téma a člověk bez praxe by se měl poradit se zkušenějším kolegou.

Ale to platí obecně - když by si člověk sedne k adekvátně náročnému tématu v C (což datové struktury a pointerová aritmetika podle mě jsou), bude dělat zvěrstva úplně stejně - zase by se měl o principiálních věcech poradit.

Takže to vidím spíš na problém výuky případně problém kompetencí. A možná i vedení projektu - například taková časová tíseň spolehlivě zničí veškeré myšlení, zejména u méně zkušených lidí.

Jinak java je skutečně trochu polovičatá a lehce matoucí (hraje to na obě strany - je OOP ale ne dost důsledně), ale že by bylo C snadné mi zrovna nepřijde. Ostatně cokoli člověk dělá pořádně je dřina Na jazyk snů jsem bohužel ještě nenarazil.

[Miloslav Ponkrác]

Přejde mi, že design pattern jsou spíše velmi jednoduché téma.

Co se týká jazyka snů, problém je spíše v tom, že dnešní jazyky, které jsou mainstream jsou spíše jen klony jednoho jazyka.

Dnes se razí styl, jazyk musí být blbý a nic neumět a vše se dohání knihovnami. Takové je C, taková je Java, takový je Python, taková je spousta dnešních jazyků. Někdy se těm jazykům říká „glue language“, je to v zásadě jen lepidlo, kterými se lepí knihovny k sobě.

Řada lidí má přímo panickou hrůzu z toho, když jazyk toho umí hodně, protože v tom nedokáží psát efektivně, neboť nemají v sobě řád, pořádek, a schopnost využít možností jazyka aniž by se v tom ztratili. Proto mnoho lidí obhajuje C nebo Javu s argumentem, jehož podstata zní: „on toho moc neumí a tak v něm nikdo netápe“. Předchozí věta se říká líbivěji, ale její sytová podstata je tak jak jsem to napsal. Tato věta na obhajobu C i Javy zazněla i v této diskusi v několika příspěvcích.

Holt někdo musí mít nejslabšího fichtla, jinak si ublíží. Jiný zvládne nadupanou mašinu a dokáže jí ovládat. Je to stejné v motorkách, programovacích jazycích i ve všech oborech.

Kdyby zámečník pracoval jako dnešní programátor, měl by jen kladivo a šroubovák. Vše ostatní by tím nahradil – to je zhruba analogie dneníšho C, Javy a dalších jazyků, které jsou dnes módní. Kdyby potřeboval tyč obdélníkového profilu, jednoduše by vzal kulatinu a mlátil do ní kladivem tak, až by jí zdeformoval do obdélníkového průřezu. Tak se dnes mainstreamově programuje.

---

Jakmile vejdete do hájemství jazyků, kde jazyk řadu věcí řeší jako jazyk, ne jako knihovnu, dostanete daleko většího pomocníka jako benefit. Ta špatná zpráva je, že se takový jazyk budete chvíli učit, protože je jeho složitost vyšší.

Sám mám raději jazyky té druhé skupiny, protože jsou efektivnější na vývoj. Píši v několika takových jazycích a jazykům snů se to z mého pohledu přibližuje. Ze známějších jazyků je to jen to C++.

---

Spíš bych doporučil, zkuste si několik jazyků s naprosto odlišnou filozofií. Zkuste chvíli Smalltalk, pak si vezměte Prolog, pokračujte Adou, atd. Každý ten jazyk chce diametrálně odlišný přístup. A změníte celý názor na jazyky i programování.

[xxx]

Co je tou podstatnou vlastnosti C++, ze na rozdil od Javy, nepatri mezi gluue languages?

[Miloslav Ponkrác]

Že Java není samonosná. Potřebuji podporu jiného programovacího jazyka, jinak nefunguje. Tedy potřebuje, aby většina běžícího kódu nebyla Javou.

JVM (Javovská virtuální mašina), na které Java běží jsou milióny řádek kódu napsaných v C++.

Část javovské knihovny je psána opět v jazyku rodiny C/C++.

A to je přesně „glue language“. Jádro jazyka nejde napsat v jazyce samém, protože jazyk pro to nemá prostředky. Část knihoven nejde napsat v jazyce samém, protože jazyk pro to nemá prostředky. Tedy jazyk v podstatě slepuje jádro a knihovny jiného jazyka, a programování nad ním tvoří vyšší vrstvu.

Řada jazyků samonosná je. Ada, C, C++, Fortran, Modula, Objective-C, Pascal, Simula, atd. Můžete napsat kompilátor/interpretr i knihovny v těchto jazycích přímo bez pomoci dalšího jazyka.

Řada jazyků potřebuje, aby alespoň část knihoven byla napsána v jiném jazyce – buť pro to, že jazyk nemá pro to vůbec prostředky, nebo proto, že takové knihovny budou extrémně pomalé, jsou-.li zcela psány v jazyce samém. A takovým jazykům se říká glue languge – jazyky lepidla, které dohromady slepují kusy kódů jiného jazyka pomocí svých konstrukcí.

[kralyk z abclinuxu]

Celkově s tebou v týhle diskusi spíš souhlasim, ale tohle není fér kritérium. Jestliže nastolíš bootstrapping jako podmínku 'dobrého jazyka', automaticky se tím vyřadí všechny nekompilované skriptovací jazyky a jazyky běžící ve VM.

Navíc mam mlhavý dojem, že i Javu je možné bootstrapnout... Ale nejsem si jist.

[xxx]

Tak ona i ta definice glue language je v tomhle pripade ucelove priohunta. Ono se tim mysli jazyky spojujici hotove kusy kodu. Tedy, ze clovek vic lepi existujici reseni, nez ze vymysli reseni vlastni. V tom se ale C, Java ani C++ diametralne nelisi. Proste se saha do standardnich knihoven, ktere poskytuji +/- to same (i kdyz v tom C spis -).

Jazyk v jakem jsou jednotlive komponenty napsany je z hlediska definice "glue language" naprosto nepodstatne.

[xxx]

Takze v momente, kdy nekdo postavi HW JVM, tak se Java stane samonosnou? Jednoduse samonosny muze byt jedine takovy jazyk, ktery umi volat funkce OS. A pokud se podivame treba na glibc, tak ty casti v asm asi taky nejsou z hlediska samonosnosti ok. Takze samonosnost je takova pekna akademicka vlastnost, ale z hlediska hodnoceni kvalit jazyka naprosto nesmyslna.

Jinymy slovy Java je fuj, protoze preklada do bytecodu, zatimco C++ je fajn, protoze preklada do strojaku?

Ja spis ocekaval odpoved na to, kde je ten podstatny rozdil v moznostech jazyka. Jake jazykove konstrukce nahrazuji v C++ to lepeni knihoven, ktere vidite v Jave.

[pavlix]

Jen pro zajímavost...

Je otázkou, zda si pod HW JVM všichni představují hardware, který je Javu schopný interpretovat bez dalšího kódu psaného v jiném jazyce. Pokud jde o glibc, bylo by možné alespoň teoreticky asm části eliminovat?

[xxx]

Imho by ten asm slo eliminovat i prakticky, zas tolik ho neni. Navic jsou to casto platforme zavisle casti kodu. Hodne ho je, jak se zda okolo fpu, takze by se ztratila nebo zpomalila nejaka funkcionalita.

Ale asi tezko bez asm napiste program pro nejakej jednocip, na kterem nebezi OS, nebot tu incializace HW, kterou za vas jinak provede OS (a ktera je z casti v asm), si musite pridat primo do vaseho programu.

[pavlix]

Otázka se týkala jen glibc, které bylo zmíněno i v předchozím příspěvku, tedy zda je teoreticky soběstačné a veškerý asm kód je z důvodu optimalizace nebo zda potřebuje nějaký glue kód, aby mohla knihovna vůbec fungovat.

[pavlix]

Jonak celé programování je o dizajn patternech, ne?

Tím bys z programování vyloučil používání mozku (k něčemu jinému než paměti) a tvůrčí činnost.

[Miloslav Ponkrác]

„Už jsem narazil na příliš mnoho začátečníků v Javě (a příliš mnoho jsem jich např. musel mít v týmu), abych si dělal iluze o snadnosti zvládnutí Javy pro začátečníky. Někteří měli plnou hlavu dizajn patternů, ale přitom mezery v základech programování. Možná je to chyba výuky, těžko říct...“

To je přesně to, co jsem měl na mysli, když píši, že začátečník, který se skutečně chce naučit programovat nemůže udělat hůře, než když se začne učit Javu.

Neexistuje horší první jazyk pro programátora, než je Java. Pokud je začátečník vytrvalý, Java mu prodlouží naučení se programování tak o 3–5 let, a to ještě pokud se bude snažit.

Základní problém je, že Java je jeden velký emulátor a matrix, který fixluje a předstírá. Neexistují tam zřetelné moduly, jsou příliš v relaci se třídami. Neexistují tak adresáře projektu, jsou příliš v relaci s namespacy. Neexistují tam výčtové typy, jsou emulované třídami. Neexistuje tam tak miliarda věcí, vše je emulované třídou.

Kromě toho javisté začátečníkům lžou, protože jsou fanatičtí. Oni začátečníkům neřeknou, že Java má daleko do čistě objektového programování. Totiž že čistá objektovost je narušená znaky, čísly, atd., které nejsou objekty. Fanatičtí javisté nabulíkují začátečníkovi, že OOP == přesně to co má Java.

Jinak řečeno, všechno je přeházené. Pokud přicházíte z jiného jazyka a máte v tom základy a pořádek – Java je v pohodě. Ale pokud získáváte rozhled na Javě, tak Java je dokonalý Orwell. Válka je mír, svoboda je otroctví, moduly jsou třídy, výčtové typy jsou třídy, OOP je Java, atd., vše se ztrácí a mlží v politicko korektních nepravdivých termínech, které si Java z reklamních důvodů ohnula. Začátečník to nerozchodí, nerozluští a jsou to ztracené roky.

Nemluvě o tom, že javisti nutí začátečníka, který neumí programovat hrát si na enterprise prostředí –. tedy ty design pattern, unit testy, build mašiny, atd. To je jako kdyby chirurg, který neví, kde je žlučník a játra se začal učit transplatovat srdce. Stejná kravina.

Kdo je masochista, nechť se jako první jazyk učí Javu. Jako odměna mu bude, že bude dlouho špatný programátor.

Zdůrazňuji, že nehaním Javu, jen silně nedoporučuji Javu jako první a jako učební jazyk, to považuji za úplnou krávovinu.

Stejně tak jako kolega mluvil o Pascalu jako o mrtvém jazyce si zapomněl všimnout, že jsem ho doporučil pro variantu, že se chcete naučit dobře programovat na nepraktickém jazyce, a pak pro praxi se naučíte jiný.

Mimochodem 99 % programovacích jazyků je absolutně mrtvých. Stačí počkat tak 10 let.

Miloslav Ponkrác

[:::]

+1

[OldFrog {Ondra Nemecek}]

Nojo, lidi jako vy by měli psát učebnice nebo učit a problém by možná zmizel

[Miloslav Ponkrác]

Děkuji moc.

[JS1]

Zajimalo by me, jak vypada clovek, co se ucil programovat na Haskellu.. Nechcete to nekdo zkusit? Muj tip je, ze bude liny a mit problemy s uklidem odpadku.

[OldFrog {Ondra Nemecek}]

1++ skvělá oponentura

[Pavel Píša]

Zaprvé, single-linked listy se hodí opravdu jen na velmi omezené množství úloh. Zadruhé, implementace, kdy je zadrátovaný napevno typ prvku má velmi omezené použití. Zatřetí, v normálních prostředích (POSIX) je již podpora listů v C-knihovně standardně k dispozici #include <sys/queue.h>. A nakonec začtvrté, určitě je velmi užitečné si implementaci zkusit napsat sám, aby člověk pochopil, co je dobré a jaké vlastnosti od různých jiných implementací čekat.

Odkazy na standardní lib-C manuélovou stránku man QUEUE, man TAILQ_INSERT_TAIL, ...

V době , kdy jsem podobné konstrukce potřeboval opakovaně řešit a to především na embedded systémech, tak ještě standardně tato implementace nebyla k dispozici. Takže jsem si napsal vlastní implementaci listů (základní struktura pro kompatibility převzatá z jádra), stromů a dalších podpůrných algoritmů. Řešení pro verzi s vygenerovanými custom inline funkcemi zajišťuje typovou bezpečnost / relační příslušnost prvek list. Ale je to docela makro-magie. Knihovna uLUt - uLan/Universal Light Utilities Library je k dispozici je včetně dokumentace na stránce projektu http://ulan.sourceforge.net. Na pochopení je implementace dost náročná, díky nutnosti použití maker není dobře čitelná, ale optimalizuje se dobře a lze jí přeložit od 8-bit systémů (když zrovna není v SDCC chyba tak i tím) až po 64-bitů - Linux, RTEMS, Windows, bez systému, x86, ARM, m68k, msp430 a je již používaná v množství průmyslově využitých aplikací.

[pavlix]

Zatřetí, v normálních prostředích (POSIX) je již podpora listů v C-knihovně standardně k dispozici sys/queue.h

To vypadá docela děsivě, ale to je s části tou hrou s makry a z části těmi prvními dvěma z mého pohledu redundantními implementacemi.

[Miloslav Ponkrác]

Má to jenom jednu nevýhodu. sys/queue.h není ani součastí standardu C, ani součástí standardu POSIXu. Je to přesně to, řemu se říká proprietární a nekompatibilní extenze.

Je hezké, že někdo považuje za POSIX všechno co najde na svém počítači. Zřejmě do POSIX standard pak patří i drobky v klávesnici a rozlitá Cola.

[Pavel Píša]

Máte pravdu, že to sys/queue.h je (zatím) jen BSD rozšíření, ale před nedávnem jsem viděl něco v diskuzi o Newlib nebo jinde, kde o požadavcích standardu na implementaci front diskutovali a nedal jsem si dostatek práce dohledat, jestli to již je ve standardu a nebo jsem si to spletl.

V každém případě POSIX nebo spíš IEEE Std 1003.1-2001 již nějaké fronty a hashe jako povinné definuje.

http://pubs.opengroup.org/onlinepubs/009696799/functions/remque.html

Jinak zajímavým zdrojem algoritmů pro psaní programů v C, který také listy a vyšší datové struktury obsahuje, je Rusty Russell's CCAN (C Code Archive Network) http://ccodearchive.net/index.html.

Dále menším takovým repository je libUCW http://www.ucw.cz/libucw/, kterou udržují lidé z Matfyzu. Pro některá embedded zařízení je ale problém LGPL.

[Miloslav Ponkrác]

Ano, a na rozdíl od hloupé a nedomyšlené sys/queue.h si všimli, že jednosměrný a obousměrný spojový seznam libovolného typu se dá i v C implementovat bez maker. Čehož si nevšimli v BSD a mastí to špatným stylem makrovitě.

On totiž seznam libovolného typu je stále stejná struktura. Jen poslední prvek je různý typ (pokud si hodnotu dáte na konec).

Takže lze zobecnit, že práce se seznamy je práce s ukazatelem na:

struct simple_list { struct simple_list * next; };

nebo

struct double_list { struct double_list * prev, * next; };

Pak můžete napsat obecné funkce typu create, add, delete, atd. bez maker čistějším stylem.

Je hloupé, že BSD je nositelem praseckého stylu programování, a ještě hloupější, že někdo něco prasíckého jako sys/queue.h vůbec začátečníkům doporučuje. POSIX standartizátoři jsou trochu o úroveň výše.

Ale alespoň začátečník vidí, že kdekdo doporučuje kraviny, mluví kraviny (o tom, co je POSIX standard). A že si musí dávat pozor i na to, co mu říkají „zkušenější“.

[:::]

Nevzniklo to treba jeste pred tim nez byly v C inline funkce?

Vzhledem k tomu ze ty operace nad spojovym seznamem vetsinou budou par instrukci tak by se dala pochopit snaha odstranit overhead volani funkce.

[Miloslav Ponkrác]

Ono to hlavně vzniklo v době, kdy frčel Kerninghan & Ritchie C, tedy bez prototypů funkcí, kdy programovací jazyk C nebyl schopen ani kontrolovat správnost počtu a typů parametrů při volání funkce.

Tehdy bylo fakt jedno, jestli voláte makro nebo funkci, protože C nekontrolovalo nic.

Tedy sys/queue.h existuje z historických důvodů. A z historických důvodů je takové, jaké je. Tehdy jednoduše byl programovací jazyk C impotentní a mentálně retardovaný oproti stavu, v jakém je dnes. Psal se rok 1977, když BSD vznikalo. Teprve v roce 1983 se z programovacího jazyka C stalo ANSI C, které ze strašného Kernighan & Ritchie, ve kterém by dnes nikdo nechtěl dobrovolně programovat udělalo docela příjemný jazyk.

A ano, i odstranění overheadu volání funkce byl ten důvod. Jak napovídá „sys“ v názvu headeru, používalo se to pro kernel.

[Pavel Píša]

Bez maker nebo templátů nebo dědičnosti to nelze v C/C++ napsat tak, aby to hlídalo proti sobě typy vkládaných prvků a hlavy listu. Přitom nabídnutí uživateli funkcí s void* jako doporučeného API je cesta k výjimečnému hrobu. takže z tohoto pohledu tu verzi z standardu považuji bez wrapperu jako mnohem horší. Také počítat s tím, že struktura musí mít fieldy v pořadí, jak je deklarovaná a na začátku že uživatel vloží dva ukazatele nebo strukturu s nimi je opět náchylné k chybám, které se zavlečou nesouvisející úpravou v kódu. Přitom často je výhodné mít ve struktuře položky/uzly pro řazení do více nezávislých seznamů. Takže i jen kontrola na strukturu nodu, tak jak je to v jádře Linuxu, může vést k fatálním chybám.

Mnou používané řešení v uLUt veškeré tyto chyby odchytne, ale chybové hlášky jsou dost nepřehledné.

Asi nejelegantnější řešení typové kontroly v případě implementace v C jsem viděl v následující sérii patchů pro Red-Black stromy používané v Linuxovém jádru http://thread.gmane.org/gmane.linux.kernel/1367138/focus=1367138

Na rozdíl od uLUt je mnohem více implemetace realizováno v inline funkcích, kterým se předává popisová struktura vkládaných typů. Type safe funkce stejně nakonec vyžadují jejich generování makrem, ale je to mnohem přehlednější. Na druhou stranu je to řešení, které je mnohem více závislé na kvalitách kompilátoru. Novější verze GCC ale dokáží overhead kódu (popisu problému) zredukovat na přímočarou implementaci shodnou s použitím kódu bez typové kontroly a s optimalizovanými voláními základních vyvažovacích funkcí přímo v místech vkládání a výběru prvků. Bohužel se toto řešení zatím do jádra nedostalo. Spíš kvůli strachu z velmi starých kompilátorů používaných pro některé architektury. Ale řešení je to pěkné, ideu by z něj bylo dobré reimplementovat nad nějakým jiným základem Red-Black stromů, protože ty z jádra jsou licenčně jen GPL2only.

O reimplementaci tohoto řešení byl zájem v komunitě RTEMSu, ale nebyl zatím dostatek sil. Mohla by to být celkem pěkná semestrálka, pokud by se někdo přihlásil. Třeba v rámci našeho předmětu Open-Source programování na FEL. Ale znamená to někoho, kdo se opravdu v C vyjadřuje plynně. Sám na takové pěkné psaní bohužel čas v dohledné době mít nebudu.

[Miloslav Ponkrác]

Začal bych selským rozumem. Pokud uvádíte do seznamu C++, nikdo nebude psát práci se seznamy bez tříd a šablon. Proč by to dělal?

Pokud zůstaneme v jazyce, pak univerzální obecné řešení pro seznamy má vždy nějaké handicapové ale, a je jedno, jestli to děláme pomocí maker nebo funkcí.

Ostatně od toho jazyk C byl, byl vynalezen jako „přenositelný assembler“ a není to jazyk pro bezpečné programování, ale jazyk, ve kterém se musí dodnes trikovat pro dosažení mnoha věcí.

Proto dnes naprosto nechápu nikoho, kdo používá jazyk C a nikoli C++ pro nové projekty. Jazyk C není schopen nabídnout jedinou výhodu proti C++, zato má oproti C++ obrovskou řadu nevýhod.

Sám jsem v C psal mnoho let, ještě v době, kdy C++ fakticky neexistovalo. Když se pak objevilo C++, tehdy ještě relativně hloupé jako „C s třídami“, tak jsem přešel a rychle jsem poznal, že C nemůže už nic dát.

Jediný důvod pro C je dnes udržování historických projektů, nebo psaní pro platformy, kde není kompilátor C++ (těch je rok od roku méně).

Rozhodně ale držím palce s tou semestrálkou. Určitě se zde někdo najde. Mně už dvě vysoké školy stačí, a na doktorát je to málo.

[pavlix]

Popravdě řečeno mi C vyhovuje při psaní daleko víc než C++ už jenom kvůli udržování ABI. Při čtení cizího kódu vidím výhodu v C hlavně v jednoznačnosti a v menší potřebe přečíst velké množství kontextu, aby bylo zřejmé co a proč nějaká funkce dělá. A i když odhlédnu od těchto dvou věcí, mám pocit, že mi C++ na systémové programování nemá oproti C co nabídnout. Ale umím si představit, že na jiných typech projektů to zajímavé být může.

[Miloslav Ponkrác]

Zřejmě jste neměl štěstí na programátora, jehož kód je samokomentující – což lze docílit téměř v každém jazyce.

Psát přehledný kód, ve kterém se rychle orientujete, je schopnost, kde na použitém jazyce příliš nezáleží. Jde o vhodné volení názvu identifikátorů, tedy obvykle tříd, proměnných a podprogramů. Plus vhodná code style na formátování textu.

---

Nerozumím tomu, proč si myslíte, že v systémovém programování nejsou benefitem namespaces, třídy, šablony, lepší detekce chyb, atd., tedy vše, co C chybí.

Výrazným benefitem C++ oproti C jsou přístupová práva kódu (private, protected, public). V C++ na rozdíl od C nemůžete sáhnout na jakákoli data (bez hackování) ani volat všechny funkce, co se v programu vyskytují. Neuvěřitelně to zmenšuje počet chyb, zejména v týmu. Takový jaderný vývojář v C++ nemusí psát dlouhosáhlé traktáty kolegům, na co se sní sahat a co je jen pro vnitřní potřebu, protože jim k tomu rovnou zakáže přístup ve zdrojáku.

Píšu v C++ i jádra krabiček, které mají 32 KB RAM a o něco víc ROM. Efektivita vývoje, přehlednost a možnosti C++ jsou úplně někde jinde, než C.

Jen pro Vaší informaci, Microsoft používá v jádře Windows i vyhazování a chytání výjimek. Pro hloupější jazyky napodporující nativně výjimky přidal dokonce API funkce kernelu, jako třeba RaiseException(), kterou můžete vyhodit výjimku i z jazyka C:

http://msdn.microsoft.com/en-us/library/windows/desktop/ms680552%28v=vs.85%29.aspx

Stejně tak nerozumím tomu, proč není lepší mít základní struktury jádra operačního systému jako třídy. Nic to nestojí z hlediska rychlosti. Navíc máte výrazný benefit jednak v tom, že nezabíráte globální identifikátory na názvy funkcí pracující se strukturami jádra. A hlavně výrazným benefitem je řízení práv a omezit různé vrstvy kódu, kam smí sahat. Na rozdíl od porad a dokumentace pak přístupová práva vynucuje přímo kompilátor C++.

Miloslav Ponkrác

[pavlix]

V celé reakci ani zmínka o mém prvním a hlavním argumentu ve prospěch C, kterým byla údržba a jednoznačnost ABI?

[Miloslav Ponkrác]

C nemá jednoznačné ABI, to vám celý život lhali, pokud si to myslíte.

[Miloslav Ponkrác]

Abych to rozvedl.

POkud chcete mít stejné API a BI jako C, není nic jednoduššího, než k libovolnému identifikátoru v C++ napsat “C":

int "C" nejaka_funkce();

Co se týká udržovatelnosti, je C++ asi o 3000 mil vepředu ve prospěch C++ před C.

Co se týká jednoznačnosti ABI, programovací jazyk C žádné ABI nezaručuje, a nezaručuje ani jeho jednoznačnost a neměnnost. Pokud chcete mít stejné ABI jako C, viz výše konstrukce s "C", což je součástí C++ standardu.

---

Požadavek na nějaké přesné ABI je v přímé opozici k požadavku na maximálně efektivní strojový kód lezoucí z kompilátoru. Tedy čím přesněji svážete ABI u nějakého jazyka, tím horší kód z toho leze. Proto programovací jazyky nic takového, jako že by dělaly nějaké záruky kolem ABI neprovozují a nenechají se k takové ptákovině přemluvit a slíbit.

ABI jazyka C není ani stabilní ani jednoznačné. Jakkoli si to můžete myslet, ale jde o mylný dojem.

[pavlix]

Kdokoli, kdo se stará o údržbu software zařazovaného do běžných binárních linuxových distribucí, ví, o čem mluvím.

[kralyk z abclinuxu]

No, to je ale daný tím, že na linuxu se v 99% případů kompiluje buď GCCčkem nebo kompilátorem s GCC binárně kompatibilním (Clang, Intel, tcc,...).

Jinak obecně to ABI opravdu jednoznačné není, existuje celá řada možných problémů s kompatibilitou ABI. Například odlišný structure padding nebo calling convention. Ale nemusíme chodit tak daleko, i třeba tak základní věc jako velikost integerů by AFAIK u dvou různých kompilátorů na stejném stroji mohla být odlišná.

[Martin Mareš]

V C na Linux by rozhodně neměla. Standardní ABI tyto věci definuje velmi konkrétně.

[Miloslav Ponkrác]

Zvláštní. Dělám pro ARMy a ABI se několikrát změnilo. Je to proto, že ARM má jistá specifika a nedaří se plně trefit způsob ABI, aby to bylo co nejefektivněšjí.

Takže když vyvíjím pro ARMy, musím si dávat bacha, aby GCC pro ARM kompiloval do mého ABI. Ten, abych citoval Vaše slova, „přesně určený ABI“ totiž není až tak přesně určený.

Jinak řečeno, ABI není stabilní. A ani v rámci C a GCC a Linuxu. Zřejmě buď lžete ohledně stability ABI, nebo jste mylně informovaný.

Protože to všichni profesionálové vědí, tak se na ABI příliš nespoléhají. Proto si linux kernel definuje vlastní způsob volání kernelu, který je jiný, než je běžný způsob volání Ckových funkcí.

Stejně tak ABI není definováno příliš konkrétně. Pro sdílené knihovny a různé moduly je definováno někdy pouze to, které registry se musí při volání zachovat, a jak se předává int a pointer. A tím ABI končí.

Jakmile už začnete hromadně mezi různými sdílenými knihovnami předávat jen pitomý float/double, už máte problém.

---

Pokud potřebujete přesné ABI, není nic jednoduššího, než ho v C/C++ zdrojovém kódu předepsat. To je jediný způsob, jak to zaručit. Případně násilím zavést nějaké defaultní ABI (calling convention) v přepínačích kompilátoru.

Na to jsou různé nestandardní extenze, které jsou v každém kompilátoru jiné.

Takže znovu: Jakékoli záruky ohledně ABI jsou v C mylné, pokud si o to kompilátoru sami v C/C++ neřeknete.

Tečka.

Dále se budu na toto téma bavit jen s konkrétními argumenty zakládající se na nějakých seriózních podkladech.

[Martin Mareš]

Zvláštní. Dělám pro ARMy a ABI se několikrát změnilo.

Situaci na ARMu nesleduji úplně detailně, ale pokud vím, tak se ABI nezměnilo, nýbrž se začalo používat jiné – deklarované jako nové a jinak pojmenované. Není to tedy tak, že by se člověku bez varování změnilo pod rukama.

Stejně tak ABI není definováno příliš konkrétně. Pro sdílené knihovny a různé moduly je definováno někdy pouze to, které registry se musí při volání zachovat, a jak se předává int a pointer. A tím ABI končí.

Vážně by mně zajímalo, jestli jste někdy nějakou specifikaci linuxového ABI četl Doporučuji přečíst si například AMD64 ABI, kapitolu Function Calling Sequence.

[kralyk z abclinuxu]

V C na Linux by rozhodně neměla. Standardní ABI tyto věci definuje velmi konkrétně.

No, to už se ale moc netýká jazyka jako takového.

Každopádně, původní argument byl, že C má jednoznačné ABI, zatímco C++ ne. Už nějak nevím, o čem je diskuse , ale pokud se bavíme čistě o jazyce, tak ABI není definované ani v C ani v C++, pokud se bavíme o použití C/C++ v Linuxu na x64, tak je AFAIK definované stejně dobře pro pro C i C++.

Nebo ne? Nějak nevidím, kde by mělo to C++ ABI oproti C postrádat jednoznačnost...

[pavlix]

Každopádně, původní argument byl, že C má jednoznačné ABI, zatímco C++ ne.

Pak je otázkou, kdo takový argument položil. Pokud máš pocit, že já, problém bude spíše v porozumnění, zkus si můj komentář přečíst pozorněji.

[pavlix]

Nezpochybňuju tvá jednotlivá tvrzení, ale jsou úplně mimo kontext. Distribuce se typicky kompiluje jedním kompilátorem a nejčastěji dokonce jen jednou jeho verzí. Zbytek viz Martin Mareš, oproti kterému o tématu nevím nic.

[Kvakor]

Já osobně si nevzpomínám na případ, kdy bych použil jednoduchý spojový seznam (mimo školních úloh, kde to bylo nařízené), právě ze vzpomínaných důvodů. A souhlasím, že jediné místo, kde má smysl si dělat vlastní implementaci (a když už tak alespoń obousměrného) spojového seznamu jsou embedded systémy a podobné platformy, kde je zaprvé chybí podpora v knihovnách, zadruhé je nejen málo paměti, neexistuje stránkování a navíc často neexistuje paměťový alokátor (protože program běží "přímo na železe" bez OS) a je třeba si dělat vlastní hromady.

Naprotitomu na "normálních" platformách typu PC, kde jsou knihovny, paměti je (relativně) dost a hlavně je stránkovaná, považuju implementaci spojového seznamu za zbytečnost (a jednosměrného obzvlášť), snad s vyjímkou omezených jazyků typu Pascal (a tím nemyslím rozličné vylepšené verze), kde jiné možnosti nejsou. V Céčku a spol. jsou mnohem rychlejší a pohodlnější dynamicky (re)alokovaná pole (viz fce realloc()), v objektových jazycích typu C++ je na to přehršel už hotových objektů a ve zbytku většinou ukazatele vůbec nejsou.

Mimo toho, procházení spojového seznamu sice vypadá hezky na papíře, ale na reálném stroji, kde existují cache a paměť je proti CPU velmi pomalá, může být v patologickém případě rozdíl v rychlosti mezi spojovým seznamem a polem řádově takový, jako je rozdíl mezi rychlostí cache a necachované paměti. A když se k tomu ještě přidá fragmentace hromady a swapování ...

[Miloslav Ponkrác]

Běžný případ, kde se používá jednosměrný spojový seznam je jako podsoučást jiných struktur.

Znovu píši, tam, kde procházíte vždy od začátku je obousměrný seznam jen plýtváním paměti, jakkoli dostatek jí máte k dispozici.

Jedno z ideálních použití jednosměrného seznamu je v hašovacích tabulkách pro rychlé vyhledávání pomocí klíče. Pokud použijete vhodnou hašovací funkci s předpokladem, že většina haš kódů bude mít max. jeden prvek. Pokud se stane, a to se u hašovacích funkcí stává, že stejný hash kód má 2 a více prvků, skladují se v jednosměrném seznamu.

Vlastní implementace seznamu má tu výhodu, že si můžete pořešit i alokaci. Můžete alokovat či dealokovat hromadně – a alokační funkce typu malloc, realloc, free jsou velmi velmi brutálně pomalé a zdržující funkce – zejména v multithreadovém prostředí. Nehledě na to, že vlastní alokace je příznivější i k procesorové keši, máte bloky u sebe.

Ono se někdy i v reále velmi vyplatí si datové struktury napsat nízkoúrovňově. Obecné funkce z knihoven jsou generálně psané, ale jejich efektivita není nejlepší.

Miloslav Ponkrác

[pavlix]

V Céčku a spol. jsou mnohem rychlejší a pohodlnější dynamicky (re)alokovaná pole (viz fce realloc()), v objektových jazycích typu C++ je na to přehršel už hotových objektů a ve zbytku většinou ukazatele vůbec nejsou.

Pravdou je, že technicky jsou seznamy hodnot realizované spojově a polem dost odlišné, ač to někteří mí přátelé užívající GLib zcela ignorují.

Já osobně na drtivou většinu věcí používám pole a právě ten realloc, protože nejjednodušší přístupové API, co můžu uživateli knihovny dát, je dvojice funkcí, z nichž jedna vrátí počet prvků a druhá vrátí nějakou reprezentaci prvku na základě indexu.

Implementace bez dalších knihoven je triviální, kdy stačí zvětšit velikost paměti o jeden prvek s možnou optimalizaci na rezervování místa v případě výkonnostních problémů nebo když už předem vím, že se jedná o načítání velkého množství malých jednotek.

Běžně nenarážím na situaci, kdy bych dal přednost spojovému seznamu, ale na druhou stranu běžně neudržuju velké množství dat, kde hraje roli pořadí a na kterých by probíhalo velké množství lokálních úprav. Třeba v textovém editoru bych realloc celého souboru při vložení nového řádku viděl nerad. Na druhou stranu si umím představit i jiná řešení.

[Miloslav Ponkrác]

Pak nepracujete s datovou strukturou seznam, ale s datovou strukturou pole. OBě struktury mají jiné vlastnosti a jiné náročnosti stejných operací.

Síla seznamů je v rychlé operaci vložení nového prvku a smazání prvku kdekoli uprostřed seznamu. Stejně tak setřízení seznamu je jednodušší.

V čem seznamy excelují je, že můžete nechat putovat prvky mezi více seznamy – což je velmi levná operaci. Můžete mít 5 seznamů, kde čas od času prvek z jednoho seznamu bude přmeístěn do jiného seznamu – a to se na seznamech reaguje velmi levně a bez potřeby alokace.

Z tohoto důvodu každý operační systém mívá procesy a jejich scheduling řízen několika frontami – v podstatě skoro seznamy. Uspání procesu je pouhé převedení prvku z fronty aktivních procesů do jiné fronty čekajících procesů na událost. A probuzení procesu je zase převedení zpět do fronty běžících procesů. Tyhle šaukle se seznamy jsou zadarmo, bez alokací, bleskově rychlé, a proto vhodné i do low level věcí.

Do extrémní dokonalosti a do obrovské intuitivity a obecnosti dovedl práci se seznamy programovací jazyk Simula. Její knihovna simset je extrémně jednoduchá, snadno implementovatelná v jakémkoli jazyce, a je to velmi šikovně udělaná knihovna na práci se seznamy. A je hlavně didaktická, když si simset prohlédnete, ťuknete se do čela a teprve si uvědomíte, jak mocné seznamy jsou a co se s nimi všechno dá dělat.

Sílou seznamu je vyhnutí se kopírování dat při vkládání, mazání a nebo přemísťování do jiného seznamu. V poli data neustále do blba kopírujete, což nevadí u znaků či čísel, ale vadí u dat mající pár kilobajtů na prvek.

Pokud používáte na všechno pole, které realokujete, pak často rozvažujete mezi plýtváním pamětí (realloc() alokuje mnoho paměti navíc, aby se stále nerealokovalo) a rychlostí. Je to řešení, které vás stojí buď plýtvání pamětí, nebo plýtvání časem – jedno z toho si musíte zvolit. Buď plýtváte zdroji počítače nebo výkonem počítače.

Miloslav Ponkrác

[pavlix]

Pak nepracujete s datovou strukturou seznam, ale s datovou strukturou pole.

Ale nepovídejte ;).

[Miloslav Ponkrác]

„Zaprvé, single-linked listy se hodí opravdu jen na velmi omezené množství úloh.“

Nicméně se občas hodí. Různé datové struktury mají různé vlastnosti směrem k operacím. Single linked list je pro situce, kdy potřebujete pouze přidávat či ubírat prvky a hledat prvky ze začátku seznamu je plně dostačující.

Případně tam, kde je větší paměťové omezení a nevadí občasná vyšší náročnost některých dalších operací.

---

„Zadruhé, implementace, kdy je zadrátovaný napevno typ prvku má velmi omezené použití.“

To záleží na účelu.

---

Zatřetí, v normálních prostředích (POSIX) je již podpora listů v C-knihovně standardně k dispozici #include <sys/queue.h>.

Ano, to velmi „standardní“. Ve standardu C jazyka to není. V standardu POSIXu to také není.

Zřejmě nějaký okrajový význam slovo standard, který mi zůstal utajen.

---

A nakonec začtvrté, určitě je velmi užitečné si implementaci zkusit napsat sám, aby člověk pochopil, co je dobré a jaké vlastnosti od různých jiných implementací čekat.

S tím souhlasím.

---

Přidal bych, že pokud se dnes někdo učí C, ať začne rovnou na C++ kompilátoru. C++ obsahuje (až na nepatrné rozdíly) celý jazyk C. Výsledné binárky, které lezou z C++ kompilátorů jsou stejně efektivní a rychlé, jako z C.

Nevidím dnes jediný důvod učit se čistě jazyk C, protože C nemá jedinou výhodu nad C++.

Dokonce můžete vzít C knihu a sázet to do C++ kompilátoru.

Na rozdíl od C můžete vyzkoušet efektivní věci, jako je struktury, šablony a další – zejména na ty seznamy je to nebe a dudy.

Každopádně bych zůstal u strukturovaného programování a neučil se objektové, dokud nepokročím. Na strukturovaném programování se hodně naučíte. A tato strukturovaná fáze je potřeba, chcete-li být virtuózní progrmátor.

[kralyk z abclinuxu]

Tak jsem si zkusil podobné cvičení v jazyce Rust:

use std::iter::Iterator;


enum List<T> 
{
	Node(T, ~List<T>),
	Nil
}

impl<'lf, T: Clone> List<T>
{
	fn new(vector: &[T]) -> List<T>
	{
		let mut list: List<T> = Nil;
		for el in vector.rev_iter()
		{
			list = Node((*el).clone(), ~list);
		}
		list
	}

	fn add(&mut self, item: T)
	{
		match *self
		{
			Node(_, ref mut next) => next.add(item),
			Nil => *self = Node(item, ~Nil)
		}
	}

	fn iter(&'lf self) -> ListIterator<'lf, T>
	{
		ListIterator{ current: self }
	}

	fn each(&self, function: |e: &T|)
	{
		for e in self.iter()
		{
			function(&e);
		}
	}
}

struct ListIterator<'lf, T>
{
	priv current: &'lf List<T>
}

impl<'lf, T: Clone> Iterator<T> for ListIterator<'lf, T>
{
	fn next(&mut self) -> Option<T>
	{
		match *self.current
		{
			Node(ref value, ~ref next) => { (*self).current = next; Some((*value).clone()) }
			Nil => None
		}
	}
}


fn main()
{
	let mut list: List<int> = List::new([1, 2, 3]);
	list.add(4);
	list.add(5);

	list.each(|e| print!("{} ", *e));
	println!("");
}

Bylo to náročnější než jsem čekal a ty borrowed reference a lifetimes mi pořád ještě nejsou úplně jasný. Ale jinak zajímavej pokus...

[Miloslav Ponkrác]

Teď už chybí jenom založit stránku www.seznamy.cz a nabídnout implementaci seznamů ve všech myslitelných jazycích.

[kralyk z abclinuxu]

Linked list @ Rosetta Code

Ale u Rustu mají pouze definici nodu...

[andrej]

a verzia pred obfuskaciou by nebola?

[Miloslav Ponkrác]

Ne, ale autor uvažuje, že názvy funkcí bude mít takovéto: Vytvoření seznamu bude OOOOOOO0(), připojení prvku na konec bude OOOOOO0O(), smazání prvku bude OOOOO00O(), a výpis fronty bude OOOOOO00().

Omlouvá se zatím za nedokonalou obfuskaci.

[noo]

Já bych tam pro jistotu zahrnul nějaký polymorfický algoritmus, který by jména funkcí přepisoval v paměti.

[JS1]

Jinak, co jsem slysel, Linuxove jadro ma docela peknou implementaci spojovych seznamu..