Zajímavé úlohy pro programátory v C a C++ #1

Dnešním dnem zahajuji seriál, ve kterém mohou čtenáři řešit zajímavé úlohy z oblasti programovacích jazyků C a C++. Na čtenáři bude najít správné řešení zadané úlohy a podělit se s ním s ostatními do komentáře. Úlohy nebudou nikterak dlouhé ani časově pracné - půjde především o znalost těchto jazyků (a jejich možností), programovacích technik a jazykových idiomů. Pokud se žádnému z čtenářů nepodaří najít správné řešení, tak po určité době zveřejním své (komentované) řešení a rád zodpovím případné dotazy (to se týká i nejasnostech v zadání). Nuže, pojďme se podívat na první úlohu :).

Zadání

Je dán následující zdrojový kód v jazyce C++:

#include <iostream>
 
// Zde doplňte kód
 
int main() {
    int p1[] = {1, 2, 3, 4, 5, 6, 7, 8};
    std::cout << sum(p1) << std::endl; // 36
 
    int p2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << sum(p2) << std::endl; // 45
}

Doplňte do programu definici funkce (lze definovat i jako šablonu funkce, ovšem ne jako makro) sum(), která sečte všechny prvky v předaném (jednorozměrném) poli (délka pole je vždy větší než 0) a vrátí tuto sumu jako výsledek (int).

Omezení

Uvažujte standard C++98. Program musí být přeložitelný podle tohoto standardu a nesmí se spoléhat na nespecifikované či nedefinované chování užitých konstrukcí. Funkce musí být reentrantní (vrátí korektní výsledek, i když je zavolána několikrát "ve stejnou chvíli", např. z několik vláken současně, tj nelze využívat statické proměnné atd.). Mimo vyznačenou část v programu nic neměňte.

Řešení

Zkusíme na to jít postupně. Prvním problémem je, jak do funkce sum() předat velikost předaného pole. Pokud totiž funkci deklarujeme jako

int sum(const int *a);

nebo (ekvivalentně, protože const int a[] se chová úplně stejně jako const int *a, čili a bude pořád ukazatel na konstantní int)

int sum(const int a[]);

tak ztratíme informaci o jeho délce a neexistuje (přenositelný) způsob, jak ji zjistit (pokud za posledním prvkem pole nebude nějaká zarážka, což v našem případě není).

Jednoduché pokusy jako

int sum(const int a[size_t size]);

skončí nezdarem, protože toto není v C++ syntakticky možné.

Tady nastává okamžik pro první "trik", který využívá netypové paramtery šablon. V C++ totiž lze definovat šablonu, jejíž parametr bude hodnota (předat se ale takto (při instanciaci šablony) může pouze konstanta vyčíslitelná v době překladu) a C++ navíc v určitých případech samo dokáže tuto hodnotu vydedukovat při instanciaci šablony (tedy bez explicitního uvedení). S touto znalostí lze zkusit sum() nadelarovat takto:

template <size_t size>
int sum(const int (*a)[size]);

Tato šablona funkce má jako parametr ukazatel na pole o size prvcích a pokud ji zavoláme takto

int p1[] = {1, 2, 3, 4, 5, 6, 7, 8};
sum(&p1);

tak překladač automaticky vydedukuje hodnotu šablonového parametru size jako velikost předávaného pole a to je přesně to, čeho jsme chtěli dosáhnout. Ovšem nyní vyvstal jiný problém, a to, že v zadání se funkce sum() volá bez ampersandu, čili sum(p1);, takže překlad selže...

To je vhodný okamžik na "trik" číslo dvě - každý určitě ví, že pokud se chceme vyhnout předávání prvku explicitně přes ukazatel (tj adresu), tak můžeme argument předávat referencí, čili proč nevyzkoušet referenci na pole :).

template <size_t size>
int sum(const int (&a)[size]);

Samotná definice funkce už je triviální.

Ukázkové řešení je tedy následující:

template <size_t size>
int sum(const int (&a)[size]) {
    int s = 0;
    for (size_t i = 0; i < size; ++i)
        s += a[i];
    return s;
}

Mimochodem, pokud by někoho napadlo deklarovat funkci sum() pouze takto

int sum(const int (&a)[]);

s tím, že si velikost pole zjistí v těle funkce přes operátor sizeof, tak zjistí, že C++ neumožňuje předat referencí pole o neznámé délce.