Effective Analysis Programming Part 1

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/

access to machines

You 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>@<hostname>
• connection from Windows: use an ssh client like putty, or use cygwin

This is a list of hostnames:

• tba

Run the following command in order to enable gcc 4.7:

$ scl enable devtoolset-1.1 bash

Check version of gcc:

$ gcc --version 
gcc (GCC) 4.7.2 20121015 (Red Hat 4.7.2-5)

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).