Pętla z wyróżnionym startem

Jednym z powodów, dla których nie lubię diagramów blokowych, jest ich prymitywna notacja przedstawiania instrukcji sterujących. Jedyne, czym się tam dysponuje, to if i skok. Jak przy pomocy tylko tego można w klarowny sposób przedstawić jakikolwiek nietrywialny algorytm? To trochę tak, jakby w programowaniu używać tylko pętli nieskończonych i instrukcji break.
Można to robić, oczywiście, ale konsekwencje nie są zbyt ciekawe. Jeśli kryterium opuszczenia pętli jest tak skomplikowane, że trzeba je rozbić na kilka konstrukcji if-break i żadna z nich "nie zasługuje" na wyciągnięcie do warunku w samym while/for, to coś tu brzydko pachnie. Nie chciałbym być w skórze tego, kto będzie musiał później takie dzieło debugować.

W bardziej rozsądnych przypadkach da się uniknąć pętli nieskończonych, nawet jeśli od razu nie widać, jak można by to zrobić. I tak odkryłem na przykład, jak można to ładnie zrobić w sytuacji podobnej do poniższej:

Nazywam to pętlą z wyróżnionym startem, bo typowa jej postać, która nie zawiera (pozornie) nieskończonego kręcenia się w kółko, wygląda tak:

Cała zabawa polega na tym, że pierwsze wywołanie SomeFunction może dać niepoprawną wartość w foo. (Może to być jakieś wyszukiwanie w pojemniku i element odpowiadający kluczowy sth nie został w ogóle znaleziony). Sama treść pętli nie może być wtedy wykonana, bo zdarzy się zapewne jakieś nieszczęście. Dlatego trzeba wyodrębnić to pierwsze wywołanie, i oczywiście zadbać także o kolejne. A to daje, jak widać, dublowanie kodu. Chciałoby się to zrobić lepiej.

I można, na szczęście. Możemy za to podziękować feature'owi C++, który często bywa krytykowany jako ułatwiający popełnianie błędów. Bowiem to dzięki temu, że instrukcja przypisania zwraca wartość przypisywaną, możemy to wszystko zapisać tak:

Zdaję sobie sprawę, że dla wielu fakt ten jest równie oczywisty jak pisanie return a == b; zamiast:

ale dla niektórych taka postać pętli for może być zupełnie zaskakująca. Pamiętajmy, że kiedyś (prawie) każdy pisał też i takie ify jak powyżej ;-)

Split

Tytuł dzisiejszej notki nie ma nic wspólnego z miejscowością wypoczynkową na południu Chorwacji, chociaż pewnie obecne temperatury nasuwają takie skojarzenia :) Zamiast tego chodzi o split łańcucha znaków, czyli bardzo często potrzebną w praktyce operację na stringach.
Danymi dla niej są najczęściej dwa napisy, zaś wynikiem jest tablica podciągów pierwszego z nich, powstała poprzez podzielenie go względem wystąpień drugiego (tzw. separatora). Ponieważ jak zwykle przykład będzie mówił najwięcej, niniejszym podaję nawet kilka:

Zwłaszcza ostatni pokazuje, że split jest rzeczywiście użyteczną funkcją, mogącą ułatwiać parsowanie formatów tekstowych (zwłaszcza, jeśli daje się ją zastosować wielokrotnie). Warto więc mieć takową w swoim języku/bibliotece. Jak więc przedstawia się jej dostępność na różnych platformach?

Tradycyjnie w .NET i Javie jest dobrze, a nawet lepiej. W obu przypadkach funkcja (a właściwie metoda) Split/split klasy String dodaje nawet trochę więcej możliwości niż to opisałem wyżej. I tak w .NET można podać więcej niż jeden oddzielacz, natomiast w Javie domyślnie może być nim również wyrażenie regularne.
Niektóre języki skryptowe i skryptopodobne też mają się w tym względnie całkiem dobrze. W Pythonie jest metoda split w klasie napisu, natomiast PHP ma funkcję explode, która mimo innej nazwy działa bardzo podobnie.

