C++ bez cholesterolu

Beast

Wstęp

To jest z mojej strony drobny żart. Z jednej strony. Z drugiej jednak mam nadzieję, że biblioteka beast będzie dla kogokolwiek użyteczna. I może się nawet będzie rozwijać.

Biblioteka beast powstała początkowo jako zestaw najróżniejszych użytków ogólnego przeznaczenia, które przyszły mi do głowy podczas pracy nad różnymi projektami. Nazwa `beast' też oczywiście nie powstała od razu i takoż nadal nie jestem do tej nazwy przekonany. Ale brzmi zawsze lepiej od różnych dziwacznych skrótów, a powstała – jak się niektórzy domyślają – po części w związku z nazwą `boost'.

Zbiorniki właścicielskie

Zbiorniki właścicielskie to jest właściwie tylko jeden zbiornik na razie (bo planuje się więcej, o ile będzie to miało sens, którego aktualnie tylko poszukuję :). Najpierw może zatem opiszę historię jego powstania. Co ciekawsze (i śmieszniejsze), do jej powstania przyczynił się po części... język C.

Zbiorniki z założenia mają nie tylko trzymać owe elementy; powinny nimi również dysponować. A tu problemem jest zawsze to, co i zawsze było (i co rozwiązuje się w innych językach odśmiecaczami), mianowicie brak jednoznacznie ustalonego właścicielstwa do obiektów. W tym wypadku w szczególności, do obiektów trzymanych w zbiorniku. Problem zresztą nie jest taki prosty. Można to rozwiązać na kilka sposobów. Jednym z prezentowanych jest std::auto_ptr, ale niestety w aktualnej implementacji jego operator przypisania dokonuje zmian w swoim prawostronnym argumencie (więc tak naprawdę nie da się z nim nic zrobić w STL-u). Można też użyć boost::shared_ptr. Jednak nadal nie jest to najlepsze możliwe wyjście, bo shared_ptr zakłada arbitralne podejście do kwestii właścicielstwa (zakłada, że może być jednocześnie kilku właścicieli do obiektu).

Prezentowany tu zbiornik, beast::olist, powstał właśnie w wyniku próby naśladowania zachowania się zwykłych, ręcznie klejonych "list" robionych w języku C, gdzie ma się jedną strukturę, wewnątrz pola next i prev, które są wskaźnikami do tego samego typu. Oczywiście, naturalnym podejściem w przypadku C++ było zrobienie tego jako klasy bazowej, a pola next i prev są wskaźnikami na ten sam typ, tyle że typ jest wyprowadzony z... no właśnie. Tu się zrodził mały problem: zdefiniować węzeł tak, żeby klasa listy zawierała tylko węzeł główny, ale typ elementu był jednocześnie pochodną węzła (bo to jedyny sposób, żeby mu "wdusić" te pola "next" i "prev"). Okazało się to nie takie trudne...

Prezentowany zbiornik (i pewnie będzie to spełniać każdy inny zbiornik właścicielski, jeśli powstanie jeszcze jakiś) jest zbiornikiem intruzyjnym. To oznacza, że jego elementy nie mogą być dowolnego typu. Mogą być tylko i wyłącznie tego typu, który wyprowadzono z typu węzła (dostępnego wewnatrz listy). Typ ten zatem należy zdefiniować w następujący sposób:

class Typ;
class Typ: public beast::olist<Typ>::node_t
{...};

Na tym właśnie polega cały myk. Co w zamian za takie utrudnienie zyskujemy? Otóż przede wszystkim to, że węzeł jest elementem podległym, a nie nadrzędnym dla typu elementu. W związku z tym, lista trzyma tylko węzły, ale operuje nimi jak obiektami. Trochę to pachnie programowaniem obiektowym, ale akurat lista nie jest robiona obiektowo. Jeśli ktoś się przyjrzy, zobaczy że następuje tam w odpowiednich miejscach pozyskiwanie referencji lub wskaźnika do elementu poprzez... statyczne rzutowanie z typu węzła na typ elementu. W ogólności static_cast jest niebezpieczne, ale tutaj przecież doskonale wiemy, jaki jest typ podległych elementów (oczywiście nie zakładam, że ktoś próbuje eksperymentować z utworzeniem listy "gołych" węzłów, żeby mi udowodnić, że w tym wypadku nie będzie działać poprawnie :).

