: Home / inne tematy / c / c++ / Struktury danych
Struktury danych
Ocena użytkowników: / 0
SłabyŚwietny 
Wpisany przez Patryk yarpo Jar   
sobota, 02 stycznia 2010 18:37

Taki przedmiot jest na studiach informatycznych. Każdych. Czasem się inaczej nazywa (u mnie to było Projektowanie i Analiza Algorytmów na przykład). Zasadniczo struktury danych to rzecz użyteczna, szczególnie jak ktoś je implementuje za nas.
495px-suffix_tree_bananasvg

Dla programistów nowoczesnych języków fakt istnienia dużej ich ilości w gotowych pakietach jest normą. A programiści C++ co mają? STLa oczywiście, a więc drzewo (*map, *set), tablicę (vector, deque) i listę (list). Plus kolejkę (i kolejkę priorytetową), stos i w pewnym sensie kopiec. Coś pominąłem? Może i tak, ale raczej niewiele.

Z TR1 i następną wersją standardu (C++2009?) dostajemy do naszej kolekcji tablicę mieszającą (unordered_*map, unordered_*set). To już fajna rzecz, ale programiści takiej n.p. Javy mają java.util.Hashtable niemal od zawsze i nie jest to dla nich nic ekscytującego.

Coś jeszcze? Ano dużo! Jak jest jakaś rzecz, której w standardzie C++ nie ma, a uważamy, że być powinna, to najpewniej ona już od dawna jest. W bibliotece Boost. Boost ma mapy dwukierunkowe, wielowymiarowe tablice, bufory cykliczne, tablice stałej wielkości (weszły do TR1), uogólnione krotki (także TR1) i wspomniane tablice mieszające (i znowu TR1).
boost
To już trochę bardziej imponujący arsenał. Czy czegoś jeszcze brakuje?

Nie będę przedstawiał Google Summer of Code – znacie ten wspaniały program znajdowania wakacyjnego zajęcia dla ambitnych młodych programistów. Owóż jeden z uczestników onego programu zaproponował wzbogacenie boosta o to, co w nim brakuje, a mianowicie całą gamę drzew słownikowch (trie, skompresowane trie, drzewa sufiksowe… oj czego to on nie zaproponował). Muszę powiedzieć, że kibicuję temu projektowi z całego serca, bo jest on w moim odczuciu arcyważny dla społeczności C++’owej. Dlaczego? Ano dlatego, że daje nam kolejną standardową strukturę danych.
soc08-300x300_white
Dlaczego standardowe struktury danych są ważne? Ano dlatego, że ułatwiają łączenie kodu. Jest w internecie taka znakomita (pod pewnymi względami) biblioteka, co się nazywa Xerces-C. Biblioteka ta stanowi zaawansowaną implementację DOMu w języku C++. Albo kompletną, albo temu stanowi bliską.
apache-xerces
Biblioteki onej używałem w jednym z projektów szkolnych, i niestety nie było to mimo wszystko przyjemne doświadczenie. Mimo, że mieliśmy dobrze zaprojektowaną aplikację, a – bez fałszywych przechwałek – byliśmy już naonczas całkiem wyszkolonymi programistami (temat z drugiego roku – znaliśmy już język programowania i kilka API). Dlaczego użycie Xercesa było nieprzyjemne? Bo xerces używał xercesowych standardów.

Mniejsza o to, że do wewnętrznej reprezentacji tekstu używa on własnego typu (ni to char ni to wchar_t) : on używa go również w API. jako jedynej opcji. Nie da się xercesa przekonać do stworzenia elementu pisząc:

document.createElement ("hello");

Trzeba być dużo bardziej dosadnym:

using namespace xercesc;
document.createElement ((XMLCh[]){chLatin_h, chLatin_e, chLatin_l, chLatin_l, chLatin_o, chNull});

Tłumaczenia, że to interoperacyjność czy że to unikod o kant stołu rozbić. Program bez konkretnej potrzeby (tu takiej nie ma) porzucający standardowe API na rzecz własnych wynalazków tylko dlatego, że te drugie są własne to niedobry program. Tworząc taki program utrudniamy życie autorom, którzy chcą z naszym programem się komunikować lub choćby chcą włączyć fragmenty naszego programu w swój program, czyż nie? Szczególnie bolesne jest to w kwestii bibliotek, dla których łączenie z innymi programami jest racją bytu.
xmlch
Mając takie XMLCh[] nie możemy używać żadnych (zarówno standardowych, jak i przez nas na nasze potrzeby napisanych) funkcji, klas czy modułów zbudowanych z myślą o współpracy ze standardowym std::wstring’iem czy std::string’iem. Truć można tak w kółko, a i tak znajdą się mądrzejsi, którzy będą klepać własne łańcuchy znaków, smart pointery (mimo, że istnieje tr1::shared_ptr) czy opakowania delegatów (mimo, że tr1::function ma się dobrze).

Jeśli takie cyrki robi się w ramach zamkniętego oprogramowania, to mniejszy problem (bo tego nie widzę), ale niech mi ktoś wyjaśni, czemu służy robienie takiego mętliku w oprogramowaniu otwartym?

Autorem artykułu jest Maciej Kamiński.

 

Dodaj komentarz


Kod antysapmowy
Odśwież