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