Deprecated: mysql_connect(): The mysql extension is deprecated and will be removed in the future: use mysqli or PDO instead in /home/www/novacisko.cz/subdomains/bredy/init.php on line 11

Warning: mysql_connect(): Headers and client library minor version mismatch. Headers:50562 Library:100020 in /home/www/novacisko.cz/subdomains/bredy/init.php on line 11

Warning: Cannot modify header information - headers already sent by (output started at /home/www/novacisko.cz/subdomains/bredy/init.php:11) in /home/www/novacisko.cz/subdomains/bredy/index.php on line 38
Tanečky na obecném poli (GenericArray) - Bredyho blog - Ondřej Novák
Bredyho blog - Ondřej Novák

Tanečky na obecném poli (GenericArray)

Jak sloučit dvě pole, aniž by bylo třeba alokovat jediný bajt? Jak smazat dvě hodnoty z prostřed pole, aniž by se muselo pole fyzicky posouvat? Jak vyzvednout subpole? Jak přerovnat pole bez fyzického přesunu prvku?


Na začátek příklad

Článek začneme příkladem. To nám vytýčí cíl celého článku.
Mějme následující program:

int main(int argc, const char* argv[])
{
int a[] = {1,2,3,4,5,6,7};
int z[] = {12,24,32,40,60,78,120,130,151,162};
Array<int> arr_a(a,lenof(a));
Array<int> arr_z(z,lenof(z));

printArray(arr_a + arr_z);
printArray(arr_a(2,4));
printArray(arr_a.Insert(3,arr_z));
printArray(arr_a.Delete(2,3));
printArray(arr_a.Reversed());
printArray(arr_a.Repeat(3));
printArray(arr_a.Repeat(3)(3,7));
printArray(arr_a.UnaryOp(Functors::AddConst(10)));
printArray(arr_a.Repeat(3).BinaryOp(arr_z,Functors::Multiply()));
printArray(arr_z.Reorder(arr_a.Reversed()));
}

Výstup z tohoto programu je následující:

1,2,3,4,5,6,7,12,24,32,40,60,78,120,130,151,162
3,4,5
1,2,3,12,24,32,40,60,78,120,130,151,162,4,5,6,7
1,2,6,7
7,6,5,4,3,2,1
1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7
4,5,6,7,1
11,12,13,14,15,16,17
12,48,96,160,300,468,840,130,302,486
130,120,78,60,40,32,24

Co je v pozadí?

Je asi zřejmé, že program demonstruje možnosti třídy Array<T>, která zabaluje klasické C/C++ pole do objektu. Výhodou tohoto zabalení je zejména to, že pole vystupuje jako objekt, který může definovat kromě přístupu přes [] i metodu zjišťující velikost pole (Size()) a spoustu dalších metod, které s polem mohou manipulovat

Ještě by bylo dobré uvést část programu, která provádí výpis výsledků operací. To možná napoví vše:

template<class A, class T>
void printArray(const GenericArray<A,T> &arr)
{
arr.ForEach(Functors::PrintFields());
}

Aha, takže teď už to začíná být zajímavý. Na první pohled je vidět, že se bude jednat o šablony. Vystupuje tady nějaká šablona "GenericArray", která má dva parametry, zatím nevíme jaké. Pravděpodobně T bude Typ prvku.

Ještě se podívejme na funktor, který výpis provádí:

namespace Functors
{
class PrintFields
{
mutable const char *first;
public:
PrintFields():first("") {};
~PrintFields() {std::cout<<std::endl;};
bool operator()(int a) const
{
std::cout<<first<<a;
first = ",";
return false;
}
};
}

Obecné pole

Cílem článku je představit šablonu GenericArray. Šablona má za úkol řešit manipulace s poli tak, aby jakékoliv operace byly prováděny jaksi "na oko", virtuálně, bez nutnosti alokovat prostor v paměti. Důvod, proč je to důležité uvedu v závěru.

Navrhneme třídu GenericArray, která bude výchozí pro všechny pole, jenž připadají v úvahu.