Ale nie wszędzie funkcja typu split jest od razu dostępna; niekiedy trzeba ją sobie samemu napisać. Przykładem języka, gdzie może być to koniecznie, jest Lua oraz - jakżeby inaczej - C++ :) Ze względu na użyteczność splita często znajdowałem się w sytuacji, gdzie konieczne/wygodne było jego napisanie. Po kilku(nastu?) takich przypadkach doszedłem wreszcie do czegoś podobnego do poniższego kodu:

Na koniec zwrócę jeszcze uwagę na to, że czasami trzeba ostrożnie postępować z rezultatem splitu. Zdecydowana większość wersji tej operacji dopuszcza, by w wynikowej tablicy występowały puste ciągi. Odpowiadają one kilku kolejnym wystąpieniom separatora lub jego obecnością na początku bądź końcu ciągu. Jeśli nie są one nam potrzebne (a rzadko są), to należy je zignorować lub usunąć.

Dokładny czas na wielu platformach

Gry i inne podobne aplikacje wymagają precyzyjnego pomiaru czasu, aby realizować obliczenia związane z fizyką, animacją, itp. Jak niemal wszystko, API potrzebne do tego celu jest różne w zależności od platformy, czyli (głównie) systemu operacyjnego. Dzisiaj chciałbym pokazać, jak wygląda to na dwóch najpopularniejszych systemach: Windows i POSIX (a więc między innymi na wszelkiego typu Linuksach).

Interfejs programistyczny systemu spod znaku okienek udostępnia dwie funkcje od dokładnego mierzenia czasu. Są to QueryPerformanceFrequency i QueryPerformanceCounter. Tę pierwszą wywołuje się tylko raz, a jej wynikiem jest częstotliwość wewnętrznego systemowego zegara, który służy do precyzyjnego pomiaru upływającego czasu. Wyrażana jest ona w liczbie "tyknięć" na sekundę i na dzisiejszym sprzęcie może być bardzo duża, bo liczona w (kilku(nastu/dziesięciu)) milionach.
Druga funkcja jest używana nieporównywalnie częściej, gdyż to ona zwraca aktualną wartość zegara, czyli liczbę jego "tyknięć". Stąd wynika, że obliczenie tej wartości w sekundach wymaga podzielenia rezultatu QPC przez uzyskaną wcześniej częstotliwość:

Używana tu unia LARGE_INTERGER to nic innego, jak zwykła liczba 64-bitowa.

W systemach POSIX-owych rzecz jest odrobinę prostsza, jako że tutaj dokładność zegara jest ściśle ustalona. Funkcja gettimeofday (z nagłówka sys/time.h) zwraca rezultat z precyzją mikrosekundową w postaci struktury timeval:

Część odpowiadającą niepełnym sekundom (pole tv_usec) trzeba więc podzielić przez milion.

Chcąc mieć bardziej uniwersalne rozwiązanie, możemy napisać klasę opakowującą zegar z implementacją kontrolowaną docelową platformą, na którą kompilujemy:

Można by na koniec zapytać jeszcze, co tak naprawdę znaczy zwracana wartość zegara. Kiedy wynosi ona zero?... Otóż wbrew pozorom odpowiedź na to pytanie nie jest istotna, bo w praktyce interesuje nas tylko interwał czasowy, tj. różnica między dwoma wskazaniami timera. To na jej podstawie liczymy zmianę w prędkościach obiektów, klatkach animacji czy w końcu niezbędnie konieczną do wyświetlenia wartość FPS :)

Szablony klas i funkcje zaprzyjaźnione

Chcę dzisiaj napisać o pewnego rodzaju "ciekawostce", związanej z dwoma pojęciami z tytułu notki, na którą natknąłem się jakiś czas temu. Po zredukowaniu nadmiaru szczegółów można przyjąć, że rzecz dotyczy sytuacji, w której mamy szablon klasy oraz zadeklarowaną wewnątrz niego funkcję zaprzyjaźnioną - na przykład przeciążony operator strumieniowy <<:

