Difference between revisions of "Effective Analysis Programming Part 1"
m (→exercise 2: user-defind comparison) |
m (→string) |
||
Line 18: | Line 18: | ||
===string=== |
===string=== |
||
====excercise 1==== |
====excercise 1==== |
||
+ | #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(); |
||
+ | } |
||
+ | |||
+ | // explicit cast needed to resolve ambiguity |
||
+ | // std::transform(myString.begin(), myString.end(), myString.begin(), |
||
+ | // (int(*)(int)) std::tolower); |
||
+ | |||
+ | |||
+ | |||
+ | 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; |
||
+ | } |
||
+ | |||
===vector=== |
===vector=== |
||
====excercise 1: size and capacity==== |
====excercise 1: size and capacity==== |
Revision as of 13:05, 19 August 2013
Contents
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
- 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();
}
// explicit cast needed to resolve ambiguity
// std::transform(myString.begin(), myString.end(), myString.begin(), // (int(*)(int)) std::tolower);
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;
}
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).