W każdym razie, dzięki takiemu rozkładowi można dowolnie wrzucać i wyciągać elementy z listy bez martwienia się o kwestie poprawności węzła. Można zatem wykonać nawet operację uzyskania węzła mając jedynie referencję do obiektu, co jest nie do uzyskania w przypadku zbiorników nieintruzyjnych. Wielu "purystów" językowych na pewno uzna to za "dyskwalifikację". Jednak ja jestem praktykiem i zrobiłem taki typ, bo był mi po prostu potrzebny, a to, czy ktoś uważa go za poprawny względem jakiejś teorii programistycznej, niech tak sobie uważa dalej, mnie to nie zraża.

Dwie rzeczy są nie do końca zgodne z STL. Po pierwsze, olist ma tylko jeden parametr - typ wartości. Żadnych alokatorów. Przyczyna jest prosta, mianowicie do niczego tam alokator nie jest potrzebny. Po drugie, nie wymaga się od wartości, żeby spełniała koncept przypisywalny i domyślnie-konstruowalny. Co do alokacji, to wszelkie automatyczne alokacje są wykonywane operatorem new (zatem sposób alokacji zależy od definicji operatora new typu elementów).

Zbiornik olist posiada metody pozwalające zakwalifikować do zbiorników dwukierunkowych oraz ciągów. Nie jest niestety ciągiem żadnego wstawiania, za to jest ciągiem magazynowania. To oznacza, że zamiast metod insert, push_front i push_back posiada odpowiednio store, store_front i store_back. Inna nazwa jest uwarunkowana zupełnie innym protokołem. Metoda store() powoduje wstawienie, owszem, ale już istniejącego obiektu, podanego przez wskaźnik (odmiennie niż insert, która powoduje skopiowanie obiektu!). Inaczej mówiąc, w przypadku olist należy najpierw element utworzyć, a następnie "wkleić" do listy za pomocą jednej z metod magazynowania. O-lista posiada takoż metody charakterystyczne dla ciągów wstawiania, erase, pop_front i pop_back. Działają one tak samo, jak w std::list, czyli usuwają definitywnie element. Z tym tylko, że tutaj wygląda to nieco inaczej: usunięcie elementu oznacza naprawdę jego usunięcie, czyli użycie operatora delete. Dodatkowo jednak istnieje metoda symetryczna do "store" - pull. Powoduje ona wyciągnięcie elementu z listy. Z tym tylko, że jest to tak naprawdę metoda węzła, a nie listy (jest to zatem metoda statyczna samej listy); Sam węzeł zawiera już wystarczającą ilość informacji, żeby można było go "wywiązać" z listy. Właściwie to nawet owo "pull" powinno wystarczyć za wszelkie usuwania elementów, a metody erase, pop_front i pop_back są trochę nadmiarowe.

Poza tym dostępne są pozostałe metody charakterystyczne dla std::list: splice, remove, remove_if, unique, merge, reverse i sort. No i oczywiście standardowe jak na zbiornik: begin, end, rbegin, rend, front, back, empty, size i clear. Dodatkowo istnieją metody beginP() i endP(), które pozwalają poruszać się po zbiorniku tak, żeby wyłuskanie iteratora zwróciło wskaźnik (a nie, jak normalnie, referencję). Rozważałem, czy nie sensowniej byłoby utworzyć adaptor, ale okazało się, że nie jest to potrzebne, bo można wykorzystać inny zbiornik, który zaprezentuję za chwilę.

Pliki nagłówkowe: beast/olist.hh

Iteratory magazynowania

Co prawda store to nie to samo, co insert, ale jak nie mamy insert, to nie można użyć inserter, back_inserter itd. Dlatego w tym celu powstał dość podobny zestaw iteratorów, front_store_iterator, back_store_iterator i store_iterator. I takoż podobnie istnieją funkcje pomocnicze, front_storer, back_storer i storer.

