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
#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";
}8 2.5 peartemplate <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.
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).
| Kontejner | Hlavička | K čemu | Poznámka |
|---|---|---|---|
std::vector | <vector> | dynamické pole | výchozí volba |
std::array | <array> | pole pevné délky | velikost při překladu |
std::list | <list> | dvojitě vázaný seznam | rychlé vkládání doprostřed, pomalý přístup |
std::map | <map> | klíč a hodnota, seřazeno | prohledávání O(log n) |
std::unordered_map | <unordered_map> | klíč a hodnota, hash | průměrně O(1), pořadí není zaručené |
std::set | <set> | množina bez duplicit | seřazeno |
Algoritmy
Algoritmy z <algorithm> a <numeric> pracují s dvojicí iterátorů (od, do).
#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";
}1 2 5 9
2 17std::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š.
Co vypíšou algoritmy?
std::map
std::map<K, V> ukládá dvojice klíč a hodnota, seřazené podle klíče.
#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";
}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.
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).
#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";
}4 2Po 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 správně
Spoj pojem s významem
Ke každému pojmu najdi popis.
Který kontejner?
Roztřiď úkoly podle nejvhodnějšího kontejneru.
Co vrací v.end()?
end() ukazuje za konec rozsahu. Nesmí se dereferencovat, slouží jen k porovnání.
Proč se nepřeloží maxOf(3, 2.5) pro template <typename T> T maxOf(T a, T b)?
Oba parametry mají tentýž typ T, takže argumenty musí mít stejný typ. Pomůže maxOf<double>(3, 2.5).
Co udělá std::map<std::string, int> m; int x = m["a"]; std::cout << m.size();?
Operátor [] vloží chybějící klíč s hodnotou 0, takže velikost je 1.
Co dělá std::remove s vektorem?
K opravdovému smazání se používá idiom v.erase(std::remove(...), v.end()), v C++20 std::erase.
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.