SERVING THE QUANTITATIVE FINANCE COMMUNITY

  • 1
  • 2
  • 3
  • 4
  • 5
  • 10
 
User avatar
lballabio
Topic Author
Posts: 983
Joined: January 19th, 2004, 12:34 pm

C++ quiz --- generic programming

October 26th, 2005, 11:33 am

Your code base contains an average() function taking two parameters, namely, a vector of doubles and a number of items. The latter parameter is useful for averaging only the first n elements of the vector, as well as for the purposes of this quiz The current definition of the function is at the end of this post.Your mission, should you choose to accept it, is to generalize this function.1) The best way to generalize the function to different containers (std::vector, std::list...) and different underlying types (double, int, float...) is to use iterators. Write such a generic function. Extra points for using STL facilities instead of hand-written loops. 2) Just for this quiz, we will also choose an inferior approach and implement a semi-generic functiontemplate <class C> ??? average(const C& container, std::size_t n);where C is the container type passed to the function. We'll require that C defines operator[].Write the return type of the function (it should equal the type of the contained data) and the function itself. It should work for all STL containers providing operator[] (vector, deque) as well as built-in arrays. Also, it should be possible for a user to make it work with her own containers by writing a few lines of extra code but without modifying the function nor her container. Extra points for mentioning the name of the used technique.Luigi
 
User avatar
madmax
Posts: 1093
Joined: October 31st, 2003, 9:56 am

C++ quiz --- generic programming

October 26th, 2005, 8:43 pm

As someone noted before that I was always the first to see the quiz and solve it, I will try to keep quiet for little bit to let others try first.
 
User avatar
Cuchulainn
Posts: 59679
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ quiz --- generic programming

October 27th, 2005, 12:31 am

QuoteOriginally posted by: madmaxAs someone noted before that I was always the first to see the quiz and solve it, I will try to keep quiet for little bit to let others try first.Max,yes, you are a real star! Does Luigi send you the answers before us mere mortals ?
 
User avatar
ckarakus
Posts: 474
Joined: October 28th, 2004, 8:05 am

C++ quiz --- generic programming

October 27th, 2005, 6:29 am

This is for item#1 with handcoded facilitiestemplate<class InputIt>typename iterator_traits<InputIt>::value_type average1(InputIt beg, InputIt end, std::size_t n){ typedef typename iterator_traits<InputIt>::value_type value_type; value_type sum = 0.0; InputIt it = beg; for (std::size_t i = 0; i < n && it != end; ++it) { sum += *it; } return sum/n;}
Last edited by ckarakus on October 26th, 2005, 10:00 pm, edited 1 time in total.
 
User avatar
ckarakus
Posts: 474
Joined: October 28th, 2004, 8:05 am

C++ quiz --- generic programming

October 27th, 2005, 7:05 am

this for item#1 which uses STL facilities somehow.template <typename ValueType>class BoundedSummer : std::unary_function<ValueType, void>{ ValueType sum_; std::size_t count_; const std::size_t bound_;public: BoundedSummer(int bound) : sum_(0.0), count_(0), bound_(bound) { } void operator()(ValueType v) { if (count_ < bound_) { sum_ += v; count_++; } } ValueType sum() const { return sum_; } std::size_t count() const { return count_; }};template<class InputIt>typename iterator_traits<InputIt>::value_type average2(InputIt beg, InputIt end, std::size_t n){ typedef typename iterator_traits<InputIt>::value_type value_type; typedef BoundedSummer<value_type> BoundedSummerType; BoundedSummerType sum = for_each(beg, end, BoundedSummerType(n) ); return sum.sum()/sum.count();}
Last edited by ckarakus on October 26th, 2005, 10:00 pm, edited 1 time in total.
 
User avatar
lballabio
Topic Author
Posts: 983
Joined: January 19th, 2004, 12:34 pm

C++ quiz --- generic programming

October 27th, 2005, 7:21 am

Ckarakus,I knew you were good.Almost correct, but there's a glitch in your solution and one in my question (note: I'm referring to your first solution, as I wrote the rest of this post before you contributed your second one.)The glitch in my question is that I didn't specify the interface of the iterator-taking function. There were three alternatives.The first is your solution, taking two iterators and n.The second isaverage(InputIt begin, std::size_t n);since we can just start from begin and increment n times, leaving it to client code to enforce bound-checking.The third isaverage(InputIn begin, InputIt end);since one can limit the average to n elements by writing, e.g.,std::vector<double> v(...);average(v.begin(), v.begin()+n);I admit that the third was what I had in mind (and was the one that could be written using STL functions, namely,average(begin, end) <-> std::accumulate(begin,end,value_type())/std:istance(begin,end)sorry to have put you on a wrong track.) but on second thought it has serious drawbacks. One is that the above can be done with lists, as in std::list<double> l(...);average(l.begin(), std::advance(l.begin(), n));but it is not efficient, as one would traverse the list twice (one inside std::advance and one while collecting the values.) The same applies to accumulate & distance; and for the same reason, one would need at least forward iterators as input iterators might not be read twice.The glitch in your solution is the check for i != end. On the one hand, it is good to check that we don't dereference an off-the-end iterator as it would cause undefined behavior. But on the other hand, if the iterator reach the end your code just ends the loop silently, which gives the client code a result but no hint that anything went wrong. For instance, vector<double> v(2);v[0] = 1;v[1] = 5;double x = average(v.begin(),v.end(),3);returns (1+5)/3 = 2. It might be better to raise an exception if it == end.The solution is otherwise correct---and with the added touch of using iterator_traits so that it works with built-in arrays as well.Luigi
 
User avatar
ckarakus
Posts: 474
Joined: October 28th, 2004, 8:05 am

C++ quiz --- generic programming