Do czego je można wykorzystać? Np. chcemy sobie utworzyć kilka obiektów za pomocą kolejnych wywołań odpowiedniego generatora, który będzie zwracał referencję do naszego typu:

struct CreateObject {
  Object& operator()() { return *new Object; }
};
generate_n( back_storer( ls ), 10, CreateObject() );

Podobnie można zorganizować tworzenie obiektów podczas wczytywania ich ze strumienia.

Pliki nagłówkowe: beast/iterator.hh

Interwały

Pojęcie "interwał" pochodzi ze Smalltalka. Nie jestem oczywiście fanem Smalltalka; zapożyczyłem to określenie z uwagi na rzeczy, do jakich służy. Jest to w ogólności rodzaj "wirtualnego zbiornika", właściwie samego czystego zakresu. Jest jednak dostosowany do konceptu zbiornika, tylko że z kilkoma zastrzeżeniami. Po pierwsze, jest to zbiornik stały. Nie można używając go wykonywać operacji, która modyfikuje zbiornik. Po drugie, szczegółowy koncept tego zbiornika zależy od konceptu podległego mu iteratora (spełnia zatem co najmniej koncept zbiornika postępowego).

Interwał jest to odpowiednio uatrakcyjniona para iteratorów (tak nawet to jest on dokładnie wyprowadzony z pary dwóch iteratorów). Podlega zatem wszystkim prawom takim samym, jak każdy iterator (i to jest właśnie jeden z powodów, dla których jako zbiornik jest zbiornikiem stałym). Jako zbiornik (zaznaczam, że nie jest ciągiem) posiada metody: begin, end, size, empty i max_size. Dodatkowo są dostępne następujące metody:

• minsize(rozmiar); zwraca true, jeśli size() jest <= rozmiar (przydaje się dla zbiorników, dla których size() jest liniowego czasu)
• set_begin(i), set_end(i); ustawia jeden z iteratorów na `i'
• shift_begin(s), shift_end(s), shift(s) - przesuwa jeden z iteratorów lub oba o podaną wartość (również ujemną)
• shift_begin(), shift_end() - "skurczają" zakres; początkowy iterator jest przesuwany o jeden do przodu, a końcowy o jeden do tyłu
• operator[] - to samo co [] dla np. wektora, tyle że działa niezależnie od kategorii iteratora (zatem nie należy go używać dla iteratorów innych, niż swobodnego dostępu)

A poza tym jako metody istnieją najpopularniejsze, istniejące w standardzie algorytmy:

• apply(pred), apply_safe(pred) = for_each(begin(), end(), pred). Wersja "apply_safe" jest to wersja "bezpieczna", tzn. dokonuje inkrementacji ZANIM wykona operację określoną przez pred (zatem pred może również usunąć element, choć można to zastosować tylko do listy)
• filter(op [[,with], out]) = transform(begin(), end(), [with,] out, op). Ma efektywnie trzy wersje, z tym tylko że wersja wyłącznie z "op" jest trochę rozszerzeniem: powoduje wstawienie rezultatu w to samo miejsce
• find, find_if - podobnie jak ogólny algorytm o tej nazwie
• shift_find, shift_find_if - podobne do powyższych, z tym tylko że nie zwracają iteratora, lecz interwał, w którym pierwszy jest zwrócony przez te powyższe funkcje, a drugi jest end().
• get_if - podobne do find_if(), z tym tylko że zwraca od razu wartość znajdującą się na podanym miejscu lub wartość domyślnie skonstruowaną, jeśli takowej nie znaleziono. Przydaje się np. do wyszukiwania elementu po wskaźniku.
• count, count_if - wiadomo
• copy(out) = copy(begin(), end(), out)
• copy_over(cont) = copy(begin(), end(), cont.begin())
• copy_front(cont), copy_back(cont); wstawiają cały zakres reprezentowany przez interwał na początek lub koniec zbiornika. Metoda copy_front oczywiście wcale nie używa front_inserter; elementy są wstawiane w tej samej kolejności
• rcopy = copy_backward
• search(c) = std::search(begin(), end(), c.begin(), c.end())
• firstof = find_first_of
• rsearch = find_end
• sort ...
• msort = stable_sort
• acm = accumulate
• min, max = odpowiednio min_element i max_element

Do utworzenia interwału służy kilka pomocniczych funkcji:

• beast::iv(x, y) - tworzy interwał z x i y
• beast::all(cont) - tworzy interwał z cont.begin() i cont.end()
• beast::all_ra(arr) - tworzy interwał z podanej tablicy surowej

Spodziewam się, że znajdzie się na pewno mnóstwo przeciwników nazwy 'iv'. Trudno. Interwał powstał głównie po to, żeby skrócić i uczytelnić zapis. Przykładowo, zamiast pisać:

for_each(
  object.field.container.begin(),
  object.field.contained.end(),
  Something()
);

Można napisać:

all( object.field.container ).apply( Something() );

Można też stosować i bardziej wymyślne kombinacje, jak np.:

interval< olist<Object>::iterator > in =
  all(ch->m_objects);
size_t i;
for ( i = 0; i < amount; ++i ) {
  in.set_begin(
    in.find_if(
      bind( &Object::Matches, _1, arg1 )
    )
  );
  if ( in.empty() ) break;
  objects.push_back( &*in.begin() );
}
...
Object::LIter o =
  ch->m_place->m_objects.begin(),
  e = ch->m_place->m_objects.end();
for (;o != e; ++o ) {
  o = find_name<Object>(
    iv( o, e ),
    name,
    FCanSee<Object>( ch )
  );
  if ( o == e ) break;
  found = true;
  ch->GetObjFrom( &*o, container );
}

Biorąc to pod uwagę, zrobienie dodatkowo przydługawej nazwy funkcji pomocniczej w stylu "make_interval" byłoby samobójstwem.

Notabene, przyda się to w planowanym już następnym standardzie C++. Jednym z proponowanych dodatków jest użycie martwego praktycznie słowa kluczowego "auto". Np. pierwsza linijka z powyższego przykładu miałaby "auto" zamiast nazwy typu: auto in = all( ch->m_objects );

Integer iterator

Integer iterator znajduje się w tym samym pliku, co interval, gdyż jest z nim dość ściśle związany. Interwał w ogólności jest w stanie zrobić wirtualny zbiornik mając do dyspozycji iterator (ściślej parę iteratorów). Jednym z takowych może być iterator całkowity.

Iterator całkowity udaje iterator do zbiornika, który zawiera kolejne liczby całkowite. Kolejność ich oraz krok iteracji jest określany przez jeden z parametrów wzorca. Iterator ten może być inicjalizowany zwykłą liczbą całkowitą. Iterator ten należy do kategorii iteratorów swobodnego dostępu, z tym tylko ograniczeniem, że jest jedynie iteratorem wejściowym, czyli można z niego tylko czytać. Po takim wirtualnym zbiorniku można się poruszać operatorami ++ i -- oraz + i -. Wyłuskanie tego iteratora operatorem * zwróci aktualnie przechowywaną liczbę. W ogólności, można go traktować jako iterator do zbiornika, w którym mamy tylko liczby całkowite ułożone w odpowiedniej kolejności. Do stworzenia interwału z iteratora całkowitego istnieją również funkcje pomocnicze:

• beast::ivi( b, e ) - tworzy interwał od b do e z krokiem 1
• beast::ivd( e, b ) - tworzy interwał od e do b z krokiem -1
• beast::ivs<krok>( x, y ) - tworzy interwał od x do y z podanym krokiem

Zastrzegam oczywiście, że taki interwał nadal zachowuje zasadę "past-the-end". To oznacza, że jeśli utworzymy interwał przez ivi( 0, 10 ), to wtedy ostatnią liczbą "wyczytaną" z tego zbiornika będzie 9.

Pliki nagłówkowe: beast/interval.hh

Algorytmy

Algorytmy powstają na bieżąco, w zależności od tego, co mi jest w danej chwili potrzebne, podobnie jak wszystko inne. Dlatego na razie istnieje tylko jeden algorytm, który jest w jakiś sposób specyficzny dla beast. Nazywa się mało oryginalnie 'mismatch'. Związek z std::mismatch oczywiście istnieje.

Różni się jednak od std::mismatch w dość znaczący sposób. Jest prostszy w użyciu i w samej definicji. Algorytm beast::mismatch działa następująco: porównuje dwa podane zakresy (przy czym każdy zakres jest określany jednym obiektem, w odróżnieniu od std::mismatch) i zwraca parę iteratorów, na których owe zakresy się różnią. To może również oznaczać dojście jednego z nich do end().

Przypominam, że w std::mismatch jest postawione pewne założenie, które je dyskwalifikuje z wielu zastosowań. Mianowicie pierwsze dwa argumenty wyznaczają zakres pierwszy, którego ilość elementów jest podstawową ilością elementów dla algorytmu. To oznacza, że std::mismatch, jeśli wszystkie elementy są takie same, zatrzyma się dopiero jak w pierwszym zakresie dojdzie do górnego zakresu. Efekt jest taki, że w drugim zakresie musi być co najmniej tyle elementów, co w pierwszym.

Algorytm beast::mismatch nie posiada tego ograniczenia. Iteracja zostanie przerwana jeśli dowolny z iteratorów osiągnie swój end() oraz jeśli elementy równoległe się różnią. Fakt, że std::mismatch jest szybszy, bo dokonuje mniej porównań, ale beast::mismatch ma więcej zastosowań i jest wygodniejszy.

Pliki nagłówkowe: beast/algorithm.hh

Field

Funkcja pomocnicza field() tworzy obiekt typu odpowiednio sprecyzowanego wzorca field_t, który to obiekt jest funktorem udostępniającym pole danej struktury. Składnia:

field( &Klocek::scianka );

Wyrażenie takie zwraca funktor. Jeśli temu funktorowi poda się jako argument referencję do obiektu typu - w tym wypadku - Klocek, to jako rezultat zwróci on referencję do pola 'scianka' tego obiektu.

Funktor ten, jak każdy funktor adaptacyjny, jest sens umieszczać tylko w wyrażeniach binderów (w tym również ewentualnie kompozytorów). Całkiem dobrze się zwłaszcza komponuje z binderami z biblioteki boost.

Beastdef: null i auto_ptr

Kiedyś krążyła stara wersja auto_ptr. Miała ona, w odróżnieniu od obowiązującej aktualnie, jedną zaletę: argument operatora przypisania był const, jak normalnie powinno być. Niestety jest to okupione dodatkowymi komplikacjami (w tym czasu-wykonywania): posiada dodatkowe pole, którym określa, czy jest jego właścicielem. Obiekt takiego autowskaźnika zatem może być, ale może też nie być właścicielem do swojego obiektu. Wersja auto_ptr, dostępna jako beast::auto_ptr, jest właśnie kopią tamtej wersji.

Dodatkowo, dostarczona została specjalna postać null, jako beast::null. Jest to bardzo specjalny obiekt specjalnego typu, który sam konwertuje się na dowolny typ wskaźnikowy i zawsze tworzy z niego zero. Posiada wzorzec metody cast(), która odpowiada za dokonanie tej konwersji. Można dla danego typu oczywiście dostarczyć własne cast(), jeśli chce się, żeby null nie oznaczało zera.

No i poza tym, jest też obiekt 'infinity'. Obiekt ten jako taki nie posiada żadnego specyficznego sensu. Jest on zdefiniowany niemal identycznie jak null, chodzi tylko o to, żeby zwrócił wartość inną, niż null, ale również inną od każdej możliwej wartości wskaźnika. Obiekt infinity może zostać wykorzystany przez iteratory, gdzie trzeba np. podać jakiś end() (bo wymaga tego algorytm), ale taki end(), żeby iterator początkowy nigdy nie był w stanie go osiągnąć.