Funkcja jest zadeklarowana, lecz nie jest od razu zaimplementowana wewnątrz bloku class. Zamiast tego umieszczamy jej kod osobno:

co jest może trochę osobliwe, ale wydaje się poprawne. No właśnie; wydaje się. Próba użycia tak zdefiniowana operatora:

nie przeszkadza wprawdzie kompilatorowi, jednak linker ma poważne zastrzeżenia. Okazuje się, że funkcja operator << w wymaganej postaci nie jest zdefiniowana - czyli mamy zwyczajny unresolved external, aczkolwiek o niecodziennych przyczynach.

Przyznać muszę teraz, że nie jestem do końca pewien co do ich natury, jako że konsultacja z zaufanymi źródłami (w postaci książki C++. Szablony panów Vandevoorde'a i Josuttisa) nie dała jednoznacznej odpowiedzi, co tutaj tak naprawdę się dzieje. Przypuszczam, że ma tu miejsce pewien dziwnej interakcji między konkretyzacją szablonu klasy a deklaracją friend, która przy okazji jest też deklaracją funkcji operator <&lt. Mimo że nie stanowi ona części szablonu, owej konkretyzacji podlega, czego skutkiem jest stworzenie zwykłej (nieszablonowej) deklaracji:

Nie ma więc ona nic wspólnego z szablonem funkcji operator <<, który jest zdefiniowany później! W rzeczywistości wygląda zresztą tak, że ów szablon jest całkowicie pominięty przy kompilacji jako niewykorzystywany; to zapewne z powodu reguł przeciążania funkcji w C++, nakazujących najwyraźniej wybranie raczej funkcji nieszablonowej (o powyższej deklaracji) zamiast szablonu funkcji. A że przypadkiem funkcja ta nie ma implementacji... Cóż, kompilator nie ma obowiązku się o to martwić :)

Tyle moja teoria. Niezależnie od tego, czy jest ona prawdziwa czy nie, dobrze byłoby wiedzieć, jak z problemu wybrnąć. Naturalnym wyjściem jest przenieść kod funkcji tam, gdzie jego miejsce - czyli z deklaracji funkcji w klasie (opatrzonej słówkiem friend) uczynić też jej definicję. Faktycznie, to działa; najwyraźniej powstaje wtedy nieszablonowa funkcja o nagłówku danym wyżej, razem ze swoją implementacją - czyli wszystko jest w porządku.
Drugie rozwiązanie to opatrzenie deklaracji friend klauzulą template:

W tej wersji - jak sądzę - następuje zaprzyjaźnienie każdej specjalizacji klasy Foo z odpowiadającą jej specjalizacją metody operator <<. Oba szablony podlegają niezależnym konkretyzacjom, ale linker potrafi prawidłowo rozwiązać relację między nimi.

Uff, trochę to skomplikowane. Jak widać, z zaprzyjaźnianiem bywają problemy - i to nie tylko dlatego, iż "In C++ friends touch each other's private parts." ;) Dziwne efekty związane z szablonami i konkretyzacją potrafią bowiem skonfudować nawet doświadczonych programistów.

Dwukierunkowe funkcje i obiekty proxy

Jedną z pierwszych rzeczy poznawanych w trakcie nauki programowania jest sposób działania funkcji. Mam tu na myśli zupełnie elementarny fakt, iż funkcje przyjmują zero lub więcej argumentów na wejściu i produkują co najwyżej jeden rezultat na wyjściu. Niezachwiana pewność w tę własność funkcji może być potem mocno nadwątlona, jeśli poznamy języki o bardziej egzotycznym sposobie działania, jak na przykład Prolog; tam wszystkie parametry funkcji mogą przekazywać dane w obu kierunkach, dzięki czemu np. za dzielenie i łączenie ciągów lub list odpowiada jedna i ta sam funkcja.
Nie trzeba jednak uciekać tak daleko od starego dobrego programowania imperatywnego, żeby zaobserwować odstępstwa od reguły. Parametry mogą przecież służyć do zwracania wartości - dzieje się to przy pomocy słów kluczowych ref/out w C# lub zwykłych wskaźników/referencji w C++. Często zdarza się wtedy, że "normalny" rezultat zwracany przez funkcję służy jedynie przekazaniu informacji o ewentualnym błędzie.

Rzadsza sytuacja polega na tym, że wynik funkcji staje się jej argumentem wejściowym. Technicznie nie jest nawet możliwe, ale można tak traktować sytuacje, gdy rezultatem jest l-wartość (l-value), tj. obiekt, do którego można przypisywać:

Typowo jest to referencja (tutaj int&), a powyższa konstrukcja - poprzez swojej podobieństwo do indeksowania zwykłej tablicy - nie należy do wielce zaskakujących. Co jednak można powiedzieć o tej:

poza widocznym od razu faktem, że pochodzi ona z języka, którego rozwlekłość składni przyprawia o niestrawność? :) Mianowicie tutaj nie ma już oczywistych przesłanek co do tego, czym jest lewa strona. Widać bowiem, że możemy jej przypisać dłuższy podciąg niż oryginalny i zostanie on mimo wszystko poprawnie zastąpiony - nie jest to więc żaden prosty "wyrób wskaźnikopodobny". Może więc to po prostu feature akurat tego języka, którego nie da się zreplikować?...

Odpowiedź jest - jak można się domyślać, skoro o tym piszę - oczywiście negatywna :) Ażeby podobny efekt osiągnąć w C++, konieczne jest jednak zastosowanie techniki znanej jako obiekt pośredniczący - proxy. Powinien on zachowywać się jak zwykły rezultat funkcji, ale w razie potrzeby dawać również możliwość przypisywania do siebie. Naturalnie efekt takiego działania jest specyficzny dla konkretnej funkcji, która swoją drogą może być często zredukowana do samego tworzenia obiektu proxy:

Minimum, jakie rzeczony obiekt musi zapewniać, to operator przypisania oraz jakiś operator rzutowania, który pozwoli na "wyciągnięcie" rezultatu funkcji, gdy jest ona użyta w zwykły sposób:

Widzimy tutaj, że przy takim proxy nasza funkcja Mid użyta w zwykły sposób zachowuje się jak metoda substr. Gdy jednak umieścimy jej wywołanie po lewej stronie przypisania, zadziała metoda replace, służąca do zastępowania podciągu innym. W sumie więc poniższy kod:

będzie działał analogicznie do prezentowanego wyżej fragmentu w języku Visual Basic.

Opisana tu sztuczka nie jest oczywiście doskonała. Do pełni możliwości potrzebna jest jeszcze wersja read-only funkcji Mid, przyjmująca stałą referencję do stringa i wywołująca substr bezpośrednio, z pominięciem obiektu proxy. To jednak da się łatwo zauważyć.
Mniej widoczny jest natomiast fakt, że obiekt proxy, dodając kolejną warstwę niejawnych konwersji (tutaj: z siebie na string) może spowodować kłopoty tam, gdzie jedna niestandardowa konwersja jest już wykorzystywana. Dobry przykład to interakcja ze strumieniem:

która nie powiedzie, bo operator strumienowy << nie posiada wersji dla lewego prawego argumentu będącego std::stringiem, a jedynie dla const char* (co swoją drogą jest dość dziwne). Rozwiązaniem jest napisanie takowego dla samego obiektu proxy.

Typ std::bitset i flagi logiczne

Napiszę dzisiaj o nierzadko zapominanej klasie z biblioteki standardowej C++, czyli o tytułowym zbiorze bitów - std::bitset. Działania na pojedynczych bitach nie są raczej czymś, co wykonujemy codziennie, ale zdarzają się sytuacje, gdy stanowią one najrozsądniejsze rozwiązanie w danej chwili. Takim typowym przypadkiem jest zbiór flag logicznych: kilku opcji działających jak przełączniki, których możliwą wartością jest tylko true albo false. Wszelkie API doskonale zna takie konstrukcje, czego przykładem może być metoda Clear urządzenia DirectX:

D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER jest właśnie kombinacją flag bitowych, a dwie występujące tu stałe zostały odpowiednio zdefiniowane, by dało się je łączyć operatorem sumy bitowej |.

Używając std::bitset możemy nieco uprościć obsługę takich opcji. Zamiast deklarowania specjalnych wartości, możemy użyć zwykłego enuma, np.:

bitset jest wtedy łatwy w użyciu:

Zachowana jest przy tym "kompatybilność wsteczna" w stosunku do ręcznie definiowanych stałych, jeśli chcielibyśmy z nich korzystać:

lub jeżeli jakieś zewnętrzne API, w którym programujemy, korzysta z wartości bitowych zapisywanych w typach liczbowych:

Na koniec wspomnę tylko, że aby korzystać z klasy bitset do tych lub innych zastosowań, należy wpierw dołączyć standardowy nagłówek o nazwie... bitset :)

if (false) { }

Jeśli widzieliśmy już w swoim wystarczająco dużą ilość kodu w C lub C++, to istnieje pewna szansa, że natrafiliśmy na konstrukcję znaną jaką do-while(false). Występuje ona w dwóch wersjach. W pierwszej jest to właściwie goto w przebraniu - dzięki otoczeniu jakiegoś fragmentu kodu taką "pętlą" sprawiamy, że instrukcja break będzie powodowała skok tuż za nią. To pozwala na "wyjście" z danego fragmentu kodu np. wtedy, gdy wystąpi w nim jakiś błąd - oczywiście przy założeniu, że w środku nie ma kolejnej pętli lub switcha ;)
O drugiej wersji pisałem kilkanaście miesięcy temu. Jej zastosowaniem są makra preprocesora zawierająca kilka instrukcji; zamknięcie ich w do-while(false) zamiast w zwykły blok kodu ({ }) gwarantuje nam brak błędów składniowych niezależnie od miejsca użycia takiego makra.

Widać więc, że pętla z zawsze fałszywym warunkiem ma - mimo wszystko - jakieś zastosowanie... A co z analogicznym ifem? Czy if(false) ma jakieś sensowne zastosowanie poza ukazywaniem, że osoba używająca takiej konstrukcji do wyłączania kodu z kompilacji zapomniała o istnieniu dyrektywy #if, że o komentarzach nie wspomnę?...
Okazuje się, że jednak ma - przynajmniej mi dało się takowe zastosowanie znaleźć. Chcąc je zaprezentować, zacznę od takiego oto ciągu ifów:

który w założeniu może być oczywiście dowolnie długi i niekoniecznie musi też udawać switcha dla stringów. Rzecz w tym, aby każdy if miał podobną formę - na tyle podobną, że aż prosi się o jej zmakrowanie:

To by wyszło gdyby nie feler w postaci pierwszego ifa, który bynajmniej nie zaczyna się wcale od else'a. Można jednak sprawdzić, żeby tak było. Jak?... Ano właśnie dzięki zawsze fałszywemu if(false):

Robi on dokładnie nic, ale jednocześnie sprawia, że następujące dalej, prawdziwe ify mają dokładnie taką samą strukturę. Teraz już możemy je skrócić:

Naturalnie dla trzech wariantów taka zabawa nie ma specjalnego sensu, ale dla dłuższej listy - czemu nie? Sam użyłem tej sztuczki parę razy, m.in. w parserze wyrażeń matematycznych, gdzie ciąg ifów wybierał wywołanie jednej z ponad 20 wbudowanych w niego funkcji. Nie jest to ładne - trzeba to przyznać - ale cóż, takie jest życie: czasami rozwiązania eleganckiego po prostu nie ma...