PB161 – Programování v jazyku C++
●
Textové řetězce (2. část)
●
Vstupy a výstupy
●
●
Základ (0. část)
●
Manipulátory
STL ●
Kontejnery
●
Iterátory
●
Algoritmy
Řetězce ve stylu C++ ●
Používá se třída „string“. Řetězec ve stylu C++ již není obyčejné pole znaků, je to objekt.
●
Definována řada operátorů
●
●
●
Definována řada metod ●
●
==, !=, <, >, <=, >=, +, <<, >>, =, [] append(), at(), begin(), c_str(), clear(), compare(), empty(), end(), erase(), find(), find_first_of, getline(), length(), push_back, replace(), substr(), …
http://www.cppreference.com/cppstring/index.html
Řetězce ve stylu C++ (2) string s = "Ahoj jak se mas"; ● append() s.append("012345", 1,3); ●
s obsahuje „Ahoj jak se mas123“
s.append(5, '#'); ●
●
s obsahuje „Ahoj jak se mas#####“
clear(), empty(), erase() s.empty() // false s.erase(3,3); ●
s obsahuje „Ahoak se mas“
s.clear(); s.empty() // true
Řetězce ve stylu C++ (3) string s = "Ahoj jak se mas"; ●
find(), find_first_of(), find_first_not_of() s.find("jak") // 5 s.find("ada") == string::npos // true s.find("ada") >= s.length() // true int(string::npos) // 1 s.find_first_of("*jas") // 3 s.find_first_not_of("*jas") // 0
●
replace() s.replace(0, 4, "Zdarec,"); ●
s obsahuje „Zdarec, jak se mas“
Vstupy, výstupy ios_base istream
●
istream ● ●
●
iostream
vstupní operace, např. >> instance: cin
ostream ● ●
●
ostream
výstupní operace, např. << instance: cout, cerr, clog
instance cin, cout, … definovány v
Vstupy, výstupy – manipulátory ●
●
Hlavičkový soubor Vkládají se „mezi“ operátory vstupu a výstupu (dojde k volání funkce). ● ●
●
Prototyp jednoduchého manipulátoru ●
●
cout<<"|"<<setw(10)<<"ahoj"<<"|"<<endl; vypíše „| ahoj|“ ostream& manipulator (ostream&);
Většina manipulátorů má platnost až do změny ● nastaví „stav“ proudu ● (neplatí pro setw)
Vstupy, výstupy – manipulátory (2) ●
boolalpha/noboolalpha ●
●
true, false / 1,0
left/right ●
zarovnání vlevo/zarovnání vpravo cout<
Ahoj 145 145
Vstupy, výstupy – manipulátory (3) ●
fixed ●
●
scientific ●
●
výstupy budou v osmičkové, šestnáctkové soustavě
setbase(n) ●
●
reálná čísla ve „vědeckém“ tvaru
oct, hex ●
●
reálná čísla s pevnou řádovou čárkou
určuje (0, 8, 10, 16) číselnou soustavu
endl ●
zapíše konec řádku ('\n')
Vstupy, výstupy – manipulátory (4) ●
setprecision(n) ●
●
setfill(int n) ● ●
●
výplňový znak např. u setw(), jeli vstup kratší
flush ●
●
přesnost
vyprázdní buffer
skipws/noskipws ●
přeskakuj/nepřeskakuj bílé znaky
Vstupy, výstupy – manipulátory (5) ●
skipws/noskipws
char c;
char c;
while (cin >> c) cout <
cin>>noskipws; while (cin >> c) cout <
ahoj jak se mas ahojjaksemas
ahoj jak se mas ahoj jak se mas
Vstupy, výstupy (6) ●
Bude se probírat později podrobně
●
Nyní jen krátné info o několika metodách: ● ● ● ● ●
getline 2x jinak put get peek putback
Vstupy, výstupy (7) <string> istream& getline( istream& is, string& s,\ char delimiter = '\n' ); ●
● ●
Přečte celý řádek z proudu „is“ a uloží do parametru „s“. Pracuje s řetězci dle C++ Není nutné uvádět maximální délku řetězce. string s; getline(cin, s); cout << "napsano: " << s << endl;
Vstupy, výstupy (8) istream& getline( char* buffer,\ streamsize num, char delim ); ● Přečte nejvýše „num 1“ znaků a uloží je do „buffer“ = řetězec dle C. ● Oddělovač není nutno specifikovat (přetíženo). char radek[100]; while(fin.getline(radek, 100)) cout << "precteno: " << radek << endl;
Vstupy, výstupy (9) ●
ostream& put( char ch ); ●
●
istream& get( char& ch ); ● ●
●
přečte z proudu znak a uloží do ch mnohonásobně přetížen
int peek(); ●
●
vloží znak do výstupního proudu
podívá se a vrátí další znak bez „destruktivního“ čtení
istream& putback( char ch ); ●
vrátí do vstupního proudu přečtený znak
STL Standard Template Library ●
Obsahuje ● ●
šablony kontejnerů, iterátorů, funkcí (algoritmy) pomocné třídy ●
●
● ● ● ●
páry, alokátory, komparátory
…
„Objekty“ STL jsou značně parametrizovatelné. Široce používané, urychluje práci. Často logaritmický čas hledání, nlog(n) třízení. Standardizováno, přenositelné.
Kontejner ●
● ● ●
●
Datová struktura, do/ze které lze ukládat/číst data. Čtění dat může odpovídat jistým pravidlům. Např. seznam, pole, strom, množina, … Kontejner s pořadím označujeme jako posloupnost. Lineární spojový seznam ●
každý prvek má svého předchůdce a následníka
Iterátor ●
●
Objekt, zapouzdřený ukazatel do prvků kontejneru. Index pole je „taková neobjektová varianta iterátoru“. ●
●
Dámeli dohromady index do pole, metody (funkce) pro dopředný a zpětný krok, … dostaneme (+) iterátor.
Některé iterátory mají „omezený“ pohyb ● ● ● ●
dopředný (operace ++, lineární seznam a>b>c>...) zpětný (operace ) obousměrný (operace ++, , např. a<>b<>c<>...) náhodný přístup (operace [], např. pole), ...
STL kontejnery ●
●
●
vector ●
zobecněné pole
●
obousměrný seznam
list
queue ● ●
fronta deque ●
●
priority_queue ●
●
dvoustranná fronta fronta se seřazenými prvky
stack ●
zásobník
STL kontejnery (2) ●
set ● ●
množina multiset ●
●
map ● ●
asociativní pole multimap ●
●
množina s více opakujícími se prvky
asociativní pole s opakujícími se dvojicemi klíč, hodnota
valarray ●
optimální jednorozměrné pole pro matematické operarace
STL kontejner – vektor ●
●
Zobecnění klasického pole ●
efektivní vkládání na konec vektoru
●
efektivní náhodný přístup
●
neefektivní vkládání doprostřed
[], at() ●
●
first(), back() ●
●
indexace, přímý (náhodný) přístup reference na první/poslední prvek
insert() ●
neefektivní vložení na přesné místo
STL kontejner – vektor (2) ●
erase() ●
●
push_back() ●
●
odstraní poslední prvek vektoru
empty() ●
●
připojí prvek na konec vektoru
pop_back() ●
●
odstraní prvky v rozmezí (předaných iterátorů)
zjištění, zda je vektor prázdný
clear() ●
vymaže všechny prvky
vektor.cc
STL kontejner – vektor (3), příklad ●
begin(), end() ●
●
vrací iterátor na první/za poslední prvek
rbegin(), rend() ●
vrací reverzní iterátor na poslední / před první prvek
for(vector::iterator i = v.begin();\ i != v.end(); i++) cout << *i << " "; for(vector::reverse_iterator \ i = v.rbegin(); i != v.rend(); i++) cout << *i << " ";
STL kontejner – mapa <map> ●
map ● ● ● ●
●
●
K – typ klíče D – typ dat C – komparátor (nepoužívá se vždy) A – alokátor (nepoužívá se vždy)
Asociativní pole (sváže jedinečný klíč s hodnotou datové položky) Udržuje setřízené dle klíče (existují implicitní komparátory, stejně jako alokátory).
mapa_basic.cc
STL kontejner – mapa (2) map<string, int> sez; ●
Vložení prvku sez.insert(pair<string, int>( Petr , 100)); sez[ Petr ] = 100;
●
Nalezení prvku sez.find( Petr ); ● ●
vrátí iterátor na prvek s klíčem „Petr“ sez.find( Petr )->second == 100 // true
sez.find( Slonbidlo ); ● ●
vrátí iterátor roven sez.end() ukazuje tedy za poslední prvek
STL kontejner – mapa (3) úkol (tady a teď) ●
Použijte soubor ●
● ● ●
http://www.fi.muni.cz/~xbayer/pb161/2007/04/mapa_basic.cc
Upravte tak, aby šlo načítat ze vstupu Po CTRL+D vypíše seznam. Zkuste doplnit hledání ● na vstup přijde jméno a jako výsledek bude hlášení, že neexistuje, nebo rodné číslo.
STL kontejner – mapa (4) ●
Mírně komplikovanější příklad ●
● ● ●
Ukládáme strukturu „tel“ Klíčem je struktura „zaznam“ Třídíme sestupně dle příjmení a pak dle jména. ●
●
http://www.fi.muni.cz/~xbayer/pb161/2007/04/mapa.cc
Explicitní komprarátor
Úkol ● ●
změnit pořadí na vzestupné třízení Kam se poděl druhý „Jarda Bayer“?
Některé další kontejnery (velmi stručně) ● ● ●
http://www.cppreference.com/ http://www.sgi.com/tech/stl/ Zásobník <stack> ●
LIFO ●
● ●
last in first out
top(), push(), pop(), empty(), size(), ==, < adaptér ● ●
stack<double, list > zasobnik; implicitně použije oboustrannou frontu
Některé další kontejnery (velmi stručně) (2) ●
Množina <set> ● ● ● ●
set uspořádaný kontejner, každý prvek nejvýše jednou size(), empty(), insert(), clear(), find(), count(), erase() multiset ● ●
●
multimnožina, povoluje násobný výskyt prvků v kontejneru stejný hlavičkový soubor
množinové operace jsou řešeny jako generické algoritmy ●
set_intersection(), set_difference(), set_union(), ...
Některé další kontejnery (velmi stručně) (3) ●
Seznam <list> ● ●
instance se chovají jako obousměrný seznam lze používat obousměrné iterátory ●
● ●
podobné metody jako u vektoru splice() ●
● ●
umí ++ i
přesun prvků jednoho seznamu do druhého
unique(), remove_if(), sort(), merge(), ... reverse() ●
otočí seznam
Některé další kontejnery (velmi stručně) (4) ● Dvoustranná fronta ● ●
<deque> efektivně přidává na obou koncích kontejneru ●
●
●
uvnitř lineární časová složitost
[], at(), front(), back(), insert(), push_back(), push_front(), pop_back(), pop_front(), clear(), …
Fronta ● ●
adaptér ● ●
●
queue > fronta; neuvedemeli, použije se dvoustrannou frontu
front(), back(), pop(), push(), empty(), size(), ==, <, ...
Generické algoritmy , ●
STL obsahuje generické algoritmy ● ● ●
●
šablony obyčejných funkcí pracují pomocí iterátorů pracují se všemi (+) kontejnery
for_each(), find(), find_if(), count(), equal(), copy(), swap(), replace(), replace_if(), fill(), generate(), unique(), reverse(), random_shuffle(), sort(), stable_sort(), partial_sort(), merge(), set_operace(), ...
Algoritmy, příklad ● ● ●
●
Načteme posloupnost čísel do vektoru. Překopírujeme je do jiného. Setřídíme. http://www.fi.muni.cz/~xbayer/pb161/2007/04/alg_1.cc
Úkol – sedlový prvek matice ●
http://www.fi.muni.cz/usr/jkucera/pb161/sedlo.htm
●
Sedlový prvek matice ● ●
● ● ●
nejmenší v příslušném řádku největší v příslušném sloupci
Max. 8 x 8 matice Řádky ukládat do vektoru Sedlové prvky ukládat do kontejneru ●
pak vypsat
