slajdy k cvičení

Report
cvičení
Filip Zavoral

Docházka
◦ aktivní účast, znalost předchozí látky
◦ 3 nepřítomnosti OK, déledobější domluvit předem

DÚ
◦ uprostřed semestru jedna větší domácí úloha

Zápočtový program
◦ do 15.11. schválené zadání
◦ do 30.4. první pokus o odevzdání hotové verze
◦ do konce LS komplet hotovo vč. doc (jinak neuznáno)

Zápočtový test
◦ během zimního zkouškového období v labu
◦ 3 termíny (3. termín během LS)
#include <iostream>
int main()
{
std::cout << "Hello world" << std::endl;
return 0;
}
#include <iostream>
int main()
{
std::cout << "Hello world" << std::endl;
return 0;
}
VS 2013
File / New / Project
Installed / Templates / VC++ / Win32
Win32 Console Application
Name, Location - OK
!!! Application Settings
Console Application
vypnout! Precompiled header
vypnout! SDL
zapnout! Empty project
ctrl-shift-B
F5
ctrl-F5
F10
F11
F9
Debug / Window
Watch, Auto, Locals
Call Stack
Solution Explorer
Solution / Project
Source Files
Add New/Existing Item
Visual C++ / C++ File (.cpp)
(Header Files)
#include <iostream>
int main()
{
std::cout << "Hello world" << std::endl;
return 0;
}

