Jste zde

Méně známé skutečnosti o C++: size() nemusí vrátit unsigned int

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>.

Přidat komentář