Effective Analysis Programming Part 1
From Gridkaschool
Jump to navigationJump to search
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/
Standard Template Library
string
excercise 1
vector
excercise 1: 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.
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).