IBM Research – Zurich Business Integration Technologies C++ (2.Vorlesung) Grundlagen Thomas Gschwind <thg at zurich.…> © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Agenda Separate Compilation – Variables – Routines (Functions & Operators) – Types (Structures, Classes) Standard Library 2 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Separate Compilation Why? Having only one source file is unrealistic Break the code up into its logical structure Reduction of compile time – Only changed parts need to be recompiled How? Use multiple source files Need to know what information about functions and variables “used” from other files 3 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Separate Compilation in Java Each Java file is compiled into a class file If a Java class invokes a method of another class, the compiler consults the class file to – – – – Determine whether the class provides the requested method Determine whether a class file implements a given interface etc. Hence, the .class file contains the entire interface That’s why in Java, the compiler needs the class path Finally, all class files are loaded by the Java Virtual Machine (and linked) Java source code can be relatively well reconstructed from .class file (see jad, the java decompiler) 4 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Some Java Trivia public class Const { public static final String msg="Hello World!"; } public class Cool { public static void main(String[] args) { System.out.println(Const.msg); } } 5 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Some Java Trivia public class Const { public static final String msg="Hello World!"; } public class Cool { public static void main(String[] args) { System.out.println(Const.msg); } } Now compile both Java files and run Cool Change the msg in Const.java, recompile Const.java, and run Cool 6 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Some Java Trivia public class Const { public static final String msg="Hello World!"; } public class Cool { public static void main(String[] args) { System.out.println(Const.msg); } } Now compile both Java files and run Cool Change the msg in Const.java, recompile Const.java, and run Cool Cool still prints the old message! Why? – javac inlines constants – And according to the Java specification that’s legal 7 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Separate Compilation in C++ By convention, each source file is compiled into an object file Object files provide minimum necessary to execute the code Object files do not provide enough information for the compiler to identify – Functions provided by another compilation unit – Layout of a user-defined type Object files are not used during the compilation – C++ and C use “header” files to store the interfaces of the object file – These files need to be supplied by the developer In C/C++, we have the include path instead 8 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Header Files C++ uses so-called header files for separate compilation The header file can be viewed as the object file’s interface Header files are another encapsulation mechanism – They describe the interface(s) provided by the object files – Describe everything that should be exported to other compilation units “Everything” that should not be exported stays in the C file – Except for a few exceptions 9 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Header Files – the truth Declaration – Variables and function names – Types Definition – “Implementation” – Memory allocation & Initialization (well, mostly) 10 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Variables Variables that are global to the entire project should be declared as extern in the header file (avoid unless the variables are constant) Only constant variables can be initialized in the header file 11 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Example How can we split this file? One file for variables, one for main? #include <cstdlib> #include <iostream> vars.cc using namespace std; const double pi=3.141596; const double primes[]={2, 3, 5, …, 1234567891}; int my_dumb_global_variable=17; void main(int argc, char *argv[]) { int a1=atoi(argv[1]), a2=atoi(argv[2]); cout << arg << "^2*pi=" << a1*a2*pi << endl; cout << "e=" << e << endl; } 12 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies vars.h Variables #ifndef VARS_H_ #define VARS_H_ const double pi=3.141596; extern const int[] primes; extern int my_dumb_global_variable; #endif vars.cc #include "vars.h" 13 const int primes[]={2, 3, 5, …, 1234567891}; int my_dumb_global_variable=17; Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies vars.h Variables if VARS_H_ is not defined process the following lines #ifndef VARS_H_ define _VARS_H #define VARS_H_ extern int my_dumb_global_variable; end the last open extern const double e; #if… section const double pi=3.141596; This pattern ensures that #endif header files won’t be processed multiple times vars.cc #include "vars.h" 14 Process the file “vars.h” int my_dumb_global_variable=17; const double e=2.718281; Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Functions The signature of the function needs to be included in the header (for type checking and parameter passing) inline functions should go here if they should be inlined globally 15 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Functions #include <cstdlib> #include <iostream> using namespace std; void swap(int &a, int &b) { // definition int c=a; a=b; b=c; } int gcf(int a, int b) { // definition if (a<b) swap(a,b); while (b!=0) { a=a-b; if (a<b) swap(a,b); } return a; } inline int lcm(int a, int b) { // declaration & definition return (a/gcf(a,b))*b; } void main(int argc, char *argv[]) { int a1=atoi(argv[1]), a2=atoi(argv[2]); cout << arg << "^2*pi=" << a1*a2*pi << endl; cout << "e=" << e << endl; } 16 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies util.h Functions #ifndef UTIL_H_ #define UTIL_H_ void swap(int &a, int &b); int gcf(int a, int b); inline int lcm(int a, int b) { return (a/gcf(a,b))*b; } #endif // declaration // declaration // declaration & definition util.cc #include "util.h" void swap(int &a, int &b) { // definition int c=a; a=b; b=c; } int gcf(int a, int b) { // definition if (a<b) swap(a,b); while (b!=0) { a=a-b; if (a<b) swap(a,b); } return a; } 17 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Classes and Structures All user-defined types must be in the header file (typedefs, structures, classes) Typedefs not otherwise available Need to know the size and layout of structures (& classes) Exception – Types that are only used In the file where they are declared 18 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies fraction.h Classes and Structures (cont’d) struct fraction { // type definition int c; int d; fraction(int cntr=0, int denom=1) : c(cntr), d(denom) {}}; fraction operator*(const fraction &a, const fraction &b); fraction operator/(const fraction &a, fraction b); fraction.cc #include "fraction.h" #include "util.h" fraction operator*(const fraction &a, const fraction &b) { fraction r; int f1=gcf(a.c,b.d), f2=gcf(b.c,a.d); r.c=(a.c/f1)*(b.c/f2); r.d=(a.d/f2)*(b.d/f1); return r; } fraction operator/(const fraction &a, fraction b) { swap(b.c,b.d); return a*b; } 19 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies fraction.cc fraction.h Classes and Structures (A variation) 20 struct fraction { // type definition int c; int d; fraction(int cntr=0, int denom=1) : c(cntr), d(denom) {} fraction operator*(const fraction &b); fraction operator/(fraction b) { swap(b.c, b.d); return (*this)*b; } }; #include "fraction.h" #include "util.h" fraction::fraction operator*(const fraction &b) { fraction r; int f1=gcf(this->c,b.d), f2=gcf(b.c,this->d); r.c=(this->c/f1)*(b.c/f2); r.d=(this->d/f2)*(b.d/f1); return r; } Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies gcf & lcm main program main.cc #include #include #include #include #include <stdlib.h> <iostream> "fraction.h" "util.h" "vars.h" Hint: Include the system headers first and then your own ones. void main(int argc, char *argv[]) { int arg=atoi(argv[1]); cout << arg << "^2*pi=" << arg*arg*pi << endl; cout << "e=" << e << endl; cout << gcf(atoi(argv[1]), atoi(argv[2])) << endl; cout << lcm(atoi(argv[1]), atoi(argv[2])) << endl; … // making use of our fraction data type } 21 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Compilation and Dependencies Include all header files you need Compile each file Take care of the dependencies in the Makefile – If a header file changes the type or layout of a variable, function, or structure may have changed – Need to recompile every .cc file that includes these header files Generating the dependencies (with GNU g++) – Check out gcc’s various -M compile options – The GNU java compiler can do this also for Java files 22 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Makefile all: main Makefile main: main.o fraction.o util.o vars.o g++ -o main main.o fraction.o util.o vars.o main.o: main.cc fraction.h util.h vars.h g++ -c main.cc fraction.o: fraction.cc fraction.h util.h g++ -c fraction.cc util.o: util.cc util.h g++ -c util.cc vars.o: vars.cc vars.h g++ -c vars.cc 23 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Makefile main.cc fraction.cc main.o fraction.o fraction.h util.cc util.o main util.h vars.cc vars.h vars.o compile link Java does not have this step. It provides class loaders which are similar to the loader/dynamic linker. 24 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Tools to look into object files nm: list symbols in an object file or program – Defined, undefined, which section, etc. ldd, otool –L: list libraries needed by an object file 25 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Makefiles (made easy) Probably GNU make dependent CFLAGS=... CFLAGS+=-Wall -Wextra -Werror OBJS=main.o OBJS+=fraction.o ... # "main" file # others… all: main clean: rm -f main *.o distclean: clean rm -f .depend/*.d rm -f *~ 26 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Makefiles (cont’d) -include $(addprefix .depend/,$(OBJS:.o=.d)) %.o: %.c gcc $(CFLAGS) -c -o $@ $*.c @gcc -MM $(CFLAGS) -c $*.c >.depend/$*.d main: $(OBJS) ld $(LDFLAGS) -o $@ $(OBJS) 27 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Compilation & Execution *shell* [tom@yosemite ak3-01]$ make … [tom@yosemite ak3-01]$ ./main 91 49 91^2*pi=26015.556476 e=2.718281 7 637 … [tom@yosemite ak3-01]$ 28 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Agenda Separate Compilation – Variables – Routines – User-defined types (structures, classes) Standard Library 29 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies The Standard Library Basic Input & Output Strings Containers Iterators A good overview of the classes and its API can be found here: http://www.cppreference.com/ No significant program is written in just a bare programming language. Bjarne Stroustrup 30 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Basic Input & Output File streams <fstream> – ifstream, ofstream, fstream String streams <sstream> – istringstream, ostringstream, stringstream Functions – >>, get, getline, ignore, read, gcount – <<, write 31 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies In- & Output (cont‘d) int main(int argc, char *argv[]) { char first[256], mi, street[256]; string last, city; test.cc // read cout << cout << cout << a word terminated by whitespace "First Name? "; cin >> first; "Middle Initial? "; cin >> mi; "Last Name? "; cin >> last; // read a line terminated by newline cin.ignore(256,'\n'); cout << "Address? "; cin.get(street,256); cout << "City? "; getline(cin,city,'\n'); // suspect // ok // ok // ok // suspect // ok cout << "Hello, " << first << "!" << endl; cout << "I like " << city << "!" << endl; } 32 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Unix to DOS Converter unix2dos.cc #include <iostream> #include <fstream> int main(int argc, char *argv[]) { ifstream ifs(argv[1]); ofstream ofs(argv[2]); Ignores char c; whitespace for(;;) { ifs >> c; if(!ifs.good()) break; if(c=='\n') ofs << "\r\n"; else ofs << c; } } 33 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Unix to DOS Converter II todos2.cc #include <iostream> #include <fstream> int main(int argc, char *argv[]) { ifstream ifs(argv[1]); ofstream ofs(argv[2]); char c; for(;;) { ifs.get(c); if(!ifs.good()) break; if(c=='\n') ofs << "\r\n"; else ofs << c; } } 34 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies String Functions #include <string> … int main(int argc, char *argv[]) { string h("Hello"), w("World"), s; w.append("!"); cout << w[5] << w.at(5) << endl; w.insert(w.begin(), h.rbegin(), h.rend()); cout << w << endl; w.replace(4,2,"H W"); cout << w << endl; cout << "Enter your name: "; getline(cin, s); cout << h << " " << s << endl; return 0; } 35 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Container Provide different data structures Abstraction of a memory area User-defined allocators Can be accessed using iterators 36 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Containers (Overview) Sequence Containers – vector<T>, list<T>, deque<T> Associative Containers – map<K,V>, multimap<K,V> – set<K>, multiset<K> Sequence Container Adapters – stack<T,C> – queue<T,C>, priority_queue<T,C> 37 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Complexity Guarantees [] vector 38 Insert/Remove Elements Begin O(1) Iterator Middle End O(n)+ O(1)+ Ran O(1) Bi list O(1) O(1) forward_list O(1) O(1) O(1) O(n) For deque O(1) map O(log(n)) O(log(n))+ Bi unordered_map O(1)+ O(1)+ For string O(1) O(n)+ O(n)+ Th. Gschwind. Fortgeschrittene Programmierung in C++. O(1) O(n) Ran Ran © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies A Simple vector Example #include <iostream> #include <string> #include <vector> using namespace std; int main(int argc, char *argv[]) { vector<string> playlist; playlist.push_back("1. Have A Nice Day"); playlist.push_back("2. I Want To Be Loved"); playlist.push_back("3. Welcome To Wherever You Are"); playlist.push_back("4. Who Says You Can't Go Home"); playlist.push_back("5. Last Man Standing"); ... 39 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Iterators Define a sequence over the elements in a container vector: 40 T* #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 Iterator1: T *p Iterator2: { T* start; int pos; } Th. Gschwind. Fortgeschrittene Programmierung in C++. … #n © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies More on Iterators (cont‘d) List: lnk* Iterator3: #0 #1 #2 #3 #4 lnk lnk lnk lnk lnk … lnk *p Map: nd Iterator4: ndi p nd nd 41 nd nd nd Th. Gschwind. Fortgeschrittene Programmierung in C++. nd © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies More Java Trivia ... // store playlist in ArrayList playlist BufferedReader in=new BufferedReader(new InputStreamReader ListIterator i=playlist.listIterator(); String song="none"; for(;;) { System.out.println("playing "+song); String cmd=in.readLine(); if(cmd.equals("quit")) break; if(cmd.equals("next") && i.hasNext()) { song=(String)i.next(); } else if(cmd.equals("prev") && i.hasPrevious()) { song=(String)i.previous(); } else { System.out.println("unknown command "+cmd); } } } 42 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies More Java Trivia ... // store playlist in ArrayList playlist BufferedReader in=new BufferedReader(new InputStreamReader ListIterator i=playlist.listIterator(); Constantly going String song="none"; back and forth in the for(;;) { playlist will System.out.println("playing "+song); repeatedly play the String cmd=in.readLine(); same song if(cmd.equals("quit")) break; if(cmd.equals("next") && i.hasNext()) { song=(String)i.next(); } else if(cmd.equals("prev") && i.hasPrevious()) { song=(String)i.previous(); } else { System.out.println("unknown command "+cmd); } } } 43 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Iterators the C++ Way vector<string> playlist; ... // store playlist in ArrayList playlist vector<string>::iterator fst=playlist.begin(), cur=fst, lst=playlist.end(); string cmd; for(;;) { if(cur==lst) cout << "playing none" << endl; else cout << "playing " << *cur << endl; cin >> cmd; if(cmd=="quit") break; if(cmd=="next" && cur!=lst) ++cur; else if(cmd=="prev" && cur !=fst) --cur; else cout << "unknown command " << cmd << endl; } 44 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Different Types of Iterators Category output input Out In For Bi Ran Read =*p =*p =*p =*p Access -> -> -> -> [] *p= *p= *p= ++ ++ ++ -- == != == != == != Abbrev. Write *p= Iteration ++ Compare 45 birandomforward directional access Th. Gschwind. Fortgeschrittene Programmierung in C++. ++ -== != + < > += -= <= >= © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Iterators (Java vs. C++) Java C++ Iterator obtained using iterator(), a ListIterator using listIterator() Iterator returned through begin() and end() or rbegin() and rend() Iterator points between elements => current element cannot be accessed multiple times Iterator points to the element => current element can be returned multiple times Iterator knows about first and last position Iterator does not know about begin and end; second iterator is used for this purpose => flexibility as side effect; routine can iterate over any segment of the container => inflexible since routines cannot be easily changed to iterate over a part of the container If bounds are exceeded, an exception is raised 46 If bounds are exceeded, undefined behavior, probably a “segmentation violation” Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Iterators (Java vs. C++) C++ Iterator points to the elements (green) Repeatedly going forward and backward gives alternating elements vector: #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 … #n Java Iterator points between the elements (red) Repeatedly going forward and backward gives the same element 47 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Summary Separate Compilation – Variables – Routines (Functions & Operators) – Types (Structures, Classes) Standard Library 48 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Exercise 1 Which of these lines belong into the header file? Why? char ch; string s; extern int error_number; static double sq(double); int count=1; const double pi=3.2; // according to Indiana Pi Bill struct fraction { int c; int d; }; char *name="It's me"; char *prog[]={"echo","hello","world!",NULL}; extern "C" void c_swap(int *a, int *b); double sqrt(double); void swap(int &a, int &b) { int c=a; a=b; b=c; } namespace NS { int a; } struct user; 49 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Exercise 2 Separate compilation – Split the complex data type program into header file(s) and C++ file(s) – Write a Makefile and compile the above 50 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Exercise 3 Implement an RPN (Reverse Polish Notation Calculator) – – – – When the user enters ‘q’ the program terminates When the user enters ‘n’ followed by a number, it is put on the stack When the user enters ‘d’ the last number is removed from the stack When the user enters ‘+’, ‘-’, ‘*’, ‘/’, the calculator takes the last two numbers from the stack applies the operation to the numbers and puts the result on the stack – Use the std::vector container and its iterator! 51 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Exercise 3 – An Example (user input in bold) Command: 1: 2 2: 4 3: 3 Command: 1: 2 2: 12 Command: 1: -10 Command: 1: -5 Command: Command: 52 n 2 n 4 n 3 * n 2 / d q Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Exercise 4 Simple Spell Checker Implement a simple spell checker. The spell checker takes two files as command line arguments, a dictionary file containing a list of correctly spelled words and a file whose content is to be checked. Upon startup, your program stores the words contained in the dictionary file in a set<string>. Then it reads every word in the file to spell check, checks whether each word is correctly spelled (ie contained in the dictionary file) and if not displays it on cout. 53 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies correctly spelled words are stored in the dictionary a comprehensive dictionary is important. text.txt dict.txt Exercise 4 – An Example C:\> check dict.txt text.txt a comprehensive is important C:\> 54 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Business Integration Technologies Next Lecture C++ and Inheritance Have fun solving the examples! See you next week! 55 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation