MPU: uogólniony begin i end

Ta notatka została oznaczona jako wymagająca dopracowania: mal-repo-code.
Zawartość wpisu może ulec zmianie, zatem zapraszam do ponownych odwiedzin w niedalekiej przyszłości :)

Według obietnicy z pierwszej notki o MPU chciałbym przedstawić najczęściej używany element, który ułatwia wykorzystywanie standardowych algorytmów operujących na zakresach dla danych przechowywanych w zwykłych tablicach.

Oczywiście nie ma żadnego problemu (pomijając wszelkie biblioteki), bo do tej pory tablice w łatwy sposób mogły być używane jako zakresy w dowolnej funkcji algorytmu z STL-a. Przeważnie robiło się to w prosty sposób, podając wskaźnik na początkowy i ostatni + 1 element tablicy. Tak, jak na poniższym przykładzie wypisującym zawartość tablicy:

int tab[5] = { 1, 2, 3, 4, 5 };

int* tab_begin = tab;
int* tab_end = tab + sizeof(tab)/sizeof(tab[0]);

std::copy(tab_begin, tab_end, std::ostream_iterator<int>(std::cout, " "));

Wszystko fajnie, ale przy statycznych tablicach w oczy rzuca się ten paskudny “trick” z sizeof do pobierania ilości elementów w tablicy, który można bardziej elegancko i cpplusowo zastąpić konstrukcją templejtową, chociażby tą z MPU:

template<typename T, size_t N>
inline size_t Count(const T (&)[N]) {
	return N;
}

O dziwo, o takiej konstrukcji pisałem już dawno w notce Algorytmy STL na tablicach, gdzie również poruszyłem problem i przedstawiłem rozwiązanie jakie tutaj chcę zaprezentować. Czyżby czasem tamta konstrukcja nie wpadła automatycznie do worka MPU? ;)

Wspomniana wyżej notatka zawiera poniekąd całą esencję jaka miała zostać przekazana w niniejszym wpisie.

Jednym z pierwszych elementów MPU był właśnie przedstawiony Counter i funkcje wyznaczające zakres z tablic. Funkcje te wraz z wersjami dla tablic i zwykłych kontenerów pozwalały w prosty sposób traktować tablice jako pełnoprawny zakres, a także bezproblemowo wymieniać w implementacji użycie wektora na tablice i odwrotnie - o ile oczywiście korzystano z tych akcesoriów.

Obecnie standardowa biblioteka języka C++ zawiera takowe konstrukcje: std::begin i std::end. Implementacje zawarte w STL dokładnie odzwierciedlają przedstawione wyżej wersje (tablicowe). Wersje dla standardowych kontenerów wprawdzie także, bo odkąd w języku istnieje operator decltype oraz auto, owe implementacje wyglądają bardzo prosto - są tylko prostym proxy/przekierowaniem na wywołanie odpowiedniej funkcji kontenera:

template<typename C>
inline auto begin(C& c) -> decltype(c.begin()) {
	return c.begin();
}

template<typename C>
inline auto end(C& c) -> decltype(c.end()) {
	return c.end();
}

Mając dostępne takie użyteczne narzędzia, można potraktować tablicę jak dowolnie inny kontener z biblioteki standardowej i ten początkowy kod zapisać w dużo prostszej i standardowej postaci:

int tab[5] = { 1, 2, 3, 4, 5 };

std::copy(std::begin(tab), std::end(tab), std::ostream_iterator<int>(std::cout, " "));

Wersje tych narzędzi dla starego C++ (C++98) są nieco bardziej rozbudowane, niż te obecnie zawarte w STL-u. W MPU zastosowano kilka rozwiązań, a w zasadzie dwa - jedno proste, drugie bardziej skomplikowane.

W pierwszym uznano, że użytkownicy są mądrzy i wiedzą jak używać dane im narzędzia, zatem dostępne są tylko dwie implementacje - jedna dla tablic jak wyżej, druga, będąca przeciążaniem dla innych typów - w zamyśle dla kontenerów:

template<typename C>
inline typename C::iterator begin(C& c) {
	return c.begin();
}

template<typename C>
inline typename C::iterator end(C& c) {
	return c.end();
}

Jak można wywnioskować z implementacji, typ kontenera C musi spełniać pewne założenia z container concept STL-a - posiadać metody begin(), end() oraz współtowarzyszące typy iteratora.

Można nieco zmodyfikować i dostarczy częściowe specjalizacje dla wszystkich typów kontenera z STL-a, ale zaciemniłoby to kod, a tak naprawdę chyba raczej nic nie wzniosłoby do projektu, prócz większej kontroli nad typami wejściowymi.

Wersja dla tablic oraz ta przedstawiona wyżej w zasadzie wystarczą, działają poprawnie dopóki programista jako parametr przekaże poprawny typ kontenera lub tablicę. W innych przypadkach wystąpi błąd kompilacji - idealnie, po co dla błędnego użycia ma się nie wywalać kompilacja? Tak, więc, czego można chcieć więcej?

Drugim, bardziej skomplikowanym (na pierwszy rzut) rozwiązaniem może być skorzystanie z metaprogramowania i boostowego MPL oraz klas cech:

template <typename T>
inline T* begin(T& t, typename boost::enable_if<boost::is_array<T> >::type* dummy = 0) {
	...
}

template <typename T>
inline typename T::iterator begin(T& t, typename boost::enable_if<mpu::std::is_container<T> >::type* dummy = 0) {
	...
}

O podobnych konstrukcjach będę pewnie opowiadał kiedyś indziej, może w jednej z następnych notek poświęconych MPU lub metaprogramowaniu.

Można zastanawiać się po co w ogóle “bawić się” w takie konstrukcje. Głównym powodem jest chęć posiadania możliwości wykorzystania nowych elementów języka oraz algorytmów uogólnionych operujących na zakresach i iteratorach. A niestety nie można założyć, że wszelkie kontenery zdefiniowane przez użytkowników zawsze będą posiadać metody begin i end. Z takiego założenia wyszli twórcy nowego standardu, aktualna wersja definiuje std::begin i std::end.

Wydaje mi się, że jest to bliższe “zacieśnianie więzów” między kontenerami i zakresami dostępnymi w bibliotece STL, a tymi definiowanymi przez użytkownika, czy zwykłymi tablicami lub listami inicjalizującymi. Przecież obecnie pętla for operująca na zakresach nie ma problemów z działaniem na standardowym kontenerze, czy tablicy:

int tab[5] = { 1, 2, 3, 4, 5 };

for (const int i : tab) {
	std::cout << i;
}

To dlaczego podobnie (prosto) nie można byłoby korzystać z gamy dostępnych algorytmów uogólnionych?

Innym nasuwającym się pytaniem, może być “kiedy używać metody, a kiedy funkcji begin/end?” Według mnie, zawsze używać wersji funkcyjnej, bez problemu będziemy w stanie zmienić typ kontenera, nawet na taki który jest zwykłą tablicą, bądź nie spełniającym konceptu STL-a pojemnikiem (wystarczy wtedy przeciążyć bądź wyspecjalizować funkcje begin i end dla danego typu) bez żadnych kłopotów. Promują one jednolitość i spójność oraz pozwalają na bardziej generyczne programowanie, z czym się zgadza Herb Sutter w Elements of Modern C++ Style.

Uwaga! W niniejszej notatce przedstawiono tylko fragmenty kodu konstrukcji przyjmujących parametry jako referencje lub const-referencje, w real-world należy zadbać o obie wersje, aby się dopełniały.