Gyakorlati példa - Rendezett tömb


Ebben a fejezetben egy konkrét példában fogom összefoglalni az eddigieket. Először is mi az a rendezett tömb? Nem nehéz kitalálni, hogy egy olyan tömb aminek az elemei rendezettek. Én most a tömbben integereket fogok tárolni (később majd feljavítom).

Mire jó ez? Például rendezni lehet vele egy számsorozatot, a mozgatások miatt nem olyan gyorsan mint rendezőfával, de elsőre ez nem is baj. Az alábbi tulajdonságokat várjuk el az osztálytól:

  • lehessen előre lefoglalni memóriát
  • beszúrás
  • keresés
  • törlés
  • értékadás és copy konstruktor
  • kiíratás
Ezeket sorban fogom implementálni, kiegészítve az osztályt még néhány extra metódussal. A metódusokat aztán egyenként tesztelni is fogom minél jobb lefedettséggel.




Fölöslegesen nem tárolunk semmit, ezért összesen három adattag lesz, illetve egy statikus azért, hogy tudjuk jelezni ha a keresés nem találta meg az elemet.

CODE
class orderedarray { private: int* data; size_t mycap; size_t mysize; // ... public: static const size_t npos = 0xffffffff; // ... };

A data tagváltozó a tárolt adat (mint dinamikus tömb), a mycap azt mondja meg, hogy mennyi memória áll rendelkezésre (hogy tudjuk mikor kell újrafoglalni), a mysize pedig az elemszámot jelzi. Az npos statikus változó nyugodtan lehet a lehető legnagyobb előjel nélküli szám, ugyanis ennyit úgysem enged lefoglalni a new (legalábbis 32 bites rendszereken). Egyes fordítók esetében a static const membereket is definiálni kell a .cpp fájlban, de a Visual Studio esetében nem.

A konstruktorban nyilván ezeknek kezdőértéket kell adni, a destruktorban pedig a memóriát felszabadítani. Én az STL hibáiból tanulva nem csak a destruktorban engedem meg a felszabadítást, hanem egy külön destroy() metódusban is. Így ki lehet üríteni úgy is a tömböt, hogy ne foglalja fölöslegesen a memóriát. Általában STL konténerekben nincs ilyen metódus, helyette az swap metódust lehet használni (pl. kicserélni egy full üresre).

CODE
orderedarray::orderedarray() { data = 0; mysize = 0; mycap = 0; } orderedarray::~orderedarray() { destroy(); } void orderedarray::destroy() { if( data ) delete[] data; data = NULL; mysize = 0; mycap = 0; } void orderedarray::clear() { mysize = 0; }

Tipikus hiba szokott lenni, hogy a felszabadított pointert nem állítják vissza NULL-ra (vagy akár a többi változót), vagy a tömbös delete helyett a simát használják.


Fel kell készülni arra az esetre amikor a használó előre tudja, hogy hány elemet akar majd beszúrni, de arra is amikor egyáltalán nem tudja. Minden elemnél újrafoglalni a memóriát pazarlás és hibalehetőségeknek ad helyet, ezért ha ilyen hívás érkezik, akkor legalább +10 elemnek foglalok helyet.

Figyelembe kell venni azt az esetet, amikor még nem foglaltunk le memóriát (data == NULL), illetve ha nem sikerült az újnak lefoglalni, akkor a régi adat még maradjon meg.

CODE
void orderedarray::reserve(size_t newcap) { // csak akkor foglaljuk újra, ha szükséges if( mycap < newcap ) { // legalább 10-et lefoglalunk, így hatékonyabb lesz size_t diff = newcap - mycap; diff = std::max<size_t>(diff, 10); // ha a memcpy()-ban hiba történne akkor a régi adat még meglegyen int* tmp = new int[mycap + diff]; // if( data ) itt nem jó! if( mysize > 0 ) memcpy(tmp, data, mysize * sizeof(int)); if( data ) delete data; data = tmp; mycap = mycap + diff; } // egyébként nem kell csinálni semmit }

A C standard libraryban van egy realloc() nevezetű függvény, amit viszont nem ajánlott a new/delete-el együtt használni, ezért kézzel foglalom le/másolom át az adatot. Ha nem sikerült lefoglalni, akkor a new egy std::bad_alloc kivételt dob, tehát nem fog az utána levő kódra futni a vezérlés (megmarad a régi adat).

A későbbi metódusok garantálni fogják, hogy ha mysize > 0, akkor az adat egy érvényes pointer. Fordítva viszont ez nem feltétlenül igaz (pl. az STL-ben semmiképp), azaz ha data != NULL attól még a mysize lehet 0, és nem tudni, hogy a memcpy() ilyenkor mit csinál.


Először gondoljuk meg, hogy mit jelent a rendezett tömbbe való beszúrás. A rendezettséget nyilván nem szabad elrontani, tehát a megfelelő helyre kell berakni az elemet. A megfelelő helyet meg lehet keresni lineáris kereséssel is, de ha már úgyis rendezett a tömb akkor mért ne használnánk logaritmikus keresést? Első lépésként tehát egy _find() metódust fogok implementálni, ami megmondja, hogy hova kell beszúrni az elemet. Világos, hogy ez mindig egy érvényes hely (hacsak el nem fogyott a memória).

Az implementációt úgy fogom megírni, hogy a tömb unsigned int nagyságrendű elemszámot tudjon tárolni. Ehhez figyelembe kell venni, hogy az iterációs indexet nem szabad 0 alá csökkenteni, mert átwrappel 4 milliárdba és elrontja az algoritmust.

CODE
size_t orderedarray::_find(int value) const { size_t low = 0; size_t high = mysize; size_t mid = (low + high) / 2; // logaritmikus keresés while( low < high ) { if( data[mid] < value ) low = mid + 1; else if( data[mid] > value ) high = mid; else return mid; mid = (low + high) / 2; } return low; }

Hogyan is működik ez? A logaritmikus keresést más néven binary search-nek hívják. Azt csinálja, hogy megfelezi az intervallumot és megnézi, hogy a felezési pontnál kisebb vagy nagyobb-e az érték a keresettnél. Ha kisebb akkor megcsinálja ugyanezt a jobb oldali részre, ha nagyobb, akkor meg a bal oldali részre. Azaz egy bináris fát jár be a háttérben.

Némi magyarázat, hogy miért tértem el a klasszikus implementációtól:
  • mivel az elem helyét keresem a lehető legnagyobb index a size
  • 0 alá nem szabad menni, ezért mid-ből nem vonhatok le
  • ha esetleg benne van már az elem, akkor nem kell tovább keresni
Ez a metódus privát, tehát kivülről nem férhet hozzá senki. Ezért egy _-al kezdtem a nevét; ez persze nem kötelező, de a C++ STL-ben egy megszokott dolog. Az ilyen általánosan használható osztályoknál szoktam alkalmazni néha, hogy az STL-el valamennyire konzisztens legyen. Legalábbis kevésbé ocsmány, mint a hungarian notation.

A beszúrás ezek után már egyszerű lesz, de itt is meg kell gondolni pár dolgot: ha már benne van az elem, akkor ne rakjuk be mégegyszer; azaz meg kell vizsgálni a _find() eredményét. Amit viszont üres tömbre nem lehet.

CODE
bool orderedarray::insert(int value) { size_t i = 0; // lefoglalunk helyet reserve(mysize + 1); if( mysize > 0 ) { // megkeressük a helyét i = _find(value); // ha már benne van if( i < mysize && data[i] == value ) return false; // arrébb toljuk az elemeket size_t count = (mysize - i); if( count > 0 ) memmove(data + i + 1, data + i, count * sizeof(int)); } // berakjuk a helyére data[i] = value; ++mysize; return true; }

Nyilván az új elemnek kell +1 hely (ezt a fent implementált reserve() elintézi magában), illetve beszúrás előtt az ennél nagyobb elemeket arrébb kell tolni. Lehetne használni itt iterációt, sőt kötelező lenne azt használni ha nem int-ek lennének a tömbben. Most viszont nincs szükség erre (hacsak valaki rá nem állít egy pointert valamelyik elemre, de az viszont 100% hogy amúgyis elfelejti frissíteni).


A már megírt segédmetódust felhasználva a tényleges keresés sokkal egyszerűbb, csak arra kell odafigyelni, hogy üres tömbre ne vizsgáljunk elemeket.

CODE
size_t orderedarray::find(int value) const { if( mysize > 0 ) { size_t ind = _find(value); if( ind < mysize ) return (data[ind] == value ? ind : npos); } return npos; }

Ennek segítségével pedig a törlés is magától értetődő módon megvalósítható. Nyilván törlés után megintcsak arrébb kell mozgatni az elemeket, csak a másik irányba.

CODE
void orderedarray::erase(int value) { size_t i = find(value); if( i != npos ) { size_t count = (mysize - i); if( count > 0 ) memmove(data + i, data + i + 1, count * sizeof(int)); --mysize; if( mysize == 0 ) clear(); } }

Ha esetleg kiürülne a tömb, akkor meghívom a clear() metódust. Ezzel már garantálható, hogy ha mysize == 0, akkor data == NULL (ld. reserve()).


Az osztályoknál említettem, hogy konstruktorok nem hívhatják egymást, tehát a copy konstruktorba is le kell írni ugyanazokat, mint a simába. Metódusokat viszont lehet hívni, tehát az helyes ha ezután meghívom az értékadást.

CODE
orderedarray::orderedarray(const orderedarray& other) { data = 0; mysize = 0; mycap = 0; this->operator =(other); }

Nincs más hátra, mint az értékadást implementálni. Ami ennél fontos, hogy az értékadás-láncokat helyesen tudja kezelni, illetve az a = a; esetben ne csináljon marhaságot. Ezért konvencionálisan egy összehasonlítással kezdem (nem mindig van erre szükség).

CODE
orderedarray& orderedarray::operator =(const orderedarray& other) { if( &other == this ) return *this; reserve(other.mycap); mysize = other.mysize; memcpy(data, other.data, mysize * sizeof(int)); return *this; }

Megint csak, ha nem int-eket tárolnék, hanem objektumokat, amik esetleg saját memóriaterületeket kezelnek, akkor illene lehetőséget adni nekik a lemásolásra.

A visszatérő érték az objektumra mutató referencia, így a a = b = c; értékadás lánc is jól működik majd (hiszen az értékadás jobbról balra értékelődik ki, azaz a.operator =(b.operator =(c)); történik a háttérben).


Milyen jó lenne, ha az std::cout-al ki tudnánk íratni a tömböt egyetlen utasítással. Nagyon egyszerűen meg lehet ezt csinálni barát metódusokkal. Azt mondom, hogy az osztálynak legyen egy barát függvénye az std::ostream-ben, ami ki tudja íratni az osztály egy példányát. Ez egy tipikus módszer arra, hogy osztályokat kibővítsünk (anélkül, hogy hozzányúlnánk).

CODE
class orderedarray { // ... public: // ... // csak olvasni engedjük inline const int& operator [](size_t index) const { return data[index]; } // elemek száma inline size_t size() const { return mysize; } // kiírató barát metódus friend std::ostream& operator <<(std::ostream& os, orderedarray& oa); }; std::ostream& operator <<(std::ostream& os, orderedarray& oa) { for( size_t i = 0; i < oa.size(); ++i ) os << oa[i] << " "; return os; }

Fontos, hogy bár az osztályban deklaráltam, a metódus nem ehhez az osztályhoz tartozik, viszont a privát tagjait látja.

Az operator [] metódus konstans referenciát ad vissza, de érték szerint is ugyanolyan jól működne. A későbbi bővítések miatt írtam rögtön így. Ami fontos, hogy írni nem szabad az elemeket, illetve ez és a size metódus nem változtatja meg az objektumot, tehát const-ként deklaráltam.

Nyilván az ostream::operator <<-re hasonló igaz, mint az értékadásra, tehát láncban is hívható kell legyen.


Nincs más hátra mint tesztelni amit összehoztunk. Az egyik fő szempont, hogy minél több esetet lefedjünk (kódlefedettség), azaz lehetőleg minden lehetséges végrehajtási út lefusson egyszer. Erre léteznek eszközök is, de most a józan paraszti ész alapján fogom végigtesztelni a dolgokat. Például ilyen dolgokra érdemes gondolni:

  • beszúrás a tömb elejére
  • beszúrás a tömb végére
  • már létező elem beszúrása
  • nem létező elem keresése
  • üres tömmből törlés
Ezeken kívül még az is fontos, hogy a program ne csináljon memory leak-et. Ehhez VC++-ban a _CrtDumpMempryLeaks() függvényt lehet használni.

CODE
#define _CRTDBG_MAP_ALLOC #include <crtdbg.h> #include "orderedarray.h" int main() { { orderedarray a1; // insert a végére a1.insert(2); a1.insert(6); a1.insert(10); // copy konstruktor orderedarray a2 = a1; a2.insert(17); // operator = orderedarray a3; a3 = a2; a3.insert(-1); // ... } // memory leakek _CrtDumpMemoryLeaks(); system("pause"); return 0; }

Az objektumot külön blokkban hoztam létre, hogy biztosan lefusson a destruktor, mire elér a dumpolásig. Ha valami nem úgy működik, ahogy kéne, akkor oda egy breakpoint ott lehet rakni, és lépésenként megnézni, hogy mi történik.

Végezetül még megemlíteném, hogy fontos a metódusok dokumentációja. Ha valaki más szeretné használni az osztályt, akkor fontos, hogy értse amit csinál. A kódban doxygen stílusban kommenteztem fel a header fájlt, csak sajnos magyarul. Az ékezetes betűk nem hordozhatóak, úgyhogy soha ne kommenteljetek magyarul.

A kész kód megtekinthető itt.


Höfö:
  • Írj egy orderedmultiarray osztályt, ami enged duplikált elemeket is!

Irodalomjegyzék

http://en.cppreference.com/w/cpp
http://www.cplusplus.com/
http://www.parashift.com/c++-faq-lite/ (ezt különösen ajánlott elolvasni)
http://aszt.inf.elte.hu/~gsd/halado_cpp/ (ezt is)

back to homepage

Valid HTML 4.01 Transitional Valid CSS!