C For Scientific Computing - Heidelberg University

Memory Management in C Memory Segments in C programsIn C there are esentially thress memory segments where objects can be stored.These are:Memory segments in C 1The global memory segment. It stores all global variables and staticcomponents of classes and compiled directly into the executable file.2The stack contains all instances of currently executed methods and functionsand their related local variables.3The heap provides memory, that can be allocated for dynamically allocatedobjects.The management of dynamic memory is performed in C by the operatoren newand delete.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201522 / 85

Memory Management in C Memory Allocation with newMemory space can allocated from the heap with new:int * intPtr ;intPtr new int ; // intPtr points onto the new int memoryWithe the code line intPtr new int; memory space is allocated for namelessobject of type int and pointer to it is returned.The construct new int reserves space in the heap for an int value, provides a pointer onto the allocated memory space.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201523 / 85

Memory Management in C Freeing of Memory with deleteAllocated memory space should be freed when an object is not necessary anymore.This happens with the instruction delete:int * intPtr ;intPtr new int ;// intPtr points onto the new int memorydelete intPtr ;// memory is freedStefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201524 / 85

Memory Management in C Life Cycle of ObjectsDie life time of objects depends on the structure of the program: Static and global variables exist during the complete run time. Local variables exist as long as the function, they belong to, exist. They arecreated and destroyes with each new instance. Dynamic objects in the heap exist independently of the program structure,their life time is controlled by new and delete.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201525 / 85

Memory Management in C Life Cycle of ObjectsThe following code clarifies the different life times of dynamic and static variables:int foo () {int * p new int ;* p 5;return p ;}void main ( void ) {int * q foo () ;.delete q ;q NULL ;.}Stefan Lang (IWR, Heidelberg)////////Generate an nameless variable in the heapThe nameless variable is initialized with 5.A pointer onto a nameless variableis returned. Bad!////////q is generated is initialized with a pointeronto the nameless variable.The nameless variable in the heap is destroyedOK, q ist now secured (point to nothing)// Program end: variable q is deletedC for Scientific Computing15. Oktober 201525 / 85

Abstract Data Types and Their Realisation in C ClassesClasses and Data TypesA C class defines a data type. A data type is a status set with operations, thattransform states into each other. Example complex numbers:1# include iostream 2345678class ComplexNumber { // a class defintionpublic :void print (){std :: cout u " i * " v std :: endl ;}9101112private :double u , v ;};// ’;’ is very important!1314151617int main ( int argc , char ** argv ){ComplexNumber a , b , c ;a . print () ;// print unitialized (!) number18//c a b; // where defined?1920return 0;2122}Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201526 / 85

Abstract Data Types and Their Realisation in C ClassesClasses and Data Types C enables the encapsulation of a data type, this means separation ofimplementation and interface. public: Interface specification, private: Data and implementation. From outside only methods and data in the public part can be accessed. Implementation of methods can happen outside of the class.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201527 / 85

Abstract Data Types and Their Realisation in C Constructors and DestructorsConstructors The instruction ComplexNumber a; make the compiler generate an instance ofthe class. For initialisation the constructor is called. There can exist several constructors (polymorphism!). In certain cases the compiler generates default constructors.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201528 / 85

