Úvod do algoritmů STL
C++ 11

Ú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