Sebastian Mestre's Algorithmic Adventures

Un amigo tenía algunas dudas sobre perfect forwarding en C++, y terminé escribiendo esta explicación. value categories Antes de hablar sobre los detalles de la deduccion de tipos en C++ es fundamental mencionar las value categories. En C++ hay dos tipos de referencias. Referencias a lvalues y referencias a rvalues. Llamemoslas L-refs y R-refs, respectivamente. Normalmente, las L-refs apuntan a objetos que tienen una ubicación fija en memoria, mientras que las R-refs apuntan a objetos temporales. Normalmente, una L-ref se denota T& y una R-ref se denota T&& , donde T es un tipo concreto. Por convención, si recibís una R-ref, tenes derecho a romper el objeto al que apunta. En caso contrario, no. std::move toma una L-ref y la castea a R-ref. template argument deduction Digamos que tenemos una funcion monki , que tiene un template parameter T . Y digamos que T aparece dentro del tipo de uno de los parametros de monki . Por ejemplo: template<typename T...

When you write a type checker, there are a few ways one might go about it. First, you can do it outside-in: given an expression and a type, you check that the expression matches that type by inferring the type that the sub expressions should have, then checking that they do. This operation is typically called checking. Here, type information comes from the outside, and it flows into the expression. For example, let's check that 3+x is an int . First, we realize that both 3 and x need to be int . Now we check that 3 is an int , and discover that it is. Then, we check that x is an int , and if it is, we would be done, and type checking would be successful. If not, then we'd emit a type error. Second, you can do it inside-out: given an expression, you can infer types for the sub expressions, then use those to infer a type for the full expression. After that, you can check that the inferred type matches what you were expecting. This operation is typically called infer...

In an ICPC-style contest, 3-person teams compete in programming challenges, and they are allowed to bring a "notebook" into the contest. A notebook is a printable document, that teams usually fill with implementations of common algorithms, so that they are able to pull them out if needed in a contest. The other day, my ICPC team and I participated in one such contest (though an unofficial one) and we got stuck on a problem. Nevermind the details, but the solution called for finding all primes out of about a million numbers that were less than a trillion (that's 10 to the 12th power). Accordingly, our code looked something like this: // ... using ull = uint64_t; int main() { // ... vector<ull> numbers; populate(numbers); vector<ull> primes; for (ull x : numbers) if (is_prime(x)) primes.push_back(x); // ... } The only missing piece was fast primality testing. But since we already have that algorithm in o...

Whether it be due to numerical precision, image encoding, or logic issues, when writing or hacking on a path tracer, there tends to be a lot of duds. This is not something to be discouraged about, but a natural part of the process. (If anything, that there is any reasonable looking output at all, already means that you are 90% of the way there!) In no particular order, here are some early images that came out of a path tracer that I made. Of course, it is all the better if one gets the damned thing to work, which I did manage in the end. About me My name is Sebastian. I'm a competitive programmer (ICPC World Finalist) and coach. I also enjoy learning about programming language theory and computer graphics. Social links: Github profile LinkedIn profile Codeforces profile

I am working on a small project that involves a bunch of geometry algorithms. Since it's something I'm doing for fun, I'm rolling my own implementations of every algorithm I use, in modern C++. Right now, I needed a convex hull algorithm that was going to be used for a small amount of vertices (think up to 30 or so). A convex hull is the smallest convex polygon that contains every point in a set. You can think of it as the shape drawn by sticking a bunch of nails to a piece of wood and then releasing a rubber band around them. I don't have a picture of that but, in a more abstact setting, it looks like this: There are a few different algorithms with different performance characteristics that will compute the convex hull for us. The two major ones are The Jarvis March (a very simple O(N^2)), the Graham Scan (more complicated, O(NlogN)). Since my use case involves very few vertices, I went with the Jarvis March. The Jarvis March This is the algorith...

Template meta programming has been a mainstay in C++ for years. It provides a system for compile-time polymorphism and generic programming with capabilities not present in many other languages, enriching the language and bringing new opportunities for expressiveness to the table. Why doesn't the C language have such capabilities? Well, besides the fact that C++'s templates were added to the language years after C and C++ stopped resembling each other (at least in the common coding styles of each language), the reality is that it does. Sort of. Let me show you what I mean. The C Preprocessor Enter, the C preprocessor. For many, a glorified find-and-replace engine; but in reality it hides great opportunities for those looking to expand their frontiers. Let's go over the basics first, and then we'll take a look at the true power of the C preprocessor. Object-like macros This is how the GNU Foundation refers to the simplest form of define directive [1] . These con...