Abstract Data Types and Their Realisation in C Constructors and DestructorsConstructorsThe class ComplexNumber with two constructors:12345class Co mplexNum bers{public :// some constructorsComplexNumber () { u 0; v 0; }// default678ComplexNumber ( double re , double im ) // initialize with{ u re ; v im ; }// given numbers910void print () { . }11121314private :double u , v ;};Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201529 / 85

Abstract Data Types and Their Realisation in C Constructors and DestructorsConstructoren123456// usage of the complex number classint main ( int argc , char ** argv ){ComplexNumber a (3.0 ,4.0) ;ComplexNumber b (1.0 ,2.0) ;ComplexNumber c ;7a . print () ;c a b;89// output: 3 i * 4// where defined ?10return 0;1112};Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201530 / 85

Abstract Data Types and Their Realisation in C Constructors and DestructorsDestructors Dynamic generated objects can be destructed, if they are not necessary anymore. Deletion of objects is handled by the destructor. Destructors are especially to be (self)implemented, if the class containspointer (e.g. arrays!). Furthermore when dynamic memory is used inside a class. Keywords for dynamic memory management: new, delete.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201531 / 85

Abstract Data Types and Their Realisation in C Constructors and DestructorsOverloading of OperatorsOperations for abstract data types (classes) The instruction a b is not defined for ComplexNumber and must be defined. For classes different operations e.g. , ,*,/,-,--, ,! ,!, ,[],.can be self-implemented. Classes, that implement the operator () are called Functors.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201532 / 85

Templates and Generic ProgrammingTemplatesTemplates – Code Patterns Templates enable the parameterisation of classes and functors. Templates decouple functions or algorithms from data types. Allowed parameters: Standard types like int, double, ., Own types (classes), Templates. Templates enable static polymorphism (see later). Templates generalize code Generic Programming“.”Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201533 / 85

Templates and Generic ProgrammingExample: Templated Function1# include iostream 2345678// example for a function templatetemplate class T T getMax ( const T & a , const T & b ){return (a b ) ? a : b ;}910111213int main (){inti 5, j 6, k;double l 10.4 , m 10.25 , n ;14k getMax int ( i , j ) ; n getMax double ( l , m ) ;std :: cout k " , " n std :: endl ;// output: 6, 10.415161718return 0;1920}Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201534 / 85

Templates and Generic ProgrammingExample: Templated Array Class1234567// a class that takes a template parametertemplate typename T class Array{public :int add ( const T & next , int n ) ;// add ’next’ at data[n]T & at ( int n ) ;T & operator []( int n ) { return at ( n ) ; } // overloaded operator891011private :T data [10];};12131415161718192021// add a new data membertemplate class T int Array T :: add ( const T & next , int n ){if (n 0 && n 10){data [ n ] next ; return 0;}else return 1;}Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201535 / 85

Templates and Generic ProgrammingExample: Templated Array Class2324252627// get a certain data membertemplate class T T & Array T :: at ( int n ){if (n 0 && n 10) return data [ n ];}2829303132333435// main program# include iostream int main (){Array int c ; c . add (3 ,0) ; c . add (4 ,5) ; c . add (0 ,1) ;std :: cout c . at (5) std :: endl ;// output: 436Array char d ; d . add ( ’x ’ ,9) ;std :: cout d . at (9) std :: endl ;// output: x37383940return 0;4142}Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201536 / 85

Templates and Generic ProgrammingFurther on Templates Templates are the foundation of generic programming in C ! Templates can be self-specialized (for special cases). Further template parameter are possible. Parameters may have default values.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201537 / 85

The STLSTL – The Standard Template LibraryIn C ther are many preexisting template container, that can be used forimplementation purposes. They are collected in a library, named STL.The STL is a collection of template classes and algorithms, provides many container classes (class, that mananges a set of objects), has therefore standardized user interfaces for the containers, is contained in the C standard library.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201538 / 85

The STLContainer Types of the STLThe STL provides different kinds of containers: Sequential containerExamples: Vectors, lists Container adapterRestricted Interface for arbitrary containersExample: Stacks, queues Associative containerKey-Value ContainerExample: Maps, MultimapsStefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201539 / 85

The STLDis/Advantages of the STLAdvantages and disadvantages of the STL Dynamic memory management Avoidance of array overruns High quality of containers Optimizability by staticpolymorphismStefan Lang (IWR, Heidelberg)–Very complicated, unstructurederror messages–High demands for compiler anddeveloper–Not all compilers are STL-ready(despite the STL is contained in theC standard)C for Scientific Computing15. Oktober 201540 / 85

The STLExample of a Container Class: VectorsExample for the Application of STL containers:vector12# include iostream # include vector 34567int main () {// example usage of an STL vectorint result 0;std :: vector int x (100) ;8for ( int j 0; j 100; j ) x [ j ] j ;910x . push back (100) ;1112for ( int j 0; j x . size () ; j )result x [ j ];131415// output: 5050std :: cout result std :: endl ;161718return 0;1920}Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201541 / 85

The STLThe Iterator InterfaceThe Iterator InterfaceIterators provide access onto the elements of a container. They iterate over the elements of a container, provide pointer onto container elements, are provided by every container class, have r“- and w“ variants,”” help to avoid array overflows. are used in many STL algorithms like sorting, searching and others.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201542 / 85

The STLThe Iterator InterfaceExample: Iterators over a Map123# include iostream # include map # include cstring 45678int main (){// example usage of an STL-mapstd :: map std :: string , int y ;9y [ " one " ] 1; y [ " two " ] 2;y [ " three " ] 3; y [ " four " ] 4;101112std :: map std :: string , int :: iterator it ;//std::map¡std::string, double¿::iterator it; // nice error message :-)for ( it y . begin () ; it ! y . end () ; it )std :: cout it - first " : " it - second std ::endl ;// output: one: 1// two: 2 . usw.13141516171819return 0;2021}Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201543 / 85

The STLThe Iterator InterfaceAn Disadvantage of the STL: The error messaageIf in this example the wrong type of an iterator is instantiated, the compilerreturns the followoing error message:12345map . cc : In function ’ int main () ’:map . cc :15: error : no match for ’ operator ’ in ’ it y . std :: map Key ,Tp , Compare , Alloc :: begin [ with Key std :: basic string char, std :: char traits char , std :: allocator char , Tp int ,Compare std :: less std :: basic string char , std :: char traits char , std :: allocator char , Alloc std :: allocator std ::pair const std :: basic string char , std :: char traits char , std ::allocator char , int ]() ’/ usr / include / c /4.4/ bits / stl tree . h :154: note : candidates are : std ::Rb tree iterator std :: pair const std :: basic string char , std ::char traits char , std :: allocator char , double \& std ::Rb tree iterator std :: pair const std :: basic string char , std ::char traits char , std :: allocator char , double :: operator (const std :: Rb tree iterator std :: pair const std :: basic string char , std :: char traits char , std :: allocator char , double \&)map . cc :15: error : no match for ’ operator ! ’ in ’ it ! y . std :: map Key ,Tp , Compare , Alloc :: end [ with Key std :: basic string char ,std :: char traits char , std :: allocator char , Tp int ,Compare std :: less std :: basic string char , std :: char traits char , std :: allocator char , Alloc std :: allocator std ::pair const std :: basic string char , std :: char traits char , std ::allocator char , int ]() ’[.]Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201544 / 85

STL AlgorithmsAlgorithmsAlgorithms provided by the STLThe STL contains many helpful algorithms, that manipulate elements of data containers, use iterators for element access.Examples: Sorting Searching Copying Reversing the ordering in the container .Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201545 / 85

STL AlgorithmsAlgorithmsExample: Sorting-Algorithms for Vectors Different sorting orders for vectors are usable Distinction i.e. by: Used comparison operators Area of sorting Stability Complexity of Standard-Sorters for Vectors: O(n · log n) ideal O(n2 ) most unfavourable case Self-implemented comparision functions possible Caution: (double linked) lits are optimized for insertion and deletion ofelements special sorting algorithmsStefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201546 / 85

STL AlgorithmsAlgorithmsExample: Usage of a sorting algorithm for vectors12// a vector for integersvector int x ;3456x . push back (23) ; x . push back ( -112) ;x . push back (0) ; x . push back (9999) ;x . push back (4) ; x . push back (4) ;789// sort the integer vectorsort ( v . begin () , v . end () ) ;10111213// output: -112 0 4 4 23 9999for ( int i 0; i x . size () ; i )cout x [ i ] " \ t " ;Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201547 / 85

Inheritance in C Inheritance in C Inheritance Data type passes its abstractions to other data types. Is-an“ relation: Triangle is a geometric object, this means is to derive from”class GeomObject. Not to interchange with aContains-a“ relation: A triangle contains three points (but a triangle is no”point no inheritance).Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201548 / 85

Inheritance in C Inheritance in C 12345678// example of inheritance in C class Matrix{public :.private :double data [3][3]; // (3 x 3)-Matrix};910111213141516171819// the derived class: symmetrical matrix is a matrixclass SymMatrix : public Matrix{public :double getEntry ( int i , int j ) { return data [ i ][ j ]; }// error: data private in base class.// constructor calls a constructor of base classSymMatrix () : Matrix () { . }};Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201549 / 85

Inheritance in C Different Types of Inheritance in C In inheritance you have to take care of which members the derived class canaccess different types of inheritance: private inheritance:all elements of the base class get private members of the derived class. public inheritance:publicmembers of the base class get public members of the derived class,gets private.privateStefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201550 / 85

Inheritance in C Different Types of Inheritance in C Private member of the base class stay always private (otherwise theencapsulation make no sense). Problem: private members are encapsulated too strong, public members notin anyway. Ausweg: protected members can access onto derived classes.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201550 / 85

Virtual Functions and Abstract Base ClassesVirtual FunctionsVirtual FunctionsVirtual Functions enable the hiding of methods of the base class by the derivedclass:123class GeomObject{public :// base class for geo objects// ’area’ is a function member4virtual double area () { return 0.0; }.567};891011class Triangle : public GeomObject{// a derived classpublic :// has a specific member ’area’ as well12131415double area ().private :{ return 0.5 * a * h ; }16double h , a ;1718};Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201551 / 85

Virtual Functions and Abstract Base ClassesVirtual FunctionsVirtual FunctionsWhen Basis- and derived class members contain the same name – Which methodis then called?192021int main () {GeomObject * geo ;Triangle t ;22geo & t ;std :: cout geo - area () std :: endl ; // ?232425return 0;2627};Solution: If specified otherwise the methods of the basis object (!). By the keyword virtual the call is passed to the derived class. Keyphrase Late Binding, i.e. mapping method name implementationduring run time.Stefan Lang (IWR, Heidelberg)C for Scientific Computing15. Oktober 201552 / 85

Virtual Functions and Abstract Base ClassesVirtual FunctionsDynamic PolymorphismThe techniqueu of late type-bindung with virtual functions has its own name:Dynamic Polymorphism Exact type determination during runtime. Realisation by:- Virtual functions (Function Lookup Table),

10 Templates and Generic Programming 11 The Standard Template Library (STL) Stefan Lang (IWR, Heidelberg) C for Scienti c Computing 15. Oktober 2015 2 / 85. C f ur Wissenschaftliches Rechnen II Example of a Container Class: Vectors The Iterator Int