Mapa, królowa kontenerów.

Hej tam świecie, co słychać? Miałem coś zrobić na dzień kobiet i udało mi się, rzutem na taśmę, o 18 zazwyczaj mam porządną depresje i myślałem, że już nic nie zrobię, na szczęście o 22 już pełen wiary przystąpiłem do pracy i znalazłem pomysł, wykorzystałem swój Particle System ale dość oszczędnie, wyszło nieźle. Najważniejszy był pomysł i dobra muzyka, ale nie wysłałem swego dzieła choć było blisko, w ostatniej chwili postanowiłem przetestować demko na innym kompiutrze i oczywiście nie zadziałało, zapomniałem o dll-kach Visuala. Większym koszmarem były dla mnie jajca z Stl-em przy zmianie trybu pracy aplikacji z domyślnego Multi-threaded Debug DLL (/MDd) na Multi-threaded Debug (/MTd) zakładka C++->CodeGeneration, co miało zapobiec dodawania visualowych dll-ek do execa. Pieprzone kontenerki zaczęły się sypać w destruktorach na potęgę i to w dosyć losowych miejscach, kurwa …, musiałem powrócić do MDd, taką w sumie radę znalazłem w necie, podobno visualowy Stl jest trochę zjebany i nie ma rady. Poza tym wszystko w porządku.

Dzisiaj na rozkładzie std::map, std::multimap, stdext::hash_map, miał być Object Manager, ale wcześniej trzeba sobie przypomnieć mapę, poza tym chciałem wypróbować jakiegoś hasha i zrobić testy wydajnościowe, jest o czym pisać.

Mapa jest królem, ponieważ jest chyba najczęściej wykorzystywanym kontenerem, a to dlatego, że niemal każdy ObjectManager trzyma obiekty w mapie. Mapa implementowana jako drzewo binarne zrównoważone. Taka struktura zapewnia szybkie wyszukiwanie elementu O(ln N) co jest podstawą jej popularności, wisienką na tym torcie jest fakt, że jest to struktura zawsze posortowana po kluczu,iiihhhha.

Wstawiamy przez [] lub insert(make_pair(key,value)).

Usuwamy przez erase(key), erase(iterator), erase(itBegin, itEnd). Zwracam uwagę na usuwanie it-ka w pętli.

Szukamy elementu przez find(key), która zwraca iterator do obiektu, iterator mapy posiada pola first, second, czyli wskaźniki na klucz i wartość.

Klucz jest unikalny, i próba jego zmiany się nie powiedzie, trzeba usunąć obiekt z mapy i wstawić go od nowa z innymkluczem. Jeśli spróbujemy pobrać wartość przez value = map[key], to w przypadku braku klucza w mapie zwróci nam obiekt
zbudowany przez domyślny konstruktor typu, np. 0 dla long.

Dla mapek mamy iteratory, begin() wskazuje na lewy skrajny węzeł, przejście przez mapę odbywa się w porządku In-order, czyli od lewego do skrajnie prawego węzła powodując przejście w sposób uporządkowany malejąco lub rosnąco.


//kryteria sortowania funktor less, greater
map<long, long, less <long> > mapLong;
map<long, long, less <long> >::iterator itLong;
map<string, string, greater &ltstring> > mapStr;

//mapLong
mapLong[1] = 1;
mapLong[2] = 2;
mapLong[3] = 3;
mapLong[4] = 4;
value = mapLong[5];//przyjmie 0, domyslny konstruktor
itLong = mapLong.begin();

//nie można zmieniać wartości klucza
//można zmienić wartość jeśli nie stała
//można usuwać i wstawiać istniejące lub nie elementy
itLong->second = 5;
mapLong.erase(itLong);// usun przez iterator
mapLong.erase(mapLong.begin(), mapLong.end());//usun zakres mapy
mapLong.erase(7);//usun klucz 7
mapLong.insert(pair <long,long>(8, 8));
mapLong.insert(pair <long,long>(8, 8));
mapLong.insert(pair <long,long>(6, 6));
mapLong.insert(make_pair(7,7));