October 27th, 2005, 7:30 am

Thanks for compliments.Well, I did not really think about whether the interface makes sense or not since this is an exercise.Of course, when you write actual code you should try hard to make interface "easy to use without mistakes"
 
User avatar
ckarakus
Posts: 474
Joined: October 28th, 2004, 8:05 am

C++ quiz --- generic programming

October 27th, 2005, 8:08 am

this is for item#2. Name of technique?: traits perhaps.// this is just an example of what can be a non-standard containerclass CustomVector : public std::vector<double>{public: typedef double custom_value_type;};template <class ContType>struct container_traits{ typedef typename iterator_traits<typename ContType::iterator>::value_type value_type; };//for built-in arraytemplate <typename T>struct container_traits<T*>{ typedef T value_type; };//for custom containertemplate <>struct container_traits <CustomVector>{ typedef CustomVector::custom_value_type value_type; };template <class ContType> typename container_traits<ContType>::value_type average3(const ContType& container, std::size_t n){ typedef typename container_traits<ContType>::value_type value_type; value_type sum = 0.0; for (std::size_t i = 0;i<n ; i++) { sum += container [ i ]; } return sum/n;}//********************************************** test code ******************************************************void test_avarege3(){ using namespace std; vector<double> vnums; deque<double> dnums; double anums[] = {1.0, 2.0,3.0,4.0,5.0,6,7.0,8.0,9.0,10.0}; CustomVector cusnums; double avg; for (int i=1;i<=10 ;i++ ) { vnums.push_back( i * 2.0); dnums.push_back( i * 4.0); cusnums.push_back( i * 2.0); } cout << "avg3 vector = " << average3 (vnums, vnums.size()) << endl; cout << "avg3 list = " << average3 (dnums, dnums.size()) << endl; cout << "avg3 array = " << average3 (&anums[0], sizeof(anums)/sizeof(anums[0]) ) << endl; cout << "avg3 custom vector = " << average3 (cusnums, cusnums.size()) << endl;}
Last edited by ckarakus on October 26th, 2005, 10:00 pm, edited 1 time in total.
 
User avatar
lballabio
Topic Author
Posts: 983
Joined: January 19th, 2004, 12:34 pm

C++ quiz --- generic programming

October 27th, 2005, 8:34 am

We have a winner! Traits it is.
 
User avatar
ckarakus
Posts: 474
Joined: October 28th, 2004, 8:05 am

C++ quiz --- generic programming

October 27th, 2005, 8:48 am

looking forward to another quiz
 
User avatar
Cuchulainn
Posts: 59679
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ quiz --- generic programming

October 27th, 2005, 1:15 pm

// this is just an example of what can be a non-standard containerclass CustomVector : public std::vector<double>I thought this is life-threatening??? virtual destrcutors and all that?? memory leaks.I use Compositionclass Vector{private: vector<double> v; double** matrix;};
Last edited by Cuchulainn on October 26th, 2005, 10:00 pm, edited 1 time in total.
 
User avatar
lballabio
Topic Author
Posts: 983
Joined: January 19th, 2004, 12:34 pm

C++ quiz --- generic programming

October 27th, 2005, 1:39 pm

QuoteOriginally posted by: Cuchulainn// this is just an example of what can be a non-standard containerclass CustomVector : public std::vector<double>I thought this is life-threatening??? virtual destrcutors and all that?? memory leaks.I use CompositionSo do I, but this was just an example, and it was quicker than writing a number of delegating methods such asdouble CustomVector::operator[](std::size_t j) { return vector_[j]; }const_iterator CustomVector::begin() { return vector_.begin(); }etc. etc.Besides, the undefined behavior is only triggered if one does something unlikely likevector<double>* p = new CustomVector;...delete p;i.e., delete a derived class instance through a pointer to base class. The use of CustomVector in the test code was safe.Good point to raise anyway, since these quizzes should be educational...
Last edited by lballabio on October 26th, 2005, 10:00 pm, edited 1 time in total.
 
User avatar
ckarakus
Posts: 474
Joined: October 28th, 2004, 8:05 am

C++ quiz --- generic programming

October 27th, 2005, 2:44 pm

QuoteOriginally posted by: Cuchulainn// this is just an example of what can be a non-standard containerclass CustomVector : public std::vector<double>I thought this is life-threatening??? virtual destrcutors and all that?? memory leaks.I use Compositionclass Vector{private: vector<double> v; double** matrix;};you are right. Most of STL containers are not designed to be inherited(in a is-a sense) because they do not have virtual destructors.As lballabio pointed out, it was the dirty solution.
 
User avatar
Cuchulainn
Posts: 59679
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

C++ quiz --- generic programming

March 19th, 2010, 9:19 am

quiz. let's say you want to create a Calendar (or Currency) class and its specialisations in C++ and C#1. Use classic inheritance (derrived 'tiny' classes are objects, really)2. Use generic traits classes for the extra structural 'bagage'3. Use static member functionsBest one in terms of functionality, efficiency, maintainability and reliability?? //When does an object become a class? Is "Manhattan project' an instance of a class or can we model it as a class? why do we sometimes get classes with little functionality?
Last edited by Cuchulainn on March 18th, 2010, 11:00 pm, edited 1 time in total.
 
User avatar
untwigged
Posts: 262
Joined: January 14th, 2006, 3:21 pm

C++ quiz --- generic programming

March 19th, 2010, 12:14 pm

QuoteOriginally posted by: CuchulainnBest one in terms of functionality, efficiency, maintainability and reliability?? I think the key requirement is maintainability. Do you want to recompile all your binaries when the Queen passes on and there's now an extra public holiday? Or when you start trading some new currency? I often see way too many lightweight 'classes' that in my opinion should be generic objects, backed by a database or whatever.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On