Úvod do algoritmů STL
C++ 11

image_printTisk

Úvod

  1. Co jsou algoritmy STL – operace nad datovými strukturami STL
  2. Jak fungují?
    1. Vazba přes iterátory
    2. Není přímý přístup do datové struktury kvůli abstrakci od její vnitřní reprezentace
  3. Typu argumentů
    1. definovaný rozsah práce algoritmu nad datovou strukturou formou iterátorů
      1. speciální případ pro všechny prvky, begin() a end()
    2. argumenty konkrétní pro daný algoritmus jako hledaná hodnota, predikát či operace k provedení nad prvkem
  4. Jsou všechny realizovány jako šablony funkcí
    1. Výhoda je nezávislost na datovém typu, mohou být požadavky na operace u uživatelsky definovaných typů. Třídění, operátor< například.
    2. Výhoda, nezávislost na typu datové struktury. Jsou výjimky, pro poskytování příslušného druhu iterátoru. Konkretizace.
    3. Svobodná volba rozsahu práce nad datovou strukturou. Ukončující iterátor musí odkazovat o jeden prvek dál, než je poslední, se kterým se má pracovat.
      1. Speciální případ celé datové struktury, begin() a end()
    1. U mnoha algoritmů i svobodná volba operace nad jednotlivým elementem nebo volba predikátu, dotazovací operace nad prvkem. Zpravidla řešeno lambdou.
      1. Existence unárních a binární predikátů
    2. algoritmy provádějící zápis přijímají iterátor pro zápis, berou jen begin(), je na odpovědnost programátor, že je v cílové datové struktuře dost prostoru pro zápis daného počtu elementů – DÁT DO STL ALGORITMŮ, JINAK POUŽÍT INSERT ITERÁTOR
    3. Lze pracovat se I/O proudy za pomocí iterátorů proudů, či obecně s čímkoliv, co poskytuje navenek iterátory
    4. DOVOLUJÍ APLIKACI ALGORITMŮ NA DATOVOU STRUKTURU V OPAČNÉM POŘADÍ – ZPĚTNÉ ITERÁTORY
    5. SPECIÁLNÍ INSERT OPERÁTORY PRO VKLÁDÁNÍ PRVKŮ, JINAK U SEKVENČNÍCH MODIFIKUJÍCÍCH ALGORITMŮ SE PROVÁDÍ PŘEPIS AKTUÁLNÍ HODNOTY
  5. Druhy:
    1.  Sekvenční
      1. modifikující
      2. nemodifikující
    2. partitioning
    3. třídící
    4. binární hledání
    5. merge
    6. heap
    7. min a max
    8. ostatní
  6. Odkaz na oba referenční zdroje

 

image_printTisk
Úvod do algoritmů STL
C++ 11
Ohodnoťte tento článek

Související články

  • Ukazatele na pole V tomto článku si probereme ukazatele na pole. Seznámíme se nejen s ukazateli na pole jednorozměrné, ale i na složitější případ, tedy pole vícerozměrná. Vše si zase samozřejmě uvedeme na […]
  • Sekvenční algoritmy “all_of”, “any_of” a “none_of” V tomto článku si popíšeme sekvenční algoritmy all_of, any_of a none_of. Jejich princip spočívá v tom, že se jim v argumentu předá testovací operace, reprezentovaná nejčastěji lambda […]
  • Seznamy hodnot podrobněji V tomto článku se blíže seznámíme se seznamy hodnot. Máme na výběr dva typy seznamů. Seznam s pevným počtem položek nebo seznam s proměnlivým počtem položek. Seznam s pevným počtem […]
  • Úvod do iterátorů Dva hlavní pilíře STL knihovny jsou její datové struktury a obecné algoritmy pro práci s nimi. Vzhledem k různosti datových struktur a obecnosti algoritmů potřebujeme nějaký spojovací […]
  • Proměnné V minulém článku jsme si řekli, že data programu jsou uchována v různých souvislých úsecích paměti. Abychom mohli v programu používat hodnotu uloženou v nějakém takovém úseku paměti, […]
  • Varianty sekvenčního algoritmu “find” Tento článek pojednává o sekvenčních vyhledávacích algoritmech knihovny STL. Ukážeme si algoritmus pro hledání na základě hodnoty nebo za pomocí predikátu. Další možností je také hledání […]