Effective Analysis Programming Part 1
Gridka School 2013 C++ course
- Martin Heck, KIT EKP
- Jörg Meyer, KIT SCC
- Christoph-Erdmann Pfeiler, KIT SCC
Literature on C++
books
- The C++ Programming Language, Bjarne Stroustrup
- Effective C++, Scott Meyers
- More Effective C++: 35 New Ways to Improve Your Programs and Designs
- Modern C++ Design, Andrei Alexandrescu
- The C++ Standard Library, Nicolai M. Josuttis
- C++ Templates, David Vanevoorde, Nicolai M. Josuttis
- Exceptional C++, Herb Sutter
- More Exceptional C++, Herb Sutter
links
- http://www.stroustrup.com/bs_faq2.html
- http://www.cplusplus.com/reference/
- http://www.parashift.com/c++-faq/
- http://herbsutter.com/gotw/
Technical aspects for the course
Gridka School slides
- Introduction: 1EffectiveAnalysisProgramming.pdf
- Best practise: 2BestPracticeRules.pdf
- STL: GKS2013EffectiveAnalysisSTL.pdf
access to machines
You can run the exercises either on your own computer or ssh to one of our prepared machines using your Gridka School account.
- connection from Linux/Unix: ssh -p24 <username>@gks-<xxx>.scc.kit.edu
- connection from Windows: use an ssh client like putty, or use cygwin
This is a list of hostnames:
gks-175
gks-176
gks-177
gks-178
gks-179
gks-180
gks-181
gks-182
gks-183
gks-184
Run the following command in order to enable gcc 4.7:
$ source .setup_gcc47.sh
or
$ scl enable devtoolset-1.1 bash
Check version of gcc:
$ gcc --version gcc (GCC) 4.7.2 20121015 (Red Hat 4.7.2-5)
download
- Code examples from best practise rules: http://www-ekp.physik.uni-karlsruhe.de/~heck/GridKa13/
- Code for hands-on exercises:
Download this tarball: Gks2013cpp.tar.gz
wget http://wiki.scc.kit.edu/gridkaschool/upload/a/ac/Gks2013cpp.tar.gz tar xvfz Gks2013cpp.tar.gz
compilaton and execution of code
Most examples consist of just one cpp file, i.e. no header file, no additional library. Use the following commands to compile and run the code:
g++ mycode.cpp ./a.out
For C++11 support do:
g++ -std=c++11 mycode.cpp ./a.out
In order to link boost libraries (e.g. for regular expressions) do:
g++ -lboost_regex mycode.cpp
For more complex examples a Makefile is provided, i.e. just enter:
gmake
Standard Template Library
string
exercise 1: zfill
#include<string>
#include<iostream>
using namespace std;
string zfill(int i,unsigned length) {
string s=to_string(i); //c++11
unsigned l=s.length();
return l<length ? string(length-l,'0')+s : s;
}
int main() {
for (int i=0;i!=101;++i) cout<<zfill(i,3)<<'\n';
return 0;
}
- What is zfill() good for? How does it work?
excercise 2: sorting
#include<string>
#include<iostream>
#include<vector>
#include<algorithm> //std::sort
#include<cctype> //std::tolower
using namespace std;
void print(vector<string> const& v) {
for (vector<string>::const_iterator it=v.begin(); it!=v.end(); ++it) {
cout<<*it<<"\n";
}
}
bool compare_nocase (string s1, string s2) {
unsigned int i=0;
while ( (i<s1.length()) && (i<s2.length()) ) {
if (tolower(s1[i])<tolower(s2[i])) return true;
else if (tolower(s1[i])>tolower(s2[i])) return false;
++i;
}
return s1.length()<s2.length();
}
bool compare_length(string s1, string s2) {
return s1.length()<s2.length();
}
int main() {
vector<string> v;
v.push_back("Hamburg");
v.push_back("Aachen");
v.push_back("Karlsruhe");
v.push_back("Berlin");
v.push_back("BER");
v.push_back("BERLIN");
vector<string> v1(v);
sort(v1.begin(),v1.end());
print(v1);
cout<<endl;
v1=v;
sort(v1.begin(),v1.end(),compare_length);
print(v1);
cout<<endl;
v1=v;
sort(v1.begin(),v1.end(),compare_nocase);
print(v1);
return 0;
}
- What is the output of this code?
vector and list
excercise 1: vector size and capacity
#include<iostream>
#include<vector>
using namespace std;
void info(vector<double> const& v) {
cout<<"size: "<<v.size()<<endl;
cout<<"capacity: "<<v.capacity()<<endl;
}
int main() {
vector<double> v0;
info(v0);
vector<double> v1(100);
info(v1);
v0.push_back(42.);
v1.push_back(42.);
info(v0);
info(v1);
return 0;
}
- Run this code and see how size and capacity change. Results for capacity depend on the implementation of vector, i.e. are not standardized.
excercise 2: vector vs. list part 1
#include<iostream>
#include<vector>
#include<list>
using namespace std;
template <typename container>
void tripple(container& c) {
for (typename container::iterator it=c.begin();it!=c.end();++it) {
*it *= 3;
}
}
int main() {
long size=1e8;
cout<<"vector<int> v("<<size<<",7);"<<endl;
vector<int> v(size,7);
cout<<"list<int> l("<<size<<",7);"<<endl;
list<int> l(size,7);
cout<<"tripple(v) ";
tripple(v);
cout<<"done\ntripple(l) ";
tripple(l);
cout<<"done"<<endl;
cout<<v.front()<<endl;
cout<<l.front()<<endl;
return 0;
}
- Which container do you expect to perform better in this scenario? Profile the code with gprof to check.
Remark: tripple is a template function that works for any class that provides iterators and the multiplication operator for its value_type to multiply with an integer.
excercise 3: vector vs. list part 2
#include<iostream>
#include<vector>
#include<list>
using namespace std;
template <typename container>
inline void erase_first(container& c) {
c.erase(c.begin(),++c.begin());
}
void erase_vector(vector<int>& v) {
while(v.begin()!=v.end()) erase_first(v);
}
void erase_list(list<int>& l) {
while(l.begin()!=l.end()) erase_first(l);
}
int main() {
long size=1e5;
cout<<"vector<int> v("<<size<<",7);"<<endl;
vector<int> v(size,7);
cout<<"list<int> l("<<size<<",7);"<<endl;
list<int> l(size,7);
cout<<"erase_vector(v) ";
erase_vector(v);
cout<<"done\nerase_list(l) ";
erase_list(l);
cout<<"done"<<endl;
}
- Which container do you expect to perform better in this scenario? Profile the code with gprof to check.
map
exercise 1: insert
#include <map>
#include <iostream>
using std::map;
using std::cout;
using std::endl;
struct A {
A(): _p(0) {
cout<<"A::A()"<<endl;
}
A(int p): _p(p) {
cout<<"A::A(int p)"<<endl;
}
A& operator=(A const& other) {
_p=other._p;
cout<<"A& A::operator=A const& other)"<<endl;
return *this;
}
int _p;
};
int main() {
map<int,A> m;
m[1]=A(42);
m.insert(std::make_pair(4,A(11)));
for(std::pair<int,A> p: m) {
cout<<"m["<<p.first<<"]: "<<p.second._p<<'\n';
}
return 0;
}
- What is the output of this code, i.e. which constructors get called?
- What is the advantage of insert?
exercise 2: user-defind comparison
#include <map>
#include <iostream>
#include <complex>
#include <cmath>
using std::map;
using std::cout;
using std::endl;
using std::complex;
namespace gks {
struct complex_compare {
bool operator()(complex<double> const& a, complex<double> const& b) {
return std::real(a)!=std::real(b) ? std::real(a)<std::real(b) : std::imag(a)<std::imag(b);
}
};
/*
exponential of complex number; caches results in map
*/
complex<double> exp(complex<double> const& x) {
static map<complex<double>,complex<double>,complex_compare> cache;
map<complex<double>,complex<double>,complex_compare>::iterator it=cache.find(x);
return it==cache.end() ? cache[x]=std::exp(x) : it->second;
}
}
int main() {
complex<double> z1 = gks::exp(complex<double>(0.,1.));
complex<double> z2 = gks::exp(complex<double>(1.,1.));
complex<double> z3 = gks::exp(complex<double>(0.,1.));
complex<double> z4 = gks::exp(complex<double>(0.,-1.));
cout<<z1<<endl;
cout<<z2<<endl;
cout<<z3<<endl;
cout<<z4<<endl;
return 0;
}
- Familiarize yourself with the class std::complex representing complex numbers (http://www.cplusplus.com/reference/complex/)
- Why is the std::map cache static?
- What is returned by map::find? See http://www.cplusplus.com/reference/map/map/find/
- What is the size of the map cache at the end of the programm?
Complex numbers do not fulfill any order relation. That's why the less-than operator is not defined for std::complex. Thus, complex numbers are not suitable as a key for a std::map. However, it is possible to define a user-defined comparison functor and pass it as third template argument to a std::map.
- What is a functor?
- The comparison of complex numbers defined in the class complex_compare does not fulfill the criteria of a order relation. Why? (optional math question)
- There is a problem with the implementation of complex_compare::operator(). Can you find it?
C++11 remarks:
With C++11 it is possible to implement helper classes like complex_compare inside the functions, where they are being used:
complex<double> exp(complex<double> const& x) {
struct complex_compare {
bool operator()(complex<double> const& a, complex<double> const& b) {
return std::real(a)!=std::real(b) ? std::real(a)<std::real(b) : std::imag(a)<std::imag(b);
}
};
static map<complex<double>,complex<double>,complex_compare> cache;
map<complex<double>,complex<double>,complex_compare>::iterator it=cache.find(x);
return it==cache.end() ? cache[x]=std::exp(x) : it->second;
}
- What is the advantage of locally defined functors?
- How could pass the comparison as lambda expression to the std::map? (optional, C++11 only)
exercise 3: unordered_map
- Reimplement the code from excercise 2 using an std::unordered_map (C++11).
Evaluation
If you liked the course please fill this evaluation form: http://surveys.gridka.de/limesurvey/index.php?sid=36984&lang=en