Pole definujeme takto:

  • Jedná se o kontejner, ve kterém jsou prvky adresovány čísly.
  • První prvek má pevnou adresu, zpravidla 0 nebo 1
  • Poslední prvek má adresu "první prvek + velikost pole - 1"
  • Všechny ostatní prvky mají adresu mezi prvním a posledním

Tato definici přináší spoustu výhod, než kdyby jsme použili obecný kontejner a to zejména proto, že známe přesně definiční obor pole (indexů) a můžeme tak s polem volně manipulovat.

Obecné pole neříká nic o struktuře. Prvky mohou být uloženy za sebou, ale mohou být uloženy zcela jinak, nebo dokonce nemusí být vůbec uloženy, protože jsou počítány až na požádáni. Tyhle všechny případy bude řešit GenericArray.

Minimum pro pole

Aby objekt mohl být považován za pole, musí definovat následující operace.

  • operator[] - s adresací číslem (unsigned int). Operator vrací hodnotu prvku na zadané pozici, přičemž je zaručeno, že funkce pracujen jen v rozsahu 0 - (velikost-1) - použijeme tedy 0-based pole.
  • metodu Size() - vrací velikost pole. (BredyLibs mají u metod tříd první velké písmeno).
  • volitelně funkci ImplForEach(funktor, from, count), která volá funktor na každý prvek v poli v zadaném rozsahu. Pokud tato funkce chybí, GenericArray ji implementuje po svém.

Použijeme Invoker

Budeme definovat šablonu, která rozšiřuje operace jakéhokoliv pole o nové. Přesto by bylo vhodné, aby šablona byla předkem tomuto poli, protože definuje rozhraní. Pokud bysme nepoužili šablon, napíšeme tuto třídu jako base (předka) a každá varianta pole ji bude rozšiřovat svojí specifickou implementací.

Použijeme Invoker. To nám umožní definovat operace společné pro všechna pole, které můžeme spolu se šablonou použít.

Základní struktura

template<class Derived, class T>
class GenericArray: public Invoker<Derived>
{
public:
typedef T ThisType;

unsigned int Size() const {return Invoke().Size();}
T &operator[](unsigned int index) const {return Invoke().operator[](index);}

template<class Functor>
bool ForEach(const Functor &fn,unsigned int start, unsigned int len) const
{ return Invoke().ImplForEach(fn,start,len); }

template<class Functor>
bool ForEach(const Functor &fn) const
{ return Invoke().ImplForEach(fn,0,Size()); }

//... tady další metody ...

protected:
template<class Functor>
bool ImplForEach(const Functor &fn, unsigned int start = 0, unsigned int len = -1) const
{
for (unsigned int i = 0; i < len; i++)
{
if (fn((*this)[i + start])) return false;
}
return false;
}
};

Popis základní struktury

Šablona má dvě parametry: Derived obsahuje třídu, která implementuje vlastní pole. Toto je potřeba pro Invoker, aby správně pracovala funkce Invoke(). T obsahuje typ prvku v poli.

Operátor [] a Size jsou směrovány přes Invoke() na implementaci potomkem. Podobně jsou směrovány funkce ForEach. Ty jsou ale směrovány na ImplForEach(), která, v případě, že v potomkovi neexistuje je implementovaná přímo v GenericArray.

První operace: Sloučení dvou polí a řez pole

Doposud jsme psali pouze jakýsí rozhraní, které zajistí, že každé pole bude potomkem šablony GenericArray. Začíná zajímavější část a to psaní operací. Začneme sloučením dvou polí.

Myšlenka je taková, že vytvoříme pole, představující sloučené pole. Ale ke sloučení nedojde fyzicky. Místo toho vznikne nová implemenetace pole, která bude simulovat přístup do sloučeného pole.

