Effective Analysis Programming Part 1

From Gridkaschool

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

Technical aspects for the course

Gridka School slides

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

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;
 }

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