Search | Blog | Contact

C++ Algorithms, Boost and function currying 49

Posted by Brett Schuchert Sun, 13 Jun 2010 04:41:00 GMT

I’ve been experimenting with C++ using the Eclipse CDT and gcc 4.4. Since I’m a fan of boost, I’ve been using that as well. I finally got into I realistic use of boost::bind.

I converted this: 
int Dice::total() const {
  int total = 0;

  for(const_iterator current = dice.begin();
      current != dice.end();
      ++current)
    total += (*current)->faceValue();

  return total;
}
Into this: 
int Dice::total() const {
  return std::accumulate(
      dice.begin(),
      dice.end(),
      0,
      bind(std::plus<int>(), _1, bind(&Die::faceValue, _2))
  );
}

To see how to go from the first version to the final version with lots of steps in between: http://schuchert.wikispaces.com/cpptraining.SummingAVector.

This is a first draft. I’ll be cleaning it up over the next few days. If you see typos, or if anything is not clear from the code, please let me know where. Also, if my interpretation of what boost is doing under the covers (there’s not much of that) is wrong, please correct me.

Thanks!

Comments

Leave a response

  1. Avatar
    Brian Ramsay about 6 hours later:

    Are there any advantages to the second method other than experimenting with bind? The first is definitely much easier to read.

  2. Avatar
    Derek Greer about 8 hours later:

    I agree, the first way is pretty clear while the second has a lot of cognitive load.

  3. Avatar
    Oleg about 13 hours later:

    boost::bind, boost::functional and a couple of other libraries are pretty much dead with the new c++0x features. We will write this instead:

    int sum=0; for (Dice &d: dice) sum+=d.faceValue();

    and that’s a good thing.

    Currying with ‘bind(std::plus(), _1, bind(&Die::faceValue, _2))’ is using the C++ compiler as a masturbatory toy, because you can’t have the real thing…

  4. Avatar
    Wouter Lammers about 13 hours later:

    I thought people already practiced this modern c++ for years now..

    Why even use boost? If I am not mistaken gcc 4.4 already has bind and function in the std namespace (or tr1 perhaps). And I would argue to skip the bind/function stuff in favour of lambdas straight away but I guess you’ll have to use gcc 4.5 for that. The fact that type inference also works on lambdas and that lambdas are convertible to std::function makes bind almost redundant.

    I don’t really agree with the cognitive load remark although I do understand where it is coming from. It is only an extra cognitive load because people keep thinking in loops. The functional approach is actually easier in my opinion. After using it for a while it became second nature for me and the ‘old’ way actually adds cognitive overhead. A for loop does not tell me what it is doing while accumulate is more descriptive.

    I do agree the syntax is a bit verbose and difficult which is a threshold for beginners, but I think/hope lambda expressions will help with that.

    Something like:

    int Dice::total() const {
  return accumulate( 
     d.begin(), 
     d.end(), 
     0, 
     []( int acc, const Dice& d ) { return acc + d.faceValue(); }
  );
}

    Just my 2 cents.

  5. Avatar
    Wouter Lammers about 13 hours later:

    :) Oleg’s proposal is probably the best, is there already a compiler around that implements the range-based for?

    Nevertheless I think lambdas (and bind to a lesser extent) are very useful for the more complicated standard algorithms like sort or transform and for implementing delegates/closures. (Think of std::thread or have a look at microsofts ppl)

  6. Avatar
    ALynch about 18 hours later:

    return sum([die.faceValue() for die in dies])

    : python

  7. Avatar
    Brett Schuchert about 19 hours later:

    So lots of good information.

    0. I went back and remove all use of boost::bind and boost::shared_ptr for the std and std::tr1 versions. Wasn’t too much of a hassle.

    1. If I’m working on a product and I can fully select my tools, then I’d use gcc 4.5 and lambdas, for sure. If not, then boost or tr1 gives me something better than not having it.

    2. The std::tr1::bind seems to have problems with r-values on the second example. For example, given a functor created with boost’s bind, I can write: 
      functor(10);
    However, this won’t work on the functor produced by std::tr1::bind, so I have to instead write: 
      int ten = 10;
  functor(ten);

    This is not a big deal in practice where I’m passing in the result of calling bind into an algorithm. Just an observation.

    3. I like both of the suggestions by Oleg & Wouter. As for which I prefer, the use of accumulate or the new for syntax, not sure. I’m leaning to the new for syntax.

    4. Are people using modern C+? In my experience it’s like 1/7 companies. Most companies using C+ are stuck in legacy hell and not too worried about modern C++. Remember, however, I’m a consultant. I still see a lot of people using Java 1.4 or C# 2.0.

    5. I think Brian and derek bring up a good point on the difficulty of reading that second version. So given the 4 options:
    • The orignal for
    • The nested bind
    • The lambda
    • The new for syntax

    I’d say the nested bind is probably the worst. Even taking into consideration the point about functional programming (I’m sure lispers would have no problem with the nested bind), it’s just backwards and strange.

  8. Avatar
    Brett Schuchert about 19 hours later:

    Check out this article a friend pointed out to me regarding these examples. It mirrors Brian and Derek’s points. http://sheddingbikes.com/posts/1276445247.html

  9. Avatar
    Brett Schuchert about 19 hours later:

    I was unable to post a comment regarding his post. However, his comment about the subtle error was wrong in my case (not in general). Here’s what I sent to Zed:

    The subtle error you have, missing the _ on the 1, is easily captured by having effective unit tests, which I do have. In fact, given my unit tests, I’m certain I’d find it. How do I know? I made that erroneous change and I had a failing unit test – so no thought experiment, I know with certainty that your subtle error isn’t so subtle at all.

    Even so, while I did find that the code was broken, I think it would be hard to find. So on the one hand, I know it happened. On the other hand, it would be difficult to find. So I guess I’m half agreeing on that point.

    You’ll notice on the blog that your point was made by the first 2 posters. Why not post there, at least a link to article. (I took the liberty of doing that.)

    If you keep following the blog, you’ll notice I agree with you that the nested bind is ugly. There are 2 other options proposed by other posters, both of which I prefer over the nested bind.

    Brett

  10. Avatar
    Wouter Lammers 1 day later:

    @2: Like always, the implementation of c++ stdlibs take a while to catch up with the standard :) I also found some bugs in vs2010beta when using bind. Microsofts stl dev (whose name is stl :) ) replied that I should just use lambdas :)

    @4: Unfortunately you’re right.. My remark was more wishful thinking than a real expectation.. Even worse, most companies I’ve worked for that claimed to use C++ actually just compile C code in the C++ compiler..

    Still, I do not completely agree with Brian/Derek/Zed. I fully agree with their practical argument: if it confuses people then it is wrong, and something is not better just for the sake that it is new.

    Having said that I think it is also obvious that ‘conventional’ programming could use some improvements. There’s a reason why some vendors have deprecated printf, why some shops do not allow use of strcpy/memcpy, why in modern c++ we almost never write ‘delete’ anymore. Each of these have safer equivalents, without losing significant performance. They are not perfect though, but I think the improved safety/robustness outweighs the drawbacks. (For instance: some people still prefer printf over ‘cout << ..’ because it ‘looks’ easier) Disclaimer: it all depends on your specific product/target platform of course.

    The fact that functional languages are gaining some popularity lately (Scala, clojure, F#), that bind/function/lambda will be in C+0x, that C# also has delegates/lambdas, that even java 7 will include closures (or not? not sure on status quo here) tells me that the community needs/likes these functional paradigms. The word is that it facilitates safer multi-threaded programming, but imo that is just the side effect of more robust coding. It is just hard for us C++/Java guys to unlearn our set ways. :)

    Just my 2c, not trying to step on anyone’s toes or anything.

    (When someone claims a very unobvious thing how do you determine he’s either wrong/crazy or ‘returning to the cave’?)

  11. Avatar
    simpleman 1 day later:

    I can’t believe it’s 2010 and people are still researching and arguing about how to sum a vector.

  12. Avatar
    John 1 day later:

    This is why nobody wants to learn C++. It’s trying to show off some very basic FP concepts, but floundering about in magical templating syntax that nobody who is already familiar with FP would recognize. Compare that to Ruby or Clojure:

    dice.reduce { |sum, die| sum + die.face_value }

    or

    (apply + (map :faceValue dice))

    Even if you don’t know those languages, you can kind of get what’s going on. Compare that to the rather heavy dose of magic that the C++ version depends on.

    C++ obviously doesn’t want to get left off of the FP bandwagon, but this kind of example just makes it look like the fat smelly kid that thinks he’s super special and always wants to show you his YuGiOh cards… nobody wants to sit with that kid.

  13. Avatar
    L. 1 day later:

    I don’t know if you’re supposed to include boost::lambda to do this, but I know that boost placeholders (_1, _2 and _3) will “eat up” almost any operator applied to them, and return a functor accordingly. Therefore, I think you can rewrite your functor like:

    _1 + bind(&Die::faceValue, _2)

    I did not try this out, as I have no C++ environment available here. But I know boost can do it THIS elegantly. (And I think boost::bind and boost::lambda are part of the TR1 libraries that will be included in C+1x, C+ next promised standard, so bind, _1 et al. will soon be part of the std namespace)

    About the accuracy of the article, I would actually rewrite “which is a reference the the first parameter” into “which is a functor that returns the second parameter passed to its operator()”.

  14. Avatar
    Tintenpatronen 1 day later:

    I’m using the first method frequently and I have made very good experiences with this way. So if you search for an easy way to do it, I give you the advise to use the first methode.

  15. Avatar
    Adriano 1 day later:

    Where does &Die without the ‘c’ come from, in the last line of your second example?

  16. Avatar
    Brett Schuchert 1 day later:
    L wrote:
    herefore, I think you can rewrite your functor like: 
    _1 + bind(&Die::faceValue, _2)
    That would be great! Looks like both boost and tr1 only define the logical operators. I tried adding something like this: 
    template<typename RT, typename L, typename R> RT operator+(L &l, R &r) {
  return bind(std::plus<int>(), l, r);
}
    I’m a bit rusty on writing templates, so while this compiled, it did not match the bind example above. Maybe someone with better template writing skills can get it to work!-)
  17. Avatar
    Brett Schuchert 1 day later:

    Adriano,

    &Die::faceValue takes the address of a member function. That’s how you get a pointer to a member function. No object required.

  18. Avatar
    Adriano 1 day later:

    I meant that the spelling is Dice above, and Die at the end. Is it a typo, or does it C++ actually inflect?

  19. Avatar
    Die Boost Die 1 day later:

    Adriano Die is singular, dice is plural., they are two different classes. Brett I am glad you now find your refactored code and abomination.

  20. Avatar
    Brett Schuchert 1 day later:

    Andriano,

    Die Boost Die got it correct. The Dice class is a simply wrapper class that holds a number of die objects (2 in my example).

    As for “Die Boost Die”’s choice of name, if it weren’t for boost, what would have been the result of tr1, C+0x? Many things from the header-only stuff in boost has found its way into the C+ standard, right?

    There are many other things in the boost library that make C++ more usable. Dates, for example.

    So I don’t agree with the general sentiment suggested to me by the name “die boost die”, but I do understand where s/he is coming from.

  21. Avatar
    Ben 1 day later:

    Sounds like most people have not read Meyers’ “Effective STL”. He presents several reasons why the latter approach should be preferred.

    But at the end of the day, it’s all about readability. If you are the only one in the company that can understand it, then it’s best to do what everyone knows, and start getting your colleagues up to speed in a venue other than your code base.

  22. Avatar
    Mark 1 day later:

    http://en.wikipedia.org/wiki/Essential_complexity

    The implementation using bind() doesn’t provide any additional benefit of the initial implementation but does result in less clear code.

    Unless there’s a non-straightforward benefit (in which case it should be documented via at least a code comment), the use of boost in this example is making for worse code.

    If you were going to bind the function and then pass it somewhere (and not know how it was going to be used) that would be a different story.

    -Mark

  23. Avatar
    Jason Y 1 day later:

    Man…... I thought I was cutting-edge for reading generic programming books when I was in college (mid-2000’s). I need to catch up!

  24. Avatar
    p90x workout 1 day later:

    P90X is a working out system includs P90X workout and Insanity DVD which belong to P90X fitness program.

  25. Avatar
    Tim Smith 3 days later:

    When Scott first wrote about why hand written loops are evil compared to the new style of doing things, he made three important points. Sadly, he made three huge mistakes.

    1) He said it was easier to write correct code. He took a simple handle written loop that was incorrect and make multiple attempts at making a new style loop. Sadly, it would have taken one step to correct the hand written loop.

    2) He said it was easier to write correct code (part 2). In his newly created “correct” routine, he incorrectly used as part of the code to select the proper template. Sadly, his input data was doubles. What would have been a trivial bug to catch in unit tests now becomes a more subtle bug to catch. (For example, inputs of 1,2,3 wouldn’t catch Steve’s bug, but 1.4,2.8,3.9 would have)

    3) He said that the new fancy code ran just as fast. Sadly, it did not. Due to the complexity of the template code, the optimizer failed to place a temporary in a register thus resulting in the routine using stack space. The new fancy version ran THREE TIMES SLOWER than the hand written loop. (template optimizers have improved a lot since then)

  26. Avatar
    Steve 6 days later:

    The usage of iterators in the second version shows that the author of this post doesn’t understand the concepts of abstraction and of functional programming very well.

  27. Avatar
    Peach 12 days later:

    I also prefer the first version. I is an easy, clear code that works properly. I don’t think that the second has a lot of advantages, in my opiniton the amenity of the first one ist clear and so I would choose this one.

  28. Avatar
    galbur 15 days later:

    the use of boost in this example is making for worse code.

  29. Avatar
    cell phone headset 16 days later:

    Nice one. I have stumbled and twittered this for my friends. Hope others find it as interesting as I did.

  30. Avatar
    pump shoes 16 days later:

    It seems that you have set many work in to your article and We require more of

    those about the net presently. I truly got a drag out of one’s article. We do not

    actually possess a lot in order to communicate reacting, I just wished to comment

    in order to respond incredible perform

  31. Avatar
    r9 irons 16 days later:

    The noblest search is the search for excellence

  32. Avatar
    Birkenstock 19 days later:

    thanks for your sharing, very good news.

  33. Avatar
    http://www.laviesolar.com 23 days later:

    Great web site. Than you for the information

  34. Avatar
    Olivea Copper 25 days later:

    Through my 27 years of infinite wisdom (my parents always said I was a smart-ass), I’ve learned a few things. Women, yea I consider myself an expert in the female area if you know what I mean (wink) – and the most important thing I’ve learned is to stay away from a woman on her PMS days. In fact, I’ve put together a few acronyms (abbreviations) based on my experience with the syndrome.

  35. Avatar
    human 29 days later:

    I do agree the syntax is a bit verbose and difficult which is a threshold for beginners, but I think/hope lambda expressions will help with that.

  36. Avatar
    garments about 1 month later:

    clothing

  37. Avatar
    Halter about 1 month later:

    Sunshine of summer, the beautiful flower asperses full whole body, sweet and elegant breath, the circulation of the spread of elegant silk dress eyes from the waves to linger flying skirt . A gentle and graceful elasticity waist foil, more show delicate temperament of your daughter beauties.

  38. Avatar
    lady dress about 1 month later:

    Wholesale clothing,fashion dress,lady dress,lady garment,lady fashion

  39. Avatar
    cosplay about 1 month later:

    The noblest search is the search for excellence

  40. Avatar
    Mission Hills Real Estate 2 months later:

    I made that erroneous change and I had a failing unit test – so no thought experiment, I know with certainty that your subtle error isn’t so subtle at all…...............

  41. Avatar
    Leucadia Real Estate 2 months later:

    I made that erroneous change and I had a failing unit test – so no thought experiment, I know with certainty that your subtle error isn’t so subtle at all……............

  42. Avatar
    supplynflshop 3 months later:

    good post and thanks http://www.supplynflshop.com cheap nfl jerseys

  43. Avatar
    louis vuitton wallet 3 months later:

    louis vuitton wallet, louis vuitton wallets, mens louis vuitton wallet, women louis vuitton wallet.
    Traditional country, Southwestern prints and modern city styles elegantly merge in a new collection of men’s-wear by Highland.

  44. Avatar
    gucci wallet 3 months later:

    gucci wallet, gucci wallets, mens gucci wallet, women gucci wallet.
    The continually changing fashions of the West have been generally unparalleled either in antiquity or in the other great civilizations of the world until recent decades.

  45. Avatar
    Hermes belt 3 months later:

    Hermes belts, Elegant Hermes belt, Fashion Hermes belts for men, Hermes mens belt.
    Today fashion and beauty can be affordable for everyone. There is always a range such as Avon that provides quality beauty, make up and accessory products at a prices most can afford. Mass fashion is moving so fast that fashion now moves in a weekly cycle and fashion trends are hot for a short time only.

  46. Avatar
    Men’s belts 3 months later:

    Men’s belts, LV men’s belts, Fashionable Gucci men’s belts, Attractive style Hermes men’s belts.
    Today fashion and beauty can be affordable for everyone. There is always a range such as Avon that provides quality beauty, make up and accessory products at a prices most can afford. Mass fashion is moving so fast that fashion now moves in a weekly cycle and fashion trends are hot for a short time only.

  47. Avatar
    armani belt 3 months later:

    armani belt, armani belts, armani belts for men, armani mens belt. Classic fashion styles are the looks that last through the ages and appear flattering on almost anyone. They go beyond trends and are a triumph of art. Despite the decade, figure or fashion, classic styles are always a demonstration of truly refined taste.

  48. Avatar
    dupont lighter 3 months later:

    dupont lighter, dupont lighters, st dupont lighter, s.t. dupont lighters. Some actually seem like they are created with space creatures – not real women – in mind. But this fall, designers rolled out a multitude of great wearable looks.

  49. Avatar
    UGG pas cher 3 months later:
    Tout d’accord sur votre opinion. Et moi, aussi le fan de <a href=”http://www.uggbottessoldes.com”

    target=”_blank”>bottes uggs, surtout sur sa doublure en laine. La marque

    target=”_blank”>ugg bottes

    . venait de trouver sa signature. En ce moment, vous pouvez pré-commander les

    href=”http://www.uggbottessoldes.com” target=”_blank”>UGG Soldes

    !

Comments