template<class Arr1, class Arr2, class T>
class SumArray: public GenericArray<SumArray<Arr1,Arr2,T>,T >
{
friend class GenericArray<SumArray<Arr1,Arr2,T>,T >;
Arr1 arr1;
Arr2 arr2;
public:
SumArray(Arr1 arr1,Arr2 arr2):arr1(arr1),arr2(arr2) {}

unsigned int Size() const {return arr1.Size()+arr2.Size();}
T &operator[](unsigned int pos) const
{
if (pos<arr1.Size()) return arr1[pos] = 0;
else arr2[pos - arr1.Size()];
}
}

Jak je vidět, třída skutečně představuje pole, které funguje samostatně. Všechny přístupy ale rozděluje mezi obě podřízené pole, podle indexu. Velikost, kterou pole oznamuje dána součtem velikostí obou polí. Ještě si ukažme vytvoření sloučeného pole.

template<class Derived, class T>
template<class B>
SumArray<const Derived &,const B &,T> GenericArray<Derived,T>::operator+(const GenericArray<B,T> &b) const
{
return SumArray<const Derived &,const B &,T>(this->Invoke(),b.Invoke());
}

Funkce už má docela komplikovaný zápis, zejména proto, že se jedná o šablonu funkce v šabloně. Také si všimněte použití const a &. Nová třída totiž pouze referencuje obě pole. Nicméně toto nebylo možné "zapéct" do třídy natvrdo. Umožní nám to totiž parametrem šablony rozhodnout, zda použít referenci, nebo provést kopii.

Protože do parametrů šablon vstupují vlastní třídy implementující ta pole, nikoliv GenericArray předek, musíme použít funkci Invoke()

Ukažme si ještě řez polem. Použijeme přitom stejnou myšlenku.

template<class Arr, class T>
class MidArray: public GenericArray<MidArray<Arr,T>,T>
{
friend class GenericArray<MidArray<Arr,T>,T>;
Arr arr;
unsigned int from;
unsigned int len;
public:
MidArray(Arr arr, unsigned int from, unsigned int len):arr(arr),from(from),len(len) {}

unsigned int Size() const { return len; }

ThisType &operator[](unsigned int pos) const { return arr[pos + from]; }
};

A vytvoření řezu. Používám operator závorek s dvěmi parametry. První parametr uvádí index první položky a druhý parametr uvádí index poslední položky, která bude zahrnuta v řezu (včetně)

template<class Derived, class T>
MidArray<const Derived &,T> GenericArray<Derived,T>::operator()(unsigned int first, unsigned int last) const
{
return MidArray<const Derived &,T>(this->Invoke(),first,last<first?0:last-first+1);
}

Složitější operace

Teď si demonstrujeme vkládání pole doprostřed pole. Nebudeme k tomu potřebovat novou třídu, vystačíme si pouze se sloučením a s řezem.

a(0,x-1) + b + a(x,a.Size()-1)

Funkce bude mít docela komplikovanou deklaraci:

 template<class B>
SumArray<SumArray<MidArray<const Derived &,T>,const B &,T>, MidArray<const Derived &,T>,T> Insert(unsigned int position, const GenericArray<B,T> &b) const
{
return SumArray<SumArray<MidArray<const Derived &,T>,const B &,T>, MidArray<const Derived &,T>,T>(SumArray<MidArray<const Derived &,T>,const B &,T>(MidArray<const Derived &,T>(this->Invoke(),0,position),b.Invoke()),MidArray<const Derived &,T>(this->Invoke(),position,Size()-position));
}

Deklarace vypadá opravdu složitě, ale opravdu se jedná jen o zápis výše uvedeného výrazu. Povšimněte si uvedení const a &. Jsou uváděny pouze u vstupů, ale nejsou uváděny u meziproduktů. Je zřejmé, že tyto třídy nemohou být adresovány referencí, protože vznikají pouze v této funkci a vrácená instance by se odkazovala na již zničené instance. Meziprodukty se tedy musí do výsledné instance zkopírovat. Naštěstí nejsou velké, jedná se o pár bajtů.

Výčet všech operací

