Jan 232015
 

Sean Parent posted today via Twitter this small neat algorithm:

 

 

Problem:

During my today’s work I came across the problem that inside a predicate there was a check if a specific enum value is equal to a set of possible values.

So the code looked like this:

I don’t like this collection of comparisons for equalness. From my point of view it is some kind of semantically copy-and-paste.

So with Sean’s code in mind I started thinking and I searched for alternatives. The first used a std::initializer_list:

So the example from above would read like this:

That is already better, but it does not read so fluently. So I tried to solve this with a builder like pattern:

The code example would then be like this:

That’s much better, but the curly braces inside the parameter are annoying. It would read much better this way and would be less typing, don’t you think?

So this is my next attempt to solve it with variadic templates:

My next idea was, that there must be a way to do it with variadic templates without the recursion terminating bool in(T)  method.

 

So I played around a bit with Sean’s code, after I understood what it is actually doing, this is the result (thanks to cpplearner for the improvement hint):

One disadvantage of this solution is, that the order of evaluation of the arguments is not defined.

But with Jay Miller’s comment, based on Eric Niebler’s improved version of the for_each_arg, this keeps the order of evaluation of the arguments.

Conclusion:

The last version is the most compact one, but it has the disadvantage compared to all the others, that the internal comparisons does not terminate early. So the code will compare all possible values, even a match was already found. As long as the value to be checked against the set of values cannot be evaluated during compile time, I don’t see a way to do it in a similar way like the last version. If you see one, please let me know.

Unfortunately the code does not fulfill Sean’s challenge: “Goal for Better Code: Fit each function in a tweet”. Never the less I think it is worth sharing it.

Since this is almost my very first experiment with variadic templates, all ideas for improvements or comments are welcome.

 

Note:

Please use “crayon” to enter source code in he comment. The “code” tag removes all “<” and “>”.

This code does not compile with Visual Studio 2013 update 3 in release mode, only in debug. It works fine with update 4 and VS2015 CTP and the recent Clang and GCC.

 

  18 Responses to “A Small Set Algorithm for Enum Values”

  1. Nice, this is my old C++03 solution to the same problem
    Syntax:

     namespace _impl {
      template 
      struct equal_any_impl {
        equal_any_impl(const ValueType& ref) : ref_(ref), status_(false) {}
        equal_any_impl& operator<<(const ValueType& test) {
          if (test == ref_)
            status_ = true;
          return *this;
        }
        operator bool() const {
          return status_;
        }
      private:
        bool status_;
        const ValueType& ref_;
      };
    }
    template 
    _impl::equal_any_impl equal_any(const ValueType& ref) {
      return _impl::equal_any_impl(ref);
    }
    
    
    			
  2. Based on Eric Niebler’s follow up to this same tweet, this version guarantees order of evaluation:

    • Felix Petriconi

      Yea. I wrote this before the final version of Eric was available. Thanks for the hint. I will update it.

  3. For that matter, in the original Sean Parent post, the reason for the comma operation in the pack expansion is because the values being unpacked are function calls that may return void. Yours has a real value so that comma is unnecessary:

  4. The &r is not necessary: the lambda expression, namely [&r](...){}, doesn’t need to know what r is. Only the computation of its arguments uses the variable r.

  5. Calling any_of provides early termination.

    • A little bit smaller

  6. I guess I don’t really understand what is wrong with this version:

    It’s more easily understood, maintains the order of evaluation of the arguments, and short-circuits when a match is found. As long as the list of enums to search for isn’t too long then everything should be inlined and you don’t have a big perfomance drag from all the recursive function calls (probably need to check the disassembly to be sure of this though). Was this just a code golf exercise?

    I am going to say thanks for writing this as I now understand how Sean Parent’s twitter snippet works.

  7. I actually agree with Brett that the version with the overload is best, but since we’re playing games with what is possible, here is a slightly more compact version of your solution:

    This has the advantage of only introducing one name into the surrounding namespace. I don’t see any way to implement the recursive version I prefer using lambdas this way, though.

    [UPDATE]
    After pasting the above I read Jeremy Wright’s solution, which I like. While any_of provides early termination, it’s early termination /after/ all of the equivalence operations have been performed, so I’m not sure we’ve saved much work. If all of the variable arguments are of the same type you can put those into the initializer list and pass the test on to the predicate:

    • Using generic lambdas instead of function templates also has the advantage of having fewer angle brackets to escape out in blog posts 🙂

      • Felix Petriconi

        Up to now nobody ever used code in comments. So I just found the switch to enable the editor.

    • Felix Petriconi

      This solution has it’s charme!
      But the compiler I have to use for daly work does not support so far generic lambdas.
      Thanks for sharing it!

  8. 158 chars 😉

    I agree that readability has suffered some…

    • Me and html formatting…

      On the other hand, I shrunk it some more. 153 chars now. Gives a compilation warning about unused variable v, though.

  9. This is certainly clever – and I appreciate its value as a teaching exercise – but I can’t see myself ever using this technique for the stated problem.

    I haven’t tested it, but it seems more likely that a switch statement would generate more efficient code, in practice. (Code untested:)

    Happy to be proven wrong of course!

    • Felix Petriconi

      Of course your code does the same for this case. But my point was to have a generic solution, that works with all kind of enums and a variable number of parameters.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

(required)

(required)