Najboleśniejszy strzał w stopę

Znanych jest mnóstwo kruczków w języku C++, o których trzeba pamiętać, jeśli chcemy efektywnie w nim programować i nie tracić zbyt dużo czasu na odczytywanie niespecjalnie zrozumiałych komunikatów kompilatora czy – gorzej – drapanie się po głowie podczas debugowania naszego programu. O wielu z nich miałem okazję pisać, ale oczywiście ten temat-rzeka daleki jest od wyczerpania :) W jego nurcie wyróżnia się jednak jeden wybitnie złośliwy przypadek, który przez długi czas uważałem aczkolwiek za ciekawostkę, na którą w praktyce raczej nikt się nie natknie…
Rzecz jasna, myliłem się. Okazuje się, że okaz ten jak najbardziej występuje w rzeczywistym świecie. Nie objawia się wprawdzie zbyt często, ale dzięki temu jest jeszcze bardziej podstępny, posiadając tym większą siłę rażenia, gdy w końcu na kogoś trafi. Dobrze więc wiedzieć, co robić, aby się przed nim bronić :] I tym właśnie chciałbym się dzisiaj zająć.

Pewną pomocą jest tutaj fakt, iż opisywany błąd zdaje się zazwyczaj pojawiać w pewnym konkretnym scenariuszu. Jego wystąpienie w owym kontekście jest przy tym tak zaskakujące, że zetknięcie się z nim skutecznie “uodparnia” na wszelkie inne, podobne okoliczności w których problem może wystąpić. Rzeczony scenariusz jest przy tym bardzo typowy: chodzi o wczytanie zawartości pliku (otwartego jako strumień std::ifstream) do kolekcji albo zmiennej, na przykład łańcucha znaków typu std::string.
Są naturalnie tacy, co bawiliby się tutaj w bufor pomocniczy, pętlę i funkcję getline lub coś w tym guście. Programiści lubiący operować na nieco wyższym poziomie wiedzą jednak, że std::string możemy inicjalizować zakresem znaków określonym – jak każdy zakres w C++ – parą iteratorów. Trochę mniej znanym faktem jest z kolei to, że iterować można również po strumieniach. Mamy na przykład coś takiego jak std::istream_iterator, który potrafi automatycznie dekodować ze strumienia egzemplarze ustalonego typu danych:

Jeśli nam to nie odpowiada i wolimy dostęp do “surowych” bajtów, wtedy z pomocą przychodzi bardziej wewnętrzny std::istreambuf_iterator. To właśnie przy jego pomocy możemy szybko przejść po zawartości strumienia plikowego i umieścić ją w stringu:

Jak pewnie można się domyślić, zakres zdefiniowany przez te iteratory w obu przypadkach zaczyna się na początku strumienia. Kończy się zaś w miejscu, gdzie odczyt następnej porcji danych nie jest już możliwy. W naszym “rozwiązaniu” problemu wczytywania całego pliku będzie to więc koniec tego pliku, czyli to co nam chodzi.

Nieprzypadkowo jednak słowo ‘rozwiązanie’ ująłem w cudzysłów. Powyższe dwie instrukcje zawierają bowiem ów wyjątkowo perfidny błąd, o którym wspominałem na początku. Dość powiedzieć, że jeśli spowoduje on wygenerowanie przez kompilator bardzo tajemniczego komunikatu, będzie to lepszy z jego dwóch możliwych rezultatów. Drugim jest kompilacja zakończona powodzeniem i… kod, który robi dokładnie nic. Nie tylko nic nie wczytuje, ale nawet nie tworzy zmiennej typu string! To raczej zaskakujące, nieprawdaż? ;)

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ć:

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 :)

Co może udawać obiekt w C++

Możliwości przeciążania operatorów w C++ dla własnych typów obiektów sprawiają, że mogą one (tj. te obiekty) zachowywać się w bardzo różny sposób. Mogą na przykład “udawać” pewne wbudowane konstrukcje językowe, nierzadko wykonując ich zadania lepiej i wygodniej. Przykładów na to można podać co najmniej kilka – oto one:

• Obiekt może zachowywać się jak funkcja, czyli udostępniać możliwość “wywołania” siebie z określonymi parametrami. Takie twory często nazywa się funktorami i bywają używane podczas pracy ze standardową biblioteką STL.
  Działają one przy tym w bardzo prosty sposób, zwyczajnie przeciążając operator nawiasów okrągłych (). Jest on na tyle elastyczny, że może przyjmować dowolne parametry i zwracać dowolne rezultaty, co pozwala nawet na stworzenie więcej niż jednego sposobu “wywoływania” danego obiektu. Jednym z bardziej interesujących zastosowań dla tego operatora jest implementacja w C++ brakującego mechanizmu delegatów, czyli wskaźników na metody obiektów.
• Na podobnej zasadzie obiekt może udawać tablicę – wie o tym każdy, kto choć raz używał klas STL typu vector. Wymagane jest tu przeciążenie operatora indeksowania []. Daje ono wtedy dostęp do elementów obiektu-pojemnika, który zresztą nie musi być wcale indeksowany liczbami, jak w przypadku tablic wbudowanych (dowodem jest choćby kontener map). Ograniczeniem jest jedynie to, że indeks może być (naraz) tylko jeden, bo chociaż konstrukcja typu:
  1. v[3,4] = 5;

  jest składniowo najzupełniej poprawna, to działa zupełnie inaczej niż można by było się spodziewać :)

• Obiekty mogą też przypominać wskaźniki, które wtedy określa się mianem ‘sprytnych’ (smart pointers). Dzieje się tak głównie za sprawą przeciążenia operatorów * (w wersji jednoargumentowej) i ->. Normalnie te operatory nie mają zastosowania wobec obiektów, ale można nadać im znaczenie. Wtedy też mamy obiekt, który zachowuje się jak wskaźnik, czego przykładem jest choćby auto_ptr z STL-a czy shared_ptr z Boosta.
• Wreszcie, obiekt może też działać jako flaga boolowska i być używany jako część warunków ifów i pętli. Sprytne wskaźniki zwykle to robią, a innymi wartymi wspomnienia obiektami, które też takie zachowanie wykazują, są strumienie z biblioteki standardowej. Jest to spowodowane przeciążeniem operatora logicznej negacji ! oraz konwersji na bool lub void*.

Reasumując, w C++ dzięki przeciążaniu operatorów możemy nie tylko implementować takie “oczywiste” typy danych jak struktury matematyczne (wektory, macierze, itp.), ale też tworzyć własne, nowe (i lepsze) wersje konstrukcji obecnych w języku. Szkoda tylko, że często jest to wręcz niezbędne, by w sensowny sposób w nim programować ;)

C++ i tablice asocjacyjne

Zwykłe tablice (jednowymiarowe) w “normalnych” językach programowania to po prostu ciągłe obszary pamięci, do których pierwszego elementu posiadamy odwołanie. Dostęp do kolejnych polega na korzystaniu z arytmetyki wskaźników, więc niedziwne jest, że takie tablice indeksuje się wyłącznie liczbami – i to z określonego zakresu.
Ci, którzy programowali w na przykład w Pythonie lub PHP znają jednak koncepcję tablic asocjacyjnych, dla których to ograniczenie nie obowiązuje. W C++ do ich symulowania używa się często map z STL-a:

Jest to oczywiście odpowiednie przeciążenie operatora [], a map jest rodzajem pojemnika. Skoro jednak ma to udawać tablicę, to dobrze by było, żeby narzut na obsługę dostępu do elementów nie różnił się zbytnio od tego z prawdziwych tablic. A ten, jak wiemy, jest stały.

Jak to osiągnąć?… Przede wszystkim powinniśmy – jeśli tylko możemy – nie korzystać z kontenera map. Problem z nim polega na tym, że poświęca on dużo uwagi sortowaniu elementów według ich kluczy (“indeksów”). Gdy klucze te są złożone – bo są nimi np. łańcuchy znaków – może to zająć trochę czasu i jednocześnie nie dawać nam żadnej korzyści. Dla tablicy asocjacyjnej najważniejsze są bowiem operacje wyszukiwania wartości (“indeksowania”) i dodawania nowych elementów, względnie ich usuwania. To one muszą działać szybko; wewnętrzny porządek elementów nie jest dla nas istotny.
Dlatego też lepsza jest mapa korzystająca z dobrodziejstw mechanizmu haszowania. W Visual C++ (podobnie zresztą jak w GCC) takie cudo dostępne jest od dawna jako klasa hash_map. Długo było ono niestandardowym rozszerzeniem biblioteki STL, ale wraz z nową wersją standardu staje się ono jego częścią. Poza tym “od zawsze” istnieje też rozwiązanie z Boosta w postaci klasy unordered_map. Przyjemną cechą wszystkich tych implementacji jest niemal jednolity interfejs, tożsamy ze standardową klasą map.

