-
Jméno deque je zkrácením double-ended queue (obousměrná
fronta) a vyslovujeme je jako "deck". Tento termín je obecně používán k
popisu datové struktury, která dovoluje vkládání na a odstraňování prvku
ze začátku a konce kolekce. Třída kontejneru deque toho umožňuje
ale mnohem více. Možnosti této datové struktury jsou větší než spojení
toho co poskytují třídy vektoru a seznamu.
-
Jako vektor i deque je indexovaná kolekce. Hodnoty mohou být zpřístupňovány
operátorem indexace (tuto schopnost neposkytují seznamy).
-
Jako u seznamu, hodnoty mohou být efektivně přidávány na začátek nebo na
konec deque (tato schopnost je poskytnuta pouze částečně třídou
vektoru).
-
Jako u tříd vektoru a seznamu, vkládání může být prováděno doprostřed sekvence
držené deque. Operace vkládání nejsou tak efektivní jako v seznamu,
ale jsou efektivnější než ve vektoru.
deque může být použita v situacích které vyžadují vektor nebo seznam.
Použití deque místo vektoru nebo seznamu může ve svém důsledku urychlit
program. Všechny programy, které používají datový typ deque musí
vložit hlavičkový soubor deque.
# include <deque>
-
deque je deklarováno stejným způsobem jako vektor, včetně stejných
definicí typů jako u vektoru. Metody begin a end vracejí
iterátory náhodného přístupu místo obousměrných iterátorů, které jsou vytvořeny
pro seznamy. Vkládání (insert, push_front nebo push_back)
může případně znehodnotit všechny iterátory a odkazy na prvky v deque.
Jelikož datový typ deque poskytuje iterátory náhodného přístupu,
mohou být s deque používány všechny obecné algoritmy, které operují
s vektory. Vektor drží prvky v jednom velkém bloku paměti. deque
používá několik menších bloků.
Jak jsou vkládány hodnoty, indexy přiřazené k jistým prvkům v kolekci
se mění. Např. pokud hodnota je vložena na pozici 3, pak hodnota, která
dříve měla index 3 získá index 4, následující hodnota (dříve měla index
4) získá index 5, atd.
-
Zde uvedený algoritmus řazení je dobrou ukázkou jak seznamy a deque
mohou být kombinovány s ostatními kontejnery. V tomto případě s vektorem
deque
manipulujeme podobně jako s hešovací tabulkou. Celý program nalezneme v
souboru radix.cpp (viz konec předchozí kapitoly).
Zde použitá technika je použita pro řazení seznamu kladných čísel.
Hodnoty jsou řazeny podle desítkových pozic zprava do leva. To zajistí
kopírování hodnot do balíčků, kde index balíčku je dán pozicí číslice podle,
které řadíme. Po průchodu všemi desítkovými pozicemi je seznam seřazen.
balíček |
fáze 1 |
fáze 2 |
fáze 3 |
0 |
730 |
301 |
078 |
1 |
301 |
415 |
146 |
2 |
852 |
624, 426 |
269 |
3 |
593 |
730 |
301 |
4 |
624 |
146 |
415, 426 |
5 |
415 |
852 |
593 |
6 |
426,
146 |
269 |
624 |
7 |
987 |
078 |
730 |
8 |
078 |
987 |
852 |
9 |
269 |
593 |
987 |
Předchozí tabulka zobrazuje sekvence hodnot v jednotlivých balíčcích
v průběhu čtyř kroků řazení seznamu hodnot: 624 852 426
987 269 146 415 301 730 78 593.
V průběhu první fáze jsou řazeny číslice na místě jednotek. Během druhé
fáze se řadí číslice na místě desítek atd. Po dokončení třetí fáze jsou
hodnoty seřazeny.
Náš řadící algoritmus je jednoduchý. Cyklus while je použit
pro průchod různými fázemi. Hodnota proměnné divisor indikuje právě
testovanou číslici. Příznak flag je použit k určení, kdy provádění
zastavit. Při každém průchodu cyklem je deklarován vektor deque.
Vložení deklarace této struktury do cyklu while způsobí, že v každém
průchodu je celá struktura reinicializována. Při provádění cyklu hodnoty
v seznamu jsou kopírovány do odpovídajících balíčků provedením funkce copyIntoBuckets
pro každou hodnotu. Po rozdělení do balíčků, hodnoty jsou převedeny zpět
do seznamu pomocí accumulate.
void radixSort(list<unsigned int> &
values)
{
bool flag = true;
int divisor = 1;
while (flag) {
vector<
deque<unsigned int> > buckets(10);
flag = false;
for_each(values.begin(),
values.end(), copyIntoBuckets(...));
accumulate(buckets.begin(),
buckets.end(), values.begin(), listCopy);
divisor *=
10;
}
}
Použití funkce accumulate je neobvyklé. "Skalární" hodnota zde
vytvořená je samotný seznam. Počáteční hodnotou pro akumulaci je iterátor
určující počátek seznamu. Každý balíček je zpracováván následující binární
funkcí:
list<unsigned int>::iterator
listCopy(list<unsigned
int>::iterator c, deque<unsigned int> & lst)
{
// kopírování seznamu zpět do
původního seznamu, návrat konce
return copy(lst.begin(), lst.end(),
c);
}
Obtížné je pouze definování funkce copyIntoBuckets. Problém
spočívá v tom, že funkce musí přebírat nejen vkládaný prvek, ale musí mít
také přístup ke třem hodnotám buckets, divisor a flag.
V jazycích, které umožňují definovat funkce v jiné funkci, je řešením definovat
copyIntoBuckets
jako lokální funkci v cyklu. To ale C++ neumožňuje. Musíme tedy vytvořit
definici třídy, kde můžeme inicializovat odkazy na příslušné hodnoty. Závorkový
operátor této třídy je pak použit jako funkce pro for_each vyvolanou
v řadícím programu.
class copyIntoBuckets {
public:
copyIntoBuckets
(int d, vector<
deque<unsigned int> > & b, bool & f)
: divisor(d), buckets(b), flag(f) {}
int divisor;
vector<deque<unsigned
int> > & buckets;
bool & flag;
void operator () (unsigned int
v)
{ int index = (v
/ divisor) % 10;
//nastavení
flag na true pokud existuje ještě nějaká nenulová číslice
if (index)
flag = true;
buckets[index].push_back(v);
}
};
-
Množina je kolekce hodnot. Protože kontejner použitý k implementaci datové
struktury set udržuje hodnoty v pořadí jejich reprezentace, jsou
množiny optimalizovány pro vkládání a odstraňování prvků a pro testování,
zda jistá hodnota je obsažena v kolekci. Každá z těchto operací může být
provedena v logaritmickém počtu kroků, zatímco pro seznam, vektor nebo
deque
každá tato operace vyžaduje otestování každého prvku kontejneru. Z tohoto
důvodu, je množina datová struktura, kterou zvolíme při problémech s vkládáním,
odstraňováním prvků a testováním, zda kontejner obsahuje prvek. Stejně
jako seznam i množina nemá omezenou velikost, ale zvětšuje se a zmenšuje
tak, jak jsou prvky přidávány do nebo odstraňovány z kolekce.
Standardní knihovna poskytuje dvě varianty množin. V kontejneru set
musí být každý prvek unikátní. Vkládání hodnot, které jsou již v množině
obsaženy, jsou ignorovány. V kontejneru multiset je na druhé straně
povoleno více výskytů stejných hodnot.
Když používáme set nebo multiset, pak musíme vložit hlavičkový
soubor set:
# include <set>
-
set je šablona datové struktury specializovaná typem prvků, který
obsahuje a operátorem použitým k porovnávání klíčů. Druhý parametr je volitelný
a pokud není poskytnut, pak se předpokládá použití operátoru menší než
pro typ klíče. Typ prvku může být primitivní datový typ, typ ukazatel nebo
uživatelem definovaný typ. Typ prvku musí být porovnatelný operátorem rovnosti
(operátor ==) a operátorem porovnávání menší než (operátor <).
Množiny mohou být deklarovány bez počátečních prvků nebo mohou být
inicializovány z jiného kontejneru poskytnutím dvojice iterátorů. Volitelný
parametr je v obou případech alternativní porovnávací funkci; její hodnota
přepisuje hodnotu poskytnutou parametrem šablony. Tento mechanismus je
užitečný, pokud program obsahuje dvě nebo více množin se stejnými hodnotami,
které jsou ale různě řazené. Kopírovací konstruktor může být použit ve
tvaru nové množiny, která je klonována nebo kopírována z existující množiny.
set <int> set_one;
set <int, greater<int> > set_two;
set <int> set_three(greater<int>());
set <gadget, less<gadget> > gset;
set <gadget> gset(less<gadget>());
set <int> set_four (aList.begin(), aList.end());
set <int> set_five (aList.begin(), aList.end(),
greater<int>());
set <int> set_six (set_four);
// kopírovací konstruktor
Množina může být také přiřazena jiné množině a dvě množiny mohou zaměnit
své hodnoty pomocí operace swap.
set_one = set_five;
set_six.swap(set_two);
Třídy set a multiset obsahují řadu definic typů. Nejčastěji
se používají v deklaračních příkazech. Např. iterátor pro množinu celých
čísel může být deklarován takto:
set<int>::iterator location;
Mimo iterator jsou definovány následují typy:
value_type |
Typ prvku množiny. |
const_iterator |
Iterátor, který neumožňuje modifikaci připojené sekvence. |
reverse_iterator |
Iterátor, který se přesouvá směrem dozadu. |
const_reverse_iterator |
Kombinace konstantního a reverzního iterátoru. |
reference |
Odkaz na připojený prvek. |
const_reference |
Odkaz na připojený prvek, který neumožňuje modifikaci prvku. |
size_type |
Typ použitý k odkazování na velikost kontejneru. |
value_compare |
Funkce, která může být použita k porovnání dvou prvků. |
difference_type |
Typ použitý k uložení vzdálenosti mezi iterátory. |
allocator_type |
Typ alokátoru použitého kontejnerem. |
Na rozdíl od seznamu nebo vektoru je pouze jeden způsob přidávání nového
prvku do množiny. Hodnota může být vkládána do set nebo multiset
pomocí metody insert. Pro multiset funkce vrací iterátor,
který ukazuje na vloženou hodnotu. Vkládací operace do set vrací
dvojici hodnot, kde first je iterátor a second obsahuje logickou
hodnotu, která je true pokud prvek je vložen a false v opačném
případě (množina již tento prvek obsahuje).
set_one.insert (18);
if (set_one.insert(18).second) cout <<
"prvek byl vložen" << endl;
else cout << "prvek nelze vložit" <<
endl;
Vložení několika prvků z jiného kontejneru lze provést dvojicí iterátorů:
set_one.insert (set_three.begin(), set_three.end());
Datová struktura pair je dvojice hodnot. První hodnota je zpřístupněna
pomocí jména položky first, zatímco druhá je přirozeně naznána second.
Funkce nazvaná make_pair zjednodušuje úlohu vytváření instancí páru
tříd.
template <class T1, class T2>
struct pair {
T1 first;
T2 second;
pair (const T1 & x, const
T2 & y) : first(x), second(y) { }
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(const T1&
x, const T2& y)
{ return pair<T1, T2>(x,
y); }
V určování ekvivalence klíčů, např. k určení zda klíčová část nového
prvku odpovídá libovolnému existujícímu prvku, je použita porovnávací funkce
pro klíče a ne operátor ekvivalence (==). Dva klíče se považují za ekvivalentní,
pokud porovnávací funkce použitá na klíče v obou směrech stále vrací false.
Tj. pokud Compare(key1, key2) je false a Compare(key2,
key1) je false, pak klíče key1 a key2 si jsou
ekvivalentní.
Hodnoty jsou odstraňovány z množiny pomocí metody erase. Parametr
může být konkrétní hodnota, iterátor určující jednu hodnotu nebo pár iterátorů
určujících rozsah hodnot. Pokud první tvar je použit na multiset,
pak jsou odstraněny všechny prvky odpovídající uvedené hodnotě a vrácená
hodnota indikuje počet zrušených prvků.
// zručení prvku rovnajícímu se 4
set_three.erase(4);
// zrušení prvku 5
set<int>::iterator five = set_three.find(5);
set_three.erase(five);
// zrušení všech prvků mezi 7 a 11
set<int>::iterator seven = set_three.find(7);
set<int>::iterator eleven = set_three.find(11);
set_three.erase (seven, eleven);
Metoda size vrací počet prvků držených kontejnerem a metoda
empty
vrací informaci, zda kontejner je prázdný. Metoda find přebírá hodnotu
prvku a vrací iterátor indikující místo prvku v množině nebo koncovou hodnotu,
pokud prvek v množině neexistuje. Pokud multiset obsahuje více než
jednu hledanou hodnotu, pak vrácená hodnota může určovat libovolnou z nich.
set<int>::iterator five = set_three.find(5);
if (five != set_three.end())
cout << "množina obsahuje 5"
<< endl;
Metody lower_bound a upper_bound jsou užitečné s multiset,
zatímco pro set jsou napodobeninou funkce find. Metoda lower_bound
zjistí první prvek odpovídající parametru klíče, zatímco metoda upper_boud
vrací poslední prvek odpovídající parametru klíče. Konečně metoda equal_range
vrací pár iterátorů, držících dolní a horní mez.
Metoda count vrací počet prvků odpovídajících parametru. Pro
množiny tato hodnota je nula nebo jedna, zatímco pro multiset to
může být libovolné nezáporné číslo. Protože nenulová celočíselná hodnota
je chápána jako true, funkce count může být použita jako
test zda množina obsahuje prvek. Alternativní použití find vyžaduje
testování vráceného výsledku find, zda se nejedná o koncovou hodnotu
iterátoru kolekce.
if (set_three.count(5)) cout << "množina
obsahuje 5" << endl;
Metody begin a end vytvářejí iterárory pro set
i multiset. Iterátory poskytnuté těmito funkcemi jsou konstantní
k zajištění, aby relace pořadí pro množinu byla neporušitelná přiřazením
nové hodnoty prvku množiny. Prvky jsou generovány iterátory v sekvenci,
určené porovnávacím operátorem poskytnutým při deklaraci množiny. Metody
rbegin
a rend vytvářejí reverzní iterátory.
Tradiční množinové operace (sjednocení, průnik, rozdíl apod.)
nejsou poskytnuty jako metody, ale jsou implementovány jako obecné algoritmy,
které pracují s řazenou strukturou.
Funkce includes může být použita k určení, zda jedna množina
je podmnožinou jiné, tj. zda všechny prvky z první jsou obsaženy ve druhé.
V případě multiset počet odpovídajících prvků v druhé množině musí
překračovat počet prvků v první. Čtyři parametry jsou dvojice iterátorů
reprezentujících (možnou) menší množinu a dvojice iterátorů reprezentujících
(případnou) větší množinu.
if (includes(set_one.begin(),set_one.end(),set_two.begin(),set_two.end()))
cout << "set_one je podmnožina
set_two" << endl;
Operátor menší než (operátor <) může být použit pro porovnávání
prvků, a to bez ohledu na operátor použitý v deklaraci množiny. Alternativní
verze funkce includes přebírá pátý parametr, kterým je porovnávací
funkce použitá k porovnání prvků ve dvou množinách.
Funkce set_union může být použita k vytvoření sjednocení dvou
množin. Dvě množiny jsou specifikovány páry iterátorů a sjednocení je překopírováno
do výstupního iterátoru, který je předán pátým parametrem (musí být použit
jako vkládací operátor). Pokud požadovaný výsledek je sjednocení jedné
množiny s jinou (výsledek požadujeme ponechat v původní množině), pak můžeme
vytvořit dočasnou množinu a výsledek přesunout do parametru před zrušením
dočasné množiny.
// sjednocení dvou množin a zkopírování výsledku
do vektoru
vector<int> v_one (set_one.size() + set_two.size());
set_union(set_one.begin(), set_one.end(),
set_two.begin(), set_two.end(),
v_one.begin());
// sjednocení v první množině
set<int> temp_set;
set_union(set_one.begin(), set_one.end(),
set_two.begin(), set_two.end(),
inserter(temp_set, temp_set.begin()));
set_one.swap(temp_set); // temp_set
může být zrušen
Funkce set_intersection je podobná a určuje průnik dvou množin.
Stejně jako funkce includes používá operátor < k porovnávání
prvků ve dvou množinách parametrů, a to bez ohledu na operátor uvedený
v deklaraci množiny, je tomu tak i u sjednocení a průniku. Alternativní
verze
set_union a set_intersection umožňují určit použitý
operátor jako šestý parametr.
Operaci sjednocení dvou multiset musíme odlišovat od operace
slučování množin. Předpokládejme, že jeden operand obsahuje tři hodnoty
7 a druhý operand má dvě hodnoty 7. Sjednocení pak obsahuje pouze tři hodnoty
7, zatímco sloučení jich obsahuje pět. Pro slučování používáme funkci merge
(parametry jsou stejné jako u funkce set_union).
Jsou dva tvary rozdílu množin. Jednoduchý rozdíl množin reprezentuje
prvky v první množině, které nejsou obsaženy v druhé množině. Symetrickým
rozdílem množin je sjednocení prvků v první množině, které nejsou obsaženy
v druhé množině s prvky v druhé množině, které nejsou obsaženy v první
množině. Tyto dvě hodnoty jsou vytvářeny funkcemi set_difference
a set_symmetric_difference. Použití těchto funkcí se podobá použití
funkce set_union popsané výše.
Protože množiny jsou řazené a mají konstantní iterátory, tak některé
obecné funkce na ně nejsou aplikovatelné nebo nejsou prakticky užitečné.
S množinami můžeme ale používat:
copy |
Kopírování jedné sekvence do druhé. |
find_if |
Nalezení prvku vyhovujícího podmínce. |
search |
Nalezení podsekvence v množině. |
count_if |
Počet prvků splňujících podmínku. |
accumulate |
Redukce množiny na jednu hodnotu. |
for_each |
Provedení funkce pro každý prvek. |
-
Příkladem programu používajícího množinu je tester pravopisu. Program nalezneme
v souboru spell.cpp. Tester přebírá jako parametry dva výstupní
proudy; první reprezentující proud správných slov a druhý textový soubor.
První (slovník) je přečten do množiny. To je provedeno pomocí copy
a iterátor vstupního proudu kopíruje hodnoty do inserter pro slovník.
Dále jsou slova z textu zkoumána po jednom (testována zda jsou ve slovníku).
Pokud slovo není nalezeno, pak je vloženo do množiny chybných slov. Po
projití celého textu, jsou chybná slova vypsána.
void spellCheck (istream & dictionary,
istream & text)
{
typedef set <string, less<string>
> stringset;
stringset words, misspellings;
string word;
istream_iterator<string,
ptrdiff_t> dstream(dictionary), eof;
// přečtení slovíku
copy (dstream, eof, inserter(words,
words.begin()));
// čtení textu
while (text >> word)
if (! words.count(word))
misspellings.insert(word);
// výstup chybných slov
cout << "Misspelled words:"
<< endl;
copy (misspellings.begin(),
misspellings.end(),
ostream_iterator<string>(cout,
"\n"));
}
Zajímavé je také zabývat se přesmyčkami ve slovech. Jsou různé techniky,
které mohou být použity. My použijeme techniku, kde pouze zaměňujeme sousední
písmena. Tuto funkci voláme v cyklu, který zobrazuje chyby.
void findMisspell(stringset & words,
string & word)
{
for (int I = 1; I < word.length();
I++) {
swap(word[I-1],
word[I]);
if (words.count(word))
cout << "Suggestion: " << word << endl;
// put word
back as before
swap(word[I-1],
word[I]);
}
}
-
bitset je kombinace množiny a vektoru. Jedná se o množinu binárních
hodnot ve tvaru vektoru. Množinové operace můžeme provádět na bitset
pomocí logických bitových operátorů. Třída bitset neposkytuje žádné
iterátory pro přístup k prvkům. Programy používající bitset musí
vložit hlavičkový soubor bitset:
#include <bitset>
bitset je šablona třídy. Parametrem šablony není typ, ale celočíselná
hodnota. Její hodnota udává počet bitů obsažených v množině.
bitset<126> bset_one;
// vytvoření množiny 126 bitů
Alternativní technikou určení velikosti množiny je použití parametru
v konstruktoru. Aktuální velikost bude menší z hodnot použitých jako parametr
šablony a parametr konstruktoru. Tato technika je užitečná, když program
obsahuje dva nebo více bitových vektorů různých velikostí. Použitím největší
velikosti pro parametr šablony zajistíme, že funkce množiny budou generovány
pouze jedenkrát. Aktuální velikost pak bude určena konstruktorem.
bitset<126> bset_two(100);
// tato množina má pouze 100 prvků
Třetí tvar konstruktoru přebírá jako parametr řetězec nul a jedniček.
Vytvořený bitset má potom tolik prvků jako je znaků v řetězci a
bitset
je inicializován hodnotami z řetězce.
bitset<126> small_set("10101010");
// tato množina má 8 prvků
Jednotlivé bity v bitset mohou být zpřístupňovány pomocí operátoru
indexace. Zda bit je nastaven můžeme určit metodou test. Zda některé
bity v bitset jsou nastaveny, testujeme metodou any (získáme
logickou hodnotu). Inverzi any vrací metoda none.
bset_one[3] = 1;
if (bset_one.test(4)) cout << "bit
na pozici 4 je nastaven" << endl;
if (bset_one.any()) cout << "některé
bity jsou nastaveny" << endl;
if (bset_one.none()) cout << "žádné
bity nejsou nastaveny" << endl;
Funkce set může být použita k nastavení jistého bitu. bset_one.set(I)
je
ekvivalentem k bset_one[I] = true. Vyvolání funkce bez parametru
nastavuje všechny bitové pozice na true. Funkce reset je
podobná a nastavuje určenou pozici na false (při vyvolání bez parametru
nastavuje všechny bity na false). Funkce flip invertuje zadanou
pozici nebo pokud není uveden parametr pak všechny pozice. Funkce flip
je také poskytnuta jako metoda pro individuální bitové odkazy.
bset_one.flip();
// inverze celé množiny
bset_one.flip(12);
// inverze pouze bitu 12
bset_one[12].flip(); // opakovaná
inverze bitu 12
Metoda size vrací velikost bitové množiny, zatímco metoda count
počet bitů, které jsou nastaveny.
Množinové operace na bitset jsou implementovány pomocí bitových
operátorů a to stejným způsobem jako v případě celočíselných operandů.
Operátor negace ~ aplikovaný na bitovou množinu vrací novou bitovou
množinu obsahující invertované prvky. Pro určení průniku použijeme operátor
&. Je možno jej použít i ve tvaru s přiřazením.
bset_three = bset_two & bset_four;
bset_five &= bset_three;
Sjednocení dvou množin provedeme podobně operátorem | a nonekvivalenci
operátorem ^. Operátory levého a pravého posuvu (<< a >>) mohou být
použity k posuvu bitové množiny analogicky jako je používáme pro celočíselné
operandy.
Metoda to_ulong přivádí bitovou množinu na unsigned long.
Je chybou provést tuto operaci na bitové množině s více prvky než může
být uloženo touto reprezentací.
Metoda to_string převádí bitovou množinu na objekt typu string.
Každý nulový bit je reprezentován znakem 0 a každý jedničkový bit znakem
1.
-
map je indexovaná datová struktura, podobající se vektoru nebo deque.
Od těchto struktur se ale liší ve dvou důležitých věcech. V map,
na rozdíl od vektoru nebo deque, hodnoty indexů (nazývané
klíčové hodnoty) nemusí být celočíselné, ale mohou být libovolného řaditelného
datového typu. Např. map může být indexován reálnými čísly nebo
řetězci. Jako klíč může být použit libovolný datový typ, pro nějž je definován
operátor porovnávání. Prvky jsou pak zpřístupňovány operátorem indexace.
Druhým důležitým rozdílem je to, že map je řazená datová struktura.
Její prvky jsou udržovány v pořadí daným hodnotami klíčů. Protože hodnoty
jsou udržovány v pořadí, map může velmi rychle nalézt prvek specifikovaný
daným klíčem. Velikost map není omezena a mění se přidáváním nebo
odstraňováním prvků. Podobá se množině, která udržuje kolekci párů.
Standardní knihovna poskytuje dvě varianty mapování. Datová struktura
map
požaduje unikátní klíče. Je tedy jednoznačné přiřazení mezi klíčem prvku
a jeho hodnotou. multimap na druhé straně umožňuje, aby více položek
bylo indexováno stejným klíčem. Obě datové struktury poskytují relativně
rychlé operace vkládání, rušení a zpřístupnění.
Pokud používáme map nebo multimap, pak musíme vložit
hlavičkový soubor map:
# include <map>
-
map je šablona datové struktury, specifikovaná typem prvku klíče,
typem přiřazených hodnot a operátorem použitým k porovnávání klíčů. Pokud
náš překladač podporuje implicitní typy šablony (relativně nový rys C++,
zatím nepodporovaný všemi výrobci), pak poslední z nich je volitelný a
pokud není poskytnut, pak se předpokládá operátor menší než pro typ klíče.
map
může být deklarováno bez počátečních prvků nebo inicializováno z jiného
kontejneru poskytnutím páru iterátorů. V druhém případě iterátory musí
určovat hodnoty typu pair, kde první položka v každém páru je klíčem
zatímco druhá položka je hodnotou. Kopírovací konstruktor také umožňuje
vytvářet mapy jako kopie jiných map.
// mapování indexované double obsahující
řetězce
map<double, string, less<double> >
map_one;
// mapování indexované int obsahující int
map<int, int> map_two(aContainer.begin(),
aContainer.end());
// vytvoření nového mapování a jeho inicializace
z jiného
map<int, int> map_three (map_two);
// kopírovací konstruktor
Mapování může být přiřazeno jinému mapování a dvě mapování mohou zaměnit
své hodnoty pomocí operace swap.
Třídy map a multimap obsahují řadu definic typů. Tyto
typy jsou často používány v příkazech deklarací. Např. iterátor pro mapování
řetězců na celá čísla může být deklarován následujícím způsobem:
map<string, int>::iterator location;
Mimo iterator jsou definovány následující typy:
key_type |
Typ přiřazený ke klíči použitého k indexaci mapování. |
value_type |
Typ držený kontejnerem (dvojice klíč/hodnota) |
const_iterator |
Iterátor, který neumožňuje modifikaci připojené sekvence. |
reverse_iterator |
Iterátor, který se přesouvá směrem dozadu. |
const_reverse_iterator |
Kombinace konstantního a reverzního iterátoru. |
reference |
Odkaz na připojený prvek. |
const_reference |
Odkaz na připojený prvek, který neumožňuje modifikaci prvku. |
size_type |
Typ použitý k odkazování na velikost kontejneru. |
key_compare |
Objekt funkce, který může být použit k porovnávání dvou klíčů. |
value_compare |
Objekt funkce, který může být použit k porovnávání dvou prvků. |
difference_type |
Typ použitý k uložení vzdálenosti mezi iterátory. |
allocator_type |
Typ alokátoru použitého kontejnerem. |
Hodnoty mohou být vkládány do map nebo multimap pomocí
operace insert. Povšimněte si, že parametrem musí být dvojice klíč/hodnota.
Tento pár je často vytvářen pomocí datového typu value_type přiřazeného
k mapování.
map_three.insert (map<int>::value_type(5,
7));
Vkládání může být také provedeno pomocí páru iterátorů, např. z jiného
mapování.
map_two.insert (map_three.begin(), map_three.end());
S map (ale ne s multimap) hodnoty mohou být zpřístupňovány
a vkládány pomocí operátoru indexace. Jednoduché použití klíče jako indexu
vytváří položku - jako přiřazená hodnota je použit implicitní prvek. Přiřazením
výsledku indexace mění asociovanou vazbu.
cout << "Hodnota indexu 7 je " <<
map_three[7] << endl;
// nyní změníme asociovanou hodnotu
map_three[7] = 5;
cout << "Hodnota indexu 7 je " <<
map_three[7] << endl;
Hodnoty mohou být odstraňovány z map nebo multimap uvedením
hodnoty klíče. V multimap jsou odstraněny všechny prvky s přiřazeným
klíčem. Odstraňovaný prvek může být také určen iterátorem, např. iterátorem
určeným operací find. Pár iterátorů je také možno použít k odstranění
celého intervalu prvků.
// zrušení čtvrtého prvku
map_three.erase(4);
// zrušení pátého prvku
mtesttype::iterator five = map_three.find(5);
map_three.erase(five);
// zrušení všech prvků mezi sedmým a jedenáctým
mtesttype::iterator seven = map_three.find(7);
mtesttype::iterator eleven = map_three.find(11);
map_three.erase (seven, eleven);
Pokud je pro typ prvku poskytnut destruktor, pak je vyvoláván při odstraňování
páru klíč/hodnota z kolekce.
Metody begin a end vytvářejí obousměrné iterátory pro
map
i multimap. Dereference iterátoru určuje prvek páru klíč/hodnota.
Jména položek first a second mohou být použity pro přístup
k jednotlivým položkám. Položka first je konstantní a nemůže být
modifikována. Položku second můžeme ale použít ke změně hodnoty
držené v asociaci s daným klíčem. Prvky jsou generovány v sekvenci, založené
na pořadí položek klíčů. Metody rbegin a rend vytvářejí reverzní
iterátory.
Metoda size vrací počet prvků držených v kontejneru. Metoda
empty
zjišťuje zda je kontejner prázdný. Metoda find přebírá jako parametr
klíč a vrací iterátor určující přiřazený pár klíč/hodnota. V případě multimap
je vrácena první hodnota. V obou případech je vrácen iterátor koncové hodnoty,
pokud hodnota není nalezena.
if (map_one.find(4) != map_one.end())
cout << "obsahuje čtvrtý prvek"
<< endl;
Metoda lower_bound vrací první prvek odpovídající parametru
klíče, zatímco metoda upper_bound vrací poslední hodnotu odpovídající
parametru klíče. Metoda equal_range vrací pár iterátorů, držících
dolní a horní mez. Příklad použití bude uveden později.
Metoda count vrací počet prvků, které odpovídají klíčové hodnotě
předané jako parametr. Pro map je tato hodnota vždy nula nebo 1,
zatímco pro multimap to může být libovolná nezáporná hodnota. Pokud
potřebujeme zjistit, zda kolekce obsahuje prvek indexovaný daným klíčem,
pak můžeme použít count (je to výhodnější než použití find).
if (map_one.count(4))
cout << "obsahuje čtvrtý prvek"
<< endl;
Metody key_comp a value_comp, které jsou bez parametru,
vracejí objekty funkcí, které mohou být použity k porovnávání prvků, typů
klíčů nebo hodnot. Hodnoty použité v těchto porovnáváních nemusí být obsaženy
v kolekci a žádná z funkcí nemá žádný efekt na kontejner.
if (map_two.key_comp (i, j))
cout << "prvek i je menší
než j" << endl;
Protože map a multimap jsou řazené kolekce, a protože
iterátory pro mapování určují dvojice klíč/hodnota, většina obecných funkcí
pro ně nemá smysluplné použití. Je ale několik výjimek. Funkce for_each,
adjacent_find
a accumulate mají své vlastní použití. Ve všech případech je důležité
nezapomenout, že funkce přebírají jako parametry páry klíč/hodnota.
-
Dále jsou uvedeny tři příklady, které ukazují použití map a multimap.
Jsou to databáze telefonů, grafy a konkordance.
Kompletní program pro databázi telefonů získáme v souboru tele.cpp.
Program pro údržbu jednoduché telefonní databáze je vhodnou aplikací pro
použití map. Databáze je indexovaná struktura, ve které jméno osoby
tvoří řetězec klíčové hodnoty a telefonní číslo je přiřazená položka. Můžeme
zapsat tuto třídu:
typedef map<string, long, less<string>
> friendMap;
typedef friendMap::value_type entry_type;
class telephoneDirectory {
public:
void addEntry (string name,
long number) // přidání nové položky
{ database[name]
= number; }
void remove (string name)
// odstranění položky z databáze
{ database.erase(name);
}
void update (string name, long
number) // aktualizace položky
{ remove(name);
addEntry(name, number); }
void displayDatabase()
// zobracení celé databáze
{ for_each(database.begin(),
database.end(), printEntry); }
void displayPrefix(int);
// zobrazení prvků odpovídajících předponě
void displayByPrefix();
// zobrazení databáze podle předpon
private:
friendMap database;
};
Jednoduché operace na naší databázi jsou přímo implementované příkazy
mapování. Přidávání prvku do databáze je jednoduché vkládání, odstraňování
prvků je rušení a aktualizace je kombinace obojího. K výpisu všech položek
z databáze můžeme použít algoritmus for_each a aplikujeme na každý
prvek následující funkci:
void printEntry(const entry_type & entry)
{ cout << entry.first
<< ":" << entry.second << endl; }
Dále použijeme dvě složitější operace ukazující, jak obecné algoritmy
mohou být použity s mapováním. Předpokládejme, že chceme zobrazovat všechna
telefonní čísla s jistou tříčíslicovou předponou. Můžeme použít funkci
find_if
(liší se ve třídě map od metody find) k lokalizaci první
položky. Počínaje od tohoto místa, následující volání find_if získají
další vyhovující položky.
void telephoneDirectory::displayPrefix(int
prefix)
{
cout << "Listing for prefix
" << prefix << endl;
friendMap::iterator where;
where =
find_if (database.begin(),
database.end(), checkPrefix(prefix));
while (where != database.end())
{
printEntry(*where);
where = find_if
(++where, database.end(), checkPrefix(prefix));
}
cout << "end of prefix
listing" << endl;
}
Jako tvrzení pro tuto operaci, potřebujeme funkci přebírající jeden
parametr (pár reprezentující položku databáze) a určující, zda používá
danou předponu. V našem případě použijeme řešení často používané ve standardní
knihovně; nadefinujeme funkci tvrzení jako instanci třídy a uložíme test
tvrzení jako instanci proměnné ve třídě a inicializujeme ji při vytváření
třídy. Požadovaná funkce je pak definována jako operátor volání funkce
pro třídu:
int prefix(const entry_type & entry)
{ return entry.second / 10000;
}
class checkPrefix {
public:
checkPrefix (int p) : testPrefix(p)
{ }
int testPrefix;
bool operator () (const entry_type
& entry)
{ return prefix(entry)
== testPrefix; }
};
Posledním požadavkem je zobrazení seznamu seřazeného podle předpon.
Není možné měnit pořadí samotné struktury mapování. Místo toho vytvoříme
nové mapování s reverzním typem prvků, potom překopírujeme hodnoty do nového
mapování, kde již pořadí je určeno hodnotou předpony. Po vytvoření mapování
jej můžeme vypsat.
typedef map<long, string, less<long>
> sortedMap;
typedef sortedMap::value_type sorted_entry_type;
void telephoneDirectory::displayByPrefix()
{
cout << "Display by prefix"
<< endl;
sortedMap sortedData;
friendMap::iterator itr;
for (itr = database.begin();
itr != database.end(); itr++)
sortedData.insert(sortedMap::value_type((*itr).second,(*itr).first));
for_each(sortedData.begin(),
sortedData.end(),printSortedEntry);
}
Funkce použitá k výpisu řazených položek je:
void printSortedEntry (const sorted_entry_type
& entry)
{ cout <<
entry.first << ":" << entry.second << endl; }
-
Druhý příklad se týká grafů. Celý program nalezneme v souboru graph.cpp.
Mapování prvků, které jsou sami mapováním jsou přirozenou reprezentací
orientovaných grafů. Např. předpokládejme, že používáme řetězce k zakódování
jmen měst, a že chceme vytvořit mapu, kde hodnota přiřazená ke hraně je
vzdálenost mezi propojenými městy. Pak můžeme graf vytvořit takto:
typedef map<string, int> stringVector;
typedef map<string, stringVector> graph;
const string pendleton("Pendleton");
// definice řetězců jmen měst
const string pensacola("Pensacola");
const string peoria("Peoria");
const string phoenix("Phoenix");
const string pierre("Pierre");
const string pittsburgh("Pittsburgh");
const string princeton("Princeton");
const string pueblo("Pueblo");
graph cityMap;
// deklarace grafu s mapou
cityMap[pendleton][phoenix] = 4;
// přidávání hran do grafu
cityMap[pendleton][pueblo] = 8;
cityMap[pensacola][phoenix] = 5;
cityMap[peoria][pittsburgh] = 5;
cityMap[peoria][pueblo] = 3;
cityMap[phoenix][peoria] = 4;
cityMap[phoenix][pittsburgh] = 10;
cityMap[phoenix][pueblo] = 3;
cityMap[pierre][pendleton] = 2;
cityMap[pittsburgh][pensacola] = 4;
cityMap[princeton][pittsburgh] = 2;
cityMap[pueblo][pierre] = 3;
Typ stringVector je mapa celočíselně indexovaných řetězců. Typ
graf je dvourozměrné řídké pole, indexované řetězci a držící celočíselné
hodnoty. Sekvence přiřazovacích příkazů inicializuje graf.
Některé klasické algoritmy mohou být použity k manipulaci s grafy reprezentovanými
v tomto tvaru. Jedním příkladem je algoritmus nejkratší cesty od pana Daijkstra.
Algoritmus začíná ze specifikovaného města jako počátečního místa. priority_queue
párů vzdálenost/město je pak vytvořena a inicializována vzdálenostmi od
počátečního města k sobě samému. Definice pro páry dat vzdáleností je tato:
struct DistancePair {
unsigned int first;
string second;
DistancePair() : first(0) {
}
DistancePair(unsigned int f,
const string & s)
: first(f),
second(s) { }
};
bool operator < (const DistancePair &
lhs, const DistancePair & rhs)
{ return lhs.first < rhs.first;
}
V algoritmu, který následuje, si povšimněte, jak je podmíněný test
obrácen na prioritní frontu, protože v každém kroku vložíme menší a ne
větší hodnotu z kolekce. V každé iteraci cyklu vyřešíme jedno město z fronty.
Pokud k městu nenalezneme kratší cestu, pak současná vzdálenost je zaznamenána
a graf může počítat vzdálenosti z tohoto města do všech svých sousedních
měst. Tento proces pokračuje, dokud prioritní fronta není vyčerpaná.
void shortestDistance(graph & cityMap,
const string
& start, stringVector & distances)
{
// zpracování prioritní fronty
vzdáleností k městům
priority_queue<DistancePair,
vector<DistancePair>,
greater<DistancePair> > que;
que.push(DistancePair(0, start));
while (! que.empty()) {
// vyjmutí
nejbližšího města z fronty
int distance
= que.top().first;
string city
= que.top().second;
que.pop();
if (0 == distances.count(city))
{
distances[city] = distance;
const stringVector & cities = cityMap[city];
stringVector::const_iterator start = cities.begin();
stringVector::const_iterator stop = cities.end();
for (; start != stop; ++start)
que.push(DistancePair(distance + (*start).second,
(*start).first));
}
}
}
Povšimněte si, že tento relativně jednoduchý algoritmus používá vektory,
mapování, řetězce a prioritní fronty. Prioritní fronty budou popsány později.
-
Konkordance je abecední seznam slov v textu, které zobrazují čísla řádků
na kterých se každé slovo vyskytuje. Spustitelnou verzi tohoto programu
nalezneme v souboru concord.cpp. Uvidíme zde použití tříd kontejnerů
map
a multimap. Datové hodnoty budou udržovány v multimap indexovaném
řetězci (slovy) a držící celá čísla (čísla řádků). Je použito
multimap,
protože stejné slovo se může vyskytnout na několika řádcích. Jinou možností
by bylo použít map a jako přiřazené hodnoty použít množinu celočíselných
prvků.
class concordance {
typedef multimap<string,
int less <string> > wordDictType;
public:
void addWord (string, int);
void readText (istream &);
void printConcordance (ostream
&);
private:
wordDictType wordMap;
};
Vytváření konkordance je rozděleno do dvou kroků: nejdříve program
generuje konkordance (čtením řádku ze vstupního proudu), a pak program
vypisuje výsledky do výstupního proudu. To je provedeno ve dvou metodách
readText a printConcordance. První z nich je zapsána zde:
void concordance::readText (istream &
in)
{
string line;
for (int i = 1; getline(in,
line, '\n'); i++) {
allLower(line);
list<string>
words;
split (line,
" ,.;:", words);
list<string>::iterator
wptr;
for (wptr
= words.begin(); wptr != words.end(); ++wptr)
addWord(*wptr, i);
}
}
Řádky jsou čteny ze vstupního proudu po jednom. Text řádků je nejprve
převeden na malá písmena, a pak je řádek rozdělen do slov, pomocí funkce
split
(bude
popsána později). Každé slovo je pak vloženo do konkordance. Metoda použitá
pro přidávání hodnot do konkordance je tato:
void concordance::addWord (string word, int
line)
{
// vidíme, zda slovo se vyskytuje
v seznamu
// nejprve získáme rozsah položek
se stejným klíčem
wordDictType::iterator low =
wordMap.lower_bound(word);
wordDictType::iterator high
= wordMap.upper_bound(word);
// zjistíme, zda je již na stejném
řádku
for ( ; low != high; ++low)
if ((*low).second
== line)
return;
// není-li nalezeno, pak jej
přidáme
wordMap.insert(wordDictType::value_type(word,
line));
}
addWord zajišťuje aby slova nebyla duplikována, pokud se stejné
slovo vyskytne několikrát na stejném řádku.
Posledním krokem je výpis konkordance. To je provedeno takto:
void concordance::printConcordance (ostream
& out)
{
string lastword("");
wordDictType::iterator pairPtr;
wordDictType::iterator stop
= wordMap.end();
for (pairPtr = wordMap.begin();
pairPtr != stop; ++pairPtr)
//pokud slovo je stejné jako
předchozí, pak vypíšeme pouze číslo řádku
if (lastword
== (*pairPtr).first)
out << " " << (*pairPtr).second;
else {
// první výskyt slova
lastword = (*pairPtr).first;
cout << endl << lastword << ": " << (*pairPtr).second;
}
cout << endl; // ukončení
posledního řádku
}
Iterátor cyklu je použit k procházení prvky udržovanými seznamem slov.
Každé nové slovo generuje nový řádek výstupu - pak jsou zobrazena čísla
řádek oddělená mezerami. Pokud např. máme tento vstupní text:
It was the best of times,
it was the worst of times.
pak výstup bude vypadat takto:
best: 1
it: 1 2
of: 1 2
the: 1 2
times: 1 2
was: 1 2
worst: 1
-
Mnoho lidí má dobrou intuitivní představu o datových abstraktních typech
zásobník a fronta, založenou na základě každodenních experimentů s objekty.
Vzorovým příkladem zásobníku je hromada papíru na stole nebo sloupec talířů
v příborníku. V obou případech důležitou charakteristikou je to, že prvek
na vrcholu je nejsnadněji přístupný. Nejsnadnějším způsobem přidání nového
prvku do kolekce je jeho umístění nad všechny současné prvky v zásobníku.
Obdobně, prvek odstraňovaný ze zásobníku je prvek, který byl do zásobníku
vložen naposled; např. horní papír v hromadě nebo vrchní talíř ve sloupci.
Příkladem fronty na druhé straně je řada lidí čekajících na vstup do
divadla. Nově přicházející se stavějí na konec fronty, zatímco prvky jsou
odstraňovány z čela fronty, jak lidé vcházejí do divadla. Pořadí odstraňování
z fronty je opačné než u zásobníku. Ve frontě, odstraňovaný prvek je ten,
který byl ve frontě přítomen nejdelší dobu.
Ve standardní knihovně zásobníky i fronty jsou vytvořeny nad jinými
kontejnery, které jsou použity k aktuálnímu držení hodnot. Zásobník může
být vytvořen na vektoru, seznamu nebo deque, zatímco fronta může
být založena na seznamu nebo deque. Prvky držené zásobníkem nebo
frontou musí připouštěti operátory < a ==.
Protože ani zásobník ani fronta nedefinují iterátory, není možné zkoumat
prvky kolekce mimo odstraňování hodnot po jedné. Z tohoto důvodu také není
možno používat většinu obecných algoritmů.
-
Jako abstraktní datová struktura, zásobník je obvykle definován jako objekt,
který implementuje následující operace:
empty |
vrací true pokud kolekce je prázdná |
size |
vrací počet prvků kolekce |
top |
vrací (ale neodstraňuje) nejvrchnější prvek v zásobníku |
push |
vkládá nový prvek do zásobníku |
pop |
odstraňuje (ale nevrací) nejvrchnější prvek v zásobníku |
Program používající zásobník musí mimo hlavičkového souboru stack
vložit i hlavičkový soubor pro typ kontejneru, ve kterém zásobník je uložen
(např. vector):
# include <stack>
# include <vector>
-
Deklarace pro zásobník musí specifikovat dva parametry; typ prvku a kontejner,
který drží jeho prvky. Pro zásobník je nejvhodnějším kontejnerem vektor
nebo
deque, i když seznam může být také použit. Verze s vektorem
je obecně menší, zatímco verze s deque může být rychlejší. Následují
příklady deklarací zásobníků.
stack< int, vector<int> > stackOne;
stack< double, deque<double> > stackTwo;
stack< Part *, list<Part * > > stackThree;
stack< Customer, list<Customer> > stackFour;
Poslední příklad vytváří zásobník pro uživatelem definovaný typ nazvaný
Customer.
-
Klasická aplikace používající zásobník je kalkulátor. Vstup do kalkulátoru
tvoří textový řetězec, který reprezentuje výraz zapsaný v polské reverzní
notaci (PRN). Operandy, tj. celočíselné konstanty jsou vkládány do zásobníku
hodnot. Při nalezení operátoru, je příslušný počet operandů vyjmut ze zásobníku,
operace je provedena a výsledek je vložen zpět do zásobníku. Tento program
nalezneme v souboru calc.cpp.
Vývoj našeho programu můžeme rozdělit na dvě části: na kalkulační "stroj"
a program kalkulátoru. Stroj kalkulátoru je zaměřen na aktuální práci v
simulaci, ale neprovádí žádné operace vstupu nebo výstupu. Jméno je analogie
k motoru auta nebo procesoru počítače - je to mechanismus provádějící
aktuální práci, ale uživatel mechanismus normálně přímo nepoužívá. Toto
je zaobaleno kalkulačním programem, se kterým pracuje uživatel a předává
příslušné instrukce "stroji" kalkulátoru.
Pro náš stroj kalkulátoru můžeme použít následující definici třídy.
Uvnitř deklarace třídy definujeme výčet hodnot reprezentujících možné operace
kalkulátoru. Použijeme zde dvě zjednodušení: všechny operandy budou celočíselné
hodnoty a jsou zpracovávány pouze binární operátory.
class calculatorEngine {
public:
enum binaryOperator {plus, minus,
times, divide};
int currentMemory ()
// návrat současného vrcholu zásobníku
{ return data.top();
}
void pushOperand (int value)
// vložení hodnoty operandu do zásobníku
{ data.push
(value); }
void doOperator (binaryOperator);//
provedení operátoru
protected:
stack< int, vector<int>
> data;
};
Aktuální práci provádí metoda doOperator. Vybírá hodnoty ze
zásobníku, provede operaci a výsledek vloží zpět do zásobníku.
void calculatorEngine::doOperator (binaryOperator
theOp)
{
int right = data.top();
// přečtení vrchního prvku
data.pop();
// odstranění vrchního prvku ze zásobníku
int left = data.top();
// přečtení dalšího vrchního prvku
data.pop();
// jeho odstranění ze zásobníku
switch (theOp) {
case plus:
data.push(left + right); break;
case minus:
data.push(left - right); break;
case times:
data.push(left * right); break;
case divide:
data.push(left / right); break;
}
}
Hlavní program čte hodnoty v reverzní polské notaci a vyvolává "stroj"
kalkulátoru k provedení potřebné práce.
void main() {
int intval;
calculatorEngine calc;
char c;
while (cin >> c)
switch (c)
{
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
cin.putback(c);
cin >> intval;
calc.pushOperand(intval);
break;
case '+': calc.doOperator(calculatorEngine::plus);
break;
case '-': calc.doOperator(calculatorEngine::minus);
break;
case '*': calc.doOperator(calculatorEngine::times);
break;
case '/': calc.doOperator(calculatorEngine::divide);
break;
case 'p': cout << calc.currentMemory() << endl;
break;
case 'q': return; // ukončení programu
}
}
-
Abstraktní datový typ fronta je obvykle definován jako objekt, který implementuje
následující operace.
empty |
vrací true, pokud kolekce je prázdná |
size |
vrací počet prvků kolekce |
front |
vrací (ale neodstraňuje) prvek z čela fronty |
back |
vrací prvek na konci fronty |
push |
vkládá nový prvek na konec fronty |
pop |
odstraňuje (ale nevrací) prvek z čela fronty |
Program, který používá frontu, musí vložit hlavičkový soubor queue
a
také hlavičkový soubor pro typ kontejneru, ve kterém fronta je uložena
(např. list):
# include <queue>
# include <list>
-
Deklarace fronty musí specifikovat typ prvku a také kontejner, který drží
hodnoty. Pro frontu je nejvhodnějším kontejnerem seznam nebo deque.
Verze se seznamem je menší, zatímco verze s deque může být rychlejší.
Následují příklady deklarací:
queue< int, list<int> > queueOne;
queue< double, deque<double> > queueTwo;
queue< Part *, list<Part * > > queueThree;
queue< Customer, list<Customer> > queueFour;
Poslední příklad vytváří frontu programátorem definovaného typu nazvaného
Customer.
Stejně jako pro kontejner zásobníku, všechny objekty uložené do fronty
musí znát operátory < a ==.
-
S frontami se často setkáme při obchodování, jako jsou supermarkety nebo
banky. Předpokládejme, že jsme správcem banky, a že potřebujeme zjistit,
jak mnoho pokladníků pracuje během jisté hodiny. Můžeme vytvořit počítačovou
simulaci, založenou na simulaci jistého zjištěného chování zákazníků. Kompletní
verzi simulačního programu bankovního pokladníka nalezneme v souboru teller.cpp.
Nejprve vytvoříme objekty reprezentující zákazníky. Pro zákazníky zjišťujeme
průměrný čas, který stráví čekáním ve frontě. Objekty zákazníků jednoduše
udržují dvě celočíselné položky: čas příchodu do fronty a čas strávený
u pokladníka. Hodnota je náhodně vybírána mezi 2 a 8.
class Customer {
public:
Customer (int at = 0) : arrival_Time(at),
processTime(2 + randomInteger(6)) {}
int arrival_Time;
int processTime;
bool done()
// Je dokončena naše transakce?
{ return --processTime
< 0; }
operator < (const Customer
& c) // pořadí podle času příchodu
{ return arrival_Time
< c.arrival_Time; }
operator == (const Customer
& c) // dva zákazníci se neshodují
{ return false;
}
};
Pokud chceme objekty (v našem případě zákazníky) uložené v kontejnerech
standardní knihovny porovnávat a určovat jejich pořadí, pak pro ně musíme
definovat operátory < a ==. Zákazníci také mohou oznamovat, že dokončili
své transakce.
Pokladník obsluhuje zákazníka nebo je volný. Tedy objekt každého pokladníka
drží dvě datové položky: zákazníka a logický příznak. Pokladník definuje
metodu k dotázání zda je volný a metodu, která zahajuje obsluhu zákazníka.
class Teller {
public:
Teller() { free = true; }
bool isFree() //
může obsloužit nového zákazníka?
{ if (free)
return true;
if (customer.done())
free = true;
return free;
}
void addCustomer(Customer c)
// zahájení obsluhy nového zákazníka
{
customer = c;
free = false;
}
private:
bool free;
Customer customer;
};
Hlavní program je velký cyklus, procházející každou simulovanou minutou.
Každou minutu nový zákazník s pravděpodobností 0.9 vstoupí do fronty čekajících
zákazníků. Každý pokladník je dotázán, zda je volný a pokud ano, pak přebírá
dalšího zákazníka z fronty. Jsou počítány počty obsloužených zákazníků
a celkový čas strávený ve frontě. Z těchto dvou hodnot můžeme určit průměrný
čas strávený zákazníkem ve frontě.
void main() {
int numberOfTellers = 5;
int numberOfMinutes = 60;
double totalWait = 0;
int numberOfCustomers = 0;
vector<Teller> teller(numberOfTellers);
queue< Customer, deque<Customer>
> line;
for (int time = 0; time <
numberOfMinutes; time++) {
if (randomInteger(10)
< 9)
line.push(Customer(time));
for (int i
= 0; i < numberOfTellers; i++) {
if (teller[i].isFree() & ! line.empty()) {
Customer & frontCustomer = line.front();
numberOfCustomers++;
totalWait += (time - frontCustomer.arrival_Time);
teller[i].addCustomer(frontCustomer);
line.pop();
}
}
}
cout << "average wait:"
<<
(totalWait / numberOfCustomers) << endl;
}
Program spustíme několikrát, s použitím různých počtů pokladníků a
můžeme se pokusit nalézt nejmenší počet pokladníků, kteří dokáží obsloužit
zákazníky s přípustnou dobou čekání ve frontě.
-
Prioritní fronta je datová struktura užitečná pro problémy, kde je zapotřebí
rychle a opakovaně nalézt a odstranit největší prvek z kolekce hodnot.
Každodenním příkladem prioritní fronty je seznam úkolů čekajících na provedení.
Některé úlohy nejsou důležité a mohou být odloženy, jiné je nutno provést
co nejdříve. Úlohy čekající na provedení tedy můžeme seřadit podle důležitosti
(naléhavosti), a pak je provádíme v tomto pořadí.
Příkladem více se týkajícím počítačů, je údržba seznamu procesů čekajících
na zpracování, kde hodnota přiřazená ke každému prvku je priorita úlohy.
Např. je nutné rychle reagovat na stisknutí klávesy na terminálu, dříve
než data jsou ztracena (přepsána) stiskem následující klávesy. Na druhé
straně proces kopírování výstupní fronty na tiskárnu může být zpracován
někdy později. Údržba procesů v prioritní frontě má nejvyšší prioritu a
musí být provedena dříve než cokoliv jiného.
Simulační program používá prioritní frontu "budoucích událostí". Simulace
udržuje virtuální hodiny a každá událost má přiřazený čas, kdy může nastat.
V této kolekci, prvek s nejmenší hodnotou času je následující událost,
která bude simulována. Jsou některé typy problémů, kde prioritní fronta
je užitečným nástrojem.
Program, který používá datový typ prioritní fronty musí vložit hlavičkový
soubor queue a také hlavičkový soubor s typem kontejnerů (např.
vector):
# include <queue>
# include <vector>
-
Prioritní fronta je datová struktura, která implementuje následujících
pět operací:
push |
Přidává novou hodnotu do kolekce |
top |
Vrací odkaz na nejmenší prvek v kolekci |
pop |
Ruší nejmenší prvek v kolekci |
size |
Vrací počet prvků v kolekci |
empty |
Vrací true, pokud kolekce je prázdná |
Typ prvku prioritní fronty musí být porovnatelný s ostatními, a to pomocí
implicitního operátoru menší než nebo pomocí porovnávací funkce předané
jako parametr šabloně nebo jako volitelný parametr konstruktoru. Jako u
všech kontejnerů ve standardní knihovně, má i prioritní fronta dva konstruktory.
Implicitní konstruktor je bez parametrů nebo jako volitelný parametr je
mu předána porovnávací funkce. Alternativní konstruktor přebírá dvojici
iterátorů a inicializuje hodnoty kontejneru z jiné sekvence. I zde může
být volitelný třetí parametr s porovnávací funkcí.
Datový typ prioritní fronty je vytvořen na třídě kontejneru, jejíž
struktura je použita k udržování hodnot v kolekci. Ve standardní knihovně
jsou dva kontejnery, které mohou být použity pro vytvoření prioritní fronty:
vektory a deque.
Následující ukázky ukazují deklarace několika prioritních front:
priority_queue< int, vector<int> >
queue_one;
priority_queue< int, vector<int>, greater<int>
> queue_two;
priority_queue< double, deque<double>
>
queue_three(aList.begin(),
aList.end());
priority_queue< eventStruct, vector<eventStruct>
>
queue_four(eventComparison);
priority_queue< eventStruct, deque<eventStruct>
>
queue_five(aVector.begin(),
aVector.end(), eventComparison);
Fronty vytvořené na vektorech mohou být někdy menší, zatímco fronty
vytvořené na deque mohou být rychlejší. Tyto rozdíly jsou ale nepatrné.
Protože datová struktura prioritní fronty nedokáže vytvářet iterátory
není s ní možno používat obecné algoritmy.
Prioritní fronty jsou interně implementovány na datové struktuře nazvané
hromada. Abstraktně je hromada binární strom, ve kterém každý uzel má vlastnost,
kde hodnota přiřazená k uzlu je menší nebo rovna než hodnota přiřazená
ve každému podřízenému uzlu.
-
Následující příklad ukazuje použití prioritní fronty. Příklad ukazuje jedno
z možných použití prioritní fronty pro podporu vytváření simulačního modelu.
Diskrétní událostmi řízená simulace je populární simulační technikou.
Objekty v simulačním modelu objektů z reálného světa jsou naprogramovány
tak, aby se chovaly jako reálné objekty. Prioritní fronta je použita k
uložení reprezentace událostí, které jsou očekávány. Tato fronta je uložena
v pořadí, určeném časem vzniku události, a tak nejmenší prvek je vždy následující
modelovanou událostí. Po vzniku události může přijít na řadu další událost.
Tato sekvence událostí je umístěna do fronty. Provádění probíhá dokud všechny
události nejsou zpracovány.
Události mohou být reprezentovány jako podtřídy základní třídy, kterou
nazveme event. Základní třída pouze zaznamenává čas, kdy byla umístěna.
Čirá virtuální funkce nazvaná processEvent bude vyvolána k provedení
události.
class event {
public:
event (unsigned int t) : time(t)
{ }
const unsigned int time;
virtual void processEvent()
= 0;
};
Simulační fronta musí udržovat kolekci různých typů událostí. Každá
odlišná forma události bude reprezentována jinou podtřídou třídy event.
Ne všechny události musí být stejného typu, i když všechny jsou podtřídami
třídy event. Z tohoto důvodu kolekce musí ukládat ukazatele na události,
místo událostí samotných.
Jelikož porovnávání ukazatelů nemůže být založeno na typech ukazatelů,
musíme definovat novou porovnávací funkci pro ukazatele na události. Ve
standardní knihovně je to řešeno definováním nové struktury, ve které definujeme
operátor (). Protože v tomto konkrétním příkladě používáme prioritní frontu
k návratu nejmenšího prvku místo největšího, pořadí porovnávání je určeno
takto:
struct eventComparison {
bool operator () (event * left,
event * right) const
{ return left->time
> right->time; }
};
Nyní již můžeme definovat třídu simulation, která poskytne strukturu
pro simulační aktivity. Tato třída poskytuje dvě metody. První je použita
pro vkládání nové události do fronty, zatímco druhá spouští simulaci. Je
zde také datová položka k uložení současného času simulace.
class simulation {
public:
simulation () : eventQueue(),
time(0) { }
void scheduleEvent (event *
newEvent)
{ eventQueue.push
(newEvent); }
void run();
unsigned int time;
protected:
priority_queue<event *, vector<event
*>, eventComparison> eventQueue;
};
Povšimněte si deklarace prioritní fronty použité k uložení událostí.
V našem případě je pro uložení fronty použit vektor. Úplně stejným způsobem
může být použita deque.
Jádrem simulace je metoda run, která definuje cyklus událostí.
Tato metoda používá tři z pěti operací prioritní fronty: top,
pop
a empty. Je implementována takto:
void simulation::run()
{
while (! eventQueue.empty())
{
event * nextEvent
= eventQueue.top();
eventQueue.pop();
time = nextEvent->time;
nextEvent->processEvent();
delete nextEvent;
// uvolnění paměti použité událostí
}
}
K ilustraci použití simulačního rámce vytvoříme jednoduchou simulaci
prodejny zmrzliny. Celý program nalezneme v souboru icecream.cpp.
Simulaci můžeme použít např. k určení optimálního počtu poskytnutých židlí
na základě předpokládané frekvence příchodů zákazníků, délky jejich setrvání
v prodejně apod.
Naše simulace může být založena na podtřídě třídy simulation,
definované takto:
class storeSimulation : public simulation
{
public:
storeSimulation()
: freeChairs(35),
profit(0.0), simulation() { }
bool canSeat (unsigned int numberOfPeople);
void order(unsigned int numberOfScoops);
void leave(unsigned int numberOfPeople);
private:
unsigned int freeChairs;
double profit;
} theSimulation;
Jsou zde tři základní aktivity. Jsou to příchody, objednávání a jedení
a odchody. To je zohledněno nejen ve třech metodách definovaných ve třídě
simulace, ale i ve třech samostatných podtřídách událostí.
Metody zjednodušují záznam provedených aktivit a produkují deník činností,
který může být později studován k ověření simulace.
bool storeSimulation::canSeat (unsigned int
numberOfPeople)
{
cout << "Time: " <<
time;
cout << " group of " <<
numberOfPeople << " customers arrives";
if (numberOfPeople < freeChairs)
{
cout <<
" is seated" << endl;
freeChairs
-= numberOfPeople;
return true;
}
else {
cout <<
" no room, they leave" << endl;
return false;
}
}
void storeSimulation::order (unsigned int
numberOfScoops)
{
cout << "Time: " <<
time;
cout << " serviced order
for " << numberOfScoops << endl;
profit += 0.35 * numberOfScoops;
}
void storeSimulation::leave (unsigned int
numberOfPeople)
{
cout << "Time: " <<
time;
cout << " group of size
" << numberOfPeople <<
" leaves" << endl;
freeChairs += numberOfPeople;
}
Jak již bylo uvedeno, každá aktivita je vyřešena podtřídou události.
Každá tato podtřída obsahuje celočíselnou datovou položku, která reprezentuje
velikost skupiny zákazníků. Událost arriveEvent nastane, když skupina
vstoupí. Když je prováděna, pak vytváří a instaluje novou instanci události
orderEvent.
Funkce randomInteger je použita k výpočtu náhodného celého čísla
mezi 1 a hodnotou parametru.
class arriveEvent : public event {
public:
arriveEvent (unsigned int time,
unsigned int groupSize)
: event(time),
size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void arriveEvent::processEvent()
{
// pokud si můžeme sednout
if (theSimulation.canSeat(size))
theSimulation.scheduleEvent
(new orderEvent(time + 1 + randomInteger(4), size));
}
Událost orderEvent podobně vytváří událost leaveEvent.
class orderEvent : public event {
public:
orderEvent (unsigned int time,
unsigned int groupSize)
: event(time),
size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void orderEvent::processEvent()
{ // každá osoba
si objedná nějaký počet kopečků zmrzliny
for (int i = 0; i < size;
i++)
theSimulation.order(1
+ rand(3));
theSimulation.scheduleEvent
(new leaveEvent(time
+ 1 + randomInteger(10), size));
};
Nakonec, událost leaveEvent uvolňuje židle, ale již nevytváří
nové události.
class leaveEvent : public event {
public:
leaveEvent (unsigned int time,
unsigned int groupSize)
: event(time),
size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void leaveEvent::processEvent ()
{
// uvolnění židlí
theSimulation.leave(size);
}
Ke spuštění simulace vytvoříme nějaký počet počátečních událostí (např.
na 30 minut), a pak vyvoláme metodu run.
void main() {
// zavedení fronty několika
počátečních událostí
unsigned int t = 0;
while (t < 30) {
t += rand(6);
theSimulation.scheduleEvent(
new arriveEvent(t, 1 + randomInteger(4)));
}
theSimulation.run();
cout << "Total profits
" << theSimulation.profit << endl;
}
-
Řetězce jsou v podstatě indexované sekvence znaků. I když řetězec není
deklarován jako podtřída vector, většina operací vektoru je použitelná
i na řetězcové hodnoty (jsou zde i další užitečné operace). Ve standardní
knihovně, je řetězec šablona třídy nazvaná basic_string. Parametr
šablony reprezentuje typ znaků, které budou drženy kontejnerem. Standardní
knihovna poskytuje nejen služby pro manipulaci s normálními 8 bitovými
ASCII znaky, ale také pro manipulaci s ostatními typy znaků, jako je sekvence
16 bitových širokých znaků. Datové typy string a wstring
jsou pomocí basic_string definovány takto:
typedef basic_string<char> string;
typedef basic_string<wchar_t> wstring;
Řetězce se v mnoha směrech podobají vektoru znaků. Podobně jako datový
typ vektor, má i řetězec přiřazené dvě velikosti. První reprezentuje počet
znaků právě uložených do řetězce. Druhý je kapacita, tj. maximální počet
znaků, které mohou být uloženy v řetězci bez nutnosti realokace nové interní
vyrovnávací paměti. Kapacita řetězce se může dynamicky měnit (při vkládání
znaků do řetězce se zvětšuje).
Programy, které používají řetězce musí vložit hlavičkový soubor string:
# include <string>
Nejjednodušším tvarem deklarace řetězce je jméno nové proměnné nebo
jméno proměnné společně s novou hodnotou pro řetězec. Je také možno používat
kopírovací konstruktor.
string s1;
string s2 ("a string");
string s3 = "initial value";
string s4 (s3);
V těchto jednoduchých případech, se původní kapacita rovná počtu uložených
znaků. Alternativní konstruktory umožňují specifikovat počáteční kapacitu.
Jinou možností je nastavení kapacity a inicializace řetězce několikanásobnou
kopií jednoho znaku.
string s6 ("small value", 100);//drží 11
hodnot a může jich obsahovat až 100
string s7 (10, '\n');
//drží 10x znak nového řádku
Jako všechny třídy kontejnerů ve standardní knihovně i řetězce mohou
být inicializovány dvojicí iterátorů. Sekvence určená iterátory musí být
vhodného typu.
string s8 (aList.begin(), aList.end());
Jako u datového typu vector, současnou velikost řetězce zjistíme
metodou size, zatímco kapacitu metodou capacity. Metodou
reserve
můžeme provést zvětšení kapacity. Metoda max_size vrací maximální
použitelnou kapacitu řetězce. Tato hodnota je omezena pouze množstvím dostupné
paměti.
cout << s6.size() << endl;
cout << s6.capacity() << endl;
s6.reserve(200);
// změna kapacity na 200
cout << s6.capacity() << endl;
cout << s6.max_size() << endl;
Metoda length je pouhým synonymem pro size. Metoda resize
mění velikost řetězce, a to odříznutím koncových znaků nebo vložením nových
znaků. Volitelný druhý parametr resize může být použit ke specifikaci
vkládaného znaku na nově vytvořené znakové pozice.
s7.resize(15, '\t');
cout << s7.length() << endl;
Metoda empty vrací true, pokud řetězec je prázdný.
if (s7.empty()) cout << "string is
empty" << endl;
Proměnné řetězce může být přiřazen jiný řetězec, řetězcová konstanta
nebo samostatný znak.
s1 = s2;
s2 = "a new value";
s3 = 'x';
K připojení řetězce k řetězci již uloženému v proměnné, je také možno
použít operátor +=. Např.
s3 += "yz";
// s3 je nyní xyz
Lze také používat obecnější metody assign a append, které
umožňují specifikovat přiřazovanou nebo přidávanou podmnožinu (pomocí pozice
a počtu znaků).
s4.assign (s2, 0, 3);
// přiřazení prvních tří znaků
s4.append (s5, 2, 3);
// přidání druhého, třetího a čtvrtého znaku
Pro spojení dvou řetězců je možno použít operátor +. Tento operátor
vytváří kopii prvního operandu a připojuje k němu druhý operand.
cout << (s2 + s3) << endl;
// výstup spojení s2 a s3
Metoda swap umožňuje výměnu dvou řetězců.
s5.swap (s4);
// výměna s4 a s5
K jednotlivým znakům v řetězci můžeme přistupovat operátorem indexace.
Ke stejnému účelu je možno použít i metodu at (není zde generována
výjimka out_of_range při překročení velikosti).
cout << s4[2] << endl;
// výstup pozice 2 ze s4
s4[2] = 'x';
// změna pozice 2
cout << s4.at(2) << endl;
// výstup změněné hodnoty
Metoda c_str vrací ukazatel na nulou ukončený řetězec, jehož
prvky jsou stejné jako jsou v řetězci. To umožňuje převést řetězec na styl
C a předávat jej jako parametr funkcím, které to vyžadují.
Metody begin a end vracejí počáteční a koncový iterátor
náhodného přístupu pro řetězec. Hodnoty určené iterátory jsou jednotlivé
znaky řetězce. Metody rbegin a rend vytvářejí reverzní iterátory.
Metody insert a erase se podobají stejnojmenným metodám
vektoru (jako parametr je možno také použít iterátor nebo dvojici iterátorů).
Funkce replace je kombinace erase a insert a nahrazuje
specifikovaný rozsah novou hodnotou.
s2.insert(s2.begin()+2, aList.begin(), aList.end());
s2.erase(s2.begin()+3, s2.begin()+5);
s2.replace(s2.begin()+3, s2.begin()+6, s3.begin(),
s3.end());
Tyto funkce jsou i bez implementace iterátorů. Metoda insert
přebírá jako parametr pozici a řetězec a vkládá řetězec na danou pozici.
Funkce erase přebírá dva celočíselné parametry: pozici a délku a
odstraňuje specifikované znaky. Funkce replace přebírá dva podobné
celočíselné parametry a řetězec a nahrazuje specifikovaný rozsah řetězcem.
s3.insert (3, "abc");
// vložení abc za pozici 3
s3.erase (4, 2);
// odstranění pozic 4 a 5
s3.replace (4, 2, "pqr"); // nahrazení
pozic 4 a 5 hodnotou pqr
Metoda copy generuje podřetězec a přiřazuje jej prvnímu parametru.
Rozsah hodnot podřetězce je určen počáteční pozicí nebo pozicí a délkou.
s3.copy (s4, 2);
// přiřazení s4 od druhé pozice do konce s3
s5.copy (s4, 2, 3); //
přiřazení s4 druhé až čtvrté pozici s5
Metoda substr vrací řetězec, který je částí současného řetězce.
Rozsah je specifikován počáteční pozicí nebo pozicí a délkou.
cout << s4.substr(3) << endl;
cout << s4.substr(3, 2) << endl;
Metoda compare slouží k lexikografickému porovnávání řetězce
objektu a parametru. Volitelné parametry umožňují specifikovat jinou počáteční
pozici nebo počáteční pozici a délku řetězce. Funkce vrací zápornou hodnotu,
pokud objekt je lexikograficky menší než parametr, nulu pokud si jsou rovny
a kladnou hodnotu, když objekt je větší než parametr. Je možno také používat
operátory relace a rovnosti. Porovnávání může probíhat mezi dvěma řetězci
nebo mezi řetězcem a normální řetězcovou konstantou jazyka C.
Metoda find určuje první výskyt řetězce parametru v současném
řetězci. Volitelný celočíselný parametr umožňuje specifikovat počáteční
pozici hledání (nezapomeňte, že indexy řetězce začínají od nuly). Pokud
řetězec je nalezen, pak je vrácen počáteční index nalezeného řetězce. Jinak
je vrácená hodnota mimo rozsah přípustných indexů. Metoda rfind
je podobná, ale hledání začíná od konce řetězce.
s1 = "mississippi";
cout << s1.find("ss") << endl;
// vrací 2
cout << s1.find("ss", 3) << endl;
// vrací 5
cout << s1.rfind("ss") << endl;
// vrací 5
cout << s1.rfind("ss", 4) <<
endl; // vrací 2
Funkce find_first_of, find_last_of, find_first_not_of
a find_last_not_of berou řetězec parametru jako množinu znaků. Jako
v mnoha ostatních funkcích, jeden nebo dva volitelné celočíselné parametry
mohou být použity ke specifikaci podřetězce současného řetězce. Tyto funkce
hledají první (nebo poslední) znak, který je přítomen (nebo nepřítomen)
v množině parametru. Je vrácena pozice daného znaku (je-li nalezen). Jestliže
daný znak neexistuje, pak je vrácena hodnota mimo přípustný rozsah indexu.
i = s2.find_first_of ("aeiou");
// první samohláska
j = s2.find_first_not_of ("aeiou", i);
// následující souhláska
-
Nyní si ukážeme použití některých řetězcových funkcí k definování funkce,
která rozloží řádek textu na jednotlivá slova. Tato funkce byla použita
v našem programu na zpracování konkordance. Nalezneme ji v souboru concord.cpp.
Funkce má tři parametry. První dva jsou řetězce, popisující řádek textu
a oddělovače slov a třetí je seznam řetězců, který bude použit k návratu
jednotlivých slov řádku.
void split(string & text, string &
separators, list<string> & words)
{
int n = text.length();
int start, stop;
start = text.find_first_not_of(separators);
while ((start >= 0) &&
(start < n)) {
stop = text.find_first_of(separators,
start);
if ((stop
< 0) || (stop > n)) stop = n;
words.push_back(text.substr(start,
stop - start));
start = text.find_first_not_of(separators,
stop+1);
}
}
Funkce začíná nalezením prvního znaku, který není oddělovačem. V cyklu
je pak hledán následující znak, který je oddělovačem, nebo se použije konec
řetězce, pokud oddělovač není nalezen. Rozdíl mezi těmito dvěmi separátory
je slovo a jeho kopie je vložena do seznamu slov. Hledání pak nalezne začátek
dalšího slova a cyklus pokračuje. Po dosažení konce řetězce zpracování
končí.
-
Třída complex je šablona třídy použitelná k vytváření objektů pro
reprezentaci a manipulaci s komplexními čísly. Operace definované na komplexních
číslech pak mohou být snadno míchány s ostatními číselnými typy dostupnými
v C++. Program, který používá komplexní čísla musí vložit hlavičkový soubor
complex.
# include <complex>
Parametr šablony je použit k určení typu reálné a imaginární složky.
Musí se jednat o float, double nebo long double. Třída
má
několik konstruktorů. Konstruktor bez parametrů inicializuje obě složky
komplexního čísla nulou. Konstruktor s jedním parametrem inicializuje reálnou
část a imaginární je nulová. Konstruktor se dvěmi parametry inicializuje
reálnou i imaginární část. Kopírovací konstruktor můžeme použít k inicializaci
komplexního čísla jiným komplexním číslem.
complex<double> com_one;
// hodnota 0 + 0i
complex<double> com_two(3.14);
// hodnota 3.14 + 0i
complex<double> com_three(1.5, 3.14)
// hodnota 1.5 + 3.14i
complex<double> com_four(com_two);
// hodnota je také 3.14 + 0i
Komplexnímu číslu lze přiřadit hodnotu jiného komplexního čísla. Komplexnímu
číslu můžeme přiřadit také hodnotu reálného čísla. Reálná složka získá
přiřazovanou hodnotu zatímco imaginární část je nastavena na nulu.
com_one = com_three;
// získá 1.5 + 3.14i
com_three = 2.17;
// získá 2.17 + 0i
Funkce polar může být použita k vytvoření komplexního čísla
z dané amplitudy a fázového úhlu.
com_four = polar(5.6, 1.8);
K vytvoření komplexně sdruženého čísla lze použít funkci conj.
Pokud komplexní číslo reprezentuje x + iy, pak funkce nám dodá x
- iy.
complex<double> com_five = conj(com_four);
Metody real a image vracejí reálnou a imaginární část
komplexního čísla. Tyto funkce lze také použít jako normální funkce s komplexním
parametrem.
cout << com_one.real() << "+" <<
com_one.imag() << "i" << endl;
cout << real(com_one) << "+" <<
imag(com_one) << "i" << endl;
Aritmetické operátory +, - * a / mohou být použity k provádění sčítání,
odčítání, násobení a dělení komplexních čísel. Všechny čtyři pracují se
dvěmi komplexními čísly nebo s komplexním číslem a reálným číslem. Přiřazovací
operátory jsou také definovány pro všechny čtyři operátory.
cout << com_one + com_two <<
endl;
cout << com_one - 3.14 << endl;
cout << 2.75 * com_two << endl;
com_one += com_three / 2.0;
S komplexními čísly lze také použít unární operátory + a -.
Dvě komplexní čísla mohou být porovnávána na rovnost nebo nerovnost
pomocí operátorů == a !=. Ostatní relační operátory nelze pro komplexní
čísla použít.
Komplexní čísla mohu být zapisována do výstupního proudu nebo čtena
ze vstupního proudu a to běžným způsobem. Hodnoty jsou zapisovány v závorkách
jako (u) nebo (u,v), v závislosti na tom, zda imaginární část je nebo není
nulová. Čtené hodnoty musí být uzavřeny v závorkách (dvě číselné hodnoty).
S komplexními čísly lze používat i funkce norm a abs.
Jedná se o normalizaci a absolutní hodnotu komplexního čísla.
cout << norm(com_two) << endl;
cout << abs(com_two) << endl;
Pro převod na polární souřadnice je možno využít funkci arg.
cout << com_four << " v polárních
souřadnicích je "
<< arg(com_four)
<< " a " << norm(com_four) << endl;
Trigonometrické funkce definované pro reálná čísla (sin,
cos,
tan,
sinh,
cosh
a tanh) jsou rozšířena i na komplexní argumenty. Všechny přebírají
jako parametr komplexní číslo a jako výsledek vracejí komplexní číslo.
Totéž platí o funkcích exp,
sqrt,
log a log10.
Standardní knihovna obsahuje také několik verzí funkce
pow. Umožňují
umocnit komplexní číslo na celé číslo, komplexní číslo na komplexní číslo
nebo reálné číslo a reálnou hodnotu na komplexní číslo.
-
Následuje program řešící kvadratickou rovnici v oboru komplexních čísel.
Tento program nalezneme v souboru complx.cpp. Program přebírá tři
hodnoty double a vrací komplexní kořeny jako dvojici hodnot.
typedef complex<double> dcomplex;
pair<dcomplex, dcomplex> quadratic
(dcomplex
a, dcomplex b, dcomplex c)
{
dcomplex root = sqrt(b * b -
4.0 * a * c);
a *= 2.0;
return make_pair(
(-b + root)/a,
(-b - root)/a);
}
-
Novým rysem standardní knihovny je mechanismus pro popis charakteristik
základních typů poskytnutých prováděcím prostředím. Ve starších knihovnách
tyto charakteristiky byly často popsány jako velká kolekce symbolických
konstant. Např. nejmenší reprezentovatelnou hodnotu, která může být udržována
ve znaku můžeme nalézt v konstantě nazvané CHAR_MIN, zatímco podobnou konstantu
pro short známe jako SHRT_MIN apod.
Šablona třídy numeric_limits poskytuje nový způsob reprezentace
těchto informací pro všechny numerické typy. Místo použití různých symbolických
jmen pro každý nový datový typ, třída definuje jednu statickou funkci nazvanou
min,
která vrací příslušné hodnoty. Specializací této třídy pak poskytneme přesné
hodnoty pro každý podporovaný typ. Nejmenší hodnotu znaku zjistíme vyvoláním
funkce numeric_limits<char>::min(), zatímco nejmenší hodnotu
pro typ float získáme vyvoláním numeric_limits<float>::min(),
atd. Tím sice není omezen počet symbolických jmen potřebných k popisu operačního
prostředí, ale je zajištěna konzistentnost mezi popisy různých typů.
Standardní knihovna popisuje poskytnutím implementace třídy numeric_limits
pro specifikovaný typ. Statické funkce a statické konstantní datové složky
pak poskytují informace pro typ. Standardní knihovna zahrnuje popisy pro
následující základní datové typy.
bool |
char |
int |
float |
|
signed char |
short |
double |
|
unsigned char |
long |
long double |
|
wchar_t |
unsigned short |
|
|
|
unsigned int |
|
|
|
unsigned long |
|
Některé implementace mohou také poskytovat informace i o jiných datových
typech. Pro datové typy, které nemají specializaci jsou obecně vraceny
hodnoty 0 nebo false.
Následující tabulka uvádí informace dostupné statickými datovými složkami
a metodami numeric_limits (T je typ pro který zjišťujeme
informace).
Typ |
Jméno |
Význam |
bool |
is_specialized |
true, pokud specializace existuje, jinak false. |
T |
min() |
Nejmenší možná hodnota. |
T |
max() |
Největší možná hodnota. |
int |
radix |
Základ reprezentace. |
int |
digits |
Počet číslic, které mohou být reprezentovány hodnotou. |
int |
digits10 |
Počet číslic základu 10, které mohou být reprezentovány hodnotou. |
bool |
is_signed |
true, pokud typ je znaménkový. |
bool |
is_integer |
true, pokud typ je celočíselný. |
bool |
is_exact |
true, pokud reprezentace je přesná. |
bool |
is_bounded |
true, pokud reprezentace je omezená. |
bool |
is_modulo |
true, pokud typ je modulo (součet dvou kladných hodnot může
být oříznut a výsledek je menší než operandy). Základní celočíselné typy
jsou modulo. |
bool |
traps |
true, pokud pro typ je implementována záloha. |
radix reprezentuje interní základ pro reprezentaci. Např. většina
počítačů používá základ 2 pro celočíselné hodnoty, nicméně některé počítače
mohou také podporovat jinou reprezentaci, jako je BCD, která používá jiný
základ. Položka digits pak reprezentuje počet číslic (o daném základu),
které mohou být drženy v hodnotě. Pro celočíselné typy to je počet neznaménkových
bitů reprezentace. Všechny základní typy jsou omezené. Implementace ale
může obsahovat např. hodnotu pro nekonečno a pak typ není omezený.
Následující metody jsou specifické pro reálné hodnoty nebo pro reálné
hodnoty mají jiný význam než je uvedeno v předchozí tabulce.
Typ |
Jméno |
Význam |
T |
min() |
Minimální kladná normalizovaná hodnota. |
int |
digits |
Počet číslic v mantise. |
int |
radix |
Základ reprezentace exponentu. |
T |
epsilon() |
Rozdíl mezi 1 a reprezentací nejbližší hodnoty větší než 1. |
T |
round_error() |
Jednotka zaokrouhlovací chyby. |
int |
min_exponent |
Minimální záporný exponent. |
int |
min_exponent10 |
Minimální hodnota umocněná na 10, která je v rozsahu. |
int |
max_exponent |
Maximální kladný exponent. |
int |
max_exponent10 |
Maximální hodnota umocněná na 10, která je v rozsahu. |
bool |
has_infinity |
true, pokud je reprezentace pro kladné nekonečno. |
T |
infinity() |
Reprezentace nekonečna (je-li dostupná). |
bool |
has_quiet_NaN |
true, pokud je reprezentace nečísla (NaN). |
T |
quiet_NaN() |
Reprezentace NaN (je-li dostupné). |
bool |
has_signaling_NaN |
true, pokud je reprezentace pro signalizaci NAN. |
T |
signaling_NaN() |
Reprezentace signalizace NAN (je-li dostupná). |
bool |
has_denorm |
true, pokud reprezentace umožňuje nenormalizované hodnoty. |
T |
denorm_min() |
Minimální kladná nenormalizovaná hodnota. |
bool |
is_iec559 |
true, pokud reprezentace odpovídá standardu IEC 559. |
bool |
tinyness_before |
true, pokud před zaokrouhlením je detekováno nejmenší. |
|
round_style |
Zaokrouhlovací styl pro typ. |
Pro datový typ float hodnota v položce radix, která reprezentuje
základ exponenciální reprezentace, je ekvivalentní se symbolickou konstantou
FLT_RADIX. Pro datové typy float, double a long double
hodnota epsilon je také dostupná jako FLT_EPSILON, DBL_EPSILON a
LDBL_EPSILON.
NaN je "Not a Number". Je to hodnota, která neodpovídá žádné
číselné hodnotě. Mnoho numerických algoritmů používá tuto hodnotu.
Standard IEC 559 je standard poskytnutý International Electrotechnical
Commission. Je totožný se standardem IEEE 754.
Hodnota vrácená funkcí round_style() je jedna z následujících
hodnot: round_indeterminate, round_toward_zero, round_to_nearest,
round_toward_infinity
nebo round_toward_neg_infinity.