Skip to main content

Posts

Showing posts from May, 2014

Using The Pigeonhole Principle in C++ Metaprogramming

The Pigeonhole Principle is one of the most obvious fundamentals in mathematics. It is so obvious that you may be surprised that there is even a name for it. It states that:

"If n items are put into m containers, with n > m, then at least one container must contain more than one item."

Alternatively,

"If there are n items and m containers, with n > m, and only one item can fit in a container, then at least one item must remain out."

For those who prefer visuals and really hate math:


Even though the principle is simple it has been used to prove many complex mathematical theorems and lemmas. Here is one I find quite interesting:

"Incompressible strings of every length exist."

Alternatively,
"There is a file of every size that your favorite zip program can't compress."
The solution is left to the reader as an exercise.

So, does the Pigeonhole Principle show up in programming. Of course it does. That's why std::vector must allocate memor…

A tale of noexcept swap for user-defined classes in C++11

C++11 has taken another stab at function exception specifications for the masses. The shiny new ‘noexcept’ keyword is phasing out its zombie cousin ‘throw’. The well accepted guideline for the old exception specification is: "don’t use them!" That’s good for us because now we don’t have to bother (the reasons for not using throw specification aren’t for the faint hearted anyways.) The noexcept feature does not appear to be a walk in a park either. So hold on tight!

noexcept is meta-programmable! a.k.a conditional noexcept. It is possible to conditionally specify functions to throw any exceptions. The noexcept specification of functions can be inspected at compile-time and functions can derive their own noexcept specification based on exception specifications found elsewhere in the program. Meta-programs are not off-limits here. An excellent introduction of the noexcept feature and its history can be found in June’11 Overload Journal and on Andrzej's C++ blog. I won’t re…

Fun with Lambdas: C++14 Style (part 2)

Look at some interesting examples of C++11/14 lambdas and how they interact with other language features and libraries. I hope to find some time to add some explanations. See part 1 if you missed it.
Associative containers and lambdas std::set<int, std::function<bool(int, int)>> numbers([](int i, int j) { return i < j; }); Recursive Lambdas (see Creating recursive lambdas and returning them too!) auto make_fibo() { return [](int n) { std::function<int(int)> recurse; recurse = [&](int n){ return (n<=2)? 1 : recurse(n-1) + recurse(n-2); }; return recurse(n); }; } Composable list manipulation (e.g., cpplinq, narl, LEESA) Box boxes[] = { ... }; int sum_of_weights = cpplinq::from_array(boxes) >> where([](const Box & box) { return box.color == Color.RED; }) >> select([](const Box & box) { return box.get_weight(); }) >> sum(); Overloaded Lambdas template <class... …