5 comments on “Code critique: Fear of templates makes power set implementation useless

  1. Hi there,

    I am the author of the code snipped used.

    Just to clarify, I am not a C++ programmer, and never was. When I participate in coding competitions I always use C or Java. That code snippet was written when I was just testing the waters with C++, hence the problems you found with it. I also only focused on the algorithm itself, and not on the code quality.

    That being said, it was an interesting post, and I learned a couple of things.


  2. You should use an iterator adaptor to make the indirection transparent to the function object.

    • But I don’t want the indirection to be transparent. The reasoning is explained in the post:

      Client code may not only want the element from the source set, it may want the element’s actual location in the source set. And we can satisfy this easily by simply giving client code the same information the power set function has: the iterators into the original set. In fact, not passing on the original iterators to the user-supplied function means we would be stripping away information the caller supplied, for no good reason.

      • The user can still know the relative address of the values by taking the address of the elements of the range.
        The fact that the algorithm is implemented in terms of a range of iterators shouldn’t leak to the user IMO.

        I suggest changing
        func(p, const_ptr{q});
        func(make_indirect_iterator(p), make_indirect_iterator(const_ptr(q)));

        • You’re assuming the values have relative addresses. What if they’re proxies (like with vector[bool])? Or what if they’re generated on the fly (like with boost::irange)? Even if they do have actual physical addresses, those might be more or less useless – if all you’re given are the values of a multiset, identifying which element of the multiset a specific value actually is would be a royal pain in the ass.

          If you want the values you can get them easily from the iterators. But if you need the iterators you can’t get them easily (or at all, in some cases) if all you have is the values. Thus, the algorithm gives you the iterators.

          If the user just wants the values, they can do the “make_indirect_iterator” easily themselves – just use the first two lines of your lambda function convert the first/last arguments into indirect iterators, then use those. But you can’t go the other way – you can’t reobtain the original iterators once you’ve dereferenced them.

          The algorithm is not merely “implemented” in terms of a range of iterators – that’s not merely an implementation detail, that’s the whole point of the algorithm. The algorithm’s output is not a set of values, it is a set of iterators into the original range.

Leave a Reply

Your email address will not be published. Required fields are marked *