Insert
Vkládá jedno pole do druhého. Výsledkem je objekt, který obsahuje skombinované prvky.
Delete
Odstraní z pole zadaný rozsah. Výsledkem je třída, která přemapovává indexy tak, aby nebylo možné adresovat smazaný rozsah
Reverse
Otočí pole. Výsledkem je třída která převrátí význam indexů, tj indexu 0 přiřadí poslední prvek a podobně.
Left
Right
Funkce provádí řez zleva nebo zprava
Repeat
Zopakuje pole vícekrát, počet opakování lze zvolit. Vzniklá třída wrapuje index tak, že prvek za posledním prvkem je totožný jako prvek první, a podobně. Jedná se o mapování, tedy dojde-li ke změně v prvním prvku, projeví se změna ve všech opakování
Reorder
Umožňuje přerovnat pole. Pole indexů je mapováno podle jiného pole obsahující pouze indexy.
UnaryOp
BinaryOp
Obě tyto funkce umožní vytvořit pole, které vznikne výpočtem z původního pole, případně z dalšího pole. Pokud se jedná o druhý případ, výsledné pole má velikost menší z obou polí. Výpočet je v obou případech definován funktorem, který se předává parametrem.

Závěr

Hlavní význam manipulace s poli bez alokací je možnost připravit výpočet celé operace. Jakmile je operace sestavena, ještě před jejím provedením je už známa finální velikost celého pole. To je dost důležitá informace. Pokud se pole má přepočítat do nějakého jiného pole, musí se nejprve zaalokovat paměť. A právě informace o tom, jak velký díl paměti je třeba zaalokovat je v tuto chvíli velice cenná. Jakmile máme paměť zaalokovanou, není problém provést kopii pole na nové umístění. Přitom každý prvek se kopíruje právě jednou, bez ohledu na množství operací provedených na poli. I to je významné v případě, že samotná kopie prvku není jednoduchá.

Jiné využití polí je ve tvorbě pohledů. Někdy může být výhodné umět vytvořit pohled na pole bez zásahu do originálního pole, nebo vytváření kopíí. I přes veškeré operace provedené k vytvoření pohledu obsahuje pohled za všech okolností aktuální data. Bez nutnosti kopírování se tedy dotaz na položku v poli tvořící pohled v konečném důsledku bere z původního pole a tedy obsahuje vždy aktuální hodnotu. Za docela rozumní příklad na pohledy je právě uveden v záhlaví článku. Obě pole jsou totiž celou dobu stejná a pouze se mění pohledy, které se zobrazují.

GenericArray.h Zatím neokomentovaný prototyp. Přeloženo pouze ve MSVC 2005. K překladu je potřeba třídu Invoker. Ta je popsána v tomto článku. Příkazy Assert si nadefinujte makrem, nebo je zakomentujte.
vytvořeno: 9.4.2007 01:36:10, změněno: 9.4.2007 01:36:10
Jsou informace v článku pro Vás užitečné?
  • (1)
  • (1)
  • (0)
  • (0)
  • (1)

Podobné články

Dědičnost šablon, CRTP a Invoker

OOP prvky lze používat i při generickém programování pomocí šablon. Dědit šablony je snadné, podívejme se i na polymorfické šablony.

Výsledek povolevbního jednání - Nesvržitelný Premiér Paroubek na celé 4 roky

S údivem sleduji vývoj povolebních jednání, a nestačím se divit. Politické tanečky nekončí, zdá se, že konec je v nedohlednu. Co asi bude na konci? Jaké jsou možné varianty?

Funkce s volitelným počtem argumentů v C++

Leckterý programátor v C jistě zná syntaxtický zápis funkce s volitelným počtem argumentů. V následujícím článku se podíváme na nevýhody tohoto nástroje a způsoby jak to implementovat jinak

Klaus za hranou Ústavy

Prezident odmítl jmenovat Topolánkovu vládu.

Tuples v C++

Pokud si pamatujete na seriál Funkce s volitelným počtem argumentů v C++, tak v této části najdete jakési pokračování, i když cílem článku je trošku něco jiného
Reklama: