Avatar
petr.dar
Člen
Avatar
petr.dar:

Ahoj, zajímaly by mě 2 menší drobnosti :-)

  • jaký je rozdíl mezi kontejnerem list a vector (jen velmi zkráceně... , zatim tušim že list je rychlejší.)
  • jaký je rozdíl mezi např: list<T> a list<void>, zajímá mě ten typ šablony, u T vim, že se tam ukládají všechny možný proměnný, struktury, třídy..., ale moc nechápu to void, to je ukazatel na funkci? Jak by se s tim pracovalo?
 
Odpovědět 16. října 4:34
Avatar
Michal Martinek
Redaktor
Avatar
Michal Martinek:

Ahoj,
list je spojový seznam, zatímco vector je dynamicky velké pole. Z toho plyne i pro co je který kontejner rychlejší. List je obecné lepší na vkládání, mazání a přesouvání, když už máš ukazatel, či iterátor na to místo, kde to chceš provést. Ale třeba na řazení, hledání je to horší, protože celý list musíš sekvenčně procházet, jelikož máš prvky různě po paměti. Vektor je má všechny u sebe, jako klasické pole, takže k nim můžeš okamžitě přistupovat, což znamená, že na řazení, hledání můžeš použít lepší algoritmy, ale zase při vkládání a mazání, zvláště na místa jiná než konec vectoru, má vector větší režii, jelikož přesouvá více prvků a občas se musí realokovat, když už mu dojde místo a přesune všechny prvky. Takže se nedá říct, co je rychlejší, záleží, co s tím budeš dělat :-)
A vážně jsi někde viděl list<void>, nebylo to list<void *>, což by byl list generických pointrů.

 
Nahoru Odpovědět 16. října 10:14
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na petr.dar
Martin Dráb:

Výhody listu oproti vectoru jsou cca následující:

  • při vkládání či mazání se nezneplatňují iterátory
  • umí vkládat i na začátek, popř. kamkoliv, když máš na to místo iterátor.

Ale jak již bylo řečeno, list je implementován spojovým seznamem. Z hlediska asymptotické složitosti to samozřejmě znamená mnohé operace v O(1), ale ty konstanty tam jsou vyšší než u vektoru. Jednotlivé prvky uložené v listu navíc nejsou u sebe – nacházejí se na náhodných adresách, což není zrovna efektivní uložení vzhledem k vyrovnávacím pamětem.

Takže se nedá říci, že by byl list rychlejší, leda tak na papíře. Pokud nepotřebuješ operace, které umí navíc oproti vektoru, tak použij vektor.

Nahoru Odpovědět  +2 16. října 13:27
2 + 2 = 5 for extremely large values of 2
Avatar
petr.dar
Člen
Avatar
Odpovídá na Michal Martinek
petr.dar:

No, tak list<void> nejde, původně jsem si chtěl pokecat o něčem známějším, ale šablonu <void> jsem opravdu viděl u Qt:
funkce map z namespace QtConcurrent vrací QFuture<void> a právě jsem se chtěl zeptat, co to znamená. U <void> taky nemohu zjistit počet položek, které tam mám uložených.

 
Nahoru Odpovědět 17. října 22:35
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na petr.dar
Martin Dráb:

Sice neznám návrh a definici future v Qt, ale pokud u nějaké operace nepotřebuji znát výsledek, ale jen se dočkat jejího dokončení, tak opravdu stačí future, co vrací void, tedy nic.

Záleží, jak ty šablonované třídy a funkce ty šablonované parametry používají. Podle toho bude void mít smysl či nikoliv.

Nahoru Odpovědět  +1 17. října 22:48
2 + 2 = 5 for extremely large values of 2
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.