0 bodů

C++ · 30 min

Šablony a standardní knihovna

Funkční šablony, kontejnery vector a map, iterátory a algoritmy z <algorithm>. Past s operátorem [] u map, s std::remove a s odvozením typu v šabloně.

Lidsky řečeno

Šablona je jako formička na sušenky: tvar je jeden, těsto si dodáš sám (a z čeho je, ti formička nehlídá). Napíšeš funkci jednou a překladač z ní podle potřeby vyrobí verzi pro int, pro double i pro std::string. Standardní knihovna (STL) je skříň plná takových hotových formiček: seznamy, slovníky, třídění, hledání. Iterátor je záložka v knize, která ti říká, kde zrovna jsi.

Obtížnost: 4 z 5.

Funkční šablona

cpp
#include <iostream>
#include <string>

template <typename T>
T maxOf(T a, T b) {
    return a > b ? a : b;
}

int main() {
    std::cout << maxOf(3, 8) << " "
              << maxOf(2.5, 1.5) << " "
              << maxOf(std::string("pear"), std::string("apple")) << "\n";
}
text
8 2.5 pear

template <typename T> říká „T je libovolný typ“. Při volání překladač odvodí T z argumentů a vyrobí odpovídající funkci. U řetězců porovnává > abecedně, "pear" je za "apple", takže vyhrává pear.

Úskalí: oba argumenty musí mít stejný typ. Volání maxOf(3, 2.5) se nepřeloží, protože z prvního argumentu vyjde T = int a z druhého T = double. Řešení: maxOf<double>(3, 2.5) (zadáš T ručně), nebo přetypuješ argument. Šablona navíc funguje jen pro typy, které podporují operace použité v těle (zde >). Pro jiné typy dostaneš dlouhou chybu překladače.

Doplň

Co vypíše šablona?

Kontejnery a iterátory

Standardní knihovna nabízí kontejnery (datové struktury) a algoritmy, které s nimi pracují přes iterátory. Iterátor je objekt, který ukazuje na prvek: v.begin() míří na první prvek, v.end() za poslední (nikdy ho nečti).

KontejnerHlavičkaK čemuPoznámka
std::vector<vector>dynamické polevýchozí volba
std::array<array>pole pevné délkyvelikost při překladu
std::list<list>dvojitě vázaný seznamrychlé vkládání doprostřed, pomalý přístup
std::map<map>klíč a hodnota, seřazenoprohledávání O(log n)
std::unordered_map<unordered_map>klíč a hodnota, hashprůměrně O(1), pořadí není zaručené
std::set<set>množina bez duplicitseřazeno

Algoritmy

Algoritmy z <algorithm> a <numeric> pracují s dvojicí iterátorů (od, do).

cpp
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> v{5, 2, 9, 1};
    std::sort(v.begin(), v.end());
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
    auto it = std::find(v.begin(), v.end(), 5);
    std::cout << (it - v.begin()) << " " << std::accumulate(v.begin(), v.end(), 0) << "\n";
}
text
1 2 5 9 
2 17

std::sort seřadí vektor vzestupně: 1 2 5 9. std::find vrátí iterátor na první 5, rozdíl it - v.begin() je její index, 2. std::accumulate (z <numeric>) sečte prvky od počáteční hodnoty 0: 1 + 2 + 5 + 9 = 17. Pokud find prvek nenajde, vrátí v.end(), což musíš zkontrolovat dřív, než iterátor dereferuješ.

Doplň

Co vypíšou algoritmy?

std::map

std::map<K, V> ukládá dvojice klíč a hodnota, seřazené podle klíče.

cpp
#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> m;
    m["a"] = 1;
    m["b"] = 2;
    m["a"] += 10;
    std::cout << m["a"] << " " << m.size() << "\n";
    std::cout << m["zzz"] << " " << m.size() << "\n";
    for (const auto& kv : m) std::cout << kv.first << "=" << kv.second << " ";
    std::cout << "\n";
}
text
11 2
0 3
a=11 b=2 zzz=0 

m["a"] += 10 změní hodnotu na 11. Teď past: operátor [] u std::map pro neexistující klíč "zzz" vytvoří nový záznam s hodnotou 0 a vrátí ho. Proto se velikost zvětšila na 3, i když jsi jen četl. Pro zjištění, zda klíč existuje, použij m.find(key), m.count(key) nebo (C++20) m.contains(key). Při procházení vidíš klíče seřazené: a, b, zzz. Každý prvek je dvojice std::pair s členy first a second.

Doplň

Co vypíše map?

Úskalí: std::remove nic nezmenší

Algoritmus std::remove přeskupí prvky tak, aby ty „zachované“ byly na začátku, ale velikost kontejneru nezmění. Skutečné smazání musíš dodat přes erase (idiom erase-remove).

cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 2, 3};
    auto newEnd = std::remove(v.begin(), v.end(), 2);
    std::cout << v.size() << " ";
    v.erase(newEnd, v.end());
    std::cout << v.size() << "\n";
}
text
4 2

Po std::remove je velikost pořád 4 (jen se zbylé prvky přesunuly dopředu). Po erase je 2 (zůstaly 1 a 3). V C++20 to zkrátíš na std::erase(v, 2);.

Vyber

Vyber správně

Spoj dvojice

Spoj pojem s významem

Ke každému pojmu najdi popis.

Roztřiď

Který kontejner?

Roztřiď úkoly podle nejvhodnějšího kontejneru.

Kvíz

Co vrací v.end()?

Kvíz

Proč se nepřeloží maxOf(3, 2.5) pro template <typename T> T maxOf(T a, T b)?

Kvíz

Co udělá std::map<std::string, int> m; int x = m["a"]; std::cout << m.size();?

Kvíz

Co dělá std::remove s vektorem?

Pod kapotou · Koncepty, rozsahy a složitost

Standard u algoritmů a kontejnerů zaručuje složitost: std::sort je v průměru O(n log n), std::find O(n), std::map operace O(log n), std::unordered_map průměrně O(1). V C++20 přibyly koncepty (concept), které říkají, co šablona od typu požaduje (template <std::totally_ordered T>), a chybové hlášky jsou přehlednější. Také přibyly rozsahy (<ranges>): std::ranges::sort(v); místo dvojice iterátorů a pohledy jako std::views::filter. Podpora v překladačích je dobrá u aktuálních verzí GCC, Clang i MSVC, ověř si na cppreference.com. Šablony se vyhodnocují při překladu a jejich tělo musí být obvykle v hlavičkovém souboru. Kód šablony se vyrábí pro každý použitý typ zvlášť, což může zvětšit výsledný program.

Kartičky

Kartičky: šablony a STL