Násobilka
◦ funkce (třída, metoda)
◦ parametr
Násobilka 7:
1*7=7
2 * 7 = 14
...
10 * 7 = 70
void fnc( int x)
{
....
}
int main()
{
fnc( 7);
return 0;
}
deklarace knihovních funkcí
rozbalení prostoru jmen std
předávání parametrů odkazem
konstantní reference !
přístup k prvkům vectoru
Solution Explorer / Project
Properties / Config Properties
Debugging / Command Arguments
vektor pro komfortnější zpracování
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int delkaretezce( const string& s) { ... }
void zpracuj( const vector<string>& a) {
... a[i] ...
}
int main( int argc, char ** argv)
{
vector<string> arg( argv, argv+argc);
if ( arg.size() > 1 && arg[1] == "--help" ) {
cout << "Usage: myprg [OPT]... [FILE]..." << endl;
return 8;
}
ošetření parametrů příkazové řádky
výkonná funkce / metoda
v mainu nikdy nic užitečného
}
zpracuj( arg);
return 0;
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void vypis( const vector<string>& a)
{
for( int i = 0; i < a.size(); ++i) {
cout << "[" << a[ i] << "]";
}
cout << endl;
}
vypsat násobilku všech čísel
z parametrů příkazové řádky
... si naprogramujte sami
int main( int argc, char ** argv)
{
vector<string> arg( argv, argv+argc);
if ( arg.size() < 2) {
cout << "Usage: myprg parameters" << endl;
return 8;
}
int stoi ( const string& s);
}
vypis( arg);
return 0;
isdigit je lepší
nepovinné parametry:
- první nezkonvertovaný znak
(reference - návratový parametr)
- soustava
#include <string>
if( c >= '0' && c <= '9')
if( isdigit( c))
int n = c - '0';
OK - čísla jsou
uspořádaná
int stoi ( s, size_t& idxRet = nullptr, int base = 10);
stol, stoul, stoll, stof, stod, ...
string to_string ( val);
if( c >= 'a' && c <= 'z')
konverze čísel a stringů
písmena nejsou
uspořádaná !!
#include <sstream>
int strtoint( const string& s)
{
stringstream ss(s);
int n;
ss >> n;
return n;
}
#include <cctype>
isalpha( c)
isalnum(c)
stream z řetězce
'0'
≉ 48
num = num + c - 48;
char a[] = "ahoj";
pole znaků ≈ C-string
char* b = a;
char* b = "ahoj";
ukazatel na C-string
string c = a
string c = "ahoj";
inicializovaná instance třídy
string d = c + b + a;
přetížené operátory
b
'A'
a
'h'
'o'
'j'
'\0'
int atoi( char* s);
atoi( b)
atoi( c)
atoi( a.c_str())
int cele_jmeno( char * buf, size_t bufsize,
const char * jm,
const char * prijm)
{
size_t lj = strlen( jm);
size_t lp = strlen( prijm);
if ( lj + lp + 2 > bufsize )
{ /* error */ return -1; }
memcpy( buf, jm, lj);
buf[ lj] = ' ';
memcpy( buf + lj + 1, prijm, lp);
buf[ lj + lp + 1] = 0;
return lj + lp + 1;
}
Jméno, Příjmení
⇓
Jméno Příjmení
string cele_jmeno( const string& jm,
const string& prijm)
{
return jm + " " + prijm;
}
class Pocitadlo {
public:
Pocitadlo( void);
~Pocitadlo();
int pocet_pismen( void);
private:
int pocet_;
bool ve_slove_;
};
#include <iostream>
#include <cctype>
#include "pocitadlo.hpp"
int Pocitadlo::pocet_pismen( void)
{
char c;
...
while( cin.get(c)) {
if( ve_slove_) {
if( isspace( c)) {
...
}
deklarace třídy - .hpp
konstruktor (defaultní), destruktor
deklarace veřejných metod - rozhraní
privátní data a metody - implementace
include deklarace
definice metod - .cpp
další typy, inicializace
čtení po znacích
typ znaku - asalpha, isdigit, isupper, ...

Spočtěte
◦ počet znaků, řádek, slov, vět
◦ počet a součet čísel

Spočtěte
◦ počet znaků, řádek, slov, vět
◦ počet a součet čísel

Upřesnění zadání
◦ zdroj dat: cin, obecný istream
◦ co to je slovo, věta
◦ různá funkčnost vs. neopakovatelný vstup

Postup
◦ 1. funkční návrh
◦ 2. objektový návrh, rozhraní ! - encapsulace
◦ 3. implementace
int pocet_znaku;
int pocet_slov;
void spocitej( ...)
{
for(;;) {
c = s.get();
....
if( isspace( c)) {
pocet_slov = ...
if( ...)
...
}
}
void spocitej( ...)
{
int pocet_znaku;
int pocet_slov;
}
for(;;) {
c = s.get();
....
if( isspace( c)) {
pocet_slov = ...
if( ...)
...
}
class Ovecky {
public:
void spocitej( ...);
private:
....
};
void Ovecky::spocitej( ...)
{
int pocet_znaku;
int pocet_slov;
}
for(;;) {
c = s.get();
....
if( isspace( c)) {
pocet_slov = ...
if( ...)
...
}
class Ovecky {
public:
void zpracuj_znak( char c);
void spocitej( ...);
int pocet_znaku() { return ..; }
int pocet_slov() { return ..; }
private:
int pocet_znaku_;
int pocet_slov_;
};
void Ovecky::zpracuj_znak( char c)
{
if( isspace( c)) {
pocet_slov_ = ...
if( ...)
...
}
void Ovecky::spocitej( istream& s)
{
for(;;) {
c = s.get();
....
zpracuj_znak( c);
}
int main()
{
Ovecky ov;
ov.spocitej( cin);
...
}
int main()
{
Ovecky ov;
for(;;) {
c = cin.get();
ov.zpracuj_znak( c);
mach_etwas( c);
}
...
}
ovecky.cpp
#include "ovecky.h"
guard
ovecky.h
#include <iostream>
#ifndef OVECKY_H_
#define OVECKY_H_
class Ovecky {
public:
void zpracuj_znak( char c);
void spocitej( std::istream& s);
int pocet_znaku() { return ..; }
int pocet_slov() { return ..; }
private:
int pocet_znaku_;
int pocet_slov_;
inline
};
#endif
implementace
deklarace
void Ovecky::zpracuj_znak( ...)
{
...
}
void Ovecky::spocitej( istream& s)
{
...
}
main.cpp
#include <iostream>
#include "ovecky.h"
int main()
{
Ovecky ov;
ov.spocitej( cin);
cout << ov.pocet();
}

Spočtěte
◦ počet znaků, řádek, slov, vět, počet a součet čísel
◦ číslo: posloupnost číslic obklopená mezerovými znaky
◦ slovo: posloupnost nemezerových znaků, která není
číslo
◦ mezerové znaky (white spaces): ' ', '\t', '\n', '\r'
◦ řádky jen ty, kde je (alespoň) slovo nebo číslo
 poslední řádka nemusí být ukončená '\n'
◦ každá započítaná věta obsahuje alespoň 1 slovo
 '...' ani '31.12.2013' nejsou tři věty
◦ spočítat ze std vstupu nebo ze všech souborů
uvedených na příkazové řádce
◦ objektově a modulárně hezky
 všichni poslat!
 kdo nestihne na cvičení, dodělat doma
jakýkoliv vstupní stream
(cin, soubor, řetězec, ...)
include <iostream>
fce( istream& s) {
char c;
for(;;) {
c = s.get();
if( s.fail())
return;
process( c);
}
fce( cin);
ifstream f;
f.open( "file.txt");
if( ! f.good()) ....
fce( f);
(pokus o) načtení
jednoho znaku
(nemusí se povést)
detekce jakékoliv chyby
(např. EOF)
platná načtená hodnota
zpracování std vstupu
jaký je rozdíl?
co je lepší?
for( i = 0; i < 10; i++) { ... }
zpracování souboru
for( i = 0; i < 10; ++i) { ... }
class Trida
{
int fce( int x);
};
:: kvalifikátor
nalevo vždy typ
int Trida::fce( int x) { ... }
{
}
Trida objekt;
objekt.fce( 1);
Trida objekt = new Trida();
. operátor přístupu
k položce objektu
nalevo vždy proměnná
class Trida
trida.h
{
std::string getResult () { return r; }
std::string slozitaFce( int x);
int jinaFce( int x)
{ int y = -1;
for( i = 0; i < 10; ++i)
....
}
};
#include "trida.h"
trida.cpp
string Trida::slozitaFce( int x)
{
int y;
for( i = 0; i < 10; ++i) {
....
}
}
ale: šablony!
nutná definice při kompilaci
⇒ vše v headeru
inline metoda
s = ob.r místo volání
rozvinutí
s = ob.r
#include "trida.h"
{
}
Trida ob;
string s;
s = ob.getResult();
s = ob.slozitaFce( 1);
int z = jinaFce( 2);
předání parametrů a volání
push 1
s = call ob.slozitaFce
add esp, 8
push 2
y = -1
i=0
loop:
if( i >= 10) goto ...
...
++i
goto loop

vector - pole prvků s přidáváním zprava
◦
◦
◦
◦

celočíselně indexováno, vždy od 0
všechny prvky umístěny v paměti souvisle za sebou
při přidání možná změna lokace, neplatnost iterátorů!
odvozené: queue, stack
vector<int> vi;
list<string> ls;
array<MyClass> am;
deque [dek] - fronta s přidáváním a odebíráním z obou stran
◦ double-ended queue
◦ prvky nemusí být umístěny v paměti souvisle
◦ lze přidávat i doleva

list - obousměrně vázaný seznam
◦ vždy zachovává umístění prvků
◦ nepodporuje přímou indexaci


forward_list - jednosměrně vázaný seznam C++11
basic_string - posloupnost ukončená terminátorem
◦ string, wstring

array - pole pevné velikosti
C++11
[dekjú] ≈ dequeue
odebrat z fronty

setříděné
◦
◦
◦
◦
◦
◦
◦
setříděné podle operátoru <
pro neprimitivní typy (třídy) nadefinovat operator<
set<T> - množina
multiset<T> - množina s opakováním
map<K,T> - asociativní pole - parciální zobrazení K -> T
multimap<K,T> - relace s rychlým vyhledáváním podle klíče K
pair<A,B> - pomocná šablona - uspořádané dvojice
 položky first, second
 šablona funkce make_pair( f,s)

nesetříděné
C++11
◦ unordered_set/multiset/map/multimap
◦ hash table - nesetříděné, vyhledávání pouze na ==
◦ pro neprimitivní typy (třídy) nadefinovat hashovací funkci
 size_t hash<X>(const X &)
polootevřený
interval

Iterátor
◦ objekt reprezentující odkazy na prvky kontejneru
◦ operátory pro přístup k prvkům
◦ operátory pro procházení kontejneru

kontejner<T>::iterator
iterátor příslušného kontejneru
◦ iterátor je typovaný

kontejner<T>::const_iterator konstantní iterátor - používejte!

*it, it->x
++it
+(int) -(int)
přístup k prvku/položce přes iterátor
posun na následující prvek
posun iterátoru

begin(), end()
iterátor na začátek / za(!) konec kontejneru


const vector::iterator
≠
vector::const_iterator
vector<int> pole = { 10, 11, 20 };
vector<int>::const_iterator i;
for( i = pole.begin(); i != pole.end(); ++i)
cout << *i;




jednotné rozhraní nezávislé na typu kontejneru
ALE: ne všechny kontejnery podporují vše!
push_back(T), push_front(T) přidání prvku na konec / začátek
pop_front(), pop_back()
odebrání ze začátku / konce
◦ nevrací hodnotu, jen odebírá!


front(), back()
operator[], at()
◦ bez kontroly, s kontrolou (výjimka)








insert (T), (it, T)
insert (it, it b, it e)
insert(make_pair(K,T))
erase(it), erase(it,it)
find(T)
size(), empty()
clear()
upper_bound, lower_bound
◦ ... and many many others
prvek na začátku / konci
přímý přístup k prvku
vložení prvku, před prvek
vložení intervalu
vložení do mapy - klíč, hodnota
smazání prvku, intervalu
vyhledání prvku
velikost / neprázdost
smazání kontejneru
hledání v multisetu/mapě
#include <vector> .. map, unordered_map, ..
vector<int> pole = { 10, 11, 20 };
pole.push_back( 30);
x = pole[3];
Přidání na konec
vector<int>::const_iterator i;
for( i = pole.begin(); i != pole.end(); ++i)
cout << "[" << *i << "]";
map<string,int> m;
m.insert( make_pair( "jedna", 1));
Typová inferece
rozsahem řízený cyklus
Cyklus s iterátory
Přidání do mapy
Vytvoření pairu
vector<int> pole;
for( auto i = pole.begin(); i != pole.end(); ++i)
cout << "[" << *i << "]";
Range-based for
Kruliš 2014:
Initializers (C++11)
Typicky:
konstantní reference
vector<int> pole;
for( auto i : pole)
cout << "[" << i << "]";
vector<int> pole;
for( const auto& i : pole)
cout << "[" << i << "]";
map<string,int> mapa;
map<string,int>::const_iterator it;
fce( map<string,int>& mm);
neopisujte stále
deklarace !
Překladový slovník
(k jednomu slovu může být více překladů)
-
přidat slovo a jeho překlad(y)
odebrat jeden překlad slova
odebrat všechny překlady slova
nalézt všechny překlady slova
nalézt všechny překlady slov
začínajících prefixem
nalézt slovo když znáte překlad
Proč:
- neupíšu se
- změna druhu nebo typu
- rozlišení logicky různých typů
- čitelnost
typedef map<string,int> Mapka;
Mapka::const_iterator it;
fce( const Mapka& mm);
add slovo cizi
del slovo cizi
del slovo
find slovo -> cizi cizi cizi
pfind slovo ->
slovoxxx cizi cizi
slovoyyy cizi
slovozzz cizi cizi
rfind cizi -> slovo slovo
složitost
přidání / odebrání
na začátku
přídání /
odebrání
na i-té pozici
přídání /
odebrání
m prvků
přídání /
odebrání
na konci
funkce
push_front
pop_front
insert
erase
insert
erase
push_back begin()+i
pop_back [i]
list
konst
konst
m, konst
konst
neex
nalezení
i-tého prvku
přesuny mezi
sezn. (splice)
deque
konst
min( i, n - i)
m+
min( i, n - i)
konst
konst
vector
neex
n-i
m+n-i
konst
konst
asocia
tivní
ln
(s klicem k)
(s klicem k)
ln
ln
ln + m
nalezení podle
hodnoty ln
unsorted
konst
konst
m
konst
konst
• Do you need to be able to insert a new element
at an arbitrary position in the container?
you need a sequence container: associative containers won't do
• What category of iterators do you require? If they
must be random access iterators...
you're limited to vector, deque, and string
• Is it important to avoid movement of existing
container elements when insertions or erasures
take place?
you'll need to stay away from contiguous-memory containers
• Is lookup speed a critical consideration?
you'll want to look at hashed containers (unordered_map),
sorted vectors, and the standard associative containers —
probably in that order
• Do you need to minimize iterator, pointer, and
reference invalidation?
Use node-based containers, because insertions never invalidate
any references (unless they point to an element you are erasing).
Insertions or erasures on contiguous-memory containers may
invalidate all references into the container.
prolezeni pole 5 prvků dopředu
vector<int> v;
...
vector<int>::const_iterator i;
for( i = v.begin(); i != v.end(); ++i)
cout << *i << " ";
pozpátku
vector <string> pole;
....
x = pole.size();
pole[x] = 0;
co je zde špatně?
vector<int>::reverse_iterator i;
for( i = v.rbegin(); i != v.rend(); ++i)
cout << *i << " ";
úkol:
načíst z cin a vypsat odzadu po dvou, pak zase zepředu
1234567  7531246
void vypis( vector<int> & v)
{ vector<int>::const_iterator i;
i = v.end();
if( i == v.begin())
return;
--i;
}
for(;;) {
cout << *i << ", ";
if( i == v.begin() || i-1 == v.begin())
break;
i -= 2;
}
if( i == v.begin())
++i;
// vytisteno [0] -> [1]
else
--i;
// vytisteno [1] -> [0]
for(;;) {
cout << *i << "; ";
if( i+1 == v.end() || i+2 == v.end())
break;
i += 2;
}
cout << endl;

opatrně
◦ pozor na korektnost

mnohem
inteligentnější
řešení
◦ rovnou při čtení
rozhazovat na strany
do deque (nebo list)
vector<int> x;
for( int i = 0; i < x.size(); ++i)
.. x[i] ..
int y[MAX];
for( int *i = y; i != y+MAX; ++i)
.. *i ..
jen pro vector/array
historie: pointrová
aritmetika

vector<int>::const_iterator i;
for( i = x.begin(); i != x.end(); ++i)
.. *i ..
for( auto i = x.begin(); i != x.end(); ++i)
.. *i ..
jednotný průchod
kontejnery
type inference
C++11
for( auto i : x)
.. i ..
reference na prvek
range-based for
const auto& i : x
chci jen prohlížet
auto& i : x
potřebuji měnit
auto i : x
opravdu potřebuji kopii
explicittype i : x
potřebuji přetypovat
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string s;
vector<string> v;
for(;;) {
cin >> s;
if( cin.fail())
break;
v.push_back(s);
}
sort( v.begin(),v.end());
}
for( .... )
cout << ....;
cout << endl;
list<string> v;
list<string>::const_iterator i;
for(;;) {
cin >> s;
if( cin.fail())
break;
for( i = v.begin(); i != v.end() && *i <= s; ++i)
;
v.insert( i, s);
}
jak to setřídit?
vlastní třídění

string s;
set<string> v;
for(;;) {
cin >> s;
if( cin.fail())
break;
v.insert(s);
}
bool mysort( const string& s1, const string& s2) {
return
s1.size() < s2.size() ? true :
(s1.size() > s1.size() ? false : s1 < s2)
}
set<string, mysort> v;
...
v.insert(s);
#include <algorithm>







it find( it first, it last, T&)
int count( it first, it last, T&)
funkce modifikuje argument
for_each( it first, it last, fnc( T&))
transform( it first, it last, output_it out, fnc( T&))
vrací modifikovaný argument
copy( it first, it last, output_it out)
možnost jiného kontejneru
sort( begin, end, sort_fnc(x&, y&))
find_if, count_if, remove_if( it first, it last, pred& p)
predikát: bool fnc( const T&)
#include <algorithm>
vector<int> v = { 1, 3, 5, 7, 9 };
// vector<int>::const_iterator result;
auto result = find( v.begin(), v.end(), 5);
bool greater10 ( int value ) {
return value >10;
}
result = find_if( v.begin( ), v.end( ), &greater10 );
if ( result == v.end( ) )
cout << "Nothing" << endl;
else
cout << "Found: " << *result << endl;
predikát
vždy otestovat!
for_each( begin, end, fnc( T&))
// vynásobit všechny prvky 2
// přičíst ke všem prvkům +1, +2, +3, ...
void mul2( int& x) {
x *= 2;
}
#include <algorithm>
vector<int> v = { 1, 3, 5, 7, 9 };
// vector<int>::const_iterator result;
auto result = find( v.begin(), v.end(), 5);
bool greater10 ( int value ) {
return value >10;
}
result = find_if( v.begin( ), v.end( ), &greater10 );
if ( result == v.end( ) )
cout << "Nothing" << endl;
else
cout << "Found: " << *result << endl;
jak parametricky?
for_each( begin, end, fnc( T&))
// vynásobit všechny prvky 2
// přičíst ke všem prvkům +1, +2, +3, ...
jak zrestartovat?
jak krok parametricky?
int fce( int& x) {
static int qq = 0;
return x += (qq +=1);
}
for_each( v.begin(), v.end(), fce);
for_each( v.rbegin(), v.rend(), fce);
class ftor {
public:
ftor( int step) : step_(step), qq_(0) {}
int operator() (int& x) { return x += (qq_ += step_); }
private:
int step_;
int qq_;
};
for_each( v.begin(), v.end(), ftor(2));
najít v kontejneru
prvek větší než n
Přičíst ke všem prvkům
+n, +2n, +3n, ...
Funktor – třída s
přetíženým operátorem ()
oddělení inicializace a
běhového parametru
it = find_if( bi, ei, fnc);
• inkrementovat čísla v
zadaném rozsahu hodnot
(první +1, druhé +2, ...)
class cmp {
public:
cmp( int cmp) : n_(cmp) {}
bool operator() (int& x) { return x > n_; }
private:
int n_;
};
• najít číslo za největší dírou
(rozdíl sousedních hodnot)
auto fnd = find_if( v.begin(), v.end(), cmp(9));
cout << ( ( fnd == v.end()) ? -1 : *fnd) << endl;
• najít prvek odlišný od
předchozího alespoň o n
součet všech čísel
větších než parametr
jak získat výsledek?
po skončení hodnota
použitého funktoru
pozor!
nejde o identický objekt
class scitacka {
public:
scitacka( int limit) : limit_(limit), vysledek_(0) {}
int operator() (int& x) { if( x > limit_) vysledek += x; }
int vysledek_;
private:
int limit_;
};
scitacka s = for_each( v.begin(), v.end(), scitacka(10));
cout << s.vysledek_ << endl;


najděte všechny prvky větší než 9
lambda výrazy
◦ od C++ 11
find_if( v.begin(), v.end(), bind2nd( greater<int>(), 9));
vlastní
funktor
find_if( v.begin(), v.end(), greater_than( 9));
find_if( v.begin(), v.end(), [](int& x) { return x > 9; });
lambda výraz


 mnohem jednodušší zápis a syntaxe
 vnitřní stav  funktor
for_each() Performs an operation for each element
count() Returns the number of elements
count_if() Returns the number of elements that match a criterion
min_element() Returns the element with the smallest value
max_element() Returns the element with the largest value
find() Searches for the first element with the passed value
find_if() Searches for the first element that matches a criterion
search_n() Searches for the first n consecutive elements
search() Searches for the first occurrence of a subrange
find_end() Searches for the last occurrence of a subrange
find_first_of() Searches the first of several possible elements
adjacent_find() Searches for two adjacent elements that are equal
equal() Returns whether two ranges are equal
mismatch() Returns the first elements of two sequences that differ
lexicographical_compare() Returns whether a range is lexicogr. less
for_each() Performs an operation for each element
copy() Copies a range starting with the first element
copy_backward() Copies a range starting with the last element
transform() Modifies and copies elements; combines two ranges
merge() Merges two ranges
swap_ranges() Swaps elements of two ranges
fill() Replaces each element with a given value
fill_n() Replaces n elements with a given value
generate() Replaces each element with the result of an operation
generate_n() Replaces n elements with the result of an operation
replace() Replaces elements that have a special value
replace_if() Replaces elements that match a criterion
replace_copy() Replaces elements that have a special value while copying
the whole range
replace_copy_if() Replaces elements that match a criterion while copying
the whole range
remove() Removes elements with a given value
remove_if() Removes elements that match a given criterion - does not
remove anything!
remove_copy() Copies elements that do not match a value
remove_copy_if() Copies elements that do not match a given criterion
unique() Removes adjacent duplicates
unique_copy() Copies elements while removing adjacent duplicates
reverse() Reverses the order of the elements
reverse_copy() Copies the elements while reversing
rotate() Rotates the order of the elements
rotate_copy() Copies the elements while rotating their order
next_permutation() Permutes the order of the elements
prev_permutation() Permutes the order of the elements
random_shuffle() Brings the elements into a random order
partition() Changes the order of the elements so that elements that match
a criterion are at the front
stable_partition() Same as partition(), but preserves the relative order of
matching and nonmatching elements
sort() Sorts all elements
stable_sort() Sorts while preserving order of equal elements
partial_sort() Sorts until the first n elements are correct
partial_sort_copy() Copies elements in sorted order
nth_element() Sorts according to the nth position
partition() Changes the order of the elements so that elements that match
a criterion are at the front
stable_partition() Same as partition(), but preserves the relative order of
matching and nonmatching elements
make_heap() Converts a range into a heap
push_heap() Adds an element to a heap
pop_heap() Removes an element from a heap
sort_heap() Sorts the heap (it is no longer a heap after the call)
binary_search() Returns whether the range contains an element
includes() Returns whether each element of a range is also an element of
another range
lower_bound() Finds the first element greater than or equal to a value
upper_bound() Finds the first element greater than a given value
equal_range() Returns the range of elements equal to a given value
merge() Merges the elements of two ranges
set_union() Processes the sorted union of two ranges
set_intersection() Processes the sorted intersection of two ranges
set_difference() Processes a sorted range that contains all elements of a
range that are not part of another
set_symmetric_difference() Processes a sorted range that contains all
elements that are in exactly one of two ranges
inplace_merge() Merges two consecutive sorted ranges
accumulate() Combines all element values (processes sum, product, ...)
inner_product() Combines all elements of two ranges
adjacent_difference() Combines each element with its predecessor;
converts absolute values to relative values
partial_sum() Combines each element with all of its predecessors; converts
relative values to absolute values

vidle
◦ vstup: vektor čísel
◦ výstup: multiset čísel větších než X inkrementovaný o Y

filmová databáze
◦ název filmu, režisér, rok, ...
◦ vypsat setříděné
 podle roku a názvu filmu
 podle režiséra a roku

jednoduchý makroprocesor
◦ vstup: text #novemakro obsah makra # dalsi novemakro konec
◦ vystup: text dalsi obsah makra konec
◦ vstup: tt #m1 xx # #m2 yy m1 #
pozor - v definici makra může být
obsažena hodnota jiného makra

Zadání
◦ kontejner obsahující hodnoty libovolného typu
◦ int, double, string, complex, zlomky, ...

Technické upřesnění
◦
◦
◦
◦
◦
třída Seznam, operace add, print
společný předek prvků AbstractVal
konkrétní prvky IntVal, StringVal, ...
stačí jednoduchá implementace vektorem
pole objektů vs. pole 'odkazů'
IV
AV
x
SV
AV
s
IV
AV
x
class AbstractVal {
public:
virtual void print() = 0;
};
class Seznam {
public:
void add( valptr p );
void print();
private:
vector<valptr> pole;
};
typedef ???<AbstractVal> valptr;
typ odkazu
abstraktní předek
umí existovat a vytisknout se
vektor odkazů
int main() {
Seznam s;
s.add( ....<IntVal> 123 );
s.add( ....<StringVal> "456" );
s.print();
}
použití

??? valptr
◦
◦
◦
◦
◦
AbstractVal *
AbstractVal &
unique_ptr<AbstractVal>
shared_ptr<AbstractVal>
... ?
class AbstractVal;
typedef unique_ptr<AbstractVal> valptr;
#include <memory>
class Seznam {
public:
void add( valptr p ) { pole.push_back( move( p)); }
void print() { for( const auto& x : pole ) x->print(); }
private:
vector<valptr> pole;
};
int main() {
Seznam s;
s.add( make_unique<IntVal>(123));
s.add( make_unique<StringVal>("456"));
s.print();
}
proč '->' ?
konstruktory?
destruktory?
class IntVal : public AbstractVal {
public:
IntVal( int x) : x_( x) {}
virtual void print() { cout << x_; }
private:
int x_;
};
class StringVal : public AbstractVal {
public:
StringVal( int x) : x_( x) {}
virtual void print() { cout << x_; }
private:
string x_;
};
what's the difference?
class
class
class
class
DoubleVal : public AbstractVal;
ComplexVal : public AbstractVal;
LongintVal : public AbstractVal;
FractionVal : public AbstractVal;
int main() {
Seznam s1, s2;
s1.add( make_unique<IntVal>(123));
s1.add( make_unique<StringVal>("456"));
s2 = s1;
s2.print();
}
čím je to zajímavé?
int main() {
Seznam s1, s2;
s1.add( make_unique<IntVal>(123));
s1.add( make_unique<StringVal>("456"));
s2 = s1;
s2.print();
}
čím je to zajímavé?
compiler error:
XXXX unique_ptr XXX attempting to reference a deleted function
class Seznam {
....
Seznam( const Seznam& s) = delete;
Seznam& operator=(const Seznam& s) = delete;
};
před C++11:
private: operator=
možné řešení: zakázat !!!
copy constructor
a operator=
by se měly chovat stejně
Seznam& Seznam::operator=(const Seznam& s)
{
for( const auto& x : s.pole)
pole.push_back( x);
return *this;
}
řešení?
Seznam& Seznam::operator=(const Seznam& s)
{
for( const auto& x : s.pole)
pole.push_back( x);
return *this;
}
compiler error:
XXXX unique_ptr XXX attempting to reference a deleted function
řešení?
Seznam& Seznam::operator=(const Seznam& s)
{
for( const auto& x : s.pole)
pole.push_back( make_unique<...>( *x));
return *this;
}
nechci kopírovat ukazatel
chci vytvořit nový objekt
řešení?
motivace
int main() {
Seznam s;
s.add( make_unique<IntVal>(123));
s.add( make_unique<StringVal>("456"));
s.print();
}
Seznam& Seznam::operator=(const Seznam& s)
{
for( const auto& x : s.pole)
?
}
pole.push_back( make_unique< >( *x));
return *this;
jaký typ použít?
řešení?
Seznam& Seznam::operator=(const Seznam& s)
{
for( const auto& x : s.pole)
pole.push_back( make_unique<AbstractVal>( *x));
return *this;
}
řešení?
compiler error:
cannot instantiate abstract class
class AbstractVal {
public:
virtual void print() = 0;
};
Seznam& Seznam::operator=(const Seznam& s)
{
for( const auto& x : s.pole)
pole.push_back( make_unique<AbstractVal>( *x));
return *this;
}
řešení?
.... 2:30 v noci, ráno je deadline
tak tu abstraktnost
zrušíme!
class AbstractVal {
public:
virtual void print() {}
};

Je to správně?
◦
◦
◦
◦

Není !!
slicing
pouze část objektu
společný předek
IV
AV
x
SV
AV
s
IV
AV
horší chyba než
předchozí případ
◦ projde kompilátorem 
◦ nespadne
◦ dělá nesmysly!
AV
AV
AV
x

Co s tím?
◦ skutečná hodnota IntVal
⇒ vytvořit IntVal
◦ skutečná hodnota StringVal
⇒ vytvořit StringVal
class AbstractVal {
public:
enum T { T_INT, T_DOUBLE, ...};
virtual T get_t() const;
};
Seznam& Seznam::operator=(const Seznam& s)
{
for( const auto& x : s.pole) {
switch( x->get_t()) {
case AbstractVal::T_INT:
pole.push_back( make_unique<IntVal>( *x));
break;
case AbstractVal::T_STRING:
pole.push_back( make_unique<StringVal>( *x));
break;
}
return *this;
}
řešení?

Co s tím?
◦ skutečná hodnota IntVal
⇒ vytvořit IntVal
◦ skutečná hodnota StringVal
⇒ vytvořit StringVal
class AbstractVal {
public:
enum T { T_INT, T_DOUBLE, ...};
virtual T get_t() const;
};
Seznam& Seznam::operator=(const Seznam& s)
{
for( const auto& x : s.pole) {
switch( x->get_t()) {
case AbstractVal::T_INT:
pole.push_back( make_unique<IntVal>( *x));
break;
case AbstractVal::T_STRING:
pole.push_back( make_unique<StringVal>( *x));
break;
}
return *this;
}
FUJ !!!



ošklivé
těžko
rozšiřitelné
zásah do
předka

Jak to udělat lépe?
◦
◦
◦
◦
využít mechanismus pozdní vazby
každý prvek bude umět naklonovat sám sebe
rozhraní v AbstractVal, implementace v IntVal, ...
virtuální klonovací metoda
class AbstractVal {
public:
virtual void print() = 0;
virtual valptr clone() = 0;
};
class IntVal : public AbstractVal {
....
virtual valptr clone()
{ return make_unique<IntVal>(*this); }
};
... operator=(const Seznam& s)
{
for( const auto& x : s.pole)
pole.push_back( x->clone());
return *this;
}
od 0x11: kovariantní
návratový typ
IV
AV
x
IV
AV
x

Copy-constructor a operator=
◦ společné chování
◦ operator= navíc úklid starého stavu, vrací referenci
◦ společné tělo
class Seznam
{
řešení?
public:
....
Seznam() {}
Seznam( const Seznam& s ) { clone( s ); }
Seznam& operator=(const Seznam& s) { pole.clear(); clone( s ); return *this; }
private:
void clone( const Seznam& s )
{ for( const auto& x : s.pole ) pole.push_back( x->clone() ); }
vector< valptr> pole;
};
int main() {
Seznam s;
s.add( make_unique<IntVal>(123));
s.add( make_unique<StringVal>("456"));
s = s;
}
takhle blbě by to asi nikdo nenapsal, ale....
int main() {
vector<Seznam> s;
....
s[i] = s[j];
}
čím je to zajímavé?
class Seznam
{
public:
....
Seznam& operator=(const Seznam& s)
{ pole.clear(); clone( s ); return *this; }
};
nejdřív si sám celé pole smažu
... a potom nakopiruju ... ... NIC!
int main() {
vector<Seznam> s;
....
s[i] = s[j];
}
řešení?
rovnost ukazatelů ⇒ stejný objekt
Seznam& operator=(const Seznam& s)
{
if( this == &s) return *this;
pole.clear();
clone( s );
return *this;
};

Je třeba 'trocha' opatrnosti
◦ ... a rozumět tomu, co se v programau děje
◦ naimplementujte si sami
◦ = jen dát dohromady předchozí moudra

Námět k rozmyšlení
◦ jak by se změnila sémantika (chování), kdybychom
použili shared_ptr

Verze s raw-pointry
◦ zastaralá
◦ navíc další problémy
 destruktory, dealokace
 při nešikovné implementaci odlet!
◦ výhoda unique_ptr: kompilační kontrola
◦ pro zájemce/masochisty na konci slajdů ...
scitacka.h
class Scitacka
{
public:
Scitacka() : val_( 0) {}
void add( int x);
int result() { return val_; }
private:
int val_;
};
void Scitacka::add( int x)
{ val += x }
int main()
{
Scitacka s;
s.add( 1);
s.add( 2);
int x = s.result();
}
hlavička
šablony
hlavička i u
definice těla
tělo v
headeru !
template<typename T> class Scitacka
{
public:
Scitacka() : val_( 0) {}
void add( T x);
T result() { return val_; }
private:
T val_;
};
template <typename T>
void Scitacka<T>::add( T x)
{ val += x }
#include "Scitacka.h"
použití
instanciace
šablona těla
musí být při
kompilaci
viditelná
int main()
{
Scitacka<int> s;
s.add( 1);
s.add( 2);
int x = s.result();
}

Problém
◦ std::vector nezachovává umístění prvků
◦ přidání → invalidace referencí, iterátorů, ...

Chci: datová struktura zachovávající umístění
◦ žádné invalidace
◦ konstantní časová složitost přístupu k prvkům
◦ [i/chunk][i%chunk]
vektor s nehýbatelnými prvky
x.push_back(n)
x[i]
alternativně:
automatické rozšíření na x[i]
chunk size
u_p<T[]>
T*
T
T
T
T
T*
vector< unique_ptr<T[]>>
T*
make_unique< T[]>(chunk)
template<typename T> class Pole {
public:
Pole(size_t chunk = 100) : chunk_(chunk), size_(0) {}
void push_back(const T& x) { resize( ++size_); (*this)[size_-1] = x; }
T& operator[] (size_t i) { return hrabe_[i / chunk_][i%chunk_]; }
T& at(size_t i) { check(i); return (*this)[i]; }
private:
void check(size_t i) { if (i >= size_) throw 1; }
void resize(size_t i) { for (size_t k = hrabe_.size(); k <= i / chunk_; ++k)
hrabe_.push_back( make_unique< T[]>(chunk_)); }
size_t chunk_;
new T[chunk_]
size_t size_;
vector< unique_ptr<T[]>> hrabe_;
};
auto p = make_unique< T[]>(chunk_));
hrabe_.push_back( move( p));

vyvolání výjimky
◦ try blok
◦ nejbližší vyhovující catch blok
◦ stack unwinding
 destrukce všech objektů
try {
if( error) throw exctype;
} catch( exctype& e) {
e.xxx();
} catch( ...) {
yyy;
}
#include <stdexcept>

dvojitá výjimka
◦ terminate
class exception {
potomci
public:
std::exception
exception( );
virtual const char *what( ) const;
};
bad_alloc, bad_cast, domain_error,
invalid_argument, length_error, out_of_range,
overflow_error, range_error, underflow_error
} catch( exception& e) {
cout << e.what() << endl;
}

Výjimky v destruktoru
◦ nikdy!
◦ destruktory se volají při obsluze výjimek

Výjimky v konstruktoru
◦ ne globální!
 není kde chytit
exception-safe
programming: LS
◦ Základní třída
 konstruktor může vyvolat výjimku
◦ Odvozená třída
 výjimku inicializace je vhodné zachytit
 objekt není vytvořen
 tělo konstruktoru odvozené třídy
se neprovede
tělo try bloku je
tělem konstruktoru
class A {
public:
A( X& x) { ... throw ... }
};
class B : public A {
public:
B( X& x) try : A(x) {
...
} catch( ...) {
}
};
#include <stdexcept>, <cstdlib>
class myexc : public std::exception {
public:
myexc( int ix) : ix_(ix) { strcpy( buf_, "Chyba na indexu: ");
ltoa( ix, buf_+strlen( buf_), 10); }
virtual const char *what( ) const { return buf_; }
int getIndex() const { return ix_; }
private:
int ix_;
char buf_[100];
};
myclass::myfnc() {
whatever();
if( error_occured)
throw myexc( 17);
whatever_else();
}
vše zpracovat
v konstruktoru
kompatibilita
vlastní
diagnostika
žádné alokace !!!
anonymní instance
žádné alokace !
try {
nejakymujkod
} catch( myexc& me) {
cout << "Chyba indexu: " << me.getIndex() << endl;
} catch( exception& e) {
cout << e.what() << endl;
}
const int max = 100;
int n = random( max);
vector<int> v;
int i;
for( i = 0; i < n; i++)
v.push_back( i);
try {
for(;;) {
i = random( max);
// cout << v[i] << " "; !!! nehazi, odleti
cout << v.at(i) << " ";
}
} catch( exception &e) {
cout << endl << e.what() << endl;
} catch(...) {
cout << "Obscure exception!" << endl;
}
}

Vyzkoušet
◦ nějak velké pole
◦ náhodně zkoušet
◦ při přetečení výjimka

Podrobnější diagnostika
◦ vlastní výjimka
◦ špatný index a velikost pole
#include <random>
#include <ctime>
default_random_engine generator( time(0));
uniform_int_distribution<int> distribution(1,6);
int n = distribution(generator);

C:\> myprog.exe -n -w a.txt b.txt
pole řetězců
(ukazatelů na char)
int main( int argc, char** argv)
argv
0
argc 5
a
Počet parametrů
včetně názvu programu !
= počet ukazatelů v argv
b
.
t
x
.
t
x
t
\0
e
x
e
\0
- w \0
m y
-
n
\0
p
r
o g
.
t
\0
usage: myprog [-n] [-w] fileA fileB
int main( int argc, char** argv)
{ int n=0, w=0;
while( *++argv && **argv=='-')
{ switch( argv[0][1]) {
case 'n': n = 1; break;
case 'w': w = 1; break;
default: error();
}
}
if( !argv[0] || !argv[1])
error();
doit( argv[0], argv[1], n, w);
return 0;
}
options
nastavení
přepínače
zbývající
parametry
0
b
.
t
x
t
\0
a
.
t
x
t
\0
.
e
x
- w \0
výkonná funkce
argv
-
n
\0
p
r
g
e
\0


čtení ze souboru i std vstupu
záměnnost
◦ std vstup i soubor jsou streamy
◦ lze přiřadit za běhu
#include <iostream>
#include <fstream>
ifstream x;
x.open( "file.txt");
if( ! x.good()) { "chyba" }
for (;;) {
x >> a;
if( x.fail())
break;
f( a);
}
x.close();
istream *in;
stav streamu
výsledek
předchozí
operace
lepší než
test na eof
in = & cin;
if( ...) {
in = new ifstream(...);
}
*in << "cokoliv";
není třeba psát
zvláštní kód pro
čtení souboru


přetížení operátoru <<
není to metoda třídy ale friend globální funkce
◦ nemáme přístup do implementace ostream
class Complex {
public:
Complex() : re_(0), im_(0) {}
friend ostream& operator<< ( ostream& out, const Complex& x);
private:
double re_, im_;
toto není
};
metoda
ostream& operator<< ( ostream& out, const Complex& x) {
out << "[" << x.re_ << "," << x.im_ << "]" << endl;
return out;
}
string s1, s2;
int i1, i2;
f >> s1 >> i1 >> s2 >> i2;
if( f.fail()) ...;
...
ws (mezery, ...)
se automaticky přeskočí
stream zůstává
za posledním čtením
const int MaxBuf = 4095;
char buffer[ MaxBuf+1];
for( ;;) {
f.getline( buffer, MaxBuf);
if( f.fail()) break;
cout << "[" << buffer << "]" << endl;
}
string s;
for( ;;) {
getline( f, s);
if( f.fail()) break;
cout << "[" << s << "]" << endl;
}
vždy limit
parsování řádku
string r, s1, s2;
for( ;;) {
getline( f, r);
if( f.fail()) break;
stringstream radek(r);
radek >> s1 >> s2;
cout << "[" << s1 << s2 << "]" << endl;
}
string s;
string::iterator b, e;
char delim = ';';
while( getline( f, s)) {
b = e = s.begin();
while( e != s.end()) {
e = find( b, s.end(), delim);
string val( b, e);
cout << "[" << val << "]";
b = e;
if( e != s.end())
b++;
}
cout << endl;
}
dokud přečtené slovo
není na konci
vrátí iterator na odělovač
přečte hodnotu
mezi oddělovači
přeskočí oddělovač
f >> ws;
if( isdigit( f.peek())) {
int i;
f >> i;
cout << "[" << i << "]" << endl;
} else {
string s;
f >> s;
cout << "{" << s << "}" << endl;
}
přečte se nejbližší znak,
ale nechá se ve streamu
endl
vloží nový řádek
setw(val)
nastaví šířku výstupu
setfill(c)
nastaví výplňový znak
dec, hex, oct
čte a vypisuje v dané soustavě
left, right
zarovnávání
fixed, scientific
formát výpisu čísla
precision(val)
nastaví přesnost
ws
přeskočí bílé znaky
(no)skipws
nastavení/zrušení přeskakování bílých znaků při čtení
(no)showpoint
nastaví/zruší výpis desetinné čárky
...

speciální funkce
◦ předávané ukazatelem
◦ vrací referenci na modifikovaný stream
cout << 1 << mriz << 2 << mriz << 3 << endl;
ostream& mriz( ostream& io)
{
io << " ### ";
return io;
}

jak to funguje
ostream& operator<< (ostream& (* pf)(ostream&));
 přesněji: šablona
ukazatel na funkci
funkce
zavolá ji op<<
přetížená matoda na
ukazatel na funkci
cout << 1 << mriz(5) << 2 << mriz(3) << 3 << endl;

nelze předdefinovaná funkce
◦ libovolné možné parametry

ošklivé řešení
◦ vlastní funkce s extra parametrem
cout << mriz(cout,5) << ...

hezčí řešení
◦ zvláštní třída, zvláštní přetížení <<

vlastní třída
◦ anonymní instance
◦ parametr konstruktoru
◦ přetížení << na tuto třídu
class tecka {
private: int n_;
public: explicit tecka( int n) : n_( n) {}
int get_n() const { return n_; }
};
ostream& operator<<( ostream& io, const tecka & p)
{
int n = p.get_n();
while( n--) io << ".";
return io;
zřetězení <<
jiná instance
}
cout << 1 << tecka(5) << 2 << tecka(3) << 3 << endl;
příkládek:
rzlomek z( 3, 4);
cout << z;
3 / IV
známý trik:
separace inicializace
a volání
class A { public:
virtual int f()
{ return
int g()
{ return
int h()
{ return
virtual int j()
{ return
};
class B : public A { public:
virtual int f()
{ return
int g()
{ return
int h()
{ return
virtual int j()
{ return
};
A x; B y;
A * p = &x;
A * q = &y;
B * r = &y;
xy.fghj();
pqr -> fghj();
1; };
2; };
f(); };
g(); };
3; };
4; };
g(); };
f(); };
int x = 1;
class A { public:
A()
{ x += 1; }
virtual ~A()
{ x += 2; }
};
class B : public A { public:
B()
{ x *= 2; }
virtual ~B()
{ x *= 3; }
};
A *p = new B;
cout << x;
delete p;
cout << x;




























Sutter, Alexandrescu:
C++ 101 programovacích technik
Organizational and Policy Issues
0. Don’t sweat the small stuff. (Or: Know what not to standardize.) (C++ Coding
1. Compile cleanly at high warning levels.
2. Use an automated build system.
3. Use a version control system.
4. Invest in code reviews.
Design Style
5. Give one entity one cohesive responsibility.
6. Correctness, simplicity, and clarity come first.
7. Know when and how to code for scalability.
8. Don’t optimize prematurely.
9. Don’t pessimize prematurely.
10. Minimize global and shared data.
11. Hide information.
12. Know when and how to code for concurrency.
13. Ensure resources are owned by objects. Use explicit RAII and smart pointers.
Coding Style
14. Prefer compile- and link-time errors to run-time errors.
15. Use const proactively.
16. Avoid macros.
17. Avoid magic numbers.
18. Declare variables as locally as possible.
19. Always initialize variables.
20. Avoid long functions. Avoid deep nesting.
21. Avoid initialization dependencies across compilation units.
22. Minimize definitional dependencies. Avoid cyclic dependencies.
23. Make header files self-sufficient.
24. Always write internal #include guards. Never write external #include guards.
Standards)
























Functions and Operators
25. Take parameters appropriately by value, (smart) pointer, or reference.
26. Preserve natural semantics for overloaded operators.
27. Prefer the canonical forms of arithmetic and assignment operators.
28. Prefer the canonical form of ++ and --. Prefer calling the prefix forms.
29. Consider overloading to avoid implicit type conversions.
30. Avoid overloading &&, ||, or , (comma) .
31. Don’t write code that depends on the order of evaluation of function arguments.
Class Design and Inheritance
32. Be clear what kind of class you’re writing.
33. Prefer minimal classes to monolithic classes.
34. Prefer composition to inheritance.
35. Avoid inheriting from classes that were not designed to be base classes.
36. Prefer providing abstract interfaces.
37. Public inheritance is substitutability. Inherit, not to reuse, but to be reused.
38. Practice safe overriding.
39. Consider making virtual functions nonpublic, and public functions nonvirtual.
40. Avoid providing implicit conversions.
41. Make data members private, except in behaviorless aggregates (C-style structs).
42. Don’t give away your internals.
43. Pimpl judiciously.
44. Prefer writing nonmember nonfriend functions.
45. Always provide new and delete together.
46. If you provide any class-specific new, provide all of the standard forms (plain, in-place, and nothrow).

































Construction, Destruction, and Copying
47. Define and initialize member variables in the same order.
48. Prefer initialization to assignment in constructors.
49. Avoid calling virtual functions in constructors and destructors.
50. Make base class destructors public and virtual, or protected and nonvirtual.
51. Destructors, deallocation, and swap never fail.
52. Copy and destroy consistently.
53. Explicitly enable or disable copying.
54. Avoid slicing. Consider Clone instead of copying in base classes.
55. Prefer the canonical form of assignment.
56. Whenever it makes sense, provide a no-fail swap (and provide it correctly).
Namespaces and Modules
57. Keep a type and its nonmember function interface in the same namespace.
58. Keep types and functions in separate namespaces unless they’re specifically intended to work together.
59. Don’t write namespace usings in a header file or before an #include.
60. Avoid allocating and deallocating memory in different modules.
61. Don’t define entities with linkage in a header file.
62. Don’t allow exceptions to propagate across module boundaries.
63. Use sufficiently portable types in a module’s interface.
Templates and Genericity
64. Blend static and dynamic polymorphism judiciously.
65. Customize intentionally and explicitly.
66. Don’t specialize function templates.
67. Don’t write unintentionally nongeneric code.
Error Handling and Exceptions
68. Assert liberally to document internal assumptions and invariants.
69. Establish a rational error handling policy, and follow it strictly.
70. Distinguish between errors and non-errors.
71. Design and write error-safe code.
72. Prefer to use exceptions to report errors.
73. Throw by value, catch by reference.
74. Report, handle, and translate errors appropriately.
75. Avoid exception specifications.




























STL: Containers
76. Use vector by default. Otherwise, choose an appropriate container.
77. Use vector and string instead of arrays.
78. Use vector (and string::c_str) to exchange data with non-C++ APIs.
79. Store only values and smart pointers in containers.
80. Prefer push_back to other ways of expanding a sequence.
81. Prefer range operations to single-element operations.
82. Use the accepted idioms to really shrink capacity and really erase elements.
STL: Algorithms
83. Use a checked STL implementation.
84. Prefer algorithm calls to handwritten loops.
85. Use the right STL search algorithm.
86. Use the right STL sort algorithm.
87. Make predicates pure functions.
88. Prefer function objects over functions as algorithm and comparer arguments.
89. Write function objects correctly.
Type Safety
90. Avoid type switching; prefer polymorphism.
91. Rely on types, not on representations.
92. Avoid using reinterpret_cast.
93. Avoid using static_cast on pointers.
94. Avoid casting away const.
95. Don’t use C-style casts.
96. Don’t memcpy or memcmp non-PODs.
97. Don’t use unions to reinterpret representation.
98. Don’t use varargs (ellipsis).
99. Don’t use invalid objects. Don’t use unsafe functions.
100. Don’t treat arrays polymorphically.
Zadání:
◦ kontejner obsahující čísla libovolného typu
 int, double, string, complex, ...
Technické upřesnění:
◦ třída Seznam
◦ operace append, print
◦ společný předek prvků AbstractNum
◦ konkrétní prvky IntNum, DoubleNum, ...
◦ stačí jednoduchá implementace polem
◦ pole objektů vs. pole odkazů
S
IN AN
x
DN AN
d
IN AN
x
class AbstractNum {
public:
virtual void print()=0;
virtual ~AbstractNum() {}
};
abstraktní předek
umí existovat a vytisknout se
virtuální destruktor!
int main(int argc, char** argv){
Seznam s;
s.append( new .... );
s.append( new .... );
s.append( new .... );
s.print();
return 0;
}
class Seznam
{
public:
void append( AbstractNum *p);
void print();
Seznam();
~Seznam();
private:
enum { MAX = 100 };
AbstractNum* pole[MAX];
int n;
};
přidávání dynamicky
vytvořených konkrétních typů
// konstruktor
Seznam::Seznam()
{
for(int i=0; i<MAX; ++i)
pole[i]=0;
n=0;
}
// destruktor
Seznam::~Seznam()
{
for(int i=0; i<n; ++i)
delete pole[i];
n=0;
}
// tisk seznamu
void Seznam::print()
{
for(int i=0; i<n; ++i)
pole[i]->print();
}
// pridani prvku do seznamu
void Seznam::append(AbstractNum* p)
{
if (n<MAX)
pole[n++]=p;
}
class Seznam
{
public:
void append( AbstractNum *p);
void print();
Seznam();
~Seznam();
private:
enum { MAX = 100 };
AbstractNum* pole[MAX];
int n;
};
každý prvek ví jak se vytisknout
class IntNum : public AbstractNum {
public:
IntNum(int x) : x_(x) {}
virtual ~IntNum() {}
virtual void print() { cout << x_; }
private:
int x_;
};
konkrétní datové typy
implementují vlastní metody
jednotného rozhraní
class IntDouble : public AbstractNum {
public:
IntDouble(double d) : d_(d) {}
virtual ~IntDouble() {}
virtual void print() { cout << d_; }
private:
double d_;
};
kontejner obsahuje různé typy
... a všechny vytiskne
Seznam s;
s.append(new IntNum(234));
s.append(new DoubleNum(1.45));
s.append(new IntNum(67));
s.print();
Požadavek:

co když chci zakázat měnit hodnotu prvků
class IntNum : public AbstractNum {
public:
IntNum(int x) { x_ = x; }
private:
const int x_;
};
class IntNum : public AbstractNum {
public:
IntNum(int x) : x_(x) {}
private:
const int x_;
};
compiler error: x must be initialized in
constructor base / member initializer list
seznam inicializátorů
používejte všude, kde to lze
Problém:

přiřazení seznamů
int main(int argc, char** argv){
Seznam s, s2;
s.append(new IntNum(234));
s.append(new DoubleNum(1.45));
s.append(new IntNum(67));
s.print();
s2 = s;
return 0;
}
Je to korektní kód?
Problém:

přiřazení seznamů
int main(int argc, char** argv){
Seznam s, s2;
s.append(new IntNum(234));
s.append(new DoubleNum(1.45));
s.append(new IntNum(67));
s.print();
s2 = s;
return 0;
}
Tady!
Spadne to!

Kde?



v destruktoru ~Seznam
Proč?
Navíc:

memory leaks
problém je v s2 = s;
v Seznam není operator=
kompilátor si ho vyrobí automaticky
okopíruje datové položky a ukazatele !!!
destruktor s2 dealokuje prvky
destruktor s znovu odalokuje prvky
bloky už ale neexistují !
Možné řešení:

zakázání přiřazení
class Seznam
{
public:
void append( AbstractNum *p);
void print();
Seznam();
~Seznam();
private:
Seznam& operator=(const Seznam&);
enum { MAX = 100 };
AbstractNum* pole[MAX];
int n;
};
operator= v sekci private
znemožní přiřazení seznamů
stačí pouze deklarace (bez těla)
nikdo ho nemůže zavolat
je to už teď konečně korektní ??
Není!

copy konstruktor!
int main(int argc, char** argv){
Seznam s;
s.append(new IntNum(234));
s.append(new DoubleNum(1.45));
s.append(new IntNum(67));
s.print();
Seznam s2 = s;
return 0;
}
oprator= a copy konstruktor
by se měly chovat stejně!
class Seznam
{
public:
void append( AbstractNum *p);
void print();
Seznam();
~Seznam();
private:
Seznam& operator=(const Seznam&);
Seznam(const Seznam&);
enum { MAX = 100 };
AbstractNum* pole[MAX];
int n;
};
je to už teď konečně korektní ??

Pokud chceme dovolit přiřazení (kopírování),
je nutné si ujasnit logiku
Seznam a, b;
....
b = a;
a[1]->x = 999;
// b[1]->x ???
◦ má se změna projevit i v druhém seznamu?
◦ kopie hodnot nebo kopie datové struktury?
◦ typicky: chování jako kdyby se okopírovaly všechny prvky

Každá třída s odkazy na dynamicky alokovaná data
◦ buď zakázat přiřazení
 operator= a copy konstruktor do sekce private
◦ nebo nadefinovat kopírování
 napsat vlastní duplikaci
 VŽDY napsat hlavičku operatoru = a copy konstruktoru!
Seznam& Seznam::operator=( const Seznam& s)
{
for(int i=0; i<s.n; ++i)
pole[i] = s.pole[i];
n = s.n;
return *this
}
okopíruji všechny prvky
class Seznam
{
public:
void append( AbstractNum *p);
void print();
Seznam();
~Seznam();
Seznam& operator=(const Seznam&);
private:
enum { MAX = 100 };
AbstractNum* pole[MAX];
int n;
};
je to správně ??
Je to správně?
 Není !!
nezruší se předchozí odkazy!
 memory leaks

Seznam& Seznam::operator=( const Seznam& s)
{
for(int i=0; i<n; ++i)
// jako v destruktoru
delete pole[i];
for(int i=0; i<s.n; ++i) // jako v copy konstr.
pole[i] = s.pole[i];
n = s.n;
return *this
}
nejdříve zruším všechny
prvky cílového kontejneru
je to už teď správně ??
Je to už teď správně?
 Není !!
okopírují se pouze ukazatele
 data zůstanou stejná
 prakticky totéž, jako kdybychom nechali automaticky vygenerovaný
operator =
 musíme vygenerovat nové prvky

Seznam& Seznam::operator=( const Seznam& s)
{
for(int i=0; i<n; ++i)
delete pole[i];
for(int i=0; i<s.n; ++i)
pole[i] = new AbstractNum( *s.pole[i]);
n = s.n;
return *this
}
dynamická alokace nového
prvku
přímá konverze odvozené
třídy na AbstractNum&
je to už teď správně ??
Je to už teď správně?
 Není !!
AbstractNum je abstraktní třída
 nelze instanciovat (vytvořit objekt)
 neprojde kompilátorem

class AbstractNum {
public:
virtual void print() {};
virtual ~AbstractNum() {}
};
psychicky zdeptaný programátor:
Seznam& Seznam::operator=( const Seznam& s)
{
for(int i=0; i<n; ++i)
delete pole[i];
for(int i=0; i<s.n; ++i)
pole[i] = new AbstractNum( *s.pole[i]);
n = s.n;
return *this
}
tak tu abstraktnost odstraníme!
je to už teď správně ??
Je to už teď správně?
 Není !!
IN AN
vytvoří se pouze část objektu - společný předek
 mnohem horší chyba než předchozí případ
 projde kompilátorem, nespadne, ale dělá nesmysly!
 slicing
x


AN
Co s tím?
když je skutečná hodnota IntNum - vytvořit IntNum
 když je skutečná hodnota DoubleNum - vytvořit doubleNum

class AbstractNum {
public:
enum T { T_INT, T_DOUBLE, ...};
virtual T get_t() const;
virtual void print()=0;
virtual ~AbstractNum() {}
};
switch( s.pole[i]->get_t()) {
case AbstraktNum::T_INT:
pole[i] = new IntNum(*s.pole[i]);
break;
...
je to už teď správně ??
Je to už teď správně?
 Nooo..... dělá to to, co má, ale ...
je to ošklivé - těžko rozšiřitelné
 přidání nového typu vyžaduje zásah do impl. společného předka!
 navíc syntaktická chyba
 předka nelze automaticky konvertovat na potomka

new IntNum(*s.pole[i]) - skutečný parametr typu AbstractNum&
 konverze
 new IntNum(* (IntNum*) s.pole[i])
 new IntNum( (IntNum&) *s.pole[i])


Jak to udělat lépe?
využít mechanismus pozdní vazby
 každý prvek bude umět naklonovat sám sebe
 rozhraní v AbstractNum, implementace v IntNum, DoubleNum, ...
 virtuální klonovací metoda

class AbstractNum {
public:
virtual AbstractNum* clone() const =0;
virtual void print()=0;
virtual ~AbstractNum() {}
};
class IntNum : public AbstractNum {
public:
virtual AbstractNum* clone() const
{ return new IntNum(*this); }
IntNum(int x) : x_(x) {}
private:
const int x_;
};
Seznam& Seznam::operator=( const Seznam& s)
{ ...
for(int i=0; i<s.n; ++i)
pole[i] = s.pole[i]->clone();
...
jednotné rozhraní
na klonovací funkce
starší norma: musí být typu AbstractNum*
jinak by to nebyla stejná virt. metoda
od 0x11: kovariantní návratový typ povolen
IN AN
x
IntNum
AbstractNum
případné posunutí ukazatelů řeší
automaticky mechanismus virt. metod
je to už teď správně ??
Je to už teď správně?
 Pořád není !!!!
this
&s
co když někdo provede s = s ?
 takhle blbě to asi nikdo nenapíše, ale ...
 Seznam p[100];
p[i] = p[j];
 nejprve se zruší všechny prvky
 ... a pak se kopírují dealokované bloky!!!
 ani vynulování ukazatelů moc nepomůže
 neokopírovalo by se nic
 nutná ochrana!

Seznam& Seznam::operator=( const Seznam& s)
{
if( this == &s) return *this;
...
rovnost ukazatelů  stejný objekt
je to už teď správně ??
Seznam& Seznam::operator=( const Seznam& s)
{
if( this == &s) return *this;
...
rovnost ukazatelů  stejný objekt
Je to už teď správně?
 .... no teď už snad ano




ale co když jsou referencované objekty velké?
časté kopírování neefektivní
 optimalizace
zachování sémantiky vs. odlišná implementace
reference counting, ...

similar documents