Diskuze: kontejnery

petr.dar

Člen

petr.dar:16.10.2016 4:34

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.10.2016 4:34

Michal Martinek

Tvůrce

Michal Martinek:16.10.2016 10:14

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.10.2016 10:14

Martin Dráb

Tvůrce

Martin Dráb:16.10.2016 13:27

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

16.10.2016 13:27

2 + 2 = 5 for extremely large values of 2

petr.dar

Člen

petr.dar:17.10.2016 22:35

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.10.2016 22:35

Martin Dráb

Tvůrce

Martin Dráb:17.10.2016 22:48

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

17.10.2016 22:48

2 + 2 = 5 for extremely large values of 2

petr.dar

Člen

petr.dar:23.12.2016 18:34

Ještě by mě zajímalo jestli mohu použít asociativní kontejnery ke třídění a různé funkce obsažené v #include <algorithm>. Lze na to napsat binární funktor?

Nahoru Odpovědět

23.12.2016 18:34

Martin Dráb

Tvůrce

Martin Dráb:23.12.2016 18:56

Ano, obsah kontejnerů třídit lze, pokud to má smysl (vector, deque, list asi taky). U set a map je již obsah setříděn vzestupně podle klíče (v tomto pořadí se přes ně iteruje, ať už jakýmkoliv směrem).

Nahoru Odpovědět

23.12.2016 18:56

2 + 2 = 5 for extremely large values of 2

petr.dar

Člen

petr.dar:23.12.2016 20:58

To znamená že u map musim mít v binárním funktoru jako parametry první typ šablony? Pořád mi to nejde.

Nahoru Odpovědět

23.12.2016 20:58

Martin Dráb

Tvůrce

Martin Dráb:23.12.2016 22:31

To znamená že u map musim mít v binárním funktoru jako parametry první typ šablony? Pořád mi to nejde.

Myslím, že nerozumím, na co se ptáš. Zjednodušeně řečeno, mapa je úložiště dvojic K, V, kde první složka slouží jako klíč. Interní implementace mapy je taková, že řadí dle klíče (což znamená, že typ klíče musí mít definovaný operátor <, aby implementace mapy dokázala porovnat, který ze dvou klíčů je větší/menší). Interně je mapa myslím implementovaná jako červeno-černý strom (norma neurčuje, jak přesně má být implementována, jen dává horní odhady na časovou složitost operací).

Vzhledem k tomu, že se vlastně jedná o binární vyhledávací strom (ČC je jen trochu rozšířená varianta), setřídění položek dle hodnoty klíče dostaneš automaticky a nemůžeš jej změnit, protože je na něm fungování mapy (a také setu a jejich multi variant) založené.

(jistě, mohl by sis určitě napsat nějaký vlastní iterátor, který by mapu procházel v jiném pořadí, ale myslím, že tyhle psí kusy dělat nechceš).

Nahoru Odpovědět

23.12.2016 22:31

2 + 2 = 5 for extremely large values of 2

petr.dar

Člen

petr.dar:23.12.2016 23:13

Jasně, myslim že to trochu chápu :-D ale co když potřebuju třídit klíč, kde žádný takový operátor nemám? Třeba vstupní proměnná pro klíč bude moje struktura nebo cokoliv jinýho?

Zkrátka:

potřebuju vědět jak zapsat binární funktor, když mám např.

map <struct₁,struct₂> my_map;

a chtěl bych použít např:

template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

a poslední parametr je Compare comp, kde si musim vytvořit svůj vlastní binární funktor. Ale jaký tam mám zadat parametry? Vyskoušel jsem všchny možnosti, Key, Value, i std::pair<Key, Value> a nic mi nefunguje.

Je to vůbec vhodný postup to takto třídit, nebo mám hledat jiné možnosti?

Nahoru Odpovědět

23.12.2016 23:13

Martin Dráb

Tvůrce

Martin Dráb:23.12.2016 23:34

To se pořád tu mapu pokoušíš třídit, což právě pochybuju, že rozumně půjde vhledem k tomu, že pořadí prvků v mapě je pevné, pokud mají pevný klíč.

Pokud chceš použít tvoji strukturu jako klíč, zkus pro ni definovat operátor "menší než" nějak takhle:

bool operator <(struct_1 S1, struct_1 S2)

Nevím, zda to bude stačit; možná ještě budeš muset dodefinovat rovnost (==). Už je to dlouho, co jsem tohle dělal (a tehdy to bylo spíš znásilnění mého iterátoru tak, aby šel použít pro třídění, i když to nebyl pravý random access iterátor).

Pokud operátor nedefinuješ a použiješ svoji strukturu jako klíč, buď se bude porovnávat lexikograficky (po složkách), nebo dostaneš chybovou hlášku, ze které by mohlo jít poznat, co přesně potřebuješ definovat za operátor(y) (ale ty hlášky jsou někdy dost kryptické).

Editováno 23.12.2016 23:35

Nahoru Odpovědět

23.12.2016 23:34

2 + 2 = 5 for extremely large values of 2