Dnes se podíváme na to, proč se běžně psaný cyklus tvaru for (unsigned int i = 0; i < container.size(); ++i) může zacyklit.
(De)motivační příklad
Mějme následující kód, který jste už určitě mnohdy viděli či dokonce sami napsali:
std::vector<int> vec; // Práce s vektorem, např. přidání prvků do něj. // ... for (unsigned int i = 0; i < vec.size(); ++i) { std::cout << vec[i] << '\n'; }
Co udělá onen for cyklus? Odpověď zní, že to závisí na použitém systému/překladači a na velikosti vektoru. Někdy může vypsat všechny prvky onoho vektoru a skončit, jindy se však zacyklí. Ajajaj...
V čem je problém?
Když se podíváte na popis metody size(), tak uvidíte, že návratovým typem je size_type. Jedná se o typedef uvnitř vektoru, přístupný přes std::vector<int>::size_type. Ve standardu C++ je uvedeno, že se jedná o unsigned integer type [C++14, 23.2.1]. Nejedná se však nutně o unsigned int. Skutečně, tímto typem může být např. i unsigned long int. Pokud máme systém, kde sizeof(unsigned int) == sizeof(std::vector<int>::size_type), onen cyklus udělá to, co od něj očekáváme.
Zajímavější to je na systémech, kde sizeof(unsigned int) < sizeof(std::vector<int>::size_type). Např. u mě (64b Arch Linux, GCC 4.9) následující kód
std::cout << sizeof(unsigned int) << '\n'; std::cout << sizeof(std::vector<int>::size_type) << '\n';
vypíše
4 8
Pokud tedy bude velikost vektoru větší než std::numeric_limits<unsigned int>::max() (alias UINT_MAX v Céčku), např. jen o jeden prvek, dojde k zacyklení. Proč? Odpověď nám dá průběžný výpis hodnot proměnné i:
i = 0 // vec.size() = 4294967296 (= UINT_MAX + 1) i = 1 // vec.size() = 4294967296 ... // vec.size() = 4294967296 i = 4294967294 // vec.size() = 4294967296 i = 4294967295 // vec.size() = 4294967296 i = 0 // vec.size() = 4294967296 i = 1 // vec.size() = 4294967296 ...
Když je tedy velikost vektoru větší, než maximální číslo reprezentovatelné typem unsigned int, dojde k zacyklení z důvodu přetečení.
Teď si možná říkáte, že vám se to nestane. Kdo by vytvářel tak veliký vektor? V minulém století si při vytváření programů říkali: "Kdo by používal tento SW v roce 2000?". A pro uchování roku používali dva bajty (tedy např. "85" místo "1985"). A hle, ono se tak stalo. Nikdy nevíte, co může v budoucnu nastat. Murphyho zákony říkají, že pokud se něco může stát, tak se to stane. Běžná velikost pamětí u osobních počítačů je dnes často více, než 4 GB, a tak není nepravděpodobné, že s tak velkým vektorem budete muset časem pracovat. Mnohem lepší je psát přenositelný kód, který se bude všude chovat korektně, a to i v budoucnu: vysoce kvalitní kód. To nás přivádí na následující otázku.
Co s tím?
Dodržovat typy. Pokud std::vector<int>::size() vrací výsledek typu std::vector<int>::size_type, měli bychom jej použít:
for (std::vector<int>::size_type i = 0; i < vec.size(); ++i) { std::cout << vec[i] << '\n'; }
Tento kód bude fungovat korektně. Pokud ovšem plánujeme index využít pouze pro přístup k prvkům vektoru, tak je od C++11 k dispozici modernější způsob:
for (auto v : vec) { std::cout << v << '\n'; }
Výhoda je, že tento přístup funguje i s ostatními typy kontejnerů. Samozřejmě, vhodnější pojmenování pro vec i v je namístě. Já jsem zvolil tato pojmenování pro jednoduchost tohoto příspěvku.
Doplňující poznámky
Tento problém se netýká jen vektoru a čísel, ale prakticky všech standardních kontejnerů a použitých typů prvků. Pro jednoduchost jsem to ale vysvětloval na vektoru čísel. Taktéž může nastat problém, pokud si jen uložíte hodnotu z vec.size() do proměnné typu unsigned int (např. unsigned int size = vec.size();). Dále nezávisí na použitém standardu.
Pojďme se ještě mrknout na otázky, které by vás mohly napadnout.
Co když je potřeba onen index na něco jiného?
Pokud byste onen index potřebovali i na něco jiného, než přístup k vektoru, tak by vás mohlo napadnout použít tento přístup:
for (auto i = 0; i < vec.size(); ++i) { // Pozor, nebude fungovat korektně! // ... }
Problém je, že 0 má typ int, čili proměnná i by měla taktéž typ int. To už vůbec nechceme! Korektní je buď typ vypsat explicitně (viz výše) nebo použít decltype:
for (decltype(vec.size()) i = 0; i < vec.size(); ++i) { // ... }
Nevýhodou je, že je v tomto případě nutné duplikovat vec.size().
Co když kontejner obsahuje rozsáhlé prvky?
Pokud iterujete přes kontejner, jež obsahuje prvky, jejichž kopírování je časově náročné, doporučuji je v cyklu odchytávat přes referenci na konstantu:
for (const auto &item : container) { // ... }
Nebude tak docházet ke kopírování prvků, což by nastalo, pokud bychom napsali jen auto item.
Co když ty prvky chci měnit?
Pokud plánujete prvky měnit s tím, že chcete, aby se změna promítla do iterovaného kontejneru, lze použít klasickou referenci:
for (auto &item : container) { // Modifikace item se promítne do kontejneru. }
Pokud je však takovýto cyklus součástí šablony, tak doporučuji použít raději univerzální referenci:
for (auto &&item : container) { // Modifikace item se promítne do kontejneru. }
Důvodem je, že přístup s auto & nebude fungovat nad std::vector<bool>.