|
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).
TartalomjegyzékFö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.
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).
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:
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:
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ö:
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) |
