Effective Analysis Programming Part 1

From Gridkaschool
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

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).
Retrieved from "https://wiki.scc.kit.edu/gridkaschool/index.php?title=Effective_Analysis_Programming_Part_1&oldid=1112"