//przy usuwaniu trzeba uważać, żeby zachować ważny iterator
//wyrażenie itLong++ zwraca itLong po czym robi ++itLong
for(itLong = mapLong.begin(); itLong != mapLong.end(); )
{
if(itLong->second == 8)
mapLong.erase(itLong++);
else
++itLong;
}


Osobna kwestia to mapka dla typów zdefiniowanych przez użytkownika. Tutaj aby mapa umiała ocenić gdzie wstawić nasze obiekty, musimy dostarczyć funktor z operatorem bool operator(const Obiekt& o1, const Obiekt& o2), który zwraca
false gdy o1 <>, można sobie zmienić na greater.


class PersonLess;
class Person
{
friend class PersonLess;
public:
string firstName;
string lastName;

Person(string _firstName, string _lastName) : firstName(_firstName), lastName(_lastName){}
friend ostream& operator<<(ostream& os, const Person& per)
{
os<<per.firstName<<" "<<per.lastName;
return os;
}
};

class PersonLess
{
public:
bool operator()(const Person& p1, const Person& p2) const
{
if(p1.lastName < lastname ="="">& mapa)
{
map<Person, long, PersonLess>::iterator it = mapa.begin();
for(; it != mapa.end(); ++it)
cout<<it->first<<" "<<it->second<<endl;
cout<<endl;
}

map <Person, long, PersonLess> mapPerson;
Person per1("hari","oli"), per2("mati","hautameki"), per3("mati","nykanen"), per4("jane","ahonen");
mapPerson[per1] = 120;
mapPerson[per2] = 130;
mapPerson[per3] = 140;
mapPerson[per4] = 150;
PrintMap(mapPerson);


Obok mapy, która zapewnia unikalność klucza mamy multimapę, która umożliwia gromadzenie wielu wartości pod danym kluczem, szczerze mówiąc nigdy jej nie używałem, ale może się okazać pomocna jeśli ObjectManager grupuje obiekty po jakimś kryterium np. typie, iterator multimapy działa tak samo jak w mapie. Nie mamy tutaj operatora [], mamy metodę count(key) zwracającą liczbę wystąpień danego klucza. Metoda find(key) zwraca iterator do pierwszego z wielu kluczy key w kolekcji.Istnieje wiele metod, których nie ma w mapie, a których po prostu nie chciało mi się testować.


multimap <long, long> multmap;
multimap <long, long>::iterator itMultMap;
long i = 0;

multmap.insert(make_pair(1,1));
multmap.insert(make_pair(1,1));
multmap.insert(make_pair(2,2));
multmap.insert(make_pair(2,2));

//klucze moga sie powtarzac
cout<<"multimapa"<<endl;
cout<<"z kluczem 1: "<<multmap.count(2)<<endl;
cout<<"z kluczem 2: "<<multmap.count(2)<<endl;

cout <<"klucz 1" <<endl;
value = multmap.count(1);
for(i = 0, itMultMap = multmap.find(1); (itMultMap != multmap.end()) && i <>first <<" " <<itMultMap->second <<endl;

cout <<"klucz 2" <<endl;
value = multmap.count(2);
for(i = 0, itMultMap = multmap.find(2); (itMultMap != multmap.end()) && i <>first <<" " <<itMultMap->second <<endl;

cout <<"entire multmap" <<endl;
for(itMultMap = multmap.begin(); itMultMap != multmap.end(); ++itMultMap)
cout<<itMultMap->first <<" "<<itMultMap->second <<endl;;


Ostatnim rodzynkiem w tej grupie kontenerów jest stdext::hash_map, jest to struktura mieszająca tzn. miejsce wstawienia elementu determinuje specjalna funkcja przyjmująca jako parametr klucz elementu. Nie jest to struktura uporządkowana, dzięki temu operacje wstawiania i usuwania są szybsze niż w zwykłej mapie, ale najważniejszą właściwością struktur mieszających jest bardzo szybka operacja wyszukiwania elementu o złożoność rzędu 0(1), szybciej niż w mapie ale oczywiście wolniej niż indeksowanie w tablicy, to o ile wolniej zależy od implementacji hasha. Prezentowana tutaj stdext::hash_map nie jest częścią standardu STL, ale dostarczaną do środowiska Visual ulubionej firmy, inne implementacje można znaleźć w sieci np.: STLPort. Nowy standard C++ powinien mieć już w std struktury mieszające. Używanie nowego kontenera nie różni się wielce od używania mapy, find(), iterator, wszystko to wygląda tak samo.

Na koniec testy wydajnościowe stdext::hash_map VS std::map.
No cóż, wstawianie elementów do hasha nie jest porażająco szybkie, za to wyszukiwanie elementów jest realnie ze 2-4 razy szybsze, zależnie od wielkości struktury, im większa tym hash ma większą przewagę nad mapą. Nieźle ale jak znajdę czas
spróbuje napisać własną strukturę i wtedy zobaczymy, oczywiście co innego pisać w domu na własne potrzeby a co innego pisać
bezpieczny kod dla mas.Należy używać iteratora w pętli, jest dużo szybciej, widać też ogromną przepaść między szukaniem
w tym hashu a indeksowaniem vectora, stąd wniosek, że można samemu coś lepszego wykombiniować, w sieci można znaleźć
o wiele szybsze hashe od stdext::hash_map. Do standardowych zastosowań mapa będzie lepsza, natomiast w wąskich gardłach
przy dużej ilości iteracji i dużej ilości elementów w mapie musimy użyć hasha, póki co jeszcze takiego miejsca w moim kodzie
nie ma.


//używanie tych kontenerów jest identyczne
//declaration
std::map <long, long> mapLong;
stdext::hash_map <long, long> hashLong;
long l = 0;

//fill
for(long i = 0; i < i =" 0;" itmaplong =" mapLong.begin();" l =" itMapLong-">second;
for(itHashLong = hashLong.begin(); itHashLong != itHashLongEnd; ++itHashLong)
l = itHashLong->second;

//find by random index
for(long i = 0; i < itmaplong =" mapLong.find(tabLong[i]))" l =" itMapLong-">second;
for(long i = 0; i < ithashlong =" hashLong.find(tabLong[i]))" l =" itHashLong-">second;

String w formacie alamakota_kotmaale_ + liczba odpowiadająca indeksowi
Czas w milisekundach.
1000 000 iteracji przy Fetch.

Fill containers
Map size: 10tys 1mln
vector: 1 6
map: 21 2079
hash: 20 2527
vector: 1637 21702
map: 342 15511
hash: 133 15298

Fetch by index
vector: 1 1
map: 88 219
hash: 64 131
vector: 67 70
map: 793 1256
hash: 265 513

Fetch by iterator
vector: 9 9
map: 17 31
hash: 9 105
vector: 67 69
map: 23 62
hash: 11 109

Find random key
vector: 3 3
map: 197 1128
hash: 62 281
vector: 87 250
map: 1034 3022
hash: 341 1038


Tablica, vector, chleb powszedni.

Hej ludzie, co słychać? Jak tam wasze zajebiste projekty, moje chwilowo stoją w miejscu, powód?, Civilization 3, fuck, nie pamietam ile razy już łamałem, niszczylem, sprzedawałem płyty z tą grą, jest zabójczo uzależniająca, wiedziałem to a mimo to kupiłem ją znowu, masakra.

Dziś na tapecie mamy tablice z języka C i pytanie o sens ich istnienia w obliczu wektora i potęgi szablonów z C++. Pytanie to mnie naszło gdy natknąłem sie na klase carray z księgi "C++ biblioteka standardowa", jest to klasa osłonowa na zwykłą tablice posiadająca interfejs STL-owy, którą wam pokaże za moment. 

Na razie zwykła tablica i jej zastosowania. Oczywiście nie znamy rozmiaru tablicy w momencie jej deklaracji stąd musimy użyć wskaaźnika na typ tablicowy. Ważne jest dla nas, żeby w dowolnym momencie utworzyć tablice o dowolnym rozmiarze i pozbyć się jej gdy nam przyjdzie ochota. Jedziemy szablonem ponieważ nie wiemy jakiego typy wierzchołki będa nam potrzebne a w każdej chwili może nam przyjść do głowy zmiana koncepcji, kod powinien być gotowy na zmiany. Wszystko gra i bucy, jedyny minus to zmienna numVerts, w której musimy trzymać rozmiar, nie idzie tego inaczej rozwiązać sizeof(verts) zwróci rozmiar pointera, sizeof(*verts) rozmiar elementu, nie mam pojęcia czy da sie to jakoś zrzutować na tablice, raczej nie. Drugi minus to brak STL-wego interfejsu, stąd nie użyjemy np: algorytmów std::copy czy std::sort. Duża zaleta tablicy to ciągły obszar pamieci jaki zajmuje, dlatego możemy pojechać z funkcjami takimi jak: 

memcpy - kopiowanie bloku pamięci 
memset - wypełnianie pamięci wartością zdaje sie int lub unsigned int

Dzięki ciągłemu blokowi pamięci unikamy też fragmentacji pamięci, toteż tablica idelanie nadaje sie do przechowywania danych cząstkach systemu cząstkowego, których jest zwykle bardzo wiele, ale o tym kiedy indziej.


template
class Geometry
{
protected:
VERTEX* verts;
long    numVerts;
void CreateArrays(long _numVerts)
{
   Clear();
   numVerts = _numVerts;
   verts    = new VERTEX[_numVerts];
}
void Clear(){ SAFE_DELETE_ARRAY(verts); }
public:
Geometry(long _numVerts)
{
   verts = 0;
   CreateArrays(_numVerts);
}
~Geometry(){ Clear();}

VERTEX* GetVerts(){ return verts; }
long    GetNumVerts(){ return numVerts; }
virtual void Draw()
{
   printf("verts size = %d\n", numVerts);
     //glVertexPointer(numVerts, GL_FLOAT, 0, verts);
   //glDrawArrays(GL_POINTS,0, numVerts);
}
};


Druga klasa, którą chce pokazać to Carray z książki do STL, jako wrapper na zwykłą tablice. Jej zaletą jest to że posiada interfejs typowy dla innych kontenerów, stąd cały arsenał gotowych algorytmów stoi przed nami otworem, praktyka pokazuje jednak, że nie będziemy z tego w ogóle korzystać, ponieważ tablic danych, nie wskaźników używamy tylko po to aby przekazać, skopiować, wyzerować dane. Przy czym od nadmiaru dobrego głowa nie boli, więc mogę ją dodać do swojego commona.dll. Bezczelnie nazwałem to cudo MyArray ponieważ dodałem kilka poprawek, bewzględnie należy zapomnieć o podawaniu rozmiaru jako parametru szablonu, bo wtedy naszą tablicę możemy o kant dupy rozbić. Musi być elastyczna. Zgodnie z STL-ową manierą nazwy metod są z małej literki, niech im będzie, zresztą nazwy muszą sie zgadzać aby zachować interfejs kontenerów.


template
class MyArray
{
protected:
T*          v;
std::size_t sizeV;
public:
typedef T*          iterator;
typedef const T*    const_iterator;
typedef T&          reference;
typedef const T&    const_reference;
typedef std::size_t size_type;

MyArray(std::size_t _size)
{
   sizeV = _size;
   v     = new T[sizeV];
}
void                 clear(){ SAFE_DELETE_ARRAY(v); }
iterator             begin(){ return v; }
const_iterator       begin() const { return v; }
iterator             end() { return v+sizeV; }
const_iterator       end() const { return v+sizeV; }
reference            operator[](std::size_t i){ return v[i]; }
const_reference      operator[](std::size_t i) const { return v[i]; }
reference            at(std::size_t elem){ return v[elem]; }
const_reference      at(std::size_t elem) const { return v[elem]; }
size_type            size(){ return sizeV; }
size_type            max_size(){ return sizeV; }
T*                   as_array(){ return v; }
};

//przykład MyArray
MyGeometry* geom3  = new MyGeometry(5);
Vertex3*    verts3 = geom3->GetVerts();
MyArray     arr    = geom3->GetVertObject();
arr[0].x = 9;
geom3->Draw();


Ostatni element dzisiejszego wywodu to sławetny std::vector. Jest znany pod każdą szerokoscią geograficzną, nawet na Madaskarze go używają. Ma jedną podstawową przewage nad tablicą, umie sie rozszerzać, jego problem jest niestety taki że rośnie razy dwa, gdy mu braknie miejsca. Na szczęście możemy mu zarezerwować określone miejsce z góry. Możemy go używać zamiennie z tablicą i przekazywać &vec[0] wszędzie tam gdzie jej oczekują. Myśle że może być z powodzeniem wykorzystywany tam gdzie chcemy mieć dynamiczny bufor wierzchołków, ze wskazaniem na rozszerzanie bufora, bo niestety nasz cudowny std::vector nie umie zmiejszać swojego rozmiaru. tzn zmniejszać zapotrzebowania na zużywaną pamięć. Ponieważ jest to ciągły blok, więc możemy łatwo i szybko kopiować cały vector lub jego część przez memcpy().
Ale o wiele wygodniej jest używać algorytmów STL.


//kopiowanie vector
std::vector vec1;
std::vector vec2;
std::vector vec3;
//rezerwuj pamięć na 4 elementy
vec1.reserve(4); vec2.reserve(4);
vec1.push_back(1);
vec1.push_back(2);
vec1.push_back(3);
vec1.push_back(4);
vec2.push_back(5);
vec2.push_back(6);
vec2.push_back(7);
vec2.push_back(8);
//kopiowanie vec1 do vec3
vec3.insert(vec3.end(), vec1.begin(), vec1.end());
//kopiowanie vec1 do vec2
std::copy(vec1.begin(), vec1.end(), vec2.begin());

//tablica a vector
int* tab = NULL;
tab = &vec2[0];
memset(&vec2[0], 0, vec2.size()*sizeof(int));
memcpy(&vec3[0], &vec2[0], vec2.size()*sizeof(int));
std::copy(vec1.begin(), vec1.end(), vec2.begin());

//iteratory
//iteratory powinny być szybsze, gdyż są to poitery na obiekty, nie ma kopiowania całego obiektu
std::vector::iterator it = vec3.begin();
for(; it != vec3.end(); ++it)
   printf("value = %d ", *it);

// wyciągaj obliczenie rozmiaru przed pętle
int vecSize = vec3.size();
//++i jest szybszy od i++, brak obiektu tymczasowego
for(int i = 0; i < vecSize; ++i)
    printf("value: %d",vec3[i]);

                                                                                   
W książce do pisania gier piszą żeby używać std::vector wszędzie tam gdzie można użyć tablicy. Na pewno tak, najważniejsze, że możemy go używać zamiennie z tablicą, dzięki czemu przekażemy nasz wektor jako tablice do np: jakiejś funkcji OpenGL. Ważne jest żeby prawidłowo zalokować od razu całą pamięć i nie zrobić później głupiego push_backa, bo nam rozwali pamięć. Dlatego też wacham się trochę, ze wskazaniem na wektor. Ważny jest szablon na typ, dzięki temu mamy duże pole manewru, ale ile z tego powodu może być problemów to jeszcze kiedyś napisze.

Witaj wielki świecie.

Witaj świecie, nie moge sie dostać do ftpa starej stronki pawelad.ovh.org stąd musze sie bawić w bloga. Troche mnie wkurwia to całe bogowanie, facebooki i inne internetowe gówna, ale w tą stronę poszła cywilizacja to i ja musze sie z tym pierdolić. Nawiasem mówiąc mam mały problem z przeklinaniem, nauczyłem sie i teraz nie idzie sie tego zmienić, ale próbuje kurna.

Z nowym rokiem 2009 AD zacząłem sobie nowy projekt kilka dll-ek dźwięk na fmod, graficzka w opengl, jakiś common, input itp. Planuje sobie zrobić jakieś ciekawe demo, na razie udało mi sie strzelić walentynke, wiecie tasowanie zdjęciami, muzyczka w tle i napisy do niej zapierdalające z głebi ekranu. Oczywiście nie wysłałem bo w ostatniej chwili złapałem cykora, ale może to i lepiej, po co narażać dziewczyne na stres, jakoś to przełknąłem, ale planuje nowe demko, tym razem na dzień kobiet. Będzie się dziać, użyje napisanego niedawno lecz nie testowanego particle systemu, kwiaty bedą zapierdalać po całym ekranie, fontanna kwiatów, kwiatki z głebi, kwiatki z góry, płatki ala American Beauty .... 

Walentynki wam nie moge pokazać, ale kod już tak.
Źródła projektu dla ciekawych