Programování v C++ David Bednárek www.ksi.mff.cuni.cz/~bednarek
Pravidla studia NPRG041 2/2 Z,Zk
Zápis na cvičení Elektronický
zápis do jednotlivých skupin
is.cuni.cz/studium • Zápis předmětů a rozvrhu - zápis • Grupíček - výsledky
Zapsáni musejí být všichni Do 18.10. Kapacita laboratoře je omezena, skupiny nelze přeplňovat Zvláštní skupina pro repetenty • Repetenti kontaktují cvičícího do 18.10. Udělit
zápočet může jen cvičící, ke kterému je student zapsán Kdo nebude do 18.10. zapsán, zápočet v tomto šk. roce nedostane
Udělení zápočtu Základní
podmínky společné všem skupinám
Úspěšné složení zápočtového testu • 1. a 2. pokusy ve zkouškovém období ... 3. pokusy v dubnu • 2-3 hodiny v laboratoři, společně pro všechny skupiny
Vypracování zápočtového programu • Dohoda o tématu - do listopadu • Předvedení cvičícímu do 31.3.2014 • Doladění a odevzdání do 23.5.2014 Další
podmínky udělení zápočtu určuje cvičící
Cvičící může podmínky individuálně upravit, pokud se s ním student na začátku semestru dohodne Přiměřená účast na cvičeních Úspěšné odevzdání domácího úkolu
Zkouška Zkouška
bude provedena formou abc-testu
Vlastnosti a pravidla jazyka C++ Používání knihoven C++ (kontejnery, algoritmy, iostream) Typické konstrukce objektového programování Run-time/static polymorphism Termíny
Ve zkouškovém období ZS Během výuky v LS
Pravidla pro budoucí neúspěšné Zkouška
Pokud letos složíte zkoušku se známkou výborně nebo velmi dobře a nedostanete zápočet, bude vám příští rok uznána • Tento mechanismus je implementován zkoušejícími, nikoliv studijním oddělěním Zápočet
Pokud nedostanete zápočet, budete příští rok opakovat ty části, které jste letos nesplnili • Podmínky splněné letos se automaticky uznávají • V příštím roce se musíte na začátku semestru přihlásit v SISu k některému z cvičících a dohodnout se s ním na konkrétních podmínkách
Historie C++
Historie C++
inspirace
BCPL
B
C
(Cambridge 1966)
(Bell Labs. 1969)
(Bell Labs. 1971)
nadmnožina téměř nadmnožina významná změna
K&R C
C with classes
(Kernigan & Ritchie 1978)
(Stroustrup 1979)
The C++ programming language (Stroustrup 1985)
C++98 (ISO/IEC 14882 1998)
šablony
C++03 (ISO/IEC 14882 2003)
C++TR1 (ISO/IEC 19768 2007)
paralelismus
C++11
C++14
(ISO/IEC 14882 2011)
(2014+)
Historie C++ a C
inspirace
BCPL
B
C
(Cambridge 1966)
(Bell Labs. 1969)
(Bell Labs. 1971)
nadmnožina téměř nadmnožina významná změna
K&R C
C with classes
(Kernigan & Ritchie 1978)
(Stroustrup 1979)
The C++ programming language (Stroustrup 1985)
ANSI C (ANSI X3J11 1989)
C++98
C99
(ISO/IEC 14882 1998)
šablony
(ISO/IEC 9899 1999)
C++03 (ISO/IEC 14882 2003)
C++TR1 (ISO/IEC 19768 2007)
C11 (ISO/IEC 9899 2011)
paralelismus
C++11
C++14
(ISO/IEC 14882 2011)
(2014+)
Historie C++ - Objective-C BCPL
B
C
(Cambridge 1966)
(Bell Labs. 1969)
(Bell Labs. 1971)
inspirace nadmnožina téměř nadmnožina významná změna
K&R C Objective-C
C with classes
(Kernigan & Ritchie 1978)
(Stroustrup 1979)
(Cox & Love 1981)
The C++ programming language
Object-Oriented Programing (Cox 1986)
(Stroustrup 1985)
ANSI C (ANSI X3J11 1989)
C++98
C99
(ISO/IEC 14882 1998)
šablony
(ISO/IEC 9899 1999)
C++03
Objective-C 2.0
(ISO/IEC 14882 2003)
(Apple 2006)
C++TR1 (ISO/IEC 19768 2007)
Objective-C++ (Apple 2010)
C11 (ISO/IEC 9899 2011)
paralelismus
C++11
C++14
(ISO/IEC 14882 2011)
(2014+)
Historie C++ - významné příbuzné jazyky BCPL
B
C
(Cambridge 1966)
(Bell Labs. 1969)
(Bell Labs. 1971)
inspirace nadmnožina téměř nadmnožina významná změna
K&R C Objective-C
C with classes
(Kernigan & Ritchie 1978)
(Stroustrup 1979)
(Cox & Love 1981)
The C++ programming language
Object-Oriented Programing (Cox 1986)
(Stroustrup 1985)
ANSI C (ANSI X3J11 1989)
Java (Sun 1995)
C++98
C99 (ISO/IEC 9899 1999)
(ISO/IEC 14882 1998)
šablony
C# (Microsoft 2002)
Objective-C 2.0
C++03 (ISO/IEC 14882 2003)
(Apple 2006)
C++/CLI (Microsoft 2005)
C++TR1 (ISO/IEC 19768 2007)
Objective-C++ (Apple 2010)
C11 (ISO/IEC 9899 2011)
paralelismus
C++11
C++14
(ISO/IEC 14882 2011)
(2014+)
Historie C++ - použití C v jádrech OS BCPL
B
C
(Cambridge 1966)
(Bell Labs. 1969)
(Bell Labs. 1971)
inspirace nadmnožina
Unix
téměř nadmnožina
1973
významná změna
K&R C
C with classes
(Kernigan & Ritchie 1978)
Objective-C (Cox & Love 1981)
(Stroustrup 1979)
MacOS
Object-Oriented Programing (Cox 1986)
The C++ programming language
1984
(Stroustrup 1985)
ANSI C (ANSI X3J11 1989)
Linux
Java
1991
Windows NT
(Sun 1995)
1993
C++98
C99
OS-X
(ISO/IEC 9899 1999)
2000
(ISO/IEC 14882 1998)
šablony
C# (Microsoft 2002)
Objective-C 2.0
C++03 (ISO/IEC 14882 2003)
(Apple 2006)
C++/CLI (Microsoft 2005)
C++TR1 (ISO/IEC 19768 2007)
Objective-C++ (Apple 2010)
C11 (ISO/IEC 9899 2011)
paralelismus
C++11
C++14
(ISO/IEC 14882 2011)
(2014+)
Literatura
Literatura Pro začátečníky - před C++11 Bruce Eckel: Thinking in C++ (2000) Myslíme v jazyku C++ (Grada 2000) Miroslav Virius: Pasti a propasti jazyka C++ (Computer Press 2005) Programování v C++ (ČVUT 2001) Andrew Koenig, Barbara E. Moo: Accelerated C++ (2000) Stanley B. Lippman: Essential C++ (2000)
Literatura Pro středně pokročilé - před C++11 Andrei Alexandrescu, Herb Sutter: C++ Coding Standards (2005) Scott Meyers: Effective C++ (1998) More Effective C++ (1996) Effective STL (2001) Herb Sutter: Exceptional C++ (2000) More Exceptional C++ (2002) Exceptional C++ Style (2004) Nicolai M. Josuttis: Object-Oriented Programming in C++ (2002) The C++ Standard Library (1999)
Literatura Až si budete myslet, že všechno umíte - před C++11 Andrei Alexandrescu: Modern C++ Design (2001) Moderní programování v C++ (Computer Press 2004) David Vandevoorde, Nicolai M. Josuttis: C++ Templates (2003)
Literatura C++11 Scott Meyers: Overview of the New C++ (C++11) 360 slajdů z přednášek Vysvětluje motivaci k novým vlastnostem Bjarne
Stroustrup: The C++ Programming Language - Fourth Edition Addison-Wesley. ISBN 978-0321563842. May 2013
Učebnice celého C++ Zatím jediná učebnice obsahující C++11
Je lepší C++ nebo Java/C#?
Je lepší C++ nebo Java/C#? Špatná otázka
Co programovat v C++ Pro které oblasti je C++ lepší než Java/C#? Důraz na výkon C++ umožňuje programovat způsobem, který neubírá na výkonu • Když budete programovat v C++ stejným stylem jako v Java/C#, dostanete přibližně stejný výkon Spolupráce
s hardware
C++ nechystá na programátora nepříjemná překvapení (GC etc.) Embedded assembler, spojování s jinými jazyky Spolupráce
s OS
Všechny významné OS mají v C jádro a tudíž i rozhraní OS Většina systémových aplikací je v C nebo C++ Nativní knihovny jazyků Java/C# jsou implementovány v C/C++ Generické
programování
Mechanismus šablon v C++ je silnější než v C/C++ Způsob implementace šablon v C++ neubírá na výkonu
Co programovat v C++ Programování orientované na výkon Numerické výpočty Převládající jazyky: FORTRAN, C Pomalý posun směrem k C++ Databázové
systémy
Převládající jazyky: C/C++ • Existují i databázové systémy v Javě • Spolehlivé srovnání výkonu neexistuje Proč
je Java/C# pomalejší?
Garbage collection • GC způsobuje mj. problémy s využitím cache • Programování bez GC je pracnější, ale dává lepší výsledky Chybí pokročilé metody optimalizace v překladačích • Vektorizace, transformace cyklů, ... Existují i situace, kdy je Java/C# rychlejší • Překladače Javy/C# mají jednodušší úlohu
Co programovat v C++ Proč C++ a ne C Stávající aplikace/knihovny/OS jsou často v C Programování
v C++ je pohodlnější než v C
Menší pravděpodobnost chyb Šablony, operátory, zapouzdření, ... Při troše šikovnosti stejný výkon jako v C Moduly
psané v C++ a C lze spojovat
extern "C" void do_something_in_C( int x); void my_Cplusplus_function( int x) { do_something_in_C( x); } extern "C" void call_me_from_C( int y) { /* C++ code here */ }
Co neprogramovat v C++ Co raději neprogramovat v C++ Interaktivní
aplikace s GUI
C++ nemá standardizované rozhraní na GUI Nativní rozhraní GUI v OS je většinou archaické C Knihovny pro GUI jsou archaické, nepřenositelné nebo obojí • Qt, GTK+, wxWidgets... Garbage Collection při programování GUI citelně chybí Pokud je zároveň zapotřebí výkon, nic jiného než C++ nezbývá Aplikace
skládané z mnoha cizích součástí
Standard C++ poskytuje nedostatečné služby OS apod. Cizí knihovny obvykle doplňují chybějící části vlastní tvorbou Různé implementace chybějících částí mohou být v konfliktu
Proč C++ Proč (stále ještě) učíme C++? • Většina řadových programátorů v C++ programovat nebude MFF
chce vychovávat elitu
Programování OS, databází, překladačů Vědecké výpočty vyžadující výkon Hry, robotika,... Údržba rozsáhlých a historických softwarových systémů Porozumíte-li
tomu, jak funguje C++, budete lépe rozumět
jiným programovacím jazykům architektuře počítačů a operačních systémů překladačům Zvládnutí
C++ je odznakem zdatnosti matfyzáka
Hello, World! #include
int main( int argc, char * * argv) { std::cout << "Hello, world!" << std::endl; return 0; }
Vstupní
bod programu
Dědictví jazyka C • Žádné třídy ani metody Globální funkce main Parametry
programu
Z příkazové řádky • Děleno na kousky Archaické datové typy • Ukazatel na ukazatel • Logicky pole polí std
- namespace knihoven cout - standardní výstup globální proměnná <<
- výstup do streamu
přetížený operátor endl
- oddělovač řádek
globální proměnná
Hello, World! Dělení do modulů Rozhraní
modulů je nutno opsat do zvláštního souboru .hpp - hlavičkový soubor
Definující
i používající modul tento soubor inkluduje
// world.hpp #ifndef WORLD_HPP_ #define WORLD_HPP_ void world(); #endif
textová direktiva #include // main.cpp #include "world.hpp" int main( int argc, char * * argv) { world(); return 0; }
// world.cpp #include "world.hpp" #include void world() { std::cout << "Hello, world!" << std::endl; }
Hello, World! // world.hpp #ifndef WORLD_HPP_ #define WORLD_HPP_ #include #include <string> typedef std::vector< std::string> t_arg; void world( const t_arg & arg); #endif
// main.cpp #include "world.hpp" int main( int argc, char * * argv) { world( t_arg( argv + 1, argv + argc)); return 0; }
// world.cpp #include "world.hpp" #include void world( const t_arg & arg) { if ( arg.empty() ) { std::cout << "Hello, world!" << std::endl; } }
Architektura Překladače / interpretry
CPU
CPU
CPU rozumí pouze binárním kódu
CPU 01010000 01110100 11010111 10010110 00100010 10110001
1940... – programování ve strojovém kódu
CPU 01010000 01110100 11010111 10010110 00100010 10110001
1940... – programování ve strojovém kódu
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
CPU 01010000 01110100 11010111 10010110 00100010 10110001
1940... – programování ve strojovém kódu
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
X
CPU 01010000 01110100 11010111 10010110 00100010 10110001
X X X X X X X X XX X XX XX XX X XX X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X XX X X X XX X XXX X X X X X X X
1950... – assembler
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0 PRINT NOGEN BEGIN BEGIN REGS SR R2,R2 SR R3,R3 LOOP AR R2,R3 LA R3,1(R0,R3) C R3,=F'10' BNE LOOP CVD R2,DBL ED RESULT,DBL+6 WTO RESULT RETURN LTORG RESULT DC X'40202120' DBL DC D'0' END BEGIN
CPU assembler
X
CPU 01010000 01110100 11010111 10010110 00100010 10110001
X X X X X X X X XX X XX XX XX X XX X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X XX X X X XX X XXX X X X X X X X
1950... – operační systém
PRINT NOGEN BEGIN BEGIN REGS SR R2,R2 SR R3,R3 LOOP AR R2,R3 LA R3,1(R0,R3) C R3,=F'10' BNE LOOP CVD R2,DBL ED RESULT,DBL+6 WTO RESULT RETURN LTORG RESULT DC X'40202120' DBL DC D'0' END BEGIN
CPU assembler
X
CPU
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
loader
X X X X X X X X XX X XX XX XX X XX X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X XX X X X XX X XXX X X X X X X X
1950... – operační systém
PRINT NOGEN BEGIN BEGIN REGS SR R2,R2 SR R3,R3 LOOP AR R2,R3 LA R3,1(R0,R3) C R3,=F'10' BNE LOOP CVD R2,DBL ED RESULT,DBL+6 WTO RESULT RETURN LTORG RESULT DC X'40202120' DBL DC D'0' END BEGIN
X
CPU
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
loader
CPU assembler
myprog.exe
X X X X X X X X XX X XX XX XX X XX X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X XX X X X XX X XXX X X X X X X X
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
CPU
1950... – překladač
01010000 01110100 11010111 10010110 00100010 10110001
X X X
X X
X
X
X
X
operační systém
loader
X
myprog.exe
X X
X
X
XX
X
X
X
X
X
X
X X
XX X X X
X X X
CPU překladač Fortran
X
X
X
READ INPUT TAPE 5, 501, IA, IB, IC 501 FORMAT (3I5) IF (IA) 777, 777, 701 701 IF (IB) 777, 777, 702 702 IF (IC) 777, 777, 703 703 IF (IA+IB-IC) 777,777,704 704 IF (IA+IC-IB) 777,777,705 705 IF (IB+IC-IA) 777,777,799 777 STOP 1 799 S = FLOATF (IA + IB + IC) / 2.0 AREA = SQRT( S * (S - FLOATF(IA)) * (S - FLOATF(IB)) * + (S - FLOATF(IC))) WRITE OUTPUT TAPE 6, 601, IA, IB, IC , AREA STOP END
X X X X X X X X X XXXX X X X X X X X X X X X XX X X X X XX X X XX X X X XXX X X X X X XX XXXX X XXXX X XX XXX X X XX X X X
X X
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
CPU
1970... – překladač C
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
loader
#include <stdio.h> int main(int,char**) { printf( "Hello, world!\n"); }
CPU překladač C
myprog.exe
Hello, world!
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
CPU
1980... – překladač C++
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
loader
#include int main(int,char**) { std::cout << "Hello, world!\n"; }
CPU překladač C++
myprog.exe
Hello, world!
1960... – interpret(er)
CPU
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
10 INPUT "What is your name: ", U$ 20 PRINT "Hello "; U$ 30 INPUT "How do you want: ", N 40 S$ = "" 50 FOR I = 1 TO N 60 S$ = S$ + "*" 70 NEXT I 80 PRINT S$ 90 INPUT "Do you want? ", A$ 100 IF LEN(A$) = 0 THEN 90 110 A$ = LEFT$(A$, 1) 120 IF A$ = "Y" THEN 30 130 PRINT "Goodbye ";U$ 140 END
interpret operační systém
X X X X X X X X X XX X XX XX XX X XX X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X XX X X X XX X XXX X X X X X X X
Interpretace s mezikódem 10 INPUT "What is your name: ", U$ 20 PRINT "Hello "; U$ 30 INPUT "How do you want: ", N 40 S$ = "" 50 FOR I = 1 TO N 60 S$ = S$ + "*" 70 NEXT I 80 PRINT S$ 90 INPUT "Do you want? ", A$ 100 IF LEN(A$) = 0 THEN 90 110 A$ = LEFT$(A$, 1) 120 IF A$ = "Y" THEN 30 130 PRINT "Goodbye ";U$ 140 END
CPU
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
04FBC41E 77AB2000 1AE04E33
překladač
interpret
operační systém
X X X X X X X X X XX X XX XX XX X XX X X X X X X X XXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X XX X X X XX X XXX X X X X X X X
interpretovaný mezikód (bytecode)
CPU
myprog.class
překladač
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
04FBC41E 77AB2000 1AE04E33 Hello, world! CPU
public class HelloWorld { public static void main(String[] args) { System.out.println( "Hello, world!"); } }
interpret operační systém
JIT překladač
CPU
myprog.class
překladač
13 0 1 0 10 0 8 0 9 0 13 0 8 0 16 0 7 0 2 0 0 0 0 12 0 15 0 6 0 2 0 7 0 9 0 6 0 2 0 8 0 8 0 10 0 4 0 0 2 0 7 0 7 0 1 0 2 0 0 5 0 1 0 8 0 0 8 0 7 0 10 0 1 0 0 0 2 0 8 0 11 0 4 0 9 0 13 0 0 2 0 0 0 0 6 0 7 0 0 0 0 8 0 5 0 0 3 0 17 0 0 0 5 0 20 10 0
JIT překladač
CPU
public class HelloWorld { public static void main(String[] args) { System.out.println( "Hello, world!"); } }
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
Hello, world!
Srovnání JIT/non-JIT CPU překladač
myprog.class
JIT překladač
CPU
public class HelloWorld { public static void main(String[] args) { System.out.println( "Hello, world!"); } }
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
int main(int,char**) { std::cout << "Hello, world!\n"; }
CPU
#include
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
CPU překladač
myprog.exe
loader
Srovnání JIT/non-JIT JIT (Java, C#, C++/CLI)
non-JIT (C++)
Distribuuje se bytecode (.class, .exe)
Distribuuje se (někdy) jako binární instrukce (.exe)
Distribuce závislá na jazyku a překladači
Distribuce závislá na procesoru a OS
Překladač zná přesně cílovou architekturu, může pozorovat chování programu
Překladač má dost času na překlad
Dynamické spojování…? překladač
překladač
myprog.class
mylib.class JIT překladač
CPU
} public class } HelloWorld { public static void main(String[] args) { mylib.doit(); } }
01010000 01110100 11010111 10010110 00100010 10110001
#include int main() { int main() { doit(); } std::cout << "Hello, world!\n"; }
CPU
operační systém
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
překladač
myprog.exe
překladač
mylib.dll
loader
Dynamické spojování překladač
překladač
myprog.class
mylib.class JIT překladač
CPU
import acme.mylib; public class public class HelloWorld HelloWorld { { public static void public static void main(String[] args) main(String[] args) { System.out.println( { mylib.doit(); } "Hello, world!"); } } }
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
// mylib.hpp CPU
#include "mylib.hpp" #include int main() { int main() { doit(); } std::cout << "Hello, world!\n"; }
void doit();
01010000 01110100 11010111 10010110 00100010 10110001 operační systém
“překladač”
myprog.exe
“překladač”
mylib.dll
loader
Překlad jednoduchého programu - statické spojování // iostream // iostream
iostream.obj
#include #include namespace std { namespace std { extern ofstream extern ofstream cout, cerr; cout, cerr; }; };
// myprog.cpp #include int main() { std::cout << "Hello, world!\n"; }
msvcrt.lib
Kompilátor
myprog.obj
Linker
myprog.exe
Oddělený překlad a spojování modulů Standardní
Standardní .obj
Standardní
.lib
Uživatelské .hpp
Uživatelské .cpp
Kompilátor
Přeložené
.obj
Linker
Spustitelný soubor .exe
Spojování modulů
myprog.cpp #include "bee.hpp" int main(int,char**) { return B( 7); }
myprog.obj
Kompilátor
0000: 01010000 ???????? 11010111 export main(int,argv**) import B(int)
bee.hpp myprog.exe
#ifndef bee_hpp #define bee_hpp int B( int q); #endif
Linker
0000: 01010000 00001100 11010111 1100: 10010110 00100010 10110001
bee.cpp #include "bee.hpp" int B( int q) { return q+1; }
bee.obj
Kompilátor
0000: 10010110 00100010 10110001 export B(int)
make Standardní
Standardní .obj
Standardní
.lib
Uživatelské .hpp
Uživatelské .cpp
Kompilátor
Přeložené
Make
makefile
.obj
Linker
Spustitelný soubor .exe
Integrované prostředí Standardní
Standardní .obj
Standardní
.lib
Uživatelské .hpp
Uživatelské .cpp
Kompilátor
Přeložené
Editor
.obj
Linker
Spustitelný soubor .exe
Debugger
projekt
Statické knihovny Standardní
Standardní .obj
Standardní
.lib
Uživatelské .hpp
Uživatelské .cpp
Kompilátor
Přeložené
.obj
Knihovní
Knihovna
.hpp
Knihovní .cpp
Linker
Kompilátor
Přeložené
.obj
Spustitelný soubor .exe
.lib
Librarian
Dynamické knihovny (Microsoft) Standardní
Standardní .obj
Standardní
.lib
Uživatelské .hpp
Uživatelské .cpp
Kompilátor
Přeložené
.obj
Knihovní
Knihovna
.hpp
Knihovní .cpp
Linker
Kompilátor
Přeložené
.obj
Linker
Spustitelný soubor .exe
.lib
Knihovna .dll
Dynamické knihovny (GNU) Standardní
Standardní
.o
Standardní
.a
Uživatelské .hpp
Uživatelské .cpp
Kompilátor
Přeložené
.o
Linker
Kompilátor
Přeložené
.o
Librarian
Spustitelný soubor
Knihovní .hpp
Knihovní .cpp
Knihovna .so
Deklarace a definice
Deklarace a definice Deklarace Zápis sdělující, že věc (typ/proměnná/funkce/...) existuje Identifikátor Základní vlastnosti věci Umožňuje překladači přeložit kód, který na věc odkazuje • V některých případech je k tomu zapotřebí i definice
Definice Zápis, který určuje všechny vlastnosti věci Obsah třídy, inicializace proměnné, kód funkce Umožňuje překladači vygenerovat kód a data, která věc reprezentují za běhu Každá
definice je i deklarace Deklarace umožňují (některá) použití věci bez definice Oddělený překlad modulů Vyřešení cyklických závislostí Zmenšení objemu překládaného zdrojového kódu
Deklarace a definice One-definition rule #1: Jedna překladová jednotka... • (modul, tj. jedno .cpp včetně inkludovaných hpp) ...
smí obsahovat nejvýše jednu definici věci
One-definition rule #2: Program... • (tj. .exe včetně připojených .dll) ...
smí obsahovat nejvýše jednu definici proměnné nebo non-inline funkce Definice třídy, typu či inline funkce se v různých modulech opakovat smějí (typicky vložením téhož .hpp souboru) • Nejsou-li opakované definice totožné, nebo nesouhlasí-li definice s deklarací, program je nekorektní Diagnostika na úrovni programu není normou požadována a překladače/linkery ji dělají jen v jednoduchých případech
Deklarace a definice tříd a typů Deklarace
Definice
Třída
class A;
class A { ... };
Struktura
struct A;
struct A { ... };
Unie (v C++ prakticky nepoužitelné)
union A;
union A { ... };
Pojmenovaný typ
typedef typedef typedef typedef typedef typedef typedef typedef typedef
A A2; A * AP; std::shared_ptr< A> AS; A AA[ 10]; A AF(); AF * AFP1; A (* AFP2)(); std::vector< A> AV; AV::iterator AVI;
Deklarace a definice proměnných Deklarace
Definice
Globální proměnná
extern int x, y, z;
int x; int y = 729; int z( 729);
Statická položka třídy
class A { static int x, y, z; };
int A::x; int A::y = 729; int A::z( 729);
Statická konstantní položka třídy
class A { static const int x = 729; };
Statická lokální proměnná
void f() { static int x; static int y = 7, z( 7); }
Nestatická položka třídy
class A { int x, y; };
Nestatická lokální proměnná
void f() { int x; int y = 7, z( 7); };
Deklarace a definice funkcí non-inline
Deklarace (.hpp nebo .cpp)
Definice (.cpp)
Globální funkce
int f( int, int);
int f( int p, int q) { return p + q;}
Statická metoda
class A { static int f( int p); };
int A::f( int p) { return p + 1; }
Nestatická metoda
class A { int f( int p); };
int A::f( int p) { return p + 1; }
Virtuální metoda
class A { int A::f( int) virtual int f( int p); { return 0; }; }
inline
Deklarace (.hpp nebo .cpp)
inline int f( int p, int q) { return p + q; }
Globální inline funkce Nestatická inline metoda (a) Nestatická inline metoda (b)
Definice (.hpp nebo .cpp)
class A { int f( int p); };
inline int A::f( int p) { return p + 1; } class A { int f( int p) { return p+1;} };
Umístění dat
Umístění dat Statická
alokace = 1 instance na proces
Globální proměnná Statická položka třídy Statická lokální proměnná [C++11]
thread_local objekty = 1 instance na vlákno Zásobníková alokace = 1 instance na každé vyvolání Lokální proměnná Parametr předávaný hodnotou Návratová hodnota funkce Pomocná proměnná při výpočtu výrazu Dynamická
alokace = řízeno programem
Dynamicky alokovaná data (new/delete)
Inicializace Číselné
typy, ukazatele
Statická alokace • Inicializováno nulou Zásobníková nebo dynamická alokace • Neinicializováno! Třídy
/ struktury
Inicializováno konstruktorem • Lze určit parametry pro konstruktor Není-li konstruktor, platí tato pravidla pro jednotlivé části Parametr
předávaný hodnotou / návratová hodnota funkce
Inicializován copy-constructorem • Není-li definován, je generován překladačem
Okamžik inicializace a destrukce Inicializace
Destrukce
Globální proměnná
Před vstupem do main
Po výstupu z main
Statická položka třídy
Před vstupem do main
Po výstupu z main
Statická lokální proměnná
Při prvním průchodu řízení deklarací
Po výstupu z main
Lokální proměnná
V okamžiku průchodu řízení deklarací
Při výstupu z bloku
Parametr předávaný hodnotou
Před voláním funkce
Před návratem z funkce
Návratová hodnota funkce
V příkazu return
Po návratu z funkce
Pomocná proměnná při výpočtu výrazu
Když je vypočtena její hodnota
Na konci příkazu (v deklaraci: na konci bloku)
Dynamicky alokovaná data
Při volání new
Při volání delete
Nejdůležitější datové typy
Vybrané číselné typy bool
false, true
char
znak základní sady (např. ASCII, 8 bit)
std::wchar_t
znak rozšířené sady (např. Unicode, 16/32 bit)
int
celé číslo se znaménkem (obvykle 32 bit)
unsigned
celé číslo bez znaménka (obvykle 32 bit)
long long
extra velké celé číslo se znaménkem (64 bit)
unsigned long long
extra velké celé číslo bez znaménka (64 bit)
std::size_t
dostatečně velké číslo pro velikost čehokoliv (32/64 bit)
double
“reálné” číslo (Intel: 64 bit)
long double
přesnější “reálné” číslo (Intel: 80 bit)
std::complex<double>
komplexní číslo dané přesnosti
Další důležité typy std::string
řetězec (nad char)
std::wstring
řetězec (nad std::wchar_t)
std::istream
vstupní proud (nad char)
std::wistream
vstupní proud (nad std::wchar_t)
std::ostream
výstupní proud (nad char)
std::wostream
výstupní proud (nad std::wchar_t)
struct T { … }
struktura
std::pair
uspořádaná dvojice s prvky typu T1 a T2
std::vector
pole prvků typu T
std::list
seznam prvků typu T
std::map
asociativní pole prvků typu T indexované typem K
std::multimap
asociativní pole s opakováním
Složené typy v C++ Složené typy jsou iluze poskytovaná překladačem Souvislý úsek paměti dělený na elementární typy • sizeof(T) = velikost tohoto úseku • Zarovnání může vynutit nevyužití některých míst Veškerá manipulace je překladačem rozložena na manipulaci s elementárními typy • V jednoduchých případech (POD) lze kopírovat jako blok bajtů Pole:
T a[N]
N-tice stejných typů N musí být překladači známá konstanta Třída
(class nebo struct)
Pojmenované položky různých typů • Ve složitějších případech režijní informace Dědičnost implementována vložením předka • Virtuální dědičnost vyžaduje nepřímé odkazy na předky
Ukazatel vs. hodnota
Reference, ukazatelé, iterátory
Reference Konstrukce jazyka C++ Použití syntakticky shodné s hodnotou (r.a)
T & const T &
Ukazatel
Konstrukce jazyka C/C++ Zvláštní operátory pro přístup k hodnotě (*p, p->a) Ukazatelová aritmetika pro přístup k sousedům v polích Manuální alokace/dealokace objektů
T * const T *
Chytré ukazatele Třída ve standardních knihovnách C++ Zvláštní operátory pro přístup k hodnotě (*p, p->a) Automatická dealokace při zániku odkazů
std::shared_ptr< T> std::unique_ptr< T>
Iterátory Třídy reprezentující odkazy na prvky kontejneru typu K Zvláštní operátory pro přístup k hodnotě (*p, p->a) Napodobenina ukazatelové aritmetiky
K::iterator K::const_iterator
Referenční semantika C#/Java vs. C++ Referenční typy (C#,Java)
Ukazatele na objekty (C++)
class T { public int a; }
class T { public: int a; };
class test { static void f( T z) { z.a = 3; } static void g() { T x = new T(); //vznik
void f( T * z) { z->a = 3; } void g() { T * x = new T; //vznik
x.a = 1;
x->a = 1;
T y = x; //druhý odkaz
T * y = x; //druhý odkaz
y.a = 2; // x.a == 2
y->a = 2; // x->a == 2
f( x); // x.a == 3
f( x); // x->a == 3 delete x; //zánik je nutno vyvolat ručně
//zrušení zařídí garbage collector } }
}
Referenční semantika C#/Java vs. C++ Referenční typy (C#,Java)
Chytré ukazatele na objekty (C++)
class T { public int a; }
class T { public: int a; };
class test { static void f( T z) { z.a = 3; } static void g() { T x = new T(); //vznik
void f( T * z) { z->a = 3; } void g() { std::shared_ptr< T> x = new T; //vznik
x.a = 1;
x->a = 1;
T y = x; //druhý odkaz
std::shared_ptr< T> y = x; //druhý odkaz
y.a = 2; // x.a == 2
y->a = 2; // x->a == 2
f( x); // x.a == 3
f( x); // x->a == 3 //zrušení při zániku posledního odkazu
//zrušení zařídí garbage collector } }
}
Hodnotová semantika C#/Java vs. C++ Hodnotové typy (C#)
Objekty (C++)
struct T { int a; }
class T { public: int a; };
class test { static void f( T z) { z.a = 3; } static void g() { T x; //vznik
void f( T z) { z.a = 3; } void g() { T x; //vznik
x.a = 1;
x.a = 1;
T y = x; //kopie
T y = x; //kopie
y.a = 2; // x.a == 1
y.a = 2; // x.a == 1
f( x); // x.a == 1
f( x); // x.a == 1 //zrušení v okamžiku zániku proměnné
//zrušení v okamžiku zániku proměnné } }
}
Hodnotová semantika C#/Java vs. C++ Předání odkazem (C#) (hodnotové typy)
Předání odkazem (C++)
struct T { int a; }
class T { public: int a; };
class test { static void f( ref T z) { z.a = 3; } static void g() { T x; //vznik
void f( T & z) { z.a = 3; } void g() { T x; x.a = 1;
x.a = 1; f( ref x); // x.a == 3 } }
f( x); // x.a == 3 }
Referenční semantika C#/Java vs. C++ Předání odkazem (C#) Referenční typy
Předání odkazem (C++) Reference na ukazatel Užíváno řídce – nebezpečí chyb
class T { public int a; }
class T { public: int a; };
class test { static void f( ref T z) { z = new T(); //vznik } static void g() { T x = new T(); //vznik f( ref x); // x je nyní jiný objekt
void f( T * & z) { delete z; //zánik je nutno vyvolat ručně z = new T; //vznik } void g() { T * x = new T; //vznik f( x); // *x je nyní jiný objekt
//zrušení zařídí garbage collector }
delete x; //zánik je nutno vyvolat ručně
} }
Dynamická alokace my_class * p = 0; void f1() { p = new my_class( 20, 30); } void f2() { delete p; }
Dynamická
alokace pole
std::vector je lepší void f2( std::size_t n) { int * q = new int[ n]; q[ n-1] = p->m(); // ... delete[] q; }
Dynamickou
alokaci je nutné použít, pokud Rozsah života objektu se nekryje s vyvoláním funkce, nebo Alokovaný objekt je třída s dědičností zařazená do datové struktury
Ostatní
případy lze většinou nahradit použitím kontejnerů Kontejnery skrývají dynamickou alokaci uvnitř
Chytré ukazatele void f1() { std::unique_ptr< my_class> p = new my_class( 20, 30); std::unique_ptr< my_class> q = std::move( p); // nuluje p q.reset( new my_class( 10, 20)); // dealokuje původní objekt } // dealokuje druhý objekt void f2() { std::shared_ptr< my_class> p = new my_class( 20, 30); std::shared_ptr< my_class> q = p; q.reset( new my_class( 10, 20)); } // dealokuje oba objekty
Chytré
ukazatele řeší dealokaci samy C++11
unique_ptr
vždy jen jediný odkaz • zajistí překladač shared_ptr počítání odkazů • režie za běhu Slabší a pomalejší než Garbage Collection • problém: cyklické struktury
Reference
Reference Hodnotové typy (C++,C#,...)
Referenční Lokálně typy (C#,Java) existující objekty (C++)
f(int y);
class T {...}
void g() { int x; //vznik
void g() { T x = new T; //vznik
int y = z; //kopie
Reference na objekty (C++)
Ukazatele na objekty (C++)
class T {...}
class T {...}
class T {...}
void g() { T x; //vznik
void g() { T x; //vznik
void g() { T * x = new T; //vznik
T y = x; //druhý odkaz
T y = x; //kopie
T & y = x; //odkaz
T * y = x; //druhý odkaz
y.f();
y.f();
y.f();
y->f();
} //zrušení při //výstupu z bloku
} //zrušení zařídí //garbage //collector
} //zánik při //výstupu z bloku
} delete y; //zánik
//zánik při //výstupu z bloku
x->f(); //chyba }
Reference a ukazatelé Ukazatel
(*) a reference (&)
Z hlediska implementace ekvivalentní - ukazatel i reference na objekt jsou reprezentovány adresou tohoto objektu Ukazatel umí navíc: • Přesměrování jinam • Speciální hodnotu – nulový ukazatel • Ukazatelovou aritmetiku – posouvání na sousední objekty v poli • Dealokaci – operator delete Referenci je možno použít jenom jedním z následujících způsobů: • Typ proměnné • Typ položky třídy • Typ parametru funkce • Typ návratové hodnoty funkce Odlišná syntaxe použití: • Objekt a reference na objekt se syntakticky neliší • Ukazatel se dereferencuje operátorem * • Ukazatel na objekt se získá operátorem &
Reference a ukazatelé Pravidla pro začátečníky Kdy použít referenci: T & Výstupní parametr Návratová hodnota funkce zpřístupňující objekt • T & vector::at(size_t i) Kdy
použít konstantní referenci: const T &
Obvykle pouze kvůli rychlosti Parametr typu struktura/třída Návratová hodnota funkce zpřístupňující objekt ke čtení • const T & vector::at(size_t i) const Kdy
použít ukazatel (T *)
Je-li objekt dynamicky alokován Je-li nutná schopnost přesměrování, null, nebo aritmetika Nelze-li referenci správně namířit v okamžiku inicializace Kdy
použít konstantní ukazatel (const T *)
Sekundární odkaz na objekt, schopný pouze čtení
Reference a ukazatelé Pravidla pro pokročilejší Vlastník dynamicky alokovaného objektu je zodpovědný za jeho zrušení - musí použít ukazatel “T *” nelze-li jednoznačně určit vlastníka, použijte “shared_ptr” Uživatel
objektu
Pokud je životnost pozorovatele kratší než životnost objektu • lze použít referenci – “T &” nebo “const T &” Pokud je životnost delší než životnost objektu nebo jinak komplikovaná • je nutné použít ukazatel – “T *” nebo “const T *”
Reference Novinky
související s existencí reference
Inicializaci reference nelze nahradit přiřazením • Třídy obsahující referenci musí mít konstruktor Nelze rozlišit skutečné parametry předávané hodnotou a odkazem Návratová hodnota funkce může být l-hodnota
a.at( i) = x;
Zvýšené nebezpečí nekorektních konstrukcí
int & f() { int x; return x; // funkce vrátí referenci na neexistující objekt }
Vracení odkazem Funkce jako add nemůže vracet referenci add vrací hodnotu různou od všech svých parametrů hodnotu parametrů nesmí měnit reference nemá na co ukazovat Špatné
řešení č. 1: Lokální proměnná
Complex & add( const Complex & a, const Complex & b) { Complex r( a.Re + b.Re, a.Im + b.Im); return r; } BĚHOVÁ
CHYBA: r zaniká při návratu z funkce
Vracení odkazem Funkce jako add nemůže vracet referenci add vrací hodnotu různou od všech svých parametrů hodnotu parametrů nesmí měnit reference nemá na co ukazovat Špatné
řešení č. 2: Dynamická alokace
Complex & add( const Complex & a, const Complex & b) { Complex * r = new Complex( a.Re + b.Re, a.Im + b.Im); return * r; } PROBLÉM:
kdo to odalokuje ?
Vracení odkazem Funkce jako add nemůže vracet referenci add vrací hodnotu různou od všech svých parametrů hodnotu parametrů nesmí měnit reference nemá na co ukazovat Špatné
řešení č. 3: Globální proměnná
Complex g; Complex & add( const Complex & a, const Complex & b) { g = Complex( a.Re + b.Re, a.Im + b.Im); return g; } CHYBA:
globální proměnná je sdílená
Complex a, b, c, d, e = add( add( a, b), add( c, d));
Vracení odkazem Funkce jako add musí vracet hodnotou add vrací hodnotu různou od všech svých parametrů hodnotu parametrů nesmí měnit reference nemá na co ukazovat Správné
řešení
Complex add( const Complex & a, const Complex & b) { Complex r( a.Re + b.Re, a.Im + b.Im); return r; }
Zkrácený (ekvivalentní) zápis return Complex( a.Re + b.Re, a.Im + b.Im);
Vracení odkazem Funkce jako add musí vracet hodnotou Complex add( const Complex & a, const Complex & b) { Complex r( a.Re + b.Re, a.Im + b.Im); return r; } Data
se při vracení z funkce (několikrát) kopírují
z = add( x, y);
plnění proměnné r [constructor] kopie ven z funkce [copy-constructor] přiřazení [operator=] [C++11] rvalue reference mohou některá kopírování usnadnit Řešení
bez kopírování existuje
za cenu dynamické alokace u malých dat (Complex, string) se nevyplatí
Vracení odkazem Řešení bez kopírování class ComplexBody { public: ComplexBody( double r, double i) : re( r), im( i) {} double re, im; }; class Complex { public: Complex( double r, double i) : b( new ComplexBody( r, i)) {} double re() const { return b->re; } double im() const { return b->im; } private: std::shared_ptr< ComplexBody> b; };
Complex add( const Complex & a, const Complex & b) { return Complex( a.re() + b.re(), a.im() + b.im()); return r; }
Ekvivalent garbage-collection
ComplexBody je sdíleno několika instancemi Complex a zaniká s posledním z nich Garbage-collection metodou markand-sweep bývá rychlejší než počítání odkazů (shared_ptr) Pro malé třídy (Complex) je kopírování levnější než dynamická alokace
Reference a ukazatelé Pravidla pro vracení hodnot odkazem Pokud hodnota, kterou funkce vrací, existuje v nějakém objektu i po návratu z funkce, lze vrátit odkaz na tento objekt (konstantní) referencí T & vector::back(); const T & vector::back() const; T & T::operator+=(const T & b); T & T::operator++();// prefixová verze ++ vrací novou hodnotu Pokud
se hodnota, kterou funkce vrací, nově spočítala a není nikde uložena, funkce musí vracet hodnotou
T operator+( const T & a, const T & b); T T::operator++(int);// postfixová verze ++ vrací starou hodnotu
STL Standard Template Library
STL Kontejnery Prefabrikáty základních datových struktur Šablony parametrizované typem ukládaného objektu Všechny
kontejnery pracují s kopiemi vkládaných hodnot
Typ hodnot musí mít alespoň copy-constructor a destruktor Některé druhy kontejnerů či operací s nimi vyžadují i operator= nebo konstruktor bez parametrů Hodnoty
se přidávají a odebírají metodami odpovídajícími druhu kontejneru K hodnotám je možno přistupovat pomocí iterátoru, který reprezentuje inteligentní ukazatel dovnitř kontejneru Prostřednictvím iterátoru je možno měnit uložené hodnoty
STL – Příklad #include <deque> typedef std::deque< int> my_deque; my_deque the_deque; the_deque.push_back( 1); the_deque.push_back( 2); the_deque.push_back( 3); int x = the_deque.front(); // 1 the_deque.pop_front(); my_deque::iterator ib = the_deque.begin(); my_deque::iterator ie = the_deque.end(); for ( my_deque::iterator it = ib; it != ie; ++it) { *it = *it + 3; } int y = the_deque.back(); // 6 the_deque.pop_back() int z = the_deque.back(); // 5
STL – Kontejnery Sekvenční kontejnery • Seřazeny podle vzrůstající režie [C++11] array< T, N> - pole se staticky danou velikostí vector< T> - pole prvků s přidáváním zprava basic_string< T> - vektor s terminátorem • string = basic_string< char> - řetězec (ASCII) • wstring = basic_string< wchar_t> - řetězec (Unicode) deque< T> - fronta s přidáváním a odebíráním z obou stran [C++11] forward_list< T> - jednosměrně vázaný seznam list< T> - obousměrně vázaný seznam Odvozené
kontejnery
• queue< T> - fronta (maskovaná deque) • priority_queue< T> - prioritní fronta (vylepšený vector) • stack< T> - zásobník (maskovaný vector)
STL – Kontejnery Pomocné metody kontejneru Test prázdnosti bool empty() const Počet
prvků
size_t size() const
nepoužívat pro testy prázdnosti
STL – Kontejnery Metody kontejneru, vracející iterátory Odkaz na začátek kontejneru - první platný prvek iterator begin() const_iterator begin() const Odkaz za konec kontejneru iterator end() const_iterator end() const
- za poslední platný prvek
iterator
a const_iterator jsou typy definované uvnitř kontejneru, zvané iterátory přístupné konstrukcemi jako vector< int>::iterator vlastnosti iterátorů jsou mírně závislé na druhu kontejneru
Iterátor
kontejneru obsahujícího typ T je třída s operátory definovanými tak, aby se chovala podobně jako "T *" "(ukazatel na typ T) resp. "const T *" Vytváří se tak iluze, že kontejner je pole
Kategorie iterátorů Norma
C++ definuje 5 kategorií iterátorů
random_access bidirectional forward output input
Kategorie
určuje, které syntaktické konstrukce musí iterátor umožňovat
Pro
iterátor I jsou definovány tyto operace:
output
*I = x input
*I /* pouze pro čtení */ random_access,
bidirectional, forward
*I /* čtení i zápis */ všechny
kategorie
++I, I++ random_access,
bidirectional, forward, input
I1 == I2, I1 != I2 vector,
basic_string a deque
random_access list
bidirectional forward_list
forward
random_access,
bidirectional
--I, I-random_access
I += n, I + n, n + I I -= n, I - n, I1 - I2 I[ n] I1 < I2, I1 > I2, I1 <= I2, I1 >= I2
STL – Iterátory Operátory definované na iterátorech přístup k prvku, na který iterátor ukazuje T & iterator::operator *() const const T & const_iterator::operator *() const posouvání
iterátoru směrem ke konci
jednosměrný iterátor iterator & iterator::operator++() posouvání
iterátoru směrem k začátku
obousměrný iterátor iterator & iterator::operator--() libovolný
posun
iterátor s přímým přístupem iterator operator+( iterator, int) iterator operator-( iterator, int)
STL – Kontejnery Metody kontejneru pro vkládání iterator insert( iterator p, T x)
vsune (kopii) x před prvek, na který ukazuje iterátor p • vrací iterátor ukazující na vložený prvek void insert( iterator p, int n, T x)
vsune n kopií x před prvek, na který ukazuje iterátor p template< typename other_iterator> void insert( iterator p, other_iterator b, other_iterator e)
před prvek, na který ukazuje iterátor p, vsune kopii posloupnosti prvků ohraničené iterátory b a e • Tato posloupnost nesmí být uvnitř téhož kontejneru • Tato posloupnost může být součástí jiného druhu kontejneru
je-li p == end(), vkládání připojuje na konec kontejneru všechny dříve existující iterátory odkazující na tento kontejner jsou po použití insert neplatné, včetně p • výjimka: kontejnery list a forward_list iterátory mířící na původní prvky nebo end() zachovávají
STL – Kontejnery Konstruktory kontejneru K()
Vytvoří prázdný kontejner (array: kontejner dané velikosti) K( int n, T x = T())
Vytvoří kontejner s n kopiemi hodnoty x • Má-li typ T konstruktor bez parametrů, není třeba udávat x template< typename other_iterator> K( other_iterator b, other_iterator e)
Vytvoří kontejner naplněný kopií posloupnosti prvků ohraničené iterátory b a e • Tato posloupnost může být součástí jiného druhu kontejneru
STL – Kontejnery Původní vkládací metody kopírují vkládané prvky • Zbytečná práce, nemožnost použití některých typů (unique_ptr)
[C++11] move Metody insert a push_back/front mají move varianty iterator insert( iterator p, T && x)
Překladač ji použije, je-li parametrem pomocná proměnná... k.insert( it, a + b); // operator nebo funkce vracejici hodnotou k.insert( it, T( x, y, z)); // bezejmenny objekt
... nebo pokud je použito std::move k.insert( it, std::move( a));
• Move-semantika: Proměnná a bude (může být) vyprázdněna Move-semantika poskytuje úsporu času (a prostoru), pokud typ T • obsahuje dynamicky alokovaná data • je na move semantiku připraven (má move-konstruktory) std::vector< std::string> k; std::string a = "..."; k.push_back( a + ".kzr");
STL – Kontejnery Původní vkládací metody kopírují vkládané prvky • Zbytečná práce, nemožnost použití některých typů (unique_ptr)
[C++11] emplace Metody insert a push_back/front mají emplace varianty iterator emplace( iterator p, T1 && x1, ..., Tn && xn); void emplace_back( T1 && x1, ..., Tn && xn); void emplace_front( T1 && x1, ..., Tn && xn);
Do kontejneru je přidán nový prvek inicializovaný konstruktorem s parametry x1, ..., xn std::vector< std::vector< int> > k; k.emplace_back( 100, 0);
Šetří kopírování vkládaného prvku oproti původnímu zápisu k.push_back( std::vector< int>( 100, 0));
Šetří i v případě nepřipraveného typu bez move-semantiky • V případě vector< int> by to kopírování ušetřila sama move-semantika • Poznámka: rvalue reference v hlavičce emplace funkcí dovolují i lvalue operandy pomocí skládání referencí a funkce std::forward
STL – Kontejnery Metody kontejneru pro odebírání iterator erase( iterator p)
vyjme prvek, na který ukazuje iterátor p • p nesmí být rovno end() • vrací iterátor ukazující na prvek za vyjmutým prvkem (nebo end()) iterator erase( iterator p, iterator e)
vyjme všechny prvky mezi p a e, včetně p a vyjma e • p nesmí být rovno end() • vrací iterátor odkazující na prvek e (původní iterátor e nebude platný)
všechny iterátory odkazující na tento kontejner jsou po použití erase neplatné, včetně p a e • výjimka: kontejnery list a forward_list iterátory mířící na nesmazané prvky zachovávají void clear() { erase( begin(), end()); }
STL – Kontejnery Odvozené funkce manipulace s konci kontejneru Přidání jednotlivého prvku void push_front( T x) { return insert( begin(), x); }
• list, deque void push_back( T x) { return insert( end(), x); }
• list, deque, vector Odebrání
jednotlivého prvku
void pop_front() { return erase( begin()); }
• list, deque void pop_back() { return erase( --end()); }
• list, deque, vector
STL – Kontejnery Odvozené funkce kontejneru pro přístup k prvkům Prvky na koncích • list, deque, vector • podmínka: ! empty() T & front() const T & front() const
obě provádějí { return * begin(); } T & back() const T & back() const
obě provádějí { auto it = end(); --it; return * it; }
• [C++11] auto umožňuje deklaraci proměnné bez uvedení typu • typ si odvodí překladač z inicializace, v tomto případě K::[const_]iterator
STL – Kontejnery Odvozené funkce kontejneru pro přístup k prvkům Prvky uprostřed deque, vector, string podmínka: n < size() • at: porušení podmínky vyvolá výjimku • operator[]: porušení podmínky způsobí nedefinované chování T & at( int n) T & operator[]( int n) const T & at( int n) const const T & operator[]( int n) const
všechny provádějí return * ( begin() + n);
STL - Kontejnery složitost operace
na kontejneru s n prvky
list
deque
vector
basic_string
přídání / odebrání jednoho prvku na začátku
push_front pop_front
konstantní
konstantní
funkce neexistuje
funkce neexistuje
přídání / odebrání jednoho prvku na i-té pozici
insert erase
konstantní
min( i, n - i)
n-i
n-i
přídání / odebrání m prvků na i-té pozici
insert erase
m přesuny mezi seznamy (splice) jsou konstantní
m +min( i, n - i)
m+n-i
m+n-i
přídání / odebrání jednoho prvku na konci
push_back pop_back
konstantní
konstantní
konstantní
funkce neexistuje
nalezení i-tého prvku
begin() + i
funkce neexistuje
konstantní
konstantní
konstantní
paměťová náročnost
kontejneru s prvky velikosti s
(s + K) * n K řádově 16 B
q*s*n q kolem 1.2
q*s*n q kolem 1.2
q*s*n q kolem 1.2
Asociativní kontejnery
STL - Kontejnery Asociativní kontejnery Uspořádané
(samovyvažující se stromy)
set - množina multiset - množina s opakováním map - asociativní pole, tj. parciální zobrazení K -> T multimap - relace s rychlým vyhledáváním podle klíče K [C++11]
Hashované
[C++11] unordered_set - množina [C++11] unordered_multiset - množina s opakováním [C++11] unordered_map - asociativní pole, tj. parciální zobrazení K -> T [C++11] unordered_multimap - relace s rychlým vyhledáváním podle klíče K pair - pomocná šablona uspořádané dvojice • s položkami first, second
STL - Kontejnery Uspořádané
kontejnery vyžadují uspořádání na klíčích
Klíčem se rozumí první parametr šablony kontejneru Uspořádání se obvykle definuje operátorem < definovaným na typu klíče • Pozor na konstrukce typu set< char *>
Uspořádání lze rovněž zadat přídavným parametrem šablony Definované
uspořádání nemusí být antisymetrická relace
pokud platí ! (x < y) && ! (y < x) pak jsou prvky x a y považovány za ekvivalentní
STL - Kontejnery Uspořádané
kontejnery vyžadují uspořádání na klíčích
• Vystačí si s operací < V nejjednodušším případě to funguje samo std::map< std::string, int> mapa;
Pokud typ uspořádání nemá, lze jej definovat obecně bool operator<( const Klic & a, const Klic & b) { return ...; } std::map< Klic, int> mapa;
Pokud obecná definice uspořádání nevyhovuje, lze definovat uspořádání funktorem pouze pro daný typ kontejneru struct Usporadani { bool operator()( const Klic & a, const Klic & b) const { return ...; } }; std::map< Klic, int, Usporadani> mapa;
Pokud různé instance kontejneru mají mít různé uspořádání, lze do funktoru doplnit datové položky struct Usporadani { Usporadani( bool a); /*...*/ bool ascending; }; std::map< Klic, int, Usporadani> mapa( Usporadani( true));
STL - Kontejnery Uspořádání
na klíčích – implementace
• Knihovny definují funktor std::less< K> template< typename K> class less { public: bool operator()( const K & a, const K & b) const { return a < b; } };
• Šablona kontejneru má typový parametr - typ funktoru template< typename K, typename T, typename L = std::less< K> > class map { public: •
Konstruktor kontejneru dostává hodnotu funktoru
explicit map( const L & c = L()) : cmp_( c) { /*...*/ } /*...*/ private: •
Kontejner drží jednu instanci funktoru
•
Metody kontejneru volají operátor () na instanci funktoru
L cmp_; iterator find_( /*...*/) { /*...*/ if ( cmp_( x, y) ) /*...*/ } };
STL - Kontejnery Uspořádání
na klíčích – hashující kontejnery
Kontejner vyžaduje funktory pro hashování a pro porovnání template< typename K> class hash { public: std::size_t operator()( const K & a) const { /*...*/ } }; template< typename K> class equal_to { public: bool operator()( const K & a, const K & b) const { return a == b; } };
• Šablona kontejneru má dva další parametry template< typename K, typename T, typename H = std::hash< K>, typename E = std::equal_to< K> > class unordered_map; •
Konstruktor kontejneru dostává hodnoty funktorů
explicit unordered_map( std::size_t initial_bucket_count = /*...*/, const H & h = L(), const E & e = E());
STL - Kontejnery Asociativní kontejnery – procházení Kontejnery lze procházet iterátory Uspořádané kontejnery jsou prezentovány v uspořádání podle klíčů • Iterátor je bidirectional Hashující kontejnery jsou prezentovány v implementačnědefinovaném pořadí • Iterátor je forward Metody begin() a end() a operátory iterátorů mají stejný význam, jako u sekvenčních kontejnerů Kontejnery
[unordered_][multi]map< K, T> obsahují uspořádané dvojice - typ std::pair< const K, T> Klíč (it->first) nelze modifikovat, hodnotu (it->second) ano
Procházení
celého asociativního kontejneru se užívá
málokdy Iterátory se častěji získávají vyhledáváním
STL - Kontejnery Asociativní kontejnery – vyhledávání iterator iterator iterator iterator iterator iterator iterator iterator
set::find( T x) multiset::find( T x) map::find( K x) multimap::find( K x) unordered_set::find( T x) unordered_multiset::find( T x) unordered_map::find( K x) unordered_multimap::find( K x)
pokud v kontejneru existuje prvek s klíčem ekvivalentním x: • vrací iterátor ukazující na první takový prvek • multiset, multimap: další takové prvky jsou dostupné operací ++
jinak vrací end() složitost
operace
uspořadné kontejnery: O( log( size())) hashující kontejnery: průměrně O(1), nejhůře O( size())
STL - Kontejnery Uspořádané kontejnery - intervalové dotazy iterator iterator iterator iterator
set::lower_bound( T x) multiset::lower_bound( T x) map::lower_bound( K x) multimap::lower_bound( K x)
vrací první prvek jehož klíč není menší než x, případně end() iterator iterator iterator iterator
set::upper_bound( T x) multiset::upper_bound( T x) map::upper_bound( K x) multimap::upper_bound( K x)
vrací první prvek jehož klíč je větší než x, případně end() dvojici
takto získaných iterátorů lze využít v jiných funkcích téhož i jiného kontejneru operace mají logaritmickou složitost
STL - Kontejnery Asociativní kontejnery – vyhledávání s opakováním pair pair pair pair
multiset::equal_range( T x) multimap::equal_range( K x) unordered_multiset::equal_range( T x) unordered_multimap::equal_range( K x)
vrací polouzavřený interval [first,second) obsahující prvky s daným klíčem • pokud prvky neexistují, vrací prázdný interval na místě, kde by byly • odpovídá std::make_pair( lower_bound( x), upper_bound( x))
existuje i pro kontejnery bez opakování pair pair pair pair složitost
set::equal_range( T x) map::equal_range( K x) unordered_set::equal_range( T x) unordered_map::equal_range( K x)
operace
uspořadné kontejnery: O( log( size())) hashující kontejnery: průměrně O(1), nejhůře O( size())
STL - Kontejnery Asociativní kontejnery - vkládání set a map pair< iterator, bool> set::insert( T x) pair< iterator, bool> unordered_set::insert( T x) pair< iterator, bool> map::insert( pair< const K, T> x) pair< iterator, bool> unordered_map::insert( pair< const K, T> x) pokud
prvek ekvivalentní x (resp. x.first) v kontejneru není:
kopie x se vloží do kontejneru vrací pair< iterator, bool>( p, true) kde p je iterátor ukazující na vložený prvek pokud
prvek ekvivalentní x (resp. x.first) v kontejneru již je:
vrací pair< iterator, bool>( p, false) kde p je iterátor ukazující na existující prvek ekvivalentní x [C++11]
existuje též move-verze insert a emplace složitost operace uspořadné kontejnery: O( log( size())) hashující kontejnery: průměrně O(1), nejhůře O( size())
STL - Kontejnery Asociativní kontejnery - vkládání multiset a multimap iterator iterator iterator iterator
multiset::insert( T x) unordered_multiset::insert( T x) multimap::insert( pair< const K, T> x) unordered_multimap::insert( pair< const K, T> x)
kopie x se vloží do kontejneru vrací iterátor ukazující na vložený prvek [C++11]
existuje též move-verze insert a emplace složitost operace uspořadné kontejnery: O( log( size())) hashující kontejnery: průměrně O(1), nejhůře O( size())
STL - Kontejnery Asociativní kontejnery - odebírání podle klíče size_type [unordered_][multi]set::erase( T x) size_type [unordered_][multi]map::erase( K x)
odebere všechny prvky s klíčem ekvivalentním zadanému x vrací počet odebraných prvků složitost
operace pro N odebraných prvků
uspořadné kontejnery: O( log( size()) + N) hashující kontejnery: průměrně O(N), nejhůře O( size()) po
operaci budou iterátory na odebrané prvky neplatné asociativní kontejnery neinvalidují iterátory při insert/erase vyjma odebraných prvků
STL - Kontejnery Asociativní kontejnery - odebírání podle iterátoru - jeden prvek void erase( iterator p)
odebere prvek na který odkazuje iterátor p • p nesmí být rovno end()
operace má konstantní složitost • rozumí se amortizovaná/průměrná složitost podle
iterátorů - interval
void erase( iterator p, iterator e)
odebere všechny prvky mezi p a e, včetně p a vyjma e složitost operace pro N odebraných prvků • uspořadné kontejnery: O( log( size()) + N) • hashující kontejnery: průměrně O(N), nejhůře O( size()) po
operaci budou iterátory na odebrané prvky neplatné
STL - Kontejnery map/unordered_map – at/operator [ ] T & [unordered_]map::at( K x)
Vrátí referenci na hodnotovou (second) složku prvku s klíčem ekvivalentním x Pokud takový prvek neexistuje, vyvolá výjimku T & [unordered_]map::operator[]( K x) { return (*((insert(make_pair( x, T()))).first)).second; }
Vrátí referenci na hodnotovou (second) složku prvku s klíčem ekvivalentním x Pokud takový prvek neexistuje, vytvoří jej • Jeho hodnotová složka bude T()
Tento operátor je možno používat pro vkládání a přepisování prvků kontejneru • Kontejner [unordered_]map se chová jako asociativní pole (PHP) • Pozor: U sekvenčních kontejnerů automatické přidání nefunguje Pozor: Pro čtení nemusí být vhodné – přidává neexistující prvky
Algoritmy
STL – Algoritmy Šablona funkce for_each template Function for_each( InputIterator first, InputIterator last, Function f); first
a last jsou iterátory, určující procházený úsek nějakého kontejneru (všetně first, mimo last) f je buďto globální funkce (ukazatel na funkci), nebo funktor, tj. třída obsahující operator() Funkce
f (případně metoda operator()) je zavolána na každý prvek v zadaném intervalu prvek se předává jako * iterator, což může být odkazem funkce f tedy může modifikovat prvky seznamu
STL – Algoritmy Šablona funkce for_each template Function for_each( InputIterator first, InputIterator last, Function f) { for (; first != last; ++first) f( * first); return f; }
Takto napsanou šablonu lze zkompilovat pro jakékoliv f, na které lze aplikovat operátor (), tedy jak pro funkci, tak pro funktor
STL – Algoritmy Použití funkce for_each void my_function( double & x) { x += 1; } void increment( list< double> & c) { for_each( c.begin(), c.end(), my_function); }
[C++11] Lambda Nová syntaktická konstrukce generující funktor void increment( list< double> & c) { for_each( c.begin(), c.end(), []( double & x){ x += 1;}); }
STL – Algoritmy Použití funkce for_each class my_functor { public: double v; void operator()( double & x) const { x += v; } my_functor( double p) : v( p) {} }; void add( list< double> & c, double value) { for_each( c.begin(), c.end(), my_functor( value)); }
[C++11] Lambda void add( list< double> & c, double value) { for_each( c.begin(), c.end(), [=]( double & x){ x += value;}); }
STL – Algoritmy Použití funkce for_each class my_functor { public: double s; void operator()( const double & x) { s += x; } my_functor() : s( 0.0) {} }; double sum( const list< double> & c) { my_functor f; f = for_each( c.begin(), c.end(), f); return f.s; }
[C++11] Lambda double sum( const list< double> & c) { double s = 0.0; for_each( c.begin(), c.end(), [&]( const double & x){ s += x;}); return s; }
STL – Algoritmy Použití funkce for_each class my_functor { public: double s; void operator()( const double & x) { s += x; } my_functor() : s( 0.0) {} }; double sum( const list< double> & c) { my_functor f; for_each( c.begin(), c.end(), f); return f.s; }
Pozor: f se předává hodnotou - tato implementace vždy vrací 0.0
STL – Algoritmy Použití funkce for_each class my_functor { public: double s; void operator()( const double & x) { s += x; } my_functor() : s( 0.0) {} }; double sum( const list< double> & c) { return for_each( c.begin(), c.end(), my_functor()).s; }
Lambda
Lambda výrazy Motivace class ftor { public: ftor(int a, int b) : a_(a),b_(b) { } bool operator()(int x) const { return x*a_ v_t; v_t v; v_t::iterator vi=remove_if(v.begin(), v.end(), ftor(m, n));
Řešení std::vector v; auto vi=remove_if(v.begin(), v.end(), [=](int x){ return x*m
C++11
Lambda výrazy Lambda výraz [ capture ]( params ) mutable -> rettype { body } Deklaruje třídu ve tvaru class ftor { public: ftor( TList ... plist) : vlist( plist) ... { } rettype operator()( params ) const { body } private: TList ... vlist; };
vlist je určen proměnnými použitými v body TList je určen jejich typy a upraven podle capture operator() je const pokud není uvedeno mutable Lambda
výraz je nahrazen vytvořením objektu
ftor( vlist ...)
C++11
Lambda výrazy – návratový typ a typ funkce Návratový typ operátoru Explicitně definovaný návratový typ []() -> int { … }
Automaticky určen pro tělo lambda funkce ve tvaru []() { return V; }
Jinak void
C++11
Lambda výrazy – capture Capture [ capture ]( params ) mutable -> rettype { body }
C++11
Způsob zpřístupnění vnějších entit Určuje typy datových položek a konstruktoru funktoru Explicitní
capture
Programátor vyjmenuje všechny vnější entity v capture [a,&b,c,&d]
• entity označené & předány odkazem, ostatní hodnotou Implicitní
capture
Překladač sám určí vnější entity, capture určuje způsob předání [=] [=,&b,&d]
• předání hodnotou, vyjmenované výjimky odkazem [&] [&,a,c]
• předání odkazem, vyjmenované výjimky hodnotou
Lambda výrazy – příklad int a = 1, b = 1, c = 1; auto m1 = [a, &b, &c]() mutable { auto m2 = [a, b, &c]() mutable { std::cout << a << b << c; a = 4; b = 4; c = 4; }; a = 3; b = 3; c = 3; m2(); }; a = 2; b = 2; c = 2; m1(); std::cout << a << b << c;
Co to vypíše?
123234
C++11
Další algoritmy
STL – Algoritmy Šablona funkce find template InputIterator find( InputIterator first, InputIterator last, const T & value) { for (; first != last; ++first) if ( * first == value ) break; return first; }
STL – Algoritmy Šablona funkce find_if template InputIterator find_if( InputIterator first, InputIterator last, Predicate pred) { for (; first != last; ++first) if ( pred( * first) ) break; return first; }
Predikát pred může být funkce nebo funktor
STL – Algoritmy Přehled algoritmů Průchod kontejnerem for_each Čtení
kontejnerů
find, find_if - první prvek s danou vlastností find_end - poslední výskyt druhé sekvence v první find_first_of - první výskyt některého prvku druhé sekvence v první adjacent_find - první prvek ekvivalentní sousednímu count, count_if - počet prvků s danou vlastností mismatch - první odlišnost dvou sekvencí equal - test shody dvou sekvencí search - první výskyt druhé sekvence v první search_n - první n-násobný výskyt dané hodnoty
STL – Algoritmy Přehled algoritmů Swap swap - výměna obsahu dvou objektů • Pomocí parciální/explicitní specializace bývá implementována rychleji, než kopírování Modifikace
kontejnerů výměnou prvků
swap_ranges - výměna obsahu dvou sekvencí (volá swap) iter_swap - výměna obsahu dvou jednoprvkových sekvencí Modifikace
kontejnerů permutací (voláním swap)
partition, stable_partition - přemístění prvků s danou vlastností dopředu random_shuffle - náhodná permutace dle zadaného náhodného generátoru reverse - otočení posloupnosti rotate, rotate_copy - rotace prvků
STL – Algoritmy Přehled algoritmů Modifikace kontejnerů přiřazením copy, copy_backward - kopie první sekvence do druhé transform - aplikace zadané unární/binární operace na každý prvek první/první a druhé sekvence a zapsání výsledku do druhé/třetí sekvence replace, replace_if - nahrazení prvků s danou vlastností jinou hodnotou replace_copy, replace_copy_if - kopie s nahrazením fill, fill_n - naplnění sekvence danou hodnotou generate, generate_n - naplnění sekvence z daného generátoru Modifikace
kontejnerů odebráním
remove, remove_if - smazání prvků s danou vlastností unique, unique_copy - smazání opakujících se sousedních prvků • vhodné pro setříděné nebo asociativní kontejnery Pozor:
Tyto funkce neprodlužují ani nezkracují kontejner
STL – Algoritmy Přehled algoritmů Pozor: Algoritmy neprodlužují ani nezkracují kontejner vector< int> a, b; a.push_back( 1); a.push_back( 2); a.push_back( 3); copy( a.begin(), a.end(), b.begin()); Pro
// ilegální použití
tyto účely existují "vkládající iterátory"
obsahuje tyto funkce vracející iterátory • back_inserter( K) - iterátor vkládající na konec kontejneru K • front_inserter( K) - iterátor vkládající na začátek kontejneru K • inserter( K, I) - iterátor vkládající před iterátor I do kontejneru K
tyto iterátory jsou pouze výstupní • lze je použít jako cíl ve funkcích typu copy copy( a.begin(), a.end(), back_inserter( b));
STL – Algoritmy Přehled algoritmů min, max - minimum a maximum ze dvou hodnot Třídění
a spol.
sort, stable_sort - třídění partial_sort, partial_sort_copy, nth_element - polotovary třídění push_heap, pop_heap, make_heap, sort_heap - operace na haldě min_element, max_element lexicographical_compare next_permutation, prev_permutation Operace
na setříděných kontejnerech
lower_bound, upper_bound, equal_range - hledání prvku binary_search - test na přítomnost prvku includes - test podmnožinovosti merge, inplace_merge - sjednocení s opakováním set_union, set_intersection - sjednocení, průnik set_difference, set_symmetric_difference - množinový rozdíl
Konstruktory a destruktory Constructors and Destructors
Konstruktory a destruktory Konstruktor třídy XXX je metoda se jménem XXX Typ návratové hodnoty se neurčuje Konstruktorů může být více, liší se parametry Nesmí být virtuální Konstruktor
je volán vždy, když vzniká objekt typu XXX
Parametry se zadávají při vzniku objektu Některé z konstruktorů mají speciální význam Některé z konstruktorů může generovat sám kompilátor Konstruktor
nelze vyvolat přímo Destruktor třídy je metoda se jménem ~XXX Nesmí mít parametry ani návratovou hodnotu Může být virtuální Destruktor
je volán vždy, když zaniká objekt typu XXX
Destruktor může generovat sám kompilátor Destruktor
lze vyvolat přímo pouze speciální syntaxí
Speciální metody tříd Konstruktor bez parametrů (default constructor) XXX();
Používán u proměnných bez inicializace Kompilátor se jej pokusí vygenerovat, je-li to třeba a pokud třída nemá vůbec žádný konstruktor: • Položky, které nejsou třídami, nejsou generovaným konstruktorem inicializovány • Generovaný konstruktor volá konstruktor bez parametrů na všechny předky a položky • To nemusí jít např. pro neexistenci takového konstruktoru
Kopírovací konstruktor (copy constructor) XXX( const XXX &);
Používán pro předávání parametrů a návratových hodnot Kompilátor se jej pokusí vygenerovat, je-li to třeba a pokud třída kopírovací konstruktor nemá: • Položky, které nejsou třídami, jsou kopírovány • Na předky a položky se volá kopírovací konstruktor • To nemusí jít kvůli ochraně přístupu
Speciální metody tříd Operátor přiřazení (assignment operator) const XXX & operator=( const XXX &);
Implementace operátoru = pro typ XXX na levé straně Kompilátor se jej pokusí vygenerovat, je-li to třeba a třída jej nemá: • Položky, které nejsou třídami, jsou kopírovány • Na předky a položky se volá operátor přiřazení • To nemusí jít kvůli ochraně přístupu
Destruktor ~XXX();
Používán při zániku objektu Kompilátor se jej pokusí vygenerovat, je-li to třeba a třída jej nemá • To nemusí jít kvůli ochraně přístupu Pokud je objekt destruován operátorem delete aplikovaným na ukazatel na předka, musí být destruktor v tomto předku deklarován jako virtuální virtual ~XXX();
copy/move Speciální metody tříd – C++11
copy/move Speciální metody tříd Copy constructor T( const T & x);
Move constructor T( T && x);
Copy assignment operator T & operator=( const T & x);
Move
assignment operator
T & operator=( T && x);
C++11
copy/move Překladačem definované chování (default) Copy constructor T( const T & x) = default;
aplikuje copy constructor na složky Move constructor T( T && x) = default;
aplikuje move constructor na složky Copy assignment operator T & operator=( const T & x) = default;
aplikuje copy assignment operator na složky Move
assignment operator
T & operator=( T && x) = default;
aplikuje move assignment operator na složky default
umožňuje vynutit defaultní chování
C++11
copy/move Podmínky automatického defaultu Copy
C++11
constructor/assignment operator
pokud není explicitně deklarován move constructor ani assignment operator • budoucí normy pravděpodobně zakážou automatický default i v případě přítomnosti druhé copy metody nebo destruktoru Move
constructor/assignment operator
pokud není deklarována žádná ze 4 copy/move metod ani destruktor
copy/move Nejběžnější kombinace Neškodná třída Nedeklaruje žádnou copy/move metodu ani destruktor Neobsahuje složky vyžadující zvláštní péči (ukazatele) Složky
vyžadující zvláštní péči
Překladačem generované chování (default) nevyhovuje Bez podpory move (před C++11) T( const T & x); T & operator=( const T & x); ~T();
Plná podpora copy/move T( const T & x); T( T && x); T & operator=( const T & x); T & operator=( T && x); ~T();
C++11
copy/move Další kombinace Nekopírovatelná třída
C++11
Např. dynamicky alokované živé objekty v simulacích T( const T & x) = delete; T & operator=( const T & x) = delete;
delete zakazuje generování překladačem Destruktor může ale nemusí být nutný Přesouvatelná
nekopírovatelná třída
Např. unikátní vlastník jiného objektu (viz std::unique_ptr< U>) T( T && x); T & operator=( T && x); ~T();
Pravidla jazyka zakazují generování copy metod překladačem Destruktor typicky bývá nutný
Konverze
Speciální metody tříd Konverzní konstruktory class XXX { XXX( YYY); };
Zobecnění kopírovacího konstruktoru Definuje uživatelskou konverzi typu YYY na XXX Je-li tento speciální efekt nežádoucí, lze jej zrušit: explicit XXX( YYY);
Konverzní operátory class XXX { operator YYY() const; };
Definuje uživatelskou konverzi typu XXX na YYY Vrací typ YYY hodnotou (tedy s použitím kopírovacího konstruktoru YYY, pokud je YYY třída) Kompilátor vždy použije nejvýše jednu uživatelskou konverzi
Konstruktory a spol. Typické situace
Konstruktory a spol. POD: Plain-Old-Data Položky jsou veřejné Inicializace je v zodpovědnosti uživatele class T { public: std::string x_; };
Často se používá struct struct T { std::string x_; };
Konstruktory a spol. Všechny položky jsou neškodné Položky mají svoje konstruktory Třída nemusí mít žádný konstruktor class T { public: // ... const std::string & get_x() const { return x_; } void set_x( const std::string & s) { x_ = s; } private: std::string x_; };
Konstruktory a spol. Všechny položky jsou neškodné Položky mají svoje konstruktory Konstruktor se hodí pro pohodlnou inicializaci V takovém případě je (většinou) nutný i konstruktor bez parametrů Konstruktory s jedním parametrem označeny explicit class T { public: T() {} explicit T( const std::string & s) : x_( s) {} T( const std::string & s, const std::string & t) : x_( s), y_( t) {} // ... metody ... private: std::string x_, y_; };
Konstruktory a spol. Některé položky jsou mírně nebezpečné Některé položky nemají vhodné konstruktory Číselné typy včetně bool, char Konstruktor
je nutný pro inicializaci
V takovém případě je (většinou) nutný i konstruktor bez parametrů Konstruktory s jedním parametrem označeny explicit class T { public: T() : x_( 0), y_( 0) {} explicit T( int s) : x_( s), y_( 0) {} T( int s, int t) : x_( s), y_( t) {} // ... metody ... private: int x_, y_; };
Konstruktory a spol. Některé položky jsou hodně nebezpečné Některé položky nemají použitelnou semantiku kopírování Ukazatele (E *) na dynamicky alokovaná data Semantika definovaná překladačem nevyhovuje Je
nutný copy constructor, operator= a destruktor
Je nutný i jiný konstruktor, např. bez parametrů class T { public: T() : p_( new Data) {} T( const T & x) : p_( new Data( * x.p_)) {} T & operator=( const T & x) { T tmp( x); swap( tmp); return * this;} ~T() { delete p_; } void swap( T & y) { std::swap( p_, y.p_); } private: Data * p_; };
Konstruktory a spol. Některé položky jsou hodně nebezpečné Je nutný copy/move constructor/operator= a destruktor Je nutný i jiný konstruktor, např. bez parametrů
C++11
class T { public: T() : p_( new Data) {} T( const T & x) : p_( new Data( * x.p_)) {} T( T && x) : p_( x.p_) { x.p_ = 0; } T & operator=( const T & x) { T tmp( x); swap( tmp); return * this;} T & operator=( T && x) { T tmp( std::move( x)); swap( tmp); return * this;} ~T() { delete p_; } void swap( T & y) { std::swap( p_, y.p_); } private: Data * p_; };
Vznik a zánik objektů
Vznik a zánik objektů Lokální proměnné Pro každý lokální objekt je při jeho vzniku, to jest při průchodu řízení jeho deklarací, vyvolán specifikovaný konstruktor. Při zániku lokálního objektu, to jest při opuštění bloku s jeho deklarací (jakýmkoli způsobem včetně příkazů return, break, continue a goto nebo následkem výjimky) je vyvolán jeho destruktor. Deklarace lokálního objektu může být kdekoliv uvnitř těla funkce nebo kteréhokoliv složeného příkazu. Rozsah platnosti objektu je od místa deklarace po konec nejbližšího složeného příkazu. Skoky, které by vstupovaly do bloku a obcházely přitom deklaraci objektu, jsou zakázány.
void f() { XXX a, b; XXX c( 1), d( a); XXX e = 1, f = a; XXX g( 1, 2, 3); }
// // // //
konstruktor bez parametrů konstruktory XXX( int), XXX( XXX) (skoro) ekvivalentní zápis konstruktor XXX( int, int, int)
Vznik a zánik objektů Parametry předávané hodnotou Předání parametru je realizováno voláním kopírovacího konstruktoru
Tento konstruktor je volán na místě volání funkce před jejím zavoláním Kompilátor dokáže tento konstruktor vytvořit vlastními prostředky Destruktor objektu je vyvolán před návratem z funkce Pokud je skutečný parametr jiného typu, před voláním kopírovacího konstruktoru dojde ke konverzi • Tato konverze může zahrnovat vznik pomocného objektu a tedy volání dalšího konstruktoru (a destruktoru)
void f( XXX a) { } void g() { XXX b; f( b); // konstruktor XXX( const XXX &) f( 1); // pokud existuje konstruktor XXX( int) – po něm se volá XXX( const XXX &) }
Vznik a zánik objektů Globální proměnné Pro každý globální objekt (a statickou položku třídy) je vyvolán konstruktor (pokud je neprázdný) před vstupem řízení do funkce main Po jejím opuštění (nebo po zavolání funkce exit) je pro každý globální objekt vyvolán destruktor. V rámci jednoho překládaného modulu jsou globální proměnné inicializovány v pořadí zápisu a destruovány v opačném pořadí. Pořadí inicializací mezi moduly není definováno
XXX a( 1), b, c( 2, 3, 4); XXX d( a); // a již je inicializováno class C { static XXX h; // statická datová položka - deklarace }; XXX C::h( 1, 2, 3); // statická datová položka - definice
Vznik a zánik objektů Lokální statické proměnné Konstruktory lokálních statických proměnných se volají v okamžiku prvního vstupu do funkce Destruktory jsou volány po výstupu z main v opačném pořadí
f() { static XXX e( 1); }
// lokální statická proměnná
Vznik a zánik objektů Dynamicky alokované objekty Pro dynamickou alokaci slouží dvojice operátorů new a delete. Operátor new alokuje potřebnou oblast paměti pro objekt specifikovaného typu a vyvolává konstruktor podle zadaných parametrů. Vrací ukazatel na tento objekt. Pokud se z důvodu nedostatku paměti alokace nezdaří: • Vyvolá se výjimka std::bad_alloc Operátor delete vyvolává destruktor objektu a poté dealokuje paměť zabranou objektem. • Je odolný proti nulovým ukazatelům
XXX * p, * q; p = new XXX; // konstruktor bez parametrů q = new XXX( 1, p); // XXX( int, XXX *) /* ... */ delete p; delete q;
Vznik a zánik objektů Dynamická
alokace polí
Vyvolává pouze konstruktory bez parametrů
int n; XXX * p; p = new XXX[ n]; // pole n objektů typu XXX – konstruktory XXX() XXX * q; q = new XXX *[ n]; // pole n ukazatelů na XXX – žádné konstruktory /* ... */ delete[] p; delete[] q;
Vznik a zánik objektů Dočasné objekty Užití jména třídy jako jména funkce v operátoru volání způsobí: Vyhrazení místa pro tuto třídu na zásobníku, tedy mezi okolními lokálními proměnnými Vyvolání konstruktoru s patřičnými parametry na tomto objektu Použití tohoto objektu jako hodnoty v okolním výraze Vyvolání destruktoru nejpozději na konci příkazu
XXX a, b; a = XXX(); b = XXX( 1, 2);
// konstruktor bez parametrů + kopie + destruktor // konstruktor s parametry + kopie + destruktor
Speciální
případ této syntaxe je chápán jako typová konverze (function-style cast) Konstruktor s jedním parametrem je nazýván konverzní konstruktor
Třída jako datový typ
Speciální metody tříd Konstruktor bez parametrů (default constructor) XXX();
Používán u proměnných bez inicializace Kompilátor se jej pokusí vygenerovat, je-li to třeba a pokud třída nemá vůbec žádný konstruktor: • Položky, které nejsou třídami, nejsou generovaným konstruktorem inicializovány • Generovaný konstruktor volá konstruktor bez parametrů na všechny předky a položky • To nemusí jít např. pro neexistenci takového konstruktoru
Kopírovací konstruktor (copy constructor) XXX( const XXX &);
Používán pro předávání parametrů a návratových hodnot Kompilátor se jej pokusí vygenerovat, je-li to třeba a pokud třída kopírovací konstruktor nemá: • Položky, které nejsou třídami, jsou kopírovány • Na předky a položky se volá kopírovací konstruktor • To nemusí jít kvůli ochraně přístupu
Speciální metody tříd Operátor přiřazení (assignment operator) const XXX & operator=( const XXX &);
Implementace operátoru = pro typ XXX na levé straně Kompilátor se jej pokusí vygenerovat, je-li to třeba a třída jej nemá: • Položky, které nejsou třídami, jsou kopírovány • Na předky a položky se volá operátor přiřazení • To nemusí jít kvůli ochraně přístupu
Destruktor ~XXX();
Používán při zániku objektu Kompilátor se jej pokusí vygenerovat, je-li to třeba a třída jej nemá • To nemusí jít kvůli ochraně přístupu
Pokud je objekt destruován operátorem delete aplikovaným na ukazatel na předka, musí být destruktor v tomto předku deklarován jako virtuální virtual ~XXX();
Přetěžování operátorů Operator overloading
Přetěžování operátorů Většinu
operátorů jazyka C++ lze definovat pro uživatelské datové typy. Nelze předefinovat tyto operátory: . .* :: ? : sizeof
Alespoň
jeden z operandů musí být třída nebo výčtový typ nebo reference na ně Nelze tudíž předefinovat operace na číselných typech a ukazatelích
Předefinováním
nelze měnit prioritu a asociativitu operátorů Pro předefinované operátory nemusí platit identity definované pro základní typy, např.: ++a nemusí být ekvivalentní a=a+1 a[b] nemusí být ekvivalentní *(a+b) ani b[a] Pro
předefinované operátory && a || neplatí pravidla o zkráceném vyhodnocování
Přetěžování operátorů Typy
skutečných operandů předefinovaného operátoru nemusejí přesně odpovídat typům formálních parametrů operátoru. Pro výběr správné varianty mezi předefinovanými operátory platí stejná pravidla, jako pro přetížené funkce.
Předefinování
operátorů se provádí definováním metody se speciálním jménem operatorxxx ve třídě (prvního operandu), pro kterou má být operátor definován. Některé operátory je možno definovat i jako globální funkce s týmž speciálním jménem. Speciální jméno je možno používat i pro explicitní vyvolání této metody či funkce. Operátory, které jsou metodami, jsou s výjimkou operátoru přiřazení dědičné a smějí být virtuální.
Přetěžování operátorů - Binární operátory Binární operátor xxx z množiny + - * / % << >> < > <= >= <<= >>= ^ & | && || == != += -= *= /= %= ^= &= |= ->* lze
pro operandy typu B a C předefinovat dvěma způsoby:
Globální funkcí A operator xxx( B, C) A operator xxx( B &, C &) A operator xxx( const B &, const C &)
Metodou A B::operator xxx( C) A B::operator xxx( const C &) A B::operator xxx( const C &) const
Binární operátor [ ] lze předefinovat pouze metodou A B::operator []( C) A B::operator []( C &) A B::operator []( const C &) const
Přetěžování operátorů - Unární operátory Unární operátor xxx z množiny + - * & ~ ! a ++ --
prefixové operátory
lze
pro operand typu B předefinovat dvěma způsoby:
Globální funkcí A operator xxx( B) A operator xxx( B &) A operator xxx( const B &)
Metodou A B::operator xxx() A B::operator xxx() const
Přetěžování operátorů - Unární operátory Postfixové operátory ++ a - lze pro operand typu B předefinovat dvěma způsoby: Globální funkcí A operator xxx( B, int) A operator xxx( B &, int) A operator xxx( const B &, int)
Metodou A B::operator xxx( int) A B::operator xxx( int) const
Přetěžování operátorů - Unární operátory Operátor -> je považován za unární operátor a jeho návratovou hodnotou musí být buďto ukazatel na třídu s uvedenou položkou, nebo objekt či referenci na objekt, pro který je znovu definován operátor ->
Přetěžování operátorů - Unární operátory Operátor volání funkce () smí být definován pouze jako metoda třídy a umožňuje používat objekty této třídy jako funkce. Smí mít libovolný počet parametrů a pro výběr konkrétní varianty operátoru se použije podobný mechanismus, jako pro přetížené funkce.
Complex Komplexní číslo
Complex class Complex { public: Complex() : re_( 0.0), im_( 0.0) {} Complex( double re, double im = 0.0) : re_( re), im_( im) {} double Re() const { return re_; } double Im() const { return im_; } Complex & operator+=( const Complex & b); Complex operator-() const; // unární Complex & operator++(); // prefixové ++ Complex operator++( int); // postfixové ++ // a mnoho dalších... private: double re_, im_; }; Complex operator+( const Complex & a, const Complex & b);
Poučení - konstruktory
Ve
třídě Complex nejsou odkazy na data uložená jinde Vyhovuje chování těchto kompilátorem vytvořených metod: Complex( const Complex &);
Kopíruje datové položky Complex & operator=( const Complex &);
Kopíruje datové položky ~Complex();
Nedělá nic Tyto
metody není třeba psát vlastní
Poučení - konstruktory Ve
třídě Complex jsou datové položky atomických typů
Ty nemají konstruktory a zůstávají neinicializované Nevyhovalo
by tedy chování kompilátorem vytvořeného konstruktoru bez parametrů:
Complex();
Nedělá nic Navíc
je zde jiný konstruktor, takže kompilátor má zakázáno konstruktor bez parametrů vytvořit Nebylo by tedy možné deklarovat proměnnou typu Complex bez explicitní inicializace
Konstruktor
bez parametrů musí být napsán ručně
Měl by nastavit datové položky na vhodnou hodnotu
Poučení - konstruktory Speciální konstruktor Complex( double re, double im = 0.0);
Lze zavolat s jedním parametrem Slouží
jako konverzní konstruktor
Implementuje konverzi double => Complex Důsledky:
Bude fungovat přiřazení Complex=double Není nutné psát sčítání pro Complex+double: Complex operator+( const Complex & a, double b) const;
• Dělává se to kvůli rychlosti
Kompilátor umí použít konverzi (jednu) a najít náhradní metodu: Complex operator+(const Complex & a, const Complex & b) const;
Totéž funguje pro sčítání double+Complex • Pouze pokud je sčítání Complex+Complex globální funkce • U metod se levý operand nekonvertuje
Poučení - vracení hodnotou
Poučení: operator+ vždy vrací hodnotou Vrací novou hodnotu, která jinde neexistuje return Complex( ...);
Ale: operator+= může vracet odkazem Vrací hodnotu levého operandu return * this;
Poučení – binární operátory +, += Kanonické řešení class Complex { public: Complex( double re, double im = 0.0); // konverzní konstruktor // ... Complex & operator+=( const Complex & b) { re_ += b.re_; im_ += b.im_; return * this; } // ... };
Complex operator+( const Complex & a, const Complex & b) { Complex tmp( a); tmp += b; return tmp; }
Poučení – unární operátory -, ++ Kanonické
řešení
Unární operátory jsou vždy metodami • Není zapotřebí schopnost konverze operandů class Complex { public: // ... Complex operator-() const { return Complex( -re_, -im_); } Complex & operator++() { _re += 1.0; return * this; } Complex operator++( int) { Complex tmp( * this); operator++(); return tmp; } };
Prefixové ++, -- vrací odkazem • Může a nemusí být const
Postfixové ++, -- vrací hodnotou
Dědičnost a virtuální funkce
Dědičnost class Base { /* ... */ }; class Derived : public Base { /* ... */ }
Třída
Derived je odvozena z třídy Base
Obsahuje všechny datové položky i metody třídy Base Může k nim doplnit další •Není vhodné novými zakrývat staré, vyjma virtuálních Může změnit chování metod, které jsou v Base deklarovány jako virtuální class Base { virtual void f() { /* ... */ } }; class Derived : public Base { virtual void f() { /* ... */ } };
Virtuální funkce class Base { virtual void f() { /* ... */ } virtual void f( int) { /* ... */ } virtual void g() = 0; // čistě virtuální funkce bez těla virtual void h() const { /* ... */ } void j() { /* ... */ } };
Třída obsahující čistě virtuální funkci nemůže být samostatně instanciována. class Derived : public Base { virtual void f() { /* ... */ } virtual void f( int) const { /* ... */ } virtual void g() { /* ... */ } virtual void h() { /* toto není nové tělo pro Base::h */ } virtual void j() { /* toto není nové tělo pro Base::j */ } };
Mechanismus redefinování virtuálních funkcí je vázán na jméno i parametry včetně „const“ Je možné redefinovat i tělo privátní funkce
Virtuální funkce class Base { virtual void f() { /* ... */ } }; class Derived : public Base { virtual void f() { /* ... */ } }; Mechanismus
virtuálních funkcí se uplatní pouze v přítomnosti ukazatelů nebo referencí Base * p = new Derived; p->f(); // volá Derived::f
V jiné situaci není virtuálnost funkcí užitečná Derived d; d.f(); // volá Derived::f i kdyby nebyla virtuální
Base b = d; // slicing = kopie části objektu b.f(); // volá Base::f ikdyž je virtuální Slicing
je specifikum jazyka C++
Názvosloví Abstraktní třída Definice v C++: Třída obsahující alespoň jednu čistě virtuální funkci Běžná definice: Třída, která sama nebude instanciována Představuje rozhraní, které mají z ní odvozené třídy (potomci) implementovat Konkrétní třída Třída, určená k samostatné instanciaci Implementuje rozhraní, předepsané abstraktní třídou, ze které je odvozena
Dědičnost a destruktor class Base { public: virtual ~Base() {} }; class Derived : public Base { public: virtual ~Derived() { /* ... */ } };
Base * p = new Derived; delete p; Pokud
je objekt destruován operátorem delete aplikovaným na ukazatel na předka, musí být destruktor v tomto předku deklarován jako virtuální
Odvozené pravidlo: Každá abstraktní třída má mít virtuální destruktor Je to zadarmo Může se to hodit
Dědičnost Mechanismus
dědičnosti v C++ je velmi silný
Bývá používán i pro nevhodné účely Ideální
použití dědičnosti je pouze toto
ISA hierarchie (typicky pro objekty s vlastní identitou) •Živočich-Obratlovec-Savec-Pes-Jezevčík •Objekt-Viditelný-Editovatelný-Polygon-Čtverec Vztah interface-implementace •Readable-InputFile •Writable-OutputFile •(Readable+Writable)-IOFile Jiná použití dědičnosti obvykle signalizují chybu v návrhu •Výjimky samozřejmě existují (traits...)
Dědičnost ISA hierarchie •C++: Jednoduchá nevirtuální veřejná dědičnost class Derived : public Base
•Abstraktní třídy někdy obsahují datové položky Vztah interface-implementace •C++: Násobná virtuální veřejná dědičnost class Derived : virtual public Base1, virtual public Base2
•Abstraktní třídy obvykle neobsahují datové položky •Interface nebývají využívány k destrukci objektu Oba přístupy se často kombinují class Derived : public Base, virtual public Interface1, virtual public Interface2
Nesprávné užití dědičnosti Nesprávné
užití dědičnosti č. 1
class Real { public: double Re; }; class Complex : public Real { public: double Im; };
Porušuje pravidlo "každý potomek má všechny vlastnosti předka" • např. pro vlastnost "má nulovou imaginární složku"
Důsledek - slicing: double abs( const Real & p) { return p.Re > 0 ? p.Re : - p.Re; } Complex x; double a = abs( x);
// tento kód LZE přeložit, a to je špatně
Důvod: Referenci na potomka lze přiřadit do reference na předka • Complex => Complex & => Real & => const Real &
Nesprávné užití dědičnosti Nesprávné
užití dědičnosti č. 1
class Real { public: double Re; }; class Complex : public Real { public: double Im; };
Slicing nastává i u předávání hodnotou double abs( Real p) { return p.Re > 0 ? p.Re : - p.Re; } Complex x; double a = abs( x);
// tento kód LZE přeložit, a to je špatně
Důvod: Předání hodnoty x do parametru p je provedeno implicitně vytvořeným konstruktorem: Real::Real( const Real & y) { Re = y.Re; }
Parametr x typu Complex do tohoto konstruktoru lze předat • Complex => Complex & => Real & => const Real &
Nesprávné užití dědičnosti Nesprávné
užití dědičnosti č. 2
class Complex { public: double Re, Im; }; class Real : public Complex { public: Real( double r); };
Vypadá jako korektní specializace: "každé reálné číslo má všechny vlastnosti komplexního čísla" Chyba: Objekty v C++ nejsou hodnoty v matematice Třída Complex má vlastnost "lze do mne přiřadit Complex" • Tuto vlastnost třída Real logicky nemá mít, s touto dědičností ji mít bude
Nesprávné užití dědičnosti Nesprávné
užití dědičnosti č. 2
class Complex { public: double Re, Im; }; class Real : public Complex { public: Real( double r); };
Vypadá jako korektní specializace: "každé reálné číslo má všechny vlastnosti komplexního čísla" Chyba: Objekty v C++ nejsou hodnoty v matematice Třída Complex má vlastnost "lze do mne přiřadit Complex" • Tuto vlastnost třída Real logicky nemá mít, s touto dědičností ji mít bude void set_to_i( Complex & p) { p.Re = 0; p.Im = 1; } Real x; set_to_i( x);
// tento kód LZE přeložit, a to je špatně
Důvod: Referenci na potomka lze přiřadit do reference na předka • Real => Real & => Complex &
Nesprávné užití dědičnosti Nesprávné
užití dědičnosti č. 2
class Complex { public: double Re, Im; }; class Real : public Complex { public: Real( double r); };
Vypadá jako korektní specializace: "každé reálné číslo má všechny vlastnosti komplexního čísla" Chyba: Objekty v C++ nejsou hodnoty v matematice Třída Complex má vlastnost "lze do mne přiřadit Complex" • Tuto vlastnost třída Real logicky nemá mít, s touto dědičností ji mít bude
Poznámka: při přímem přiřazování tento problém nenastane Complex y; Real x; x = y; // tento kód NELZE přeložit
• Důvod: operátor = se nedědí Complex & Complex::operator=( const Complex &); // nezdědí se Real & Real::operator=( const Real &); // nesouhlasí typ argumentu
Ideální užití dědičnosti a virtuálních funkcí Abstraktní třída Definuje rozhraní objektu jako množinu předepsaných virtuálních funkcí class GraphicObject { public: virtual ~GraphicObject(); // každá abstraktní třída má mít v.d. virtual void paint() = 0; // čistě virtuální funkce virtual void move( int dx, int dy) = 0; // čistě virtuální funkce };
Příklad: dědičnost a virtuální funkce ISA hierarchie Osoba Student Zaměstnanec Učitel • Matikář • Fyzikář • Chemikář Ředitel Ostatní • Školník • Kuchař Které
abstraktní třídy potřebujeme?
Ty, jejichž specifické rozhraní někdo potřebuje • Třída „Ostatní“ není potřeba
Příklad: dědičnost a virtuální funkce Virtuální funkce a schopnosti tříd Osoba (dá se evakuovat) Student (platí školné) Zaměstnanec (přijímá výplatu) Učitel (umí uspořádat třídní schůzku) • Matikář (umí učit Pythagorovu větu) • Fyzikář (umí učit Archimedův zákon) • Chemikář (umí předvést výbuch) Ředitel (umí se podepsat) Školník (umí odemykat) Kuchař (umí počítat knedlíky)
Příklad: dědičnost a virtuální funkce Násobná dědičnost Absolvent učitelství na MFF umí • uspořádat třídní schůzku • učit Pythagorovu větu • učit Archimedův zákon Implementuje rozhraní Učitel, Matikář, Fyzikář • Má být potomkem všech těchto tříd class Matfyzak : virtual public Ucitel, virtual public Matikar, virtual public Fyzikar { virtual void tridni_schuzka() { ... } virtual void pythagorova_veta() { ... } virtual void archimeduv_zakon() { ... } ... }
Příklad: dědičnost a virtuální funkce Násobná dědičnost class Matfyzak : virtual public Ucitel, virtual public Matikar, virtual public Fyzikar { virtual void tridni_schuzka() { ... } virtual void pythagorova_veta() { ... } virtual void archimeduv_zakon() { ... } ... } •
na třídu vedou odkazy z různých míst:
class Trida { ... Ucitel * tridni; ... } class III : public Trida { ... Matikar * matikar; ... } class IV : public Trida { ... Fyzikar * fyzikar; ... }
•
kdo z nich je vlastník ? Nikdo. Jednoznačným vlastníkem je seznam zaměstnanců.
Příklad: dědičnost a virtuální funkce class Matfyzak : public Zamestnanec, virtual public Ucitel, virtual public Matikar, virtual public Fyzikar { virtual void evakuace() { ... } virtual void vyplata() { ... } virtual void tridni_schuzka() { ... } virtual void pythagorova_veta() { ... } virtual void archimeduv_zakon() { ... } } class Trida { ... Ucitel * tridni; ... } class III : public Trida { ... Matikar * matikar; ... } class IV : public Trida { ... Fyzikar * fyzikar; ... } class Skola { vector< Zamestnanec *> zamestnanci; vector< Trida *> tridy; };
Příklad: dědičnost a virtuální funkce ISA hierarchie Osoba Student Zaměstnanec Ředitel Školník Kuchař Potřebujeme
třídu Osoba?
Máme nějaký seznam osob?
Další rozhraní Učitel Matikář Fyzikář Chemikář Má
být Matikář odvozen z Učitele?
Mají Matikář a Fyzikář něco společného?
Příklad přesněji: Abstraktní třídy v ISA hierarchii class Osoba { public: virtual ~Osoba() {} virtual void evakuace() = 0; protected: Osoba() {} private: Osoba( const Osoba &); Osoba & operator=( const Osoba &); }; class Zamestnanec : public Osoba { public: virtual void vyplata() = 0; };
Příklad přesněji: Abstraktní třídy pro rozhraní class Ucitel { public: virtual void tridni_schuzka() = 0; protected: virtual ~Osoba() {} Ucitel() {} private: Ucitel( const Ucitel &); Ucitel & operator=( const Ucitel &); }; class Matikar : public Ucitel { public: virtual void pythagorova_veta() = 0; };
Příklad přesněji: Konkrétní třída class Matfyzak : public Zamestnanec, virtual public Ucitel, virtual public Matikar, virtual public Fyzikar { public: Matfyzak( const string & j ) : jmeno_( j) {} private: virtual void evakuace(); virtual void vyplata(); virtual void tridni_schuzka(); virtual void pythagorova_veta(); virtual void archimeduv_zakon(); string jmeno_; };
void Matfyzak::evakuace() { ... } ...
Příklad přesněji: Kontejner odkazů class Zamestnanci { public: ~Zamestnanci(); private: typedef vector< Zamestnanec *> my_vector; my_vector v; };
Zamestnanci::~Zamestnanci() { for ( my_vector::iterator it = v.begin(); it != v.end(); ++it) delete * it; } class Skola { ... private: Zamestnanci zamestnanci; };
Příklad přesněji: Kontejner odkazů na rozhraní class Ucitele { public: Matikar * najdi_matikare() const; private: typedef vector< Ucitel *> my_vector; my_vector v; }; Matikar * Ucitele::najdi_matikare() const { for ( my_vector::iterator it = v.begin(); it != v.end(); ++it) { Matikar * p = dynamic_cast< Matikar *>( * it); if ( p ) return p; } return 0; }
Cast Různé druhy přetypování
Přetypování Různé varianty syntaxe C-style cast (T)e
Převzato z C
Přetypování Různé varianty syntaxe C-style cast (T)e
Převzato z C Function-style T(e)
cast
Ekvivalentní (T)e • T musí být syntakticky identifikátor nebo klíčové slovo označující typ
Přetypování Různé varianty syntaxe C-style cast (T)e
Převzato z C Function-style T(e)
cast
Ekvivalentní (T)e • T musí být syntakticky identifikátor nebo klíčové slovo označující typ Type
conversion operators
Pro odlišení účelu (síly a nebezpečnosti) přetypování: const_cast(e) static_cast(e) reinterpret_cast(e)
Přetypování Různé varianty syntaxe C-style cast (T)e
Převzato z C Function-style T(e)
cast
Ekvivalentní (T)e • T musí být syntakticky identifikátor nebo klíčové slovo označující typ Type
conversion operators
Pro odlišení účelu (síly a nebezpečnosti) přetypování: const_cast(e) static_cast(e) reinterpret_cast(e)
Novinka - přetypování s běhovou kontrolou: dynamic_cast(e)
Přetypování const_cast(e) Odstranění
konstantnosti
const U & => U & const U * => U * Obvykle
používáno pro měnění pomocných položek v logicky konstantních objektech Příklad: Čítač odkazů na logicky konstantní objekt
class Data { public: void register_pointer() const { const_cast< Data *>( this)->references++; } private: /* ... data ... */ int references; };
Jiný příklad: datové struktury s amortizovaným vyhledáváním
Přetypování const_cast(e) Odstranění
konstantnosti
const U & => U & const U * => U * U
moderních překladačů lze nahradit specifikátorem mutable Příklad: Čítač odkazů na logicky konstantní objekt
class Data { public: void register_pointer() const { references++; } private: /* ... data ... */ mutable int references; };
Přetypování static_cast(e)
Umožňuje Všechny implicitní konverze Bezztrátové i ztrátové aritmetické konverze (int <=> double apod.) Konverze přidávající modifikátory const a volatile Konverze ukazatele na void * Konverze odkazu na odvozenou třídu na odkaz na předka: • Derived & => Base & • Derived * => Base *
Aplikace copy-constructoru; v kombinaci s implicitní konverzí též: • Derived => Base (slicing: okopírování části objektu)
Aplikace libovolného konstruktoru T::T s jedním parametrem • Uživatelská konverze libovolného typu na třídu T
Aplikace konverzního operátoru: operator T() • Uživatelská konverze nějaké třídy na libovolný typ T
Přetypování static_cast(e)
Umožňuje Všechny implicitní konverze Ekvivalentní použití pomocné proměnné tmp deklarované takto: T tmp(e);
Používá se tehdy, pokud se vynucením jedné z možných implicitních konverzí odstraní nejednoznačnost nebo vynutí volání jiné varianty funkce class A { /* ... */ }; class B { /* ... */ }; void f( A *); void f( B*); class C : public A, public B { /* ... */ void g() { f( static_cast< A>( this)); } };
Přetypování static_cast(e)
Umožňuje Všechny implicitní konverze Konverze na void - zahození hodnoty výrazu Používá se v makrech a podmíněných výrazech Konverze
odkazu na předka na odkaz na odvozenou třídu
• Base & => Derived & • Base * => Derived *
Pokud objekt, na nějž konvertovaný odkaz ukazuje, není typu Derived či z něj odvozený, je výsledek nedefinovaný • K chybě obvykle dojde později! Konverze
celého čísla na výčtový typ
Pokud hodnota čísla neodpovídá žádné výčtové konstantě, výsledek je nedefinovaný Konverze
void * na libovolný ukazatel
Přetypování static_cast(e)
Nejčastější použití Konverze odkazu na předka na odkaz na odvozenou třídu class Base { public: enum Type { T_X, T_Y }; virtual Type get_type() const = 0; }; class X : public Base { /* ... */ virtual Type get_type() const { return T_X; } }; class Y : public Base { /* ... */ virtual Type get_type() const { return T_Y; } }; Base * switch case case }
p = /* ... */; ( p->get_type() ) { T_X: { X * xp = static_cast< X *>( p); /* ... */ } break; T_Y: { Y * yp = static_cast< Y *>( p); /* ... */ } break;
Přetypování reinterpret_cast(e)
Umožňuje Konverze ukazatele na dostatečně velké celé číslo Konverze celého čísla na ukazatel Konverze mezi různými ukazateli na funkce Konverze odkazu na odkaz na libovolný jiný typ • U * => V * • U & => U &
Neuvažuje příbuzenské vztahy tříd, neopravuje hodnoty ukazatelů
Většina použití je závislá na platformě Příklad: Přístup k reálné proměnné po bajtech Typické použití: Čtení a zápis binárních souborů void put_double( std::ostream & o, const double & d) { o.write( reinterpret_cast< char *>( & d), sizeof( double)); }
• Obsah souboru je nepřenositelný
Přetypování dynamic_cast(e)
Umožňuje Konverze odkazu na odvozenou třídu na odkaz na předka: • Derived & => Base & • Derived * => Base *
Implicitní konverze, chová se stejně jako static_cast Konverze
odkazu na předka na odkaz na odvozenou třídu
• Base & => Derived & • Base * => Derived *
Podmínka: Base musí obsahovat alespoň jednu virtuální funkci Pokud konvertovaný odkaz neodkazuje na objekt typu Derived nebo z něj odvozený, je chování definováno takto: • Konverze ukazatelů vrací nulový ukazatel • Konverze referencí vyvolává výjimku std::bad_cast
Umožňuje přetypování i v případě virtuální dědičnosti
Přetypování dynamic_cast(e)
Nejčastější použití Konverze odkazu na předka na odkaz na odvozenou třídu class Base { public: virtual ~Base(); /* alespoň jedna virtuální funkce */ }; class X : public Base { /* ... */ }; class Y : public Base { /* ... */ }; Base * p = /* ... */; X * xp = dynamic_cast< X *>( p); if ( xp ) { /* ... */ } Y * yp = dynamic_cast< Y *>( p); if ( yp ) { /* ... */ }
Exception handling Mechanismus výjimek
Exception handling Srovnání: goto Start: příkaz goto Cíl: návěští Určen při kompilaci Skok
může opustit blok
Proměnné korektně zaniknou voláním destruktorů Cíl
musí být v téže proceduře
int f() { if ( something == wrong ) { goto label; } else { MyClass my_variable; if ( anything != good ) { goto label; } /* ... */ } return 0; label: std::cerr << "Error" << std::endl; return -1; }
Exception handling Srovnání: goto Start: příkaz goto Cíl: návěští Určen při kompilaci Skok
může opustit blok
Proměnné korektně zaniknou voláním destruktorů Cíl
musí být v téže proceduře
Srovnání 2: Pro pokročilé Start: volání longjmp Cíl: volání setjmp Skok může opustit proceduru Neřeší lokální proměnné Nelze použít v C++ Předává
hodnotu typu int
int f() { if ( something == wrong ) { goto label; } else { MyClass my_variable; if ( anything != good ) { goto label; } /* ... */ } return 0; label: std::cerr << "Error" << std::endl; return -1; }
Exception handling Mechanismus výjimek Start: příkaz throw Cíl: try-catch blok Určen za běhu Skok
může opustit proceduru
Proměnné korektně zaniknou voláním destruktorů Předává
hodnotu libovolného
typu Typ hodnoty se podílí na určení cíle skoku
void f() { if ( something == wrong ) throw 729; else { MyClass my_variable; if ( anything != good ) throw 123; /* ... */ } } void g() { try { f(); } catch ( int e ) { std::cerr << "Exception in f(): " << e << std::endl; } }
Exception handling Mechanismus výjimek Start: příkaz throw Cíl: try-catch blok Určen za běhu Skok
může opustit proceduru
Proměnné korektně zaniknou voláním destruktorů Předává
hodnotu libovolného
typu Typ hodnoty se podílí na určení cíle skoku Obvykle se používají pro tento účel zhotovené třídy
class WrongException { /*...*/ }; class BadException { /*...*/ }; void f() { if ( something == wrong ) throw WrongException( something); if ( anything != good ) throw BadException( anything); } void g() { try { f(); } catch ( const WrongException & e1 ) { /*...*/ } catch ( const BadException & e2 ) { /*...*/ } }
Exception handling Mechanismus výjimek Start: příkaz throw Cíl: try-catch blok Určen za běhu Skok
může opustit proceduru
Proměnné korektně zaniknou voláním destruktorů Předává
hodnotu libovolného
typu Typ hodnoty se podílí na určení cíle skoku Obvykle se používají pro tento účel zhotovené třídy Mechanismus výjimek respektuje hierarchii dědičnosti
class AnyException { /*...*/ }; class WrongException : public AnyException { /*...*/ }; class BadException : public AnyException { /*...*/ }; void f() { if ( something == wrong ) throw WrongException( something); if ( anything != good ) throw BadException( anything); } void g() { try { f(); } catch ( const AnyException & e1 ) { /*...*/ } }
Exception handling Mechanismus výjimek Start: příkaz throw Cíl: try-catch blok Určen za běhu Skok
může opustit proceduru
Proměnné korektně zaniknou voláním destruktorů Předává
hodnotu libovolného
typu Typ hodnoty se podílí na určení cíle skoku Obvykle se používají pro tento účel zhotovené třídy Mechanismus výjimek respektuje hierarchii dědičnosti Hodnotu není třeba využívat
class AnyException { /*...*/ }; class WrongException : public AnyException { /*...*/ }; class BadException : public AnyException { /*...*/ }; void f() { if ( something == wrong ) throw WrongException(); if ( anything != good ) throw BadException(); } void g() { try { f(); } catch ( const AnyException &) { /*...*/ } }
Exception handling Mechanismus výjimek Start: příkaz throw Cíl: try-catch blok Určen za běhu Skok
může opustit proceduru
Proměnné korektně zaniknou voláním destruktorů Předává
hodnotu libovolného
typu Typ hodnoty se podílí na určení cíle skoku Obvykle se používají pro tento účel zhotovené třídy Mechanismus výjimek respektuje hierarchii dědičnosti Hodnotu není třeba využívat Existuje univerzální catch blok
class AnyException { /*...*/ }; class WrongException : public AnyException { /*...*/ }; class BadException : public AnyException { /*...*/ }; void f() { if ( something == wrong ) throw WrongException(); if ( anything != good ) throw BadException(); } void g() { try { f(); } catch (...) { /*...*/ } }
Exception handling Fáze zpracování výjimky Vyhodnocení výrazu v příkaze throw Hodnota je uložena "stranou" Stack-unwinding
Postupně se opouštějí bloky a funkce, ve kterých bylo provádění vnořeno Na zanikající lokální a pomocné proměnné jsou volány destruktory Stack-unwinding končí dosažením try-bloku, za kterým je catch-blok odpovídající typu výrazu v příkaze throw Provedení
kódu v catch-bloku
Původní hodnota throw je stále uložena pro případné pokračování: • Příkaz throw bez výrazu pokračuje ve zpracování téže výjimky počínaje dalším catch-blokem - začíná znovu stack-unwinding Zpracování
definitivně končí opuštěním catch-bloku
Běžným způsobem nebo příkazy return, break, continue, goto • Nebo vyvoláním jiné výjimky
Exception handling Použití mechanismu výjimek Vyvolání
a zpracování výjimky je relativně časově náročné
Používat pouze pro chybové nebo řídké stavy • Např. nedostatek paměti, ztráta spojení, chybný vstup, konec souboru Připravenost
na výjimky také něco (málo) stojí
Za normálního běhu je třeba zařídit, aby výjimka dokázala najít cíl a zrušit proměnné • Výjimky se týkají i procedur, ve kterých není ani throw, ani try-blok
Většina kompilátorů umí překládat ve dvou režimech "s" a "bez" • Celý spojovaný program musí být přeložen stejně
Exception handling Standardní výjimky <stdexcept> Všechny standardní výjimky jsou potomky třídy exception metoda what() vrací řetězec s chybovým hlášením bad_alloc:
vyvolává operátor new při nedostatku paměti
V režimu "bez výjimek" new vrací nulový ukazatel bad_cast,
bad_typeid: Chybné použití RTTI Odvozené z třídy logic_error: domain_error, invalid_argument, length_error, out_of_range vyvolávány např. funkcí vector::operator[] Odvozené
z třídy runtime_error:
range_error, overflow_error, underflow_error
Exception handling Standardní výjimky <stdexcept> Všechny standardní výjimky jsou potomky třídy exception metoda what() vrací řetězec s chybovým hlášením bad_alloc:
vyvolává operátor new při nedostatku paměti
V režimu "bez výjimek" new vrací nulový ukazatel bad_cast,
bad_typeid: Chybné použití RTTI Odvozené z třídy logic_error: domain_error, invalid_argument, length_error, out_of_range vyvolávány např. funkcí vector::operator[] Odvozené
z třídy runtime_error:
range_error, overflow_error, underflow_error Aritmetické
ani ukazatelové operátory na vestavěných typech NEHLÁSÍ běhové chyby prostřednictvím výjimek např. dělení nulou nebo dereference nulového ukazatele
Exception handling Typické použití Deklarace výjimek class AnyException { /*...*/ }; class WrongException : public AnyException { /*...*/ }; class BadException : public AnyException { /*...*/ }; Vyvolání
výjimek
void f() { if ( something == wrong ) throw WrongException(); if ( anything != good ) throw BadException(); }
Částečné
ošetření
void g() { try { f(); } catch (...) { std::cout << "Exception in g()"; throw; } } Podrobné
ošetření
int main( /*...*/) { try { g(); h(); } catch ( WrongException ) { std::cout << "WrongException"; } catch ( BadException ) { std::cout << "BadException"; } }
Exception handling Použití se std::exception Deklarace výjimek class WrongException : public std::exception { virtual const char * what() const { return "WrongException"; } }; class BadException : public std::exception { virtual const char * what() const { return "BadException"; } }; Vyvolání
výjimek
void f() { if ( something == wrong ) throw WrongException(); if ( anything != good ) throw BadException(); }
Částečné
ošetření
void g() { try { f(); } catch (...) { std::cout << "Exception in g()"; throw; } } Podrobné
ošetření
int main( /*...*/) { try { g(); h(); } catch ( const std::exception & e ) { std::cout << e.what(); } }
Exception-safe programming
Používat
throw a catch je jednoduché
Těžší
je programovat běžný kód tak, aby se choval korektně i za přítomnosti výjimek Exception-safety Exception-safe programming
void f() { int * a = new int[ 100]; int * b = new int[ 200]; g( a, b); delete[] b; delete[] a; }
Pokud new int[ 200] způsobí výjimku, procedura zanechá naalokovaný nedostupný blok Pokud výjimku vyvolá procedura g, zůstanou dva nedostupné bloky
Exception-safe programming
Používat
throw a catch je jednoduché
Těžší
je programovat běžný kód tak, aby se choval korektně i za přítomnosti výjimek Exception-safety Exception-safe programming
T & operator=( const T & b) { if ( this != & b ) { delete body_; body_ = new TBody( b.length()); copy( body_, b.body_); } return * this; }
Pokud new TBody způsobí výjimku, operátor= zanechá v položce body_ původní ukazatel, který již míří na dealokovaný blok Pokud výjimku vyvolá procedura copy, operátor zanechá třídu v neúplném stavu
Exception-safe programming Pravidla vynucená jazykem Destruktor
nesmí skončit vyvoláním výjimky
Výjimka může být vyvolána uvnitř, ale musí být zachycena nejpozději uvnitř destruktoru Zdůvodnění:
V rámci ošetření výjimek (ve fázi stack-unwinding) se volají destruktory lokálních proměnných Výjimku zde vyvolanou nelze z technických i logických důvodů ošetřit (ztratila by se původní výjimka) Nastane-li taková výjimka, volá se funkce terminate() a program končí
Exception-safe programming Pravidla vynucená jazykem Destruktor
nesmí skončit vyvoláním výjimky
Výjimka může být vyvolána uvnitř, ale musí být zachycena nejpozději uvnitř destruktoru Toto
pravidlo jazyka sice platí pouze pro destruktory lokálních proměnných A z jiných důvodů též pro globální proměnné
Je
však vhodné je dodržovat vždy
Bezpečnostní zdůvodnění: Destruktory lokálních proměnných často volají jiné destruktory Logické zdůvodnění: Nesmrtelné objekty nechceme
Exception-safe programming Pravidla vynucená jazykem Destruktor
nesmí skončit vyvoláním výjimky
Konstruktor
globálního objektu nesmí skončit vyvoláním
výjimky Zdůvodnění: Není místo, kde ji zachytit Stane-li se to, volá se terminate() a program končí Jiné konstruktory ale výjimky volat mohou (a bývá to vhodné)
Exception-safe programming Pravidla vynucená jazykem Destruktor
nesmí skončit vyvoláním výjimky
Konstruktor
globálního objektu nesmí skončit vyvoláním
výjimky Copy-constructor
typu v hlavičce catch-bloku nesmí skončit vyvoláním výjimky Zdůvodnění: Catch blok by nebylo možné vyvolat Stane-li se to, volá se terminate() a program končí Jiné copy-constructory ale výjimky volat mohou (a bývá to vhodné)
Exception-safe programming Pravidla vynucená jazykem Destruktor
nesmí skončit vyvoláním výjimky
Konstruktor
globálního objektu nesmí skončit vyvoláním
výjimky Copy-constructor
typu v hlavičce catch-bloku nesmí skončit vyvoláním výjimky
Exception-safe programming Poznámka: Výjimky při zpracování výjimky Výjimka
při výpočtu výrazu v throw příkaze
Tento throw příkaz nebude vyvolán Výjimka
v destruktoru při stack-unwinding
Povolena, pokud neopustí destruktor Po zachycení a normálním ukončení destruktoru se pokračuje v původní výjimce Výjimka
uvnitř catch-bloku
Pokud je zachycena uvnitř, ošetření původní výjimky může dále pokračovat (přikazem throw bez výrazu) Pokud není zachycena, namísto původní výjimky se pokračuje ošetřováním nové
Exception-safe programming Kompilátory samy ošetřují některé výjimky Dynamická alokace polí Dojde-li k výjimce v konstruktoru některého prvku, úspěšně zkonstruované prvky budou destruovány • Ve zpracování výjimky se poté pokračuje
Exception-safe programming Kompilátory samy ošetřují některé výjimky Dynamická alokace polí Dojde-li k výjimce v konstruktoru některého prvku, úspěšně zkonstruované prvky budou destruovány • Ve zpracování výjimky se poté pokračuje Výjimka
v konstruktoru součásti (prvku nebo předka) třídy
Sousední, již zkonstruované součásti, budou destruovány Ve zpracování výjimky se poté pokračuje • Uvnitř konstruktoru je možno výjimku zachytit speciálním try-blokem: X::X( /* formální parametry */) try : Y( /* parametry pro konstruktor součásti Y */) { /* vlastní tělo konstruktoru */ } catch ( /* parametr catch-bloku */ ) { /* ošetření výjimky v konstruktoru Y i ve vlastním těle */ }
Konstrukci objektu nelze dokončit • Opuštění speciálního catch bloku znamená throw;
Exception-safe programming Definice (Weak)
exception safety
Funkce (operátor, konstruktor) je (slabě) bezpečná, pokud i v případě výjimky zanechá veškerá data v konzistentním stavu Konzistentní stav znamená zejména: • Nedostupná data byla korektně destruována a odalokována • Ukazatele nemíří na odalokovaná data • Platí další invarianty dané logikou aplikace
Exception-safe programming Definice (Weak)
exception safety
Funkce (operátor, konstruktor) je (slabě) bezpečná, pokud i v případě výjimky zanechá veškerá data v konzistentním stavu Konzistentní stav znamená zejména: • Nedostupná data byla korektně destruována a odalokována • Ukazatele nemíří na odalokovaná data • Platí další invarianty dané logikou aplikace Strong
exception safety
Funkce je silně bezpečná, pokud v případě, že skončí vyvoláním výjimky, zanechá data ve stejném stavu, ve kterém byla při jejím vyvolání Nazýváno též "Commit-or-rollback semantics"
Exception-safe programming Poznámky (Weak)
exception safety
Tohoto stupně bezpečnosti lze většinou dosáhnout Stačí vhodně definovat nějaký konzistentní stav, kterého lze vždy dosáhnout, a ošetřit pomocí něj všechny výjimky • Konzistentním stavem může být třeba nulovost všech položek • Je nutné upravit všechny funkce tak, aby je tento konzistentní stav nepřekvapil (mohou na něj ale reagovat výjimkou) Strong
exception safety
Silné bezpečnosti nemusí jít vůbec dosáhnout, pokud je rozhraní funkce navrženo špatně Obvykle jsou problémy s funkcemi s dvojím efektem • Příklad: funkce pop vracející odebranou hodnotu
Exception-safe programming Příklad: String č. 2 operator= Nebezpečná implementace: Pokud new char způsobí výjimku, operátor= zanechá v položce str_ původní ukazatel, který již míří na dealokovaný blok
class String { public: // ... private: char * str_; }; String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Nebezpečná implementace: Pokud new char způsobí výjimku, operátor= zanechá v položce str_ původní ukazatel, který již míří na dealokovaný blok K jiné výjimce zde dojít nemůže: • std::operator delete výjimky nikdy nevyvolává • char je vestavěný typ a nemá tedy konstruktory které by mohly výjimku vyvolávat • strlen a strcpy jsou C-funkce • Parametry a návratová hodnota se předávají odkazem
class String { public: // ... private: char * str_; }; String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Naivní
pokus o opravu:
Pokud new char způsobí výjimku, ošetří se Objekt se uvede do konzistentního stavu Výjimka se propaguje dál - ven z funkce Problém:
V catch bloku teoreticky může vzniknout nová výjimka
String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; try { str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } catch ( ... ) { str_ = new char[ 1]; * str_ = 0; throw; } } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Lepší pokus o opravu: Pokud new char způsobí výjimku, ošetří se Je
nutné pozměnit invariant třídy String: Položka str_ nyní smí obsahovat nulový ukazatel
String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; try { str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } catch ( ... ) { str_ = 0; throw; } } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Lepší pokus o opravu: Pokud new char způsobí výjimku, ošetří se Je
nutné pozměnit invariant třídy String: Položka str_ nyní smí obsahovat nulový ukazatel Takový exemplář String je považován za konzistentní Konzistentnost nemusí znamenat, že to je z uživatelského pohledu platná hodnota Může být považována i za chybovou a každá operace s takovou hodnotou může vyvolávat výjimku
String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; try { str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } catch ( ... ) { str_ = 0; throw; } } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Ekvivalentní řešení: Nulovat str_ po delete Pokud new způsobí výjimku, v str_ zůstane nulový ukazatel
String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; str_ = 0; str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Chyba: změnili jsme invariant str_ nyní může být nulové delete _str je v pořádku • operator delete je vždy proti nulovému ukazateli ošetřen (nedělá nic)
strlen a strcpy ale fungovat nebudou
String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; str_ = 0; str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Opraveno
String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; str_ = 0; if ( b.str_ ) { str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Vylepšení: operator= může vyvolávat výjimku, pokud se přiřazuje neplatná hodnota Tato výjimka může být definována např. takto: #include <exception> class InvalidString : public std::exception { virtual const char * what() const { return "Invalid string"; } }
String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; str_ = 0; if ( b.str_ ) { str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } else { throw InvalidString(); } } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Toto řešení je slabě bezpečné Silně bezpečné ale není: Pokud dojde k výjimce, nezachovává se původní stav dat To bude pro uživatele nepříjemné: String x, y; /* ... */ try { x = y + x; } catch (...) { /* ... */ }
Uživatel nedokáže rozlišit mezi výjimkami v operátorech + a = Náš operator= ale v případě výjimky ztratí hodnotu x
String & String::operator=( const String & b) { if ( this != & b ) { delete[] str_; str_ = 0; if ( b.str_ ) { str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } else { throw InvalidString(); } } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Silně bezpečné řešení Pokud dojde k výjimce v new, nestane se nic Ani před throw nenastane žádná změna
String & String::operator=( const String & b) { if ( this != & b ) { if ( b.str_ ) { char * aux = new char[ strlen( b.str_) + 1]; strcpy( aux, b.str_); delete[] str_; str_ = aux; } else { throw InvalidString(); } } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Silně bezpečné řešení Pozorování: Toto řešení je "shodou okolností" imunní proti this == & b
String & String::operator=( const String & b) { if ( this != & b ) { if ( b.str_ ) { char * aux = new char[ strlen( b.str_) + 1]; strcpy( aux, b.str_); delete[] str_; str_ = aux; } else { throw InvalidString(); } } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Silně bezpečné řešení Pozorování: Toto řešení je "shodou okolností" imunní proti this == & b Test je možno zrušit
String & String::operator=( const String & b) { if ( b.str_ ) { char * aux = new char[ strlen( b.str_) + 1]; strcpy( aux, b.str_); delete[] str_; str_ = aux; } else { throw InvalidString(); } return * this; }
Exception-safe programming Příklad: String č. 2 operator= Silně bezpečné řešení Pokud je copy-constructor silně bezpečný Standardní
řešení:
Copy-constructor naplní lokální proměnnou c kopií parametru b • Zde může dojít k výjimce
Metoda swap vyměňuje obsah this a proměnné c • Metoda swap je rychlá a nevyvolává výjimky
Před návratem z operatoru se volá destruktor c • Tím zaniká původní obsah this
void String::swap( String & x) { char * aux = str_; str_ = x.str_; x.str_ = aux; } String & String::operator=( const String & b) { String c( b); swap( c); return * this; }
Exception-safe programming Příklad: String č. 2 operator= Silně bezpečné řešení Metodu
swap je vhodné publikovat ve formě globální funkce Některé algoritmy nad kontejnery obsahujícími String se tak zrychlí a stanou se bezpečnými vůči výjimkám
void String::swap( String & x) { char * aux = str_; str_ = x.str_; x.str_ = aux; } String & String::operator=( const String & b) { String c( b); swap( c); return * this; } void swap( String & x, String & y) { x.swap( y); }
Exception-safe programming Příklad: String č. 2 operator= Silně bezpečné řešení Metodu
swap je vhodné publikovat ve formě globální funkce Některé algoritmy nad kontejnery obsahujícími String se tak zrychlí a stanou se bezpečnými vůči výjimkám
Sama
metoda swap může využívat šablonu swap pro typ char *
#include void String::swap( String & x) { swap( str_, x.str_); } String & String::operator=( const String & b) { String c( b); swap( c); return * this; } void swap( String & x, String & y) { x.swap( y); }
Exception-safe programming Příklad: String č. 2 copy-constructor Silně bezpečné řešení Pokud tělo dorazí na konec, budou datové položky korektně vyplněny Tělo může vyvolávat výjimky • V takovém případě není třeba datové položky vyplňovat • Objekt nebude považován za platný a nebude používán ani destruován
Obecně je však třeba ošetřit try-blokem situace, kdy je v objektu více dynamicky alokovaných ukazatelů
String( const String & b) { if ( b.str_ ) { str_ = new char[ strlen( b.str_) + 1]; strcpy( str_, b.str_); } else { throw InvalidString(); } }
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem Slabě
bezpečná implementace:
Při výjimce v konstruktoru proměnné s se nestane nic operator delete nezpůsobuje výjimky
struct Box { String v; Box * next; }; class StringStack { public: // ... private: Box * top_; }; String StringStack::pop() { if ( ! top_ ) throw StackEmpty(); Box * p = top_; String s = p->v; top_ = p->next; delete p; return s; }
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem Slabě
bezpečná implementace Není silně bezpečná: Funkce vrací hodnotou Pokud při vracení dojde k výjimce v copy-constructoru, zásobník již bude zkrácen
struct Box { String v; Box * next; }; class StringStack { public: // ... private: Box * top_; }; String StringStack::pop() { if ( ! top_ ) throw StackEmpty(); Box * p = top_; String s = p->v; top_ = p->next; delete p; return s; }
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem Slabě
bezpečná implementace Není silně bezpečná: Funkce vrací hodnotou Pokud při vracení dojde k výjimce v copy-constructoru, zásobník již bude zkrácen Tuto výjimku lze ošetřit try-blokem okolo příkazu return • Uvést zásobník do původního stavu • Ale: co když se uvedení do původního stavu nezdaří?
String StringStack::pop() { if ( ! top_ ) throw StackEmpty(); Box * p = top_; String s = p->v; top_ = p->next; delete p; try { return s; } catch ( ...) { p = new Box; p->v = s; p->next = top_; top_ = p; throw; } }
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem Nefunkční
implementace Není silně bezpečná: Funkce vrací hodnotou Pokud při vracení dojde k výjimce v copy-constructoru, zásobník již bude zkrácen Tuto výjimku lze ošetřit try-blokem okolo příkazu return Dokážeme udělat obnovení původního stavu bez nebezpečí výjimky • Ale: jak zrušíme proměnnou p, když k výjimce nedojde?
String StringStack::pop() { if ( ! top_ ) throw StackEmpty(); Box * p = top_; String s = p->v; top_ = p->next; // tady bylo delete p; try { return s; // tady by delete p; nepomohlo } catch ( ...) { top_ = p; throw; } }
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem Silně
bezpečná implementace
Jak zrušíme proměnnou p, když k výjimce nedojde? std::auto_ptr<
T>
"chytrý" ukazatel na T, který se chová jako "jediný vlastník objektu": • po zkopírování se vynuluje • při zániku volá delete
Pozor: auto_ptr má nestandardní copy-constructor a operator= • modifikují svůj parametr • pro auto_ptr nefungují kontejnery apod.
#include <memory> String StringStack::pop() { if ( ! top_ ) throw StackEmpty(); std::auto_ptr< Box> p = top_; top_ = p->next; try { return p->v; } catch ( ...) { top_ = p; // toto přiřazení nuluje p throw; } } // při návratu se automaticky zruší * p // pokud je p nenulové
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem Silně
bezpečná implementace Uživatel ji nedokáže použít tak, aby to bylo silně bezpečné Vracenou hodnotu je nutné okopírovat Nedá se poznat, zda výjimku vyvolala metoda pop nebo operator= • V prvním případě je zásobník nedotčen, ale ve druhém je již zkrácen
StringStack stk; String a; /* ... */ try { a = stk.pop(); } catch (...) { /* ??? */ }
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem
Řešení A Jako v STL Rozdělit pop na dvě funkce top vrací vrchol zásobníku • může jej vracet odkazem • nemodifikuje data
pop pouze zkracuje • je silně bezpečná
StringStack stk; String a; /* ... */ try { a = stk.top(); } catch (...) { /* chyba kopírování nebo prázdný zásobník, proměnná a nezměněna, zásobník nedotčen */ } try { stk.pop(); } catch (...) { /* chyba zkracování, proměnná a změněna, zásobník nedotčen */ }
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem
Řešení B Namísto vracení hodnoty funkce pop vyplňuje parametr předávaný odkazem tím se vyloučí nutnost kombinovat volání pop s dalším kopírováním Pro
uživatele jednodušší, implementace pop je však těžší
StringStack stk; String a; /* ... */ try { stk.pop( a); } catch (...) { /* chyba zkracování nebo kopírování, proměnná a nezměněna, zásobník nedotčen */ }
Exception-safe programming Příklad: StringStack::pop Zásobník prvků typu String Implementován seznamem
Řešení B Lze implementovat nad řešením A
#include <memory> class StringStack { public: /* A */ String & top(); void pop(); /* B */ void pop( String & out) { String & t = top(); swap( out, t); try { pop(); } catch (...) { swap( out, t); throw; } } };
Exception specifications Exception specifications U každé funkce (operátoru, metody) je možno určit seznam výjimek, kterými smí být ukončena Na výjimky ošetřené uvnitř funkce se specifikace nevztahuje Pokud není specifikace uvedena, povoleny jsou všechny výjimky Specifikace respektuje dědičnost, to jest automaticky povoluje i všechny potomky uvedené třídy
void a() { /* tahle smí všechno */ } void b() throw () { /* tahle nesmí nic */ } void c() throw ( std::bad_alloc) { /* tahle smí std::bad_alloc */ } void d() throw ( std::exception, MyExc) { /* tahle smí potomky std::exception a MyExc */ }
Exception specifications Exception specifications Kompilátor zajistí, že nepovolená výjimka neopustí funkci: Pokud by se tak mělo stát, volá se unexpected() • unexpected() smí vyvolat "náhradní" výjimku
Pokud ani náhradní výjimka není povolena, zkusí se vyvolat std::bad_exception Pokud ani std::bad_exception není povoleno, volá se terminate() a program končí
Exception specifications Exception specifications Kompilátor zajistí, že nepovolená výjimka neopustí funkci Toto je běhová kontrola Kompilátor smí vydávat nejvýše varování Funkce smí volat jinou, která by mohla vyvolat nepovolenou výjimku (ale nemusí)
void f() throw ( std::exception) { } void g() throw () { f(); /* tohle se smí */ }
Exception specifications Exception specifications Kompilátor (a runtime) zajistí, že nepovolená výjimka neopustí funkci Microsoft Visual C++ 7.0 to ovšem neimplementuje Kompilátor
to může využít
Speciálně při volání funkce s prázdným throw () se nemusí generovat ošetřující kód Program se zmenší a možná i zrychlí Užitek
pro programátory:
Komentář Ladicí prostředek
Šablony Templates
Šablony tříd - definice Šablona
je generická třída parametrizovaná libovolným počtem formálních parametrů těchto druhů: celé číslo – uvnitř šablony se chová jako konstanta, použitelná jako meze polí ukazatel libovolného typu libovolný typ – deklarováno zápisem class T nebo typename T, identifikátor formálního parametru se chová jako identifikátor typu, použitelný uvnitř šablony v libovolné deklaraci
Prefix
definice šablony
template< formální-parametry>
lze použít před několika formami deklarací; oblastí platnosti formálních parametrů je celá prefixovaná deklarace
Šablony tříd - instanciace Instanciace
šablony: Šablonu lze použít jako typ pouze s explicitním uvedením skutečných parametrů odpovídajících druhů: celé číslo: celočíselný konstantní výraz ukazatel: adresa globální nebo statické proměnné či funkce kompatibilního typu libovolný typ – jméno typu či typová konstrukce (včetně jiné instanciované šablony)
Užití
instanciované šablony:
Instanciované šablony jsou stejného typu, pokud jsou stejného jména a jejich skutečné parametry obsahují stejné hodnoty konstantních výrazů, adresy stejných proměnných či funkcí a stejné typy
Šablony tříd – pravidla použití Uvnitř
těla šablony (nebo jako její předky) je možno užívat libovolné typy včetně: Instancí jiných šablon Téže šablony s jinými argumenty Téže šablony se stejnými argumenty • V tomto případě se argumenty mohou, ale nemusí opisovat
Ekvivalentní varianty šablony s copy-constructorem: template< typename T> class X { X( const X< T> &); }; template< typename T> class X { X( const X &); };
• Některé překladače připouštějí i tuto variantu template< typename T> class X { X< T>( const X< T> &); };
Šablony tříd – pravidla použití Metody
šablon mohou mít těla uvnitř třídy nebo vně
Vně uvedená těla metod musejí být připojena k šabloně takto: template< typename T> void X< T>::f( int a, int b) { /* ... */ }
V kvalifikovaném jméně metody je nutné uvést patřičný seznam argumentů, tj. X< T>::f a nikoliv X::f Těla
metod musejí být viditelná z každého místa, kde jsou pro nějakou instanci šablony volána Musejí tedy typicky být v témže hlavičkovém souboru jako sama šablona. Uvedení těla metody vně třídy tedy u šablon typicky nic nepřináší, může být však vynuceno rekurzivními odkazy mezi šablonami apod.
Šablony tříd – pravidla použití Šablona
třídy se překládá až v okamžiku instanciace, tj. použití s konkrétními parametry Překladač instanciuje (tj. překládá) pouze ty metody, které jsou zapotřebí (tj. jsou volány nebo jsou virtuální) Některá těla metod tedy nemusí být pro některé případy parametrů přeložitelná template< typename Container> class Proxy { public: void pop_front() { c->pop_front(); } /* ... */ private: Container * c; };
// jen pro list/deque
Explicitní instanciace Překladač je možné donutit ke kompletní instanciaci šablony template class Array< 128, char>;
Šablony tříd – závislé typy Šablony
tříd (včetně těl metod) se při deklaraci kontrolují pouze syntakticky •Některé překladače nedělají ani to Překladač potřebuje odlišit jména typů od ostatních jmen •U jmen ve tvaru A::B to překladač někdy nedokáže •Programátor musí pomoci klíčovým slovem typename template< typename T> class X { typedef typename T::B U; // T::B je typ typename U::D p; // T::B::D je typ typename Y::C q; // Y::C je typ void f() { T::D(); } // T::D není typ } •typename
je nutné uvést před jmény typu ve tvaru A::B, kde A je závislé jméno •Závislé jméno je jméno obsahující přímo či nepřímo parametr šablony
Šablony tříd - this Pokud
je mezi předkem třídy závislé jméno
překladač pak neví, které identifikátory jsou zděděny uživatel musí pomoci konstrukcí this-> template< typename T> class X : public T { void f() { return this->a; } }
Šablony tříd – triky Dopředná deklarace šablony template< typename T> class X; /* ... zde může být použito X s jakýmikoliv argumenty U... ... pouze v kontextech, kde kompilátor nepotřebuje znát tělo šablony ... */ template< typename T> class X { /* ... */ };
Šablony funkcí Šablona
funkce je generická funkce (globální nebo metoda) prefixovaná konstrukcí template se stejnými druhy formálních parametrů šablony jako u šablon tříd
template< typename T, int k> int f( T * p, int q); template< typename T, typename U> int g( T * p, vector< U> q);
Šablony
// // // //
parametry parametry parametry parametry
šablony funkce šablony funkce
funkcí lze volat dvěma způsoby
Explicitně f< int, 729>( a, b)
Automaticky g( a, b)
• Překladač dopočte parametry šablony z typů parametrů funkce • Všechny formální argumenty šablony by měly být užity v typech formálních parametrů funkce
Šablony funkcí Pod
stejným identifikátorem může být deklarováno několik různých šablon funkce a navíc několik obyčejných funkcí. Obyčejné funkce mají přednost před generickými
template< class T> T max( T a, T b) { return a < b ? b : a; }; char * max( char * a, char * b) { return strcmp( a, b) < 0 ? b : a; }; template< int n, class T> T max( Array< n, T> a) { /* ... */ }
Příklad ze standardních knihoven: template< class T> void swap( T & a, T & b) { T tmp(a); a = b; b = tmp; };
• K tomu řada chytřejších implementací swap pro některé třídy
Šablony – pokročilé konstrukce jazyka Parciální specializace Deklarovanou šablonu lze pro určité kombinace parametrů předefinovat jinak, než určuje její základní definice template< int n> class Array< n, bool> { /* specializace pro pole typu bool */ };
Krajním případem parciální specializace je explicitní specializace
Explicitní specializace template<> class Array< 32, bool> { /* ... */ };
U šablon funkcí nahrazena obyčejnou funkcí
Explicitní instanciace Překladač je možné donutit ke kompletní instanciaci šablony template class Array< 128, char>;
Parciální specializace Parciální specializace Deklarovanou šablonu lze pro určité kombinace parametrů předefinovat jinak, než určuje její základní definice • Parciálně specializovat lze šablony funkcí, celé šablony tříd i jednotlivě těla jejich metod • Obsah specializace šablony třídy (teoreticky) nemusí nijak souviset se základní definicí - může mít zcela jiné položky, předky apod. • Základní definice dokonce nemusí vůbec existovat (ale musí být deklarována) template< class X, class Y> class C; template< class P, bool cmp( P *, Q }; template< class Z> bool set( Z &); }; template< class X, X add( Y); };
// základní deklarace
class Q> class C< P *, Q *> { // specializace *); class C< Z, Z> : public Z { // jiná specializace
class Y> class C { // základní definice
Parciální specializace Parciální specializace Deklarovanou šablonu lze pro určité kombinace parametrů předefinovat jinak, než určuje její základní definice • Parciální specializace může mít stejný, menší i větší počet formálních parametrů než základní definice, jejich hodnoty se odvozují ze skutečných parametrů šablony (kterých je vždy tolik, kolik určuje základní definice) template< class T, class U, int n> class C< T[n], U[n]> { /* specializace pro dvě pole stejné velikosti */ };
Parciální specializace Parciální specializace Deklarovanou šablonu lze pro určité kombinace parametrů předefinovat jinak, než určuje její základní definice • Parciální specializace může mít stejný, menší i větší počet formálních parametrů než základní definice, jejich hodnoty se odvozují ze skutečných parametrů šablony (kterých je vždy tolik, kolik určuje základní definice) template< class T, class U, int n> class C< T[n], U[n]> { /* specializace pro dvě pole stejné velikosti */ };
Krajním případem parciální specializace je explicitní specializace
Explicitní specializace template<> class C< char, int[ 8]> { /* ... */ };
Explicitní specializace šablony není šablona Podléhá trochu jiným (jednodušším) pravidlům • Překlad se neodkládá • Těla metod se nepíší do hlavičkových souborů
Parciální specializace Typická použití parciální a explicitní specializace Výhodnější implementace ve speciálních případech Šablona je používána přímo z nešablonovaného kódu Programátor - uživatel šablony o specializaci nemusí vědět Příklad: Implementace vector může být jednodušší
Parciální specializace Typická použití parciální a explicitní specializace Výhodnější implementace ve speciálních případech Šablona je používána přímo z nešablonovaného kódu Programátor - uživatel šablony o specializaci nemusí vědět Příklad: Implementace vector může být jednodušší Mírná
změna rozhraní ve speciálních případech
Šablona je používána přímo z nešablonovaného kódu Uživatel by měl být o specializaci informován Příklad: vector< bool> nedovoluje vytvořit ukazatel na jeden prvek
Parciální specializace Typická použití parciální a explicitní specializace Výhodnější implementace ve speciálních případech Šablona je používána přímo z nešablonovaného kódu Programátor - uživatel šablony o specializaci nemusí vědět Příklad: Implementace vector může být jednodušší Mírná
změna rozhraní ve speciálních případech
Šablona je používána přímo z nešablonovaného kódu Uživatel by měl být o specializaci informován Příklad: vector< bool> nedovoluje vytvořit ukazatel na jeden prvek Modifikace
chování jiné šablony
Specializovaná šablona je volána z jiného šablonovaného kódu Autor volající šablony předpokládá, že ke specializaci dojde • Někdy dokonce ani nedefinuje základní obsah volané šablony
Autor specializace tak upravuje chování volající šablony Příklad: šablona basic_string volá šablonu char_traits, ve které je např. definována porovnávací funkce
Parciální specializace Modifikace chování jiné šablony Specializovaná šablona je volána z jiného šablonovaného kódu Autor volající šablony předpokládá, že ke specializaci dojde • Někdy dokonce ani nedefinuje základní obsah volané šablony
Autor specializace tak upravuje chování volající šablony Příklad: šablona basic_string volá šablonu char_traits, ve které je např. definována porovnávací funkce template< class T> struct char_traits; template< class T> class basic_string { /* ... */ int compare( const basic_string & b) const { /*...*/ char_traits< T>::compare( /* ... */) /*...*/ } }; template<> struct char_traits< char> { /* ... */ static int compare(const char* s1, const char* s2, size_t n) { return memcmp( s1, s2, n); } };
Parciální specializace Modifikace chování jiné šablony Specializovaná šablona je volána z jiného šablonovaného kódu Autor volající šablony předpokládá, že ke specializaci dojde • Někdy dokonce ani nedefinuje základní obsah volané šablony
Autor specializace tak upravuje chování volající šablony
Traits Šablony, ze kterých nejsou vytvářeny objekty Obsahují pouze: Definice typů Statické funkce Určeny
k doplnění informací o nějakém typu
Příklad: char_traits doplňuje informace o typu T, např. porovnávací funkci
Traits & policies Traits Šablony, ze kterých nejsou vytvářeny objekty Obsahují pouze: Definice typů Statické funkce Určeny
k doplnění informací o nějakém typu
Příklad: char_traits doplňuje informace o typu T, např. porovnávací funkci
Policy classes Třídy, ze kterých obvykle nejsou vytvářeny objekty Předávány jako parametr šablonám Defaultní hodnotou parametru často bývá šablona traits Určeny
k definování určitého chování
Příklad: Alokační strategie
Triky s šablonami Porovnání typů s booleovským výstupem template< class A, class B> struct Equal { enum { value = false }; }; template< class A> struct Equal< A, A> { enum { value = true }; };
Equal< X, Y>::value je konstantní výraz Použití template< class T1> class Test { enum { T1_is_int = Equal< int, T1>::value}; enum { T1_is_long = Equal< long, T1>::value}; /* ... */ };
Triky s šablonami Porovnání typů s typovým výstupem template< class A, class B, class C, class D> struct IfEqual { typedef D Result; }; template< class A, class C, class D> struct Equal< A, A, C, D> { typedef C Result; };
IfEqual< X, Y, U, V>::Result je typ • Význam: X == Y ? U : V
Použití template< class T1> class Test { typedef Equal< T1, unsigned, unsigned long, long>::Result longT1; /* ... */ };
Triky s šablonami Kompilační ověření invariantu template< int x> struct AssertNot; template<> struct AssertNot< 0> { enum { value = true }; }; template< int x> struct Assert { enum { value = AssertNot< ! x>::value }; };
Triky s šablonami Kompilační ověření invariantu template< int x> struct AssertNot; template<> struct AssertNot< 0> { enum { value = true }; }; template< int x> struct Assert { enum { value = AssertNot< ! x>::value }; };
Použití template< int N> class Array { enum { check = Assert< (N > 0)>::value }; /* ... */ }; Array< -3> x;
• error C2027: use of undefined type 'AssertNot<x>' with [x=1]
Teoretický pohled na šablony Příklad template< int N> struct Fact { enum { value = Fact< N-1>::value * N }; }; template<> struct Fact< 0> { enum { value = 1 }; };
Teoretický pohled na šablony Příklad template< int N> struct Fact { enum { value = Fact< N-1>::value * N }; }; template<> struct Fact< 0> { enum { value = 1 }; }; Použití
enum { N = 10 }; int permutations[ Fact< N>::value];
Teoretický pohled na šablony Příklad template< int N> struct Fact { enum { value = Fact< N-1>::value * N }; }; template<> struct Fact< 0> { enum { value = 1 }; };
Kontrolní otázka: Kolik je Fact< -1>::value
Teoretický pohled na šablony Příklad template< int N> struct Fact { enum { value = Fact< N-1>::value * N }; }; template<> struct Fact< 0> { enum { value = 1 }; };
Kontrolní otázka: Kolik je Fact< -1>::value MS Visual C++ 7.1: • fatal error C1202: recursive type or function dependency context too complex
Řetěz instanciací Fact< -1>, Fact< -2>, Fact< -3>, ... způsobí přetečení tabulek kompilátoru
Teoretický pohled na šablony Jiný příklad template< int N> struct Fib { enum { value = Fib< N-1>::value + Fib< N-2>::value }; }; template<> struct Fib< 0> { enum { value = 1 }; }; template<> struct Fib< 1> { enum { value = 1 }; };
Kontrolní otázka: Jak dlouho trvá výpočet (tj. kompilace) Fib< 1000>::value
Teoretický pohled na šablony Jiný příklad template< int N> struct Fib { enum { value = Fib< N-1>::value + Fib< N-2>::value }; }; template<> struct Fib< 0> { enum { value = 1 }; }; template<> struct Fib< 1> { enum { value = 1 }; };
Kontrolní otázka: Jak dlouho trvá výpočet (tj. kompilace) Fib< 1000>::value MS Visual C++ 7.1: Build Time 0:00 Kompilátory ukládají již vytvořené instanciace a nepočítají je znovu