Oprócz używania właściwego pojemnika powinniśmy też wiedzieć, jak go z niego korzystać – a dokładniej mówiąc, czego unikać. Felerną operacją jest próba dodania elementu poprzez zwykłe indeksowanie z przypisaniem:

Skutkuje to stworzeniem na chwilę obiektu domyślnego dla danego typu wartości, a potem jego zastąpieniem (przypisaniem) tym właściwym, który ma się w ‘tablicy’ znaleźć. W przypadkach, gdy konstruktor i operator przypisania nie są trywialne, będzie to strata na wydajności. Powinniśmy więc używać raczej metody insert do wstawiania. Może jest to niezupełnie “tablicowe”, ale cóż – albo rybka, albo akwarium ;P

Indeksowanie od tyłu

Pewna programistyczna mądrość ludowa uczy, że jedynymi liczbami bezpośrednio występującymi w kodzie powinny być tylko 0 lub 1. Brak lub nadmiar tej drugiej jest przy tym często pojawiającym się błędem, który zyskał swoją własną nazwę pomyłek o jedynkę (off-by-one errors).

Okazji do popełnienia tego rodzaju gaf jest sporo, a objawiają się one przede wszystkim wtedy, gdy mamy do czynienia z tablicami, łańcuchami znaków, kolekcjami, itd. – innymi słowy wszystkim, co da się indeksować. Jako rzecze C++ i większość innych “normalnych” języków, indeksy tablic rozpoczynają się od zera. Startowanie ich od jedynki ma aczkolwiek pewną zaletę: pętle przeglądające zawartość tablic mają wtedy prawie identyczne postaci niezależnie od kierunku przeglądania:

W przypadku indeksowania od zera pętla odliczająca wstecz jest wyraźnie różna:

Pisząc ją, trzeba więc zwrócić baczniejszą uwagę na to, co się robi.

Jednak nawet wtedy można potknąć się o pewien kruczek, gdy pod n podstawimy rzeczywiście używane wartości. Niech to będzie np. wielkość kolekcji STL czy długość łańcucha znaków std::string – a więc coś w stylu x.size(). Otóż takie wyrażenie zwraca liczbę typu równoważnego size_t, który z kolei jest równy ni mniej, ni więcej, jak tylko unsigned int. Jest to więc liczba bez znaku.
W zwykłej wersji pętli (liczonej do przodu) powoduje to ostrzeżenie kompilatora o niezgodności typów ze znakiem i bez znaku (signed/unsigned mismatch) w warunku i < x.size(), gdy i jest typu int. Jednym ze sposobów na pozbycie się tego warninga jest oczywiście zamiana typu licznika na size_t. Jeśli teraz mamy wystarczająco zły dzień, to przez analogię będziemy licznikiem tego typu indeksować również pętlę odwrotną:

I nieszczęście gotowe. Zauważmy bowiem, że odliczanie do tyłu tablicy/kolekcji indeksowanej od zera wymaga, by na koniec licznik przyjął na koniec wartość ujemną; inaczej warunek i >= 0 nigdy nie stanie się fałszywy. To się jednak nigdy nie stanie, gdy i jest liczbą bez znaku; zamiast tego nastąpi przekręcenie na maksymalną wartość dodatnią. Skutkiem będzie pętla nieskończona lub (częściej) access violation.

Co z tego wynika? Ano to, żeby… indeksowania generalnie unikać :) Po to bowiem zarówno STL, jak i każda inna biblioteka pojemników w każdym sensownym języku ma inne sposoby dostępu do elementów – choćby iteratory – aby z nich korzystać. I unikać takich “ciekawych” błędów jak powyższy :)

Badania terenowe nad budowaniem stringów

Cokolwiek kodujemy, konieczność zbudowania dużego łańcucha znaków składającego się z kolejno dołączanych fragmentów pojawia się bardzo często. To może być zapytanie do bazy danych, misternie wyrzeźbiony adres URL, dynamicznie generowany i kompilowany później shader czy w końcu obszerny i szczegółowy komunikat o błędzie.
Wspólną cechą tych tekstów jest to, że budujemy je stopniowo, kawałek po kawałku. Na takie okazje niektóre języki (jak .NET-owe lub Java) posiadają specjalne klasy w rodzaju StringBuilder. Mają one być efektywniejsze niż bezpośrednie używanie typów string, głównie ze względu na nietworzenie wielu łańcuchów i niezaśmiecanie nimi pamięci, co odciąża garbage collector z dodatkowej pracy.

W C++ nie ma oczywiście odśmiecacza, który musiałby po nas sprzątać, i nie ma też narzędzi typu StringBuilder. Czy to oznacza więc, że możemy radośnie korzystać z samej klasy std::string do budowania dowolnie długich tekstów, bo żadnej efektywniejszej alternatywy nie ma?… To właśnie zdecydowałem się sprawdzić, przeprowadzając mały eksperyment z tworzeniem długich łańcuchów znaków kilkoma sposobami, aby potomni nie musieli rozwiązywać tego jakże uciążliwego dylematu ;]
Przechodząc do rzeczy, wpierw wysmażyłem taką oto funkcję która generuje tekst o podanej minimalnej długości:

Wyróżnienie dwóch sposobów polegało natomiast na tym, że w jednym z nich dodatkowo wywoływałem na samym początku metodę reserve w celu uprzedniej rezerwacji pamięci w wektorze na 3 * minLen / 2 elementów.

Testy przeprowadziłem na standardowej implementacji klas string i vector dostępnej w Visual C++ 2005. Wyniki eksperymentu przedstawiają się następująco:

Można w nich przede wszystkim zauważyć, że zarządzanie pamięcią w klasie string jest domyślnie znacząco lepsze niż w vector. Najszybszą metodą konstruowania napisów okazuje się jednak użycie wektora z uprzednią rezerwacją pamięci, która okazuje się o ok. 20% szybsza niż zwykła konkatenacja stringów.

Czy to oznacza, że powinniśmy stworzyć sobie własną klasę StringBuilder, opierającą się na wektorze właśnie, i jej używać? Niekoniecznie. Jak widać, znaczące różnice pojawiają się dopiero przy tworzeniu napisów o wielkościach rzędu megabajta lub więcej. Konia z rzędem temu, kto tworzy tak duże zapytania lub shadery :) Do większości typowych zastosowań bezpośrednie użycie typu string wydaje się więc wystarczające.
No chyba że istnieją bardziej efektywne sposoby na budowanie stringów w C++, których nie udało mi się wymyślić – co jest swoją drogą całkiem prawdopodobne :)

Usuwanie z kontenerów STL

Teoretycznie najlepszym sposobem na usuwanie elementów z pojemników STL jest posłużenie się idiomem erase–remove:

W praktyce bywa on dość kłopotliwy jeśli stosowany predykat (tutaj oznaczony jako funktor ToBeDeleted) musi być napisany specjalnie do tego celu. Zresztą gra często nie jest warta świeczki, bo implementacje algorytmów w rodzaju remove to w środku często nic innego, jak zwykłe pętle.

No a pętle możemy przecież napisać sobie sami, prawda?… Otóż nieprawda – zwłaszcza jeśli wcześniej nie pomyślimy przez chwilę. Łatwo bowiem wyprodukować coś takiego:

Z poprawnością ma to niewiele wspólnego. Jeśli bowiem natrafimy na element do usunięcia, to po dokonaniu tego (w nagłówku pętli) zinkrementujemy iterator, który na ów usunięty element wcześniej pokazywał. W ten sposób możemy pominąć element następny, bo go zwyczajnie “przeskoczymy”. Odpowiednik powyższej pętli używający zwykłego licznika i operatora [] jest zresztą obarczony identycznym problemem.
Jak więc usuwać? Umiejętnie, rzecz jasna :) Skoro po skasowaniu jednego elementu pozostałe przesuną się o jedno miejsce do tyłu, nie powinniśmy zawsze bezmyślnie przechodzić dalej. Trzeba to robić tylko wtedy, gdy dany element zostawiliśmy w spokoju:

To w sumie całkiem oczywiste, jeśli chwilę się nad tym zastanowić. Bowiem – w przeciwieństwie do dodawania – usuwanie elementów z kontenerów wymaga właśnie chwili